14915번: 진수 변환기 변환한 n진수의 수를 출력한다. 11~16 진수의 경우 10 이상의 수는 A~F 문자를 사용한다. 예를 들어, 10은 A, 11은 B, 12는 C, 13은 D, 14는 E, 15는 F를 사용한다. www.acmicpc.net 해당 문제는 10진법인 수를 2에서 16진법의 수로 표현하는 문제이다. 어렵다기보다는 내장 모듈이 많은 파이썬 언어의 특성상 이번에도 진수 변환을 해줄 함수를 찾는 와중에 재귀로 구현한 참신한 코드를 발견하고 코드 리뷰를 해보려 한다. 먼저 해당 함수 선언은 두 가지 파라미터를 갖고 있다. 10진수의 정수(n), 변환할 base진수(base) def convert_notation(n, base): 해당 문제는 2, 8, 16진수으로의 변환뿐만 아니라 3이나..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진트리에서 순회하는 종류는 세 가지가 있다. 루트 노드를 기준으로 루트 노드 - 왼쪽 자식 트리 - 오른쪽 자식 트리를 순차적으로 방문하는 전위 순회, 왼쪽 자식 트리 - 루트 노드 - 오른쪽 자식 트리를 순차적으로 방문하는 중위 순회, 그리고 마지막으로 왼쪽 자식 트리 - 오른쪽 자식 트리 - 루트 노드를 방문하는 후위 순회다. 재귀함수 심화 대표 문제인 하노이탑 이동 순서처럼, 방문하는 순서에 맞게 재귀를 돌려주고 그 안에서 루트 노드를 로그 프..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 고등학교 확률과 통계 시간에 경우의 수 파트에서 다루는 내용이다. 주어진 동전의 종류에 따라, 합을 만들 수 있는 경우의 수를 구하는 문제이다. 처음에는 경우의 수 문제를 풀듯이 가장 가치가 큰 동전부터 하나씩 줄여가며 갯수를 세주는 방식으로 구현하였는데, 동전 종류의 개수가 고정이 아니므로 재귀를 활용하였다. import sys sys.setrecursionlimit(10**9) n, k = map(int, input().split()) coins = list(..

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어졌을 때, N보다 작은 연속하는 소수들의 합이 N과 같을 경우의 수를 구하는 문제이다. N의 최댓값이 4,000,000이므로, 소수 판별에 있어서는 에라토스테네스의 체를, 연속합은 투 포인터 알고리즘을 통해 시간복잡도 O(n)으로 구현하였다. N = int(input()) # 예외 처리 if N == 1: print(0) exit(0) # 소수 판별 by 에라토스테네스의 체 sosu = [True for _ in range(N + 1)] number = list() for i in range(2, N + 1): if sosu[i]: for j in range(i, ..

11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net PS의 난이도가 올라가다 보면 같은 문제를 좀 더 효율적인 시간, 공간 복잡도로 구현해야 하는 순간이 온다. 이항 계수를 구할 때 n의 값이 너무 크면 메모이제이션(dp)으로도 해결하지 못한다. 문제가 요구하는 정답이 이항 계수의 모듈러 연산 값이라면, 페르마의 소정리와 곱셈의 역원을 활용하여 답을 찾을 수 있겠다. 페르마의 소정리 p가 소수라면, $$ a^{p - 1} \equiv 1\pmod{p} $$ 해당 식의 좌변과 우변이 동치이므로, $$\therefore a \times a^..

17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 50000 이하의 자연수가 주어졌을 때, 해당 자연수를 최대 4개의 제곱수의 합으로 표현할 수 있다는 라그랑주의 증명을 바탕으로 한 문제이다. 뭔가 특별한 풀이법이 존재할 것 같긴 한데, 어떤 자연수 N을 다른 자연수의 제곱수의 합으로 나타낼 때 그 개수의 최댓값은 그 자신 N을 넘을 수 없고, 1부터 N까지의 답을 순차적으로 구하려했을 때 제곱 수(1, 4, 9, 16, ...)마다 1로 초기화된다는 점에서 다이나믹 프로그래밍..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 파이썬은 힙 라이브러리가 내장되어 있어서 따로 구현없이 편히 풀 수 있다. 다만 최대, 최소, 절댓값 힙 등은 힙에 push를 해주는 과정에서 살짝 변형만 해주면 되지만 이중 우선순위 큐는 좀 더 복잡한 코드 작성을 요구한다. 기본적인 틀은 이러하다. 1. 최대, 최소 힙을 담을 리스트를 각각 하나씩 초기화한다. 2. 값을 추가할 때 최소는 그대로, 최대는 요소에 -1을 곱해준다. 3. 값에는 튜플 형태로 (값, id) 구성해 추가해주고, 지우는 과정에서 각..

25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 백준 단계별로 풀어보기 문제가 업데이트되면서 누적합 카테고리에 새롭게 추가된 Gold 5 난이도의 누적합 문제이다. 앞 선 문제인 1018 - 체스판 다시 칠하기의 브루트 포스 알고리즘과 2차원 배열의 누적합 DP를 활용하면 무난하게 AC를 받을 수 있다. 다만 반복문을 작성할 때에는 최대한 한 반복문 안에 여러 연산을 실행할 수 있게 코드를 짜주는 것이 좋다. 해당 예제 코드보다 더 효율적인 코드가 가능해 보이기도 하다. # 빠른 입출력 import sys input = sys.stdin.readlin..