문제 1로 만들기 풀이 생각나는 방법 n짜리 넣어 두고 1가는 횟수 찾기 1에 먼저 도착하면 그게 최소 시간 복잡도 O(n) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n = int(input()) INF = 1e9 arr = [INF] * (n + 1) arr[n] = 0 for i in range(n, 0, -1): if i % 3 == 0: arr[int(i/3)] = min(arr[int(i/3)], arr[i] + 1) if i % 2 == 0: arr[int(i/2)] = min(arr[int(i/2)], arr[i] + 1) arr[i-1] = min(arr[i-1], arr[i] + 1) print(arr[1]) 다른 방법 dfs
문제 구간 합 구하기5 문제 풀이 핵심 구간합 사각으로 덧셈하기 V_i_j = V_i-1_j + V_i_j-1 - V_i-1_j-1 Sum_x2_y2 - sum_x1_y2 - sum_x2_y1 + sum_x2_y2 자세히 변수 n, m, table_map, sum_map 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import sys input = sys....
문제 양 구출 작전 풀이 핵심 양있는 섬에서 1번 섬까지 가기 가는게 독립시행 자세히 맵으로 트리 만들기 트리 순회 해서 1번 섬으로 도착하는 것 하기 양 있는데는 한번씩 돌기 변수 island_map sheep_land_list 시간 복잡도 O(n^2) m_i: i번째 길 수 n: 1번까지 path 길이 수열의 합 간과 한것 사이클, 도달할 수 없는 경우가 있음 1에서 부터 후위 순회로 풀어야 했음 답 보고 푼 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import sys sys....
문제 알파벳 해결 방법을 생각해 보자. 방법 1. 생각나는 대로 핵심 백트랙킹으로 visit을 탐색하면서 돈다. 자세하게 dfs로 이동 가능한 영역 접근한다. 여러번 하지 않게 접근한 횟수를 기록한다. 갈데 없으면 비교하고 하나 뺀다. 필요 상수 directions 필요 변수 visit visitBoard n,m board 시간 복잡도 O(4 * 26) 4방향, 최대 26개 실패한 원인 in으로 확인하는데 시간이 오래 걸린다. dp처럼 풀려고 했다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 n,m = list(map(int, input()....
문제 적록 색약 해답 찾기 핵심 로직 적록색약이 아닌 경우에 구역 개수 구하기 적록색약인 경우에 구역 개수 구하기 각각 출력하기 구역 개수 구하기 n ^ 4 > 1억이니 괜찮을 것 같다. 이중 FOR 구문에서 DFS를 돌면서 VISIT_MAP을 활용해 탐색한다. 적록색약인 경우 G를 R로 바꾸는 전처리를 먼저한다. 전체 흐름 맵 복사 적록 색약인 경우 바꾸기 구역 개수 구하기 출력 필요 상수 directions 필요 변수 n : 1 ~ 100 source_map : 2차원, 100 * 100 visit_map : 2차원, 100 * 100 count : 숫자 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import sys sys....