핵심 개념DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘이다. DFS는 한 방향으로 끝까지 탐색한 후 돌아오는 방식이며, BFS는 가까운 노드부터 탐색하는 방식이다. 시간 복잡도두 탐색 방법의 시간 복잡도는 일반적으로 \( O(V + E) \)이다. 여기서 \( V \)는 vertex(or 노드) 개수, \( E \)는 edge(간선) 개수이다. DFS와 BFS 모두 모든 노드를 방문하기 때문에 그래프의 크기에 따라 탐색 시간이 결정된다. 동작방식 & 구현 DFS시작 노드에서 한 방향으로 갈 수 있는 만큼 탐색한다.더 이상 이동할 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색한다.모든 노드를 방문할..
핵심 개념투 포인터(Two Pointer)는 배열이나 리스트에서 두 개의 포인터를 활용해 문제를 해결하는 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 두 개의 배열을 병합할 때 사용된다. 탐색 범위를 줄여 효율적으로 동작하기 때문에 많은 알고리즘 문제에서 활용된다. 시간 복잡도Two Pointer 기법의 시간 복잡도는 일반적으로 \( O(N) \)이다. 각 포인터가 배열을 한 번씩만 훑고 지나가기 때문에 불필요한 중복 연산이 줄어든다. 반면, Brute Force 접근법은 \( O(N^2) \)인 경우가 많아 투 포인터를 사용하면 성능을 크게 향상시킬 수 있다. 동작방식 & 구현 투 포인터는 보통 다음과 같은 방식으로 동작한다.시작점과 끝점을 설정: 두 개의 포인터를 배열의 시..
문제https://www.acmicpc.net/problem/1018 해설BFS로 접근하는 것으로 착각하여 시간 소비를 많이 하였다. Brute Force를 이용하여 완전 탐색을 진행하면 쉽게 해결할 수 있는 문제였다. Pythonfrom sys import stdindef brute_force(matrix: list, x: int, y: int): w_start = 0 b_start = 0 for i in range(8): for j in range(8): if (i+j) % 2 == 0: if matrix[x+i][y+j] != "W": w_start += 1 eli..
문제https://www.acmicpc.net/problem/1707 해설DFS와 BFS 모두 사용가능한 문제이다. DFS를 이용하는 것이 개인적으로 이번 문제에선 이해가 잘 되었던 것 같다. PythonPython은 파이썬의 기본 재귀 깊이 제한은 1000이기 때문에 setrecursionlimit를 사용하지 않으면 런타임 에러가 발생한다. 너무 크게 설정해도 메모리 오류가 발생하므로 적절한 크기로 조절이 필요하였다. DFSfrom sys import stdin, setrecursionlimitsetrecursionlimit(100000)def dfs(graph: list, visited: list, colors: list, node: int, color: int): visited[node] = ..
문제https://www.acmicpc.net/problem/2667 해설DFS와 BFS 모두 사용하여 풀이가 가능한 문제라고 한다. 두 방법 모두 이용하여 풀어보았다. 아직 실력이 초보에 가까워 직관적으로 구현하려고 노력하였다. 이 문제는 DFS가 더 적절한 방법이라고 생각한다. 이 문제에선 DFS의 탐색 속도가 조금 더 빠르기 때문이다. BFS는 주변의 요소만 판단하며 거의 마지막 그리드까지 하나씩 확인해나가야 한다. 반면, DFS는 하나의 hit를 찾았을 때 한 번에 끝까지 모든 인접 경로를 탐색하는 방식이므로 visited 검사를 통해 BFS보다 좀 더 빠르게 조건문에서 필터가 가능하다. 다만 DFS를 사용하였을 땐 Stack Overflow의 위험이 내재되어 있다는 점은 인지하여야 한다. Pyt..
