| 번호 | 날짜 | 문제 번호 | 풀이법 | 주의사항 | 새롭게 배운 내용 | 다시 풀어보기 |
|---|---|---|---|---|---|---|
| 1 | 24.02.25 | BOJ 4963 | DFS - 재귀 | sys.setrecursionlimit(10**6)로 런타임 에러 (RecursionError) 해결 |
그래프 탐색 시 범위 제약 방법 | |
| 2 | 24.02.26 | BOJ 10026 | DFS - 재귀 | dfs() 함수 구현시 파라미터로 뭘 넘겨야 할까? (고민중🧐) |
||
| 3 | 24.02.28 | BOJ 2468 | DFS - 재귀 | max({빈배열}) 을 호출하면 런타임 에러 (ValueError) 발생 |
2차원 배열에서 최솟값, 최댓값 찾는 방법 (min, max, map 함수 사용) |
|
| 4 | 24.03.01 | BOJ 11725 | BFS - 큐 | deque가 아닌 list를 사용하여 구현하면 시간초과가 나올 수 밖에 없다. | deque 사용법 | |
| 5 | 24.03.02 | BOJ 7569 | BFS - 큐 | 3차원 list 다루기, 함수 정의할 때 기존에 사용중인 변수는 쓰지 맙시다! ^^ | 최단거리 구하는 방법 : 배열에 cnt를 저장하기 | |
| 6 | 24.03.05 | BOJ 14502 | BFS & DFS | 함수 내에서 전역변수 사용법 : global 선언하기 | DFS와 BFS를 모두 써야하는 어려운 문제ㅠ | ✅ |
| 7 | 24.03.08 | BOJ 7562 | BFS - 큐 | 예외 처리 주의 : (시작지점 == 목표지점) 일 때 고려하기 | 최단경로 (BFS) 문제에서는 그래프/리스트 자체에 cnt 누적값을 저장 | |
| 8 | 24.03.10 | BOJ 11403 | 최단경로 - 플로이드 워셜 | 그래프 생성 시 0번째 인덱스부터 시작 🆚 문제에서는 1번 노드부터 있다고 취급 | 최단경로 알고리즘에는 다익스트라, 벨만포드, 플로이드 워셜 알고리즘이 있다. |
|
| 9 | 24.03.10 | BOJ 11404 | 최단경로 - 플로이드 워셜 | arr[i][i] = 0 으로 초기화하는거 잊지 말자 |
최단경로 알고리즘에서 최소비용 테이블의 모든 값을 float('inf') 로 초기화 해주자! |
|
| 10 | 24.03.11 | BOJ 2206 | BFS - 큐 | 3차원 배열 선언 시 [[[높이] 행 개수(세로)] 열 개수(가로)] 로 선언해야 됨 |
✅ | |
| 11 | 24.03.14 | BOJ 2583 | BFS - 큐 | 문제에선 함수 좌표 제시 → 문제 풀 땐 배열좌표로 바꾸기 (x,y좌표 → 열, 행 좌표) | ||
| 12 | 24.03.16 | BOJ 1987 | 백트래킹 | 행, 열, 높이 관련 변수명 정규화하기!! | 시간 복잡도를 고려하여 list보단 set 사용하기 | |
| 13 | 24.03.18 | BOJ 14889 | 백트래킹 | for문의 루프 수를 최소화하여 시간초과를 방지하자 | 절댓값 함수 abs({값}) (import 필요X) |
|
| 14 | 24.08.22 | BOJ 16956 | BFS | BFS보다 더 단순한 문제. 비어있는 모든 칸에 울타리를 설치하면 된다. | 문제에 '최소' 조건이 들어가지 않으면 더 단순하게 풀 수 있다. | |
| 15 | 24.08.22 | BOJ 5014 | BFS | BFS로 풀이 위해서 각 층에 방문하기 위한 최소 횟수를 저장하는 배열을 만듦 | BFS는 1. deque에 남는게 없을 때까지 반복 & 2. 횟수를 저장X. 이전꺼+1 을 사용 | |
| 16 | 24.08.23 | BOJ 9376 | BFS | 2명이 탈출하는 경우 + 밖에서 들어오는 경우 -> 총 3가지 경우에서 횟수를 구한 다음에 이를 합해야한다. | 문을 여는 것보다 문이 없는 부분을 우선처리 해야한다. (문 열 때에는 append, 문이 없을 때에는 appendleft) |
✅ |
| 17 | 24.08.24 | BOJ 2251 | BFS | sorted(arr)는 정렬된 리스트를 반환하지만 arr를 바꾸진 않는다. 반면 arr.sort()는 arr를 바꾸지만 반환값은 없다. |
BFS는 반복문과 큐를 사용하기 때문에 주어진 정보(ex.물통들의 용량, 남은 물의 양)들을 리스트로 저장하는 것이 좋다. | |
| 18 | 24.08.25 | BOJ 16932 | BFS | 0->1로 바꿀 때마다 그룹의 크기를 계산하면 시간초과 발생! 처음 주어진 배열에서 각 그룹의 크기를 미리 정해놓자! | 그룹의 크기를 계산할 때, 각 그룹에 순서대로 번호를 부여하고, 그 숫자로 그룹 위치를 표시한다. group의 크기는 별도의 리스트를 만든 후 저장한다. | |
| 19 | 24.08.25 | BOJ 17086 | BFS | 그래프 탐색 문제에서는 모든 위치에서의 최단 거리를 계산하지 말고, 변하지 않는 것들(문제의 주어진 input)을 가지고 최소의 계산으로 문제를 푸는 방법을 찾아보자! | -> 이게 뭔 말인지 나도 잘 모르겠지만.. 아무튼 시간복잡도를 최소화하는 코드를 짜라는 뜻임! | |
| 20 | 24.08.26 | BOJ 1600 | BFS | visited 한 칸에는 (지금까지 이동한 최단 경로 횟수)가 k+1개 저장해야 한다. => 3차원 배열ㄱㄱ! | 이렇게 추가 제한 조건이 있을 때에는 {BFS + 3차원 배열}을 사용하자! (이 방법이 은근 많이 쓰이는 듯) | |
| 21 | 24.08.26 | BOJ 4991 | BFS | BFS+메모리제이션(DP) 인데,, 접근 방식에 따라서도 시간초과가 나는 까다로운 문제 (ꐦ°᷄▿°᷅) | 문자열 리스트를 입력받을 때에는 반드시 줄바꿈문자 제거해줘야함! .strip() |
|
| 22 | 24.08.27 | BOJ 2151 | BFS | 이 문제의 핵심은 이동 방향에 따른 각 좌표의 최소 거울개수(cnt)를 배열에 저장하기! visited |
참.. 어렵네요..ㅎ | |
| 23 | 24.08.27 | BOJ 1914 | DFS (재귀) | 입력이 20 이상이면 과정 없이 결과만 출력해도 됨!! + 하노이탑의 답에는 규칙이 숨어있다! | 문제를 작게 쪼갤 수 있을 때 재귀를 사용한다 | |
| 24 | 24.08.30 | BOJ 17141 | BFS | 2차원 배열에서 최단경로 구하는 방식을 사용해서 쉽게 풂 | deepcopy() 는 시간도 오래걸리고 메모리도 많이 사용되니까 최대한 지양하자! |
|
| 25 | 24.08.31 | BOJ 17142 | BFS | 비활성 바이러스는 뚫고 갈 수는 있지만 전파할 수는 없다! 이 부분을 처리하기가 어려워서 애를 먹었다ㅠ | 백준에서는 numpy를 쓸수 없다..그리고 deepcopy 최소화하려고 방문 횟수를 저장하는 visited 배열을 사용함! | |
| 26 | 24.09.01 | BOJ 13549 | BFS | 최단경로 -> BFS 사용하기! 근데 visited 배열을 곁들인.. | 나의 지금 위치(me)가 목표(target)보다 idx가 작은 곳에 있는 경우만 고려하기! 그러려면 입력값 받자마자 분기문으로 처리~ㄱㄱ | |
| 27 | 24.09.02 | BOJ 2234 | BFS | 요소 개수, 크기 구하는 문제는 BFS~ 마지막에 이어진 두 요소의 크기 합을 구할 때, r-1이랑 c-1까지만 탐색하려고 했다가 오류 발생 (전범위 다 다룰 수 있어야 한다!) | 비스마스킹 연산 | |
| 28 | 24.09.19 | BOJ 1753 | 다익스트라 | 처음에 queue를 써서 구현했는데 시간초과가 발생해서 heapq로 변경함 | ||
| 29 | 24.09.21 | BOJ 1916 | 다익스트라 | 한 노드에 대해 여러 종류의 비용이 존재할 수 있다! 입력을 받을 때, min으로 비교하며 최소값만 남겨야됨 | 다익스트라로 방향+가중치 그래프에서 start에서 end로 가는 데 필요한 최소비용을 구해보자! | |
| 30 | 24.09.22 | BOJ 16118 | 다익스트라 | 시간초과 극복 방법 늑대의 경우 2가지 방법(빠름/느림)으로 노드에 도착할 수 있으므로 비용을 2차원 배열로 나눠서 저장해줌 |
인접 행렬(2차원 배열)보다 인접 리스트가 더 빠르다, 힙에 배열을 저장하는 방법 | |
| 31 | 24.09.23 | BOJ 1261 | bfs | 2차원 배열에서의 최단 경로를 구하는 문제 → bfs 사용 | ||
| 32 | 24.09.24 | BOJ 11779 | 다익스트라 | 🚨주의🚨 시간초과를 피하기 위해서는 힙에서 꺼낸 값을 중복 방문하지 않게 조건문을 추가해야 한다!! 최단 경로를 찾고, 그 경로까지 기억해야하는 문제 |
arr.reverse() : arr 리스트의 순서를 바꿔줌. print(' '.join(map(str, arr))) : 이제 join에 익숙해질 때가 되지 않았니.. |
|
| 33 | 24.09.25 | BOJ 2307 | 다익스트라 | 파이썬 때문인지 내 알고리즘 때문인지.. 시간초과 해결이 너무 힘들다ㅠㅠ [오답노트] | 다익스트라 알고리즘에서는 주로 연결된 노드만 탐색하기 때문에 인접 리스트가 더 효율적이다. | ✅ |
| 34 | 24.09.26 | BOJ 4485 | bfs | 2차원 배열에서 bfs를 통해 최소합을 구하는 쉬운 문제! | ||
| 35 | 24.09.28 | BOJ 1238 | 다익스트라 | 모든 곳에서 end 까지의 최단경로 & end에서 모든 곳 까지의 최단경로를 모두 구하는 문제 | 한 노드에서 다른 모든 노드로 가는 최단 경로를 계산하는 다익스트라 알고리즘으로도 이런 문제를 풀 수 있구나! 하지만 모든 노드에서 end 까지 가는 경로를 계산할 때에는 '노드의 개수' 만큼 다익스트라 알고리즘을 수행해야 한다. | |
| 36 | 24.09.29 | BOJ 2665 | bfs | 2차원 배열 미로에서 최단경로 구할 때에는 바로 bfs!!! | 띄어쓰기 없는 정수의 나열을 하나의 정수 리스트로 저장하는 방법 : list(map(int, input().strip())) |
|
| 37 | 24.10.01 | BOJ 1445 | bfs | 2개를 고려해야 해서 어려움. 1-쓰레기를 통과하는 횟수가 최소가 되는 경로 / 2- 그 중에서 쓰레기를 지나는 횟수가 최소가 되는 경우 | 힙을 사용해서 bfs를 풀어야 시간초과 방지 가능 '쓰레기를 지난다.' 는 조건이 까다로움. 문제를 잘 읽자!!! |
✅ |
| 38 | 24.10.09 | BOJ 2644 | 다익스트라 | 시작노드와 끝노드가 정해져 있을 때에는 다익스트라가 최고!!! | ||
| 39 | 24.10.17 | BOJ 3184 | BFS | 각 영역마다 bfs를 실행하여 남은 동물의 수를 구함 | 영역 = 울타리 내에서 이동 가능한 모든 범위 | |
| 40 | 24.10.18 | BOJ 1926 | BFS | 2차원 배열에서 그래프 묶음의 수, 최대 그래프의 크기 구할 때는 BFS~ | ||
| 41 | 24.10.26 | BOJ 10451 | BFS | 그래프 요소의 개수 구할 때에도 BFS~ | ||
| 41 | 24.11.03 | BOJ 2636 | BFS | 발상의 전환! 치즈가 아닌 것들에 집중하자~ | q 에는 공기 좌표를 집어넣고, cheese 리스트에는 치즈 좌표를 집어넣어서 따로 계산하는게 신기하다! | |
| 42 | 24.12.31 | BOJ 1504 | 다익스트라 | 오랜만에 다익스트라 풀어서 heapq 사용해서 푸는거 까먹었다.. 예전 풀이 보고 기억남! 뭐든 꾸준히 하자!! | 1~N 번 노드까지 최단경로를 찾는 문제 + 지정한 2개의 노드(a, b)를 반드시 지나야함. 답 = a~b 사이의 거리 + min(1~a + b~N, 1~b + a~N) |
|
| 43 | 25.01.02 | BOJ 17144 | BFS | 사실 BFS 보다는 구현에 가까웠지만, 그 안에 BFS가 중요한 로직을 담당함. | 2차원 배열의 값을 순환시킬 때 indexError에 주의하자!! 이번에는 r, c를 혼동해서 사용했다가 오류가 남. | |
| 44 | 25.01.03 | BOJ 1967 | DFS | 가장 먼 거리에 있는 두 노드 구하는 방법 = DFS!! | 1. 루트 노드에서 가장 먼 노드를 찾기 2. 그 노드와 가장 멀리 떨어진 노드 ⇒ 답 |
✅ |
| 45 | 25.01.06 | BOJ 1707 | DFS (재귀) | 이분 그래프인지 확인하는 방법 : 지금 노드가 0이면 그 점에서 탐색한 다음 노드는 1 (지금이 1이면 다음 노드는 0) 이런 식으로 탐색해나가기! | 이분 그래프 : 그래프의 정점을 둘로 분할할 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분해할 수 있는 그래프 | |
| 46 | 25.01.07 | BOJ 14442 | BFS (w.3차원 배열) | 3차원 배열 생성 =[[[0 for _ in range(col)] for _ in range(row)] for _ in range(depth)]3차원 배열 조회 = arr[층][행][열] |
BFS에서 경로말고 또 하나를 카운트해야 한다면 3차원 배열의 depth를 통해 카운트한다. (이 문제에서는 부순 벽의 개수 카운트) | |
| 47 | 25.01.08 | BOJ 16933 | BFS (w.3차원 배열) | 최단 경로의 횟수가 홀수이면 벽을 부술 수 있다는 점을 이용하면 14442번 문제에서 변수를 추가하지 않고도 풀 수 있다! | ||
| 48 | 25.01.14 | BOJ 20208 | 백트래킹 | 모든 경우를 탐색하고 싶은데, 그 중에서 조건을 만족할 수 없는 경우는 바로바로 쳐내서 시간을 단축하는 경우 → 백트래킹을 사용해보자!! | 방문 확인 배열을 재귀함수 안에서 바꿔주면 모든 경우를 탐색할 수 없다!! 재귀함수 호출 전에 바꾸기!! (호출 후에는 또 원복해야함) | |
| 49 | 25.01.15 | BOJ 25825 | 백트래킹 | 같은 집단 내의 원소 구할 때 a, b 변수 선언을 잘못해서 많이 헤맸다ㅠ | 백트래킹에서 재귀함수 정의할 때, 각 단계에서 어디까지 계산하고 넘겨줄지 명확하게 정하는 것이 가장 중요하다!!! | |
| 50 | 25.01.16 | BOJ 9663 | 백트래킹 | 백트래킹 마스터^^ | 한 행에 하나의 퀸만 올 수 있다 → 방문 처리는 밑의 행에만 하면 된다. 이미 지나온 행까지 방문처리 할 필요가 없음. | |
| 51 | 25.06.26 | BOJ 16928 | BFS | 가중치가 동일한 그래프에서 최단 경로를 구할 때에는 BFS를 쓰자!!! | 방문 처리 배열 활용하는거 까먹지 마라~~ | |
| 52 | 25.06.26 | BOJ 16234 | BFS | BFS 방문 처리 시점 & 큐에 넣는 시점 잘 생각하기! (매번 여기서 틀리는 것 같음) | 이 문제는 모든 노드를 확인해야 하는 문제여서 이중 for 문 안에서 bfs를 실행해야 한다. (아닌 BFS 문제도 있음) | |
| 53 | 25.06.28 | BOJ 14938 | 최단경로 - 다익스트라 | 다익스트라 = 인접행렬 + 힙 | 최단경로가 갱신될 때마다 힙에 넣기 & 힙에 넣은 애들만 탐색하면 됨!! (모든 노드를 방문했는지 여부를 확인할 필요X) | |
| 54 | 25.06.29 | BOJ 1167 | 다익스트라 / DFS+DP | 다익스트라로 해도 되지만 시간초과 발생. DFS + DP (메모이제이션) 방식이 정석 풀이 | ||
| 55 | 25.07.25 | BOJ 2239 | 백트래킹 | 백트래킹 핵심 : 1. 성공/실패일 경우를 True/False 반환값으로 알려주기 2. 실패해서 되돌아온 경우 원상복구 시키기 ++ 재귀 도중 deque에서 값을 꺼내면 순서가 꼬일 수 있으니 index를 넘겨주는 방식을 사용하자!!! |
||
| 56 | 25.07.28 | BOJ 2580 | 백트래킹 | 위 문제와 동일 |
| 번호 | 날짜 | 문제 번호 | 풀이법 | 주의사항 | 새롭게 배운 내용 | 다시 풀어보기 |
|---|---|---|---|---|---|---|
| 1 | 25.06.29 | BOJ 1167 | 다익스트라 / DFS+DP | 다익스트라로 해도 되지만 시간초과 발생. DFS + DP (메모이제이션) 방식이 정석 풀이 | ||
| 2 | 25.06.30 | BOJ 1937 | DFS + DP | 모든 노드를 시작으로 DFS를 하면 시간초과 → DP 테이블을 통한 메모이제이션을 통해 중복연산 제거 | 간선 가중치 or 노드의 합이 최대가 되는 경로 찾을 때에는 DFS + DP 방식 사용하기!!! | |
| 3 | 25.07.02 | BOJ 1520 | DFS + DP | 4개의 방향에 대해서 모두 재귀를 진행할 경우 시간복잡도는 O(4^(R*C)) 가 된다. 이 때 DP(메모이제이션)을 사용해야 한다!!! |
재귀 문제풀이에서 Pypy3로 채점하면 메모리 초과 오류가 발생한다! 반드시 Python3 로 채점 해야 됨 | |
| 4 | 25.07.09 | BOJ 3109 | DFS (백트래킹?) | 백트래킹, 재귀에서 종료 조건 (base condition)을 어디서 어떻게 설정하는가에 따라 결과가 크게 달라진다.. | 너무 처리해야 하는 조건들이 많다.. 내일 다시 복습하기 |
| 번호 | 날짜 | 문제 번호 | 풀이법 | 주의사항 | 새롭게 배운 내용 | 다시 풀어보기 |
|---|---|---|---|---|---|---|
| 1 | 24.09.18 | BOJ 1766 | [위상정렬] 우선 풀어야 하는 문제들을 먼저 풀어야 하므로 위상정렬 사용, 그 중에서 가장 작은 숫자를 먼저 출력해야 하므로 우선순위 큐 사용 | |||
| 2 | 24.09.19 | BOJ 2252 | [위상정렬] 각 노드의 진입차수를 저장하는 리스트 in_degree, 각 노드가 가리키는 노드를 저장하는 리스트 graph 를 분리 |
|||
| 3 | 24.10.02 | BOJ 1197 | [MST] 유니온 파인드와 크루스칼 알고리즘을 통해 최소 비용 신장 트리(MST)를 구하는 문제! | 유니온 파인드에서 재귀를 사용하기 때문에 sys.setrecursionlimit(10**6) 을 추가해야 한다! |
유니온 파인드 알고리즘의 최적화 기법인 경로 압축에 대해서 더 공부하자!! | |
| 4 | 24.10.03 | BOJ 1922 | [MST] 유니온 파인드와 크루스칼 알고리즘을 통해 최소 비용 신장 트리(MST)를 구하는 문제~ | 유니온 파인드에서 두 노드를 이을 때에는 자신의 cycle 테이블이 아닌, 부모의 cycle 테이블을 갱신해야 한다!!! | 유니온 파인드를 통해 사이클 없는 트리를 들기 위해선 3개의 함수를 구현해야 한다. (get_parent, same_parent, union_parent) |
|
| 5 | 24.10.03 | BOJ 1647 | [MST] ,, | 두 마을을 분리하는 문제 → 만약 집(노드)이 2개밖에 없을 때에는 간선을 아예 안 그려야한다. | ||
| 6 | 24.10.04 | BOJ 4386 | [MST] 거기다 좌표 간 거리 계산을 곁들인.. | 파이썬 프로그램이 이유불문하고 종료될 때에는 재귀를 잘못 사용한 것이 아닌지 살펴보자. (ex. 자기자신 호출이 무한반복) | num의 소수점 둘째자리 까지만 필요하다면 round(num, 2) 함수를 쓰자! 제곱근은 math.sqrt(num) !! |
|
| 7 | 24.10.05 | BOJ 14950 | [MST] 이 알고리즘으로 문제를 풀면, 어느 노드가 시작점이든 상관X. 어차피 다 이어지니까~ | 예제에서 t=8로 주어지는데, 코드에 t가 아니라 숫자 8을 사용해서 틀림;; 정신차리자 | ||
| 8 | 24.10.06 | BOJ 10423 | [MST] 특수한 노드를 곁들인 MST 문제 | Q.유니온 파인드에서 필요한 사이클 리스트 크기를 v로 하기 위해 heapq에 노드들을 모두 -1 한 후 push 했는데, 왜 이거때문에 틀렸을까?? A.전력소를 항상 부모로 두기 위해서 0으로 설정했는데, 모든 노드의 번호는 -1 해버리면, -1 했을 때 0이 되는 1번 노드가 부모노드가 되는거잖어~ |
발전소는 이어져있지 않아도 된다 → 발전소 노드의 부모를 모두 0으로 초기화하자!!! → 발전소는 항상 parent가 된다! | |
| 9 | 24.10.07 | BOJ 1368 | [MST] 노드를 간선처럼 취급하기!.. 6일(내일) 풀 예정ㅠ | 노드를 사용하는 데에도 비용이 든다 → 노드도 간선처럼 취급하자! | ✅ | |
| 10 | 24.10.08 | BOJ 20010 | [MST+DFS] MST 만들고, 거기서 가장 먼 노드까지 찾기! | MST에서 노드 간의 거리 계산하는게 어렵다.. 다시ㄱㄱ | 그래프의 세계는 끝이 없구나 ＿ø(●ʘ╻ʘ●) | ✅ |
| 11 | 24.10.11 | BOJ 2623 | [위상정렬] 위상정렬은 순서에 따라 방향 그래프가 그려진다고 생각하기! a->b 순서가 정해질 때 b에서 자신을 가리키는 노드 수를 +1 하고, a노드가 가리키고 있는 노드 리스트에 b를 추가한다. | 사이클이 생기면 위상정렬을 수행할 수 없다. 만약 q에 들어온 노드의 수가 n개가 아니라면 사이클이 생긴거임! | 위상정렬에서 사이클 확인 방법 (사이클에 있는 노드 중 진입차수가 0이 노드는 없으므로 큐에 들어갈 수 없다.) | |
| 12 | 24.10.12 | BOJ 14567 | [위상정렬] | 문제집(1766번) 문제에서는 같은 우선순위인 경우 더 작은 수를 먼저 풀어야 된다는 조건이 있어서 우선순위큐를 사용했지만, 이 문제는 같은 우선순위면 순서가 상관 없기 떄문에 큐를 사용했다. | ||
| 13 | 25.07.03 | BOJ 17471 | 유니온 파인드 | 유니온 파인드 알고리즘 코드가 익숙하지 않아서 더 연습해야할 것 같다! | ||
| 14 | 25.07.04 | BOJ 1717 | 유니온 파인드 | 합집합 찾기 = 서로소 찾기 = 그래프에서 같은 그룹인 노드들 찾기 ⇒ union-find 알고리즘 | union(), get_parent() 함수에서 무한루프 발생 가능성 있음. 주의해서 함수 정의해야 함!!! |
|
| 15 | 25.07.08 | BOJ 2573 | DFS | 그룹 개수를 확인할 때, 2차원 행렬 형태로 주어지면 DFS/BFS, 리스트 형태로 주어지면 유니온 파인드를 사용하자! | 모든 빙산(iceberg)이 동시에 녹기 때문에, 바다(sea) 정보 역시 매 반복마다 한 번에 갱신해야 한다. |