문제https://www.acmicpc.net/problem/2529 해설Brute Force로 접근하였는데 생각보다 풀어내기 쉽지 않았다. 이후 생각을 바꿔 DFS를 이용하였다. 뿐만 아니라 백트래킹(Backtracking)에 대한 이해도 필요하다. 탐색 도중 더 깊은 depth에 대한 탐색이 필요 없을 때 pruning이라 불리는 가지치기를 이용하여 유망한(promising) 경로만 계속 진행한다. 이 과정은 "선택 - 탐색 - 복구" 구조로 구성되어 있고, 이를 통해 가능한 모든 경우의 수를 탐색할 수 있다. 이 Backtracking은 마치 임계구역 문제에서 한 번에 한 경로만 특정 숫자를 사용할 수 있도록 보호하는 역할과 유사한데, 공유 메모리 문제에서 고려되는 Critical Section에 ..
문제https://www.acmicpc.net/problem/1051 해설Brute Force를 이용하여 모든 경우의 수를 탐색하여 해결하였다. CNN에서의 Sliding Window를 연상해보면 더 쉽게 해결할 수 있다. Pythonfrom sys import stdindef brute_force(matrix: list, n: int, m: int): max_size = n if n Javaimport java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu..
핵심 개념완전 탐색(Brute Force)은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방법이다. 최적화 없이 모든 경우를 시도하기 때문에 구현이 간단하지만, 경우의 수가 많아지면 비효율적일 수 있다. 시간 복잡도완전 탐색의 시간 복잡도는 일반적으로 \( O(N!) \) 또는 \( O(2^N) \) 등 매우 높은 편이다. 예를 들어, n개의 요소가 있을 때 가능한 모든 순열을 탐색하는 경우 \( O(N!) \)이 된다. 따라서 입력 크기가 커질수록 실행 시간이 급격히 증가한다. 동작방식 & 구현완전 탐색은 보통 다음과 같은 방식으로 동작한다.가능한 모든 경우의 수를 생성한다.각 경우가 문제의 조건을 만족하는지 확인한다.원하는 결과를 찾으면 반환하거나 최적의 해를 갱신한다. 활용 가능한 문제 유..
핵심 개념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..
