규

문제 링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 접근 3을 만들 수 있는 경우의 수에서 1을 더한 것과 2를 만들 수 있는 경우의 수에서 2를 더한 것, 1을 만드는 경우의 수에서 3을 더한 것을 모두 합한다. d[5]는 d[4] + d[3] + d[2] 로 정리할 수 있고, 이는 곧 d[n] = d[n-3] + d[n-2] + d[n-1] 이다. 11 이하인 수이므로 for문을 10회 반복한다. 정답 코드 import sys X = int(sys.stdin.readline()) dp = [0] * (X + 1) for i in range(2, X + 1): dp[i] = dp[i - 1]..

문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근 DP 테이블을 이용한다. 현재 자신(숫자)를 만들기 위해 필요했던 연산의 개수를 저장한다. 각 수 연산을 다 해주고, 이 연산을 거친 결과를 서로 비교해서 가장 최솟값을 DP 테이블에 순차적으로 저장한다. 정답 코드 import sys X = int(sys.stdin.readline()) dp = [0] * (X + 1) for i in range(2, X + 1): dp[i] = dp[i - 1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) if i % 3 == 0: dp[i] = min(dp[i],..

동적 계획법 (Dynamic Programming) 동적 계획법, DP는 복잡한 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방식이다.다이나믹 프로그래밍이라는 이름은 고안자인 Richard Bellman이 붙인 이름인데 Dynamic이라는 단어가 멋져서 그렇게 지어졌으며 실제 원리와는 전혀 상관없다고 한다.반복되어 나오는 작은 문제들을 저장해 두었다가 재활용하기 때문에 직관적으로 '기억하며 풀기' 로 생각하는 것이 좋다. 왜 사용하는가? 피보나치 수를 구하는 재귀함수를 생각해 볼 수 있다. f(n-1)에서 구한 값을 f(n-2)에서 한번 더 구하기 때문에 실행되는 함수의 횟수가 기하급수적으로 증가하게 된다. 그러나 한번 구한 작은 문제의 값을 저장해놓는다면 연산 수가 급격히 감소하여 효율성이 증가한다...

문제 접근 재귀 문제이다. 0 -> (0000) -> (0(0011)00)… 함수가 호출되고, 매트릭스가 모두 같은 요소로 채워져 있지 않다면 해당 문자를 (xxxx)형태로 변경하고 각 x마다 재귀호출을 한다. 정답 코드 #1992번: 쿼드트리 import sys def quad_tree(matrix): size = len(matrix) start_point = matrix[0][0] flag = 0 for i in range(size): for j in range(size): if matrix[i][j] != start_point: flag = 1 break if flag == 1: new_matrices = [] new_size = size // 2 for k in range(2): # k = 0,1..

문제 접근 bfs로 이차원 배열을 탐색해야 한다. 1) 이차원 배열을 차례대로 순회하면서, 1이 등장할 때마다 bfs를 호출한다. 2) bfs를 진행하면서 해당 영역의 그림 칸 수를 카운트함과 동시에 바로 0으로 바꿔준다. 3) bfs에서 반환된 카운트 값을 가지고 max와 비교해 업데이트 4) 2)에서 방문한 부분은 0으로 바꿔줬기 때문에 1)에서는 또다른 영역의 그림만을 인식하여 bfs를 호출하게 된다. 정답 코드 #1926번: 그림 import sys from collections import deque def bfs(map, x, y): queue = deque() queue.append((x, y)) map[x][y] = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] c..

문제 링크 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 접근 치는 계란과 맞는 계란을 잘 다뤄야 한다. 치는 계란은 항상 왼쪽 첫 번째 계란이고, 이 계란이 깨지면 다음 계란이 치는 계란이 된다. 재귀를 하면서 배열 자체에서 깨진 계란을 삭제해 버리면 복잡해지므로 알고리즘 내에서 조건으로 깨짐 여부를 체크하고 그에 따라 처리해준다. 정답 코드 # 16987번: 계란으로 계란치기 import sys def count(eggs): cnt = 0 for i in eggs: if i[0]

문제 링크 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 set과 정렬을 이용해서 중복된 수가 없는 오름차순을 만들어주고 순서대로 함수를 호출하고 내부적으로 재귀호출한다. 정답 코드 # 15666번: N과 M (12) import sys def func(select): if len(select) == m: print(*select) return for j in range(len(a)): if a[j] >= select[-1]: select.append(a[j]) func(select) selec..

문제 링크 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 set과 정렬을 해준 뒤 순서대로 함수를 실행해주고 내부적으로 재귀호출을 한다. 정답 코드 # 15665번: N과 M(11) import sys def func(select): if len(select) == m: print(*select) return for i in range(len(a)): select.append(a[i]) func(select) select.pop() n, m = map(int, sys.stdin.readline(..

문제 링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 접근 재귀함수를 만들어 해결하였다. 암호의 길이가 L이고 알파벳순으로 암호가 나와야 하기 때문에, 문자가 C개 주어진다면 문자열을 순회하며 인덱스가 L-C+1인 것까지 탐색하며 재귀함수를 호출한다. L = 4, C = 6 a t c i s w 다음과 같이 주어진다면 먼저 이것을 정렬하여 알파벳순으로 만들면 a c i s t w 정렬된 상태에서 0 ~ L-C+1 인덱스를 탐색하면 a 또는 c 또는 i 로 시작하는 알파벳순의 문자열만을 만들 수 있다. (..

문제 링크 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 정답 코드 # 6603번: 로또 import sys def func(select): if len(select) == 6: print(*select) return for i in range(1, len(s)): if s[i] not in select and select[-1]