백트래킹 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M (1) # N과 M (1) (실버 3) import sys n, m = map(int, sys.stdin.readline().split()) result = [0] * m arr = [i + 1 for i in range(n)] checked = [False for _ in range(n)] def dfs(level): if level == m: print(*result)..

DP 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net (1) 처음에 생각한 방식 한 스티커 기준으로 바로 인접한 ➡️⬇️⬆️⬅️ 방향에 있는 스티커는 붙힐 수 없다. 이 문제를 보자마자 dp로 풀어야겠다고 생각했다. dp는 bottom-up(작은 -> 큰) approach으로 table을 차근차근 채워나갈 것이기 때문에 ➡️⬇️⬆️⬅️ 방향 중 ⬆️⬅️ 방향의 스티커만 고려해서 피해 붙어주면 된다. 처음에 내가 좀 헤맸던게 문제..

DP 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net (1) 처음에 실패한 이유 # 가장 긴 증가하는 부분 수열 (실버2) import sys n = int(sys.stdin.readline()) l = list(map(int, sys.stdin.readline().split())) dp = [0] * n maxNum = 0 finalCnt = 1 # dp[0]..

DFS + Memorization 문제 (DFS로만 풀 시 시간초과) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net (1) 시간초과난 코드 (실패) # 내리막 길 (골드 3) / DFS-recursion (시간 초과) import sys r, c = map(int, sys.stdin.readline().split()) arr = [] visit = [[False] * c for _ in range(r)] dx = [-1, 0, 1, 0] dy = ..

Dijkstra 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net (1) 처음에 실패한 이유 (1) 처음엔 distance[start] = 0 이부분을 빼뜨려서 dijkstra 로직이 동작하지 못했다. 즉, distance 벡터를 출력했을 때 값이 모두 최댓값으로 나오는 문제가 있었다. [10001, 10001, 10001, 10001, 10001] 이런식으로 나왔었음. (2) 두번째로는 distance..

DP로 해결 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net (1) 처음 내 코드 (런타임 에러 - 실패) # 피보나치 수4 (실버5) import sys n = int(sys.stdin.readline()) dp = (n + 1) * [0] dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) print(dp[n]) 문..