데굴데굴

15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 처음엔 딕셔너리로 풀어서 제출했다가 다른 사람들의 코드가 유난히 짧은 것을 보고 의문이 생겨 찾아보니 아스키코드로 푸는 방법이 있는 것을 알았다. 딕셔너리로 풀기 # Hashing - 딕셔너리로 풀기 m = 1234567891 r = 31 alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 생각했던 것만큼 잘 풀리지 않아 아래 링크를 참고했다. # 프린터 큐 for _ in range(int(input())): # N = 문서의 개수, M = 문서가 Queue에 놓인 순서 N, M = map(int, input().split()) # N개 문서의 중요도 prec = list(map(int, input().split())) # 중요도 리스트의 인덱스 관리 idx = list(range(N..

11050번: 이항 계수 1 (acmicpc.net) 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수 공식을 알고 팩토리얼을 구현할 수 있다면 풀 수 있는 문제이다. 이항계수 공식은 다음과 같다. 입력의 범위가 1부터 10으로 아주 작기 때문에 이 문제에서는 팩토리얼을 직접 구현하여 풀어도 무방하다. 하지만 범위가 말도 안되게 커진다면 말이 달라지는데, 이 때의 이항 계수 알고리즘은 아래 블로그를 참조하는 것을 추천한다. (나도 더 공부해야지...) [조합론] 이항계수 알고리즘 3가지 - Parkito's on the way (shoark7.github.io) [조합론] 이항계..

2164번: 카드2 (acmicpc.net) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 입력이 50만까지 주어지기 때문에 시간 초과에 유의하여 풀어야 한다. 처음에는 리스트로 해결했는데 답은 맞았지만 시간 초과가 발생하여 deque 라이브러리로 해결했다. 아래 페이지를 보면 deque의 삽입/삭제 연산 시간 복잡도는 O(1), 리스트는 O(n)이라 설명하고 있다. 리스트는 삽입/삭제 연산에서 비워진 곳을 메우기 위해, 혹은 새로 삽입된 값의 자리를 만들어 주기 위해 원소가 추가로 이동하지만 deque는 ..

4153번: 직각삼각형 (acmicpc.net) 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 피타고라스 공식을 활용하여 푸는 문제이다. 처음에는 당연하게도 a, b, c로 나눠서 입력받은 후에 계산을 수행했는데 예제 입력을 다 맞았는데도 불구하고 채점만 하면 틀렸다고 나왔다. 도저히 왜인지 모르겠어서 질문을 읽어보니 문제에 '숫자가 오름차순으로 주어진다'는 조건이 명시되어 있지 않다는 것을 알게 되었다. 즉, 빗변의 크기가 맨 앞에 제시될 수도 있음을 간과한 것이다. 따라서 이 문제는 각 수를 리스트에 한데 모은 후 최댓값..

11655번: ROT13 (acmicpc.net) 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 아스키코드를 활용하여 푸는 문제이다. 파이썬의 ord를 활용하면 문자의 아스키코드를 얻을 수 있다. 아스키코드를 다시 문자로 변환할 때는 다시 chr을 쓴다. s = input() encrypted = '' for i in range(len(s)): if s[i].isalpha(): # 아스키 코드 활용 if (ord(s[i])>64 and ord(s[i])96 and ord(s[i])

10820번: 문자열 분석 (acmicpc.net) 10820번: 문자열 분석 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있 www.acmicpc.net n개의 문장이 주어지면 그 문장에서 소문자, 대문자, 숫자, 공백의 개수를 카운트하여 한 줄에 출력하는 문제이다. 파이썬 자체에 내장된 is~~()를 활용하여 각 조건을 판별하면 된다. 백준 문제는 보통 입력의 개수도 따로 n으로 알려주는데 이 문제는 그렇지 않아서 어떻게 풀어야할지 몰라 당황스러웠다. 종료조건이 안 주어지니 내가 아는 지식으로만 풀면 분명 무한루프를 돌 것 같았다. 질문란에서 EOF를 알게 ..

11399번: ATM (acmicpc.net) 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ATM 앞에 줄을 서는 사람의 수와 각 사람이 돈을 뽑는데 걸리는 시간이 주어지면 각자 돈을 뽑는데 필요한 시간의 합의 최솟값을 구하는 문제이다. 가장 적은 시간이 걸리는 사람부터 줄을 세우면 최솟값을 구할 수 있다. 따라서 입력받은 리스트를 오름차순으로 정렬한 후 합을 구하면 된다. n = int(input()) time = list(map(int, input().split())) time.sort() sum = 0 for i in range(1..