CS · 알고리즘
백트래킹(backtracking)
주어진 문제에 대해 정답 후보를 나열하고, 후보를 탐색하기 위해 재귀함수를 사용하는 방법이다.
시뮬레이션 2
- 행 순서가 아닌 열 순서로 읽는 경우가 많음
DFS, BFS
DFS와 BFS는 모두 그래프를 탐색하기 위한 방법이다. 즉, 그래프를 탐색하기 위해 DFS나 BFS를 모두 사용할 수 있지만 탐색할 다음 노드를 결정할 때 두 방식의 동작이 다르다. 이 때문에 사용하는 방법에도 차이가 있다.
시뮬레이션
계산식 등을 이용하는 효율적인 방법을 항상 생각해내기는 어렵다. 그런 경우, 시뮬레이션을 통해 실제 세계에서 작동하는 방식을 모방하여 계산해 보면 해를 쉽게 얻을 수 있다.
완전탐색(Brute Force)
완전탐색은 어떤 문제에 대해, 해가 될 수 있는 정답 후보 집합을 결정하고, 그 집합의 모든 원소를 순회하며 조건에 만족하는 원소를 해로 확정하는 방법이다. 대부분의 문제를 이 방식으로 풀 수 있으나, N이 작아야 한다.
알고리즘 - 백트래킹
현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
자료구조 - Binary Search Tree
- $O(N)$의 시간 복잡도 - 평균 $N/2$번의 비교
자료구조 - Queue
- A, B, C, D를 넣는다 - [A][B][C][D]
알고리즘 - BFS
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 '3.'번을 진행 3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입. 4. 큐가 빌 때까지 '2.'번을 반복