알고리즘 기초 유형

★ 백준 알고리즘 기출문제집에 가보면 삼성 기출문제도 확인할 수 있다. (https://www.acmicpc.net/workbook/view/1152)

기출문제 유형

알고리즘은 큐스택을 구현할 줄 알아야 한다.

정형화된 문제 유형이 있어서 유형만 공부하면 된다.

1. DFS, BFS 무조건 2개에서는 나온다. (왼쪽이 스택, 오른쪽이 큐)

2. 백트랙킹 (스택)

3. 다익스트라: 최소 경로를 찾는 문제 (큐)

4. 바이너리 서치: 이분 탐색

5. 연결리스트 (자료구조)

st (스택), DFS, 백트랙킹은 같은 개념을 공유한다.

1, 2, 3을 넣어주면 아래부터 쌓여서 꺼낼 때 3, 2, 1 순으로 꺼내게 되는 것이다.

Q (큐), BFS도 같은 개념을 공유한다.

1, 2, 3 순으로 넣으면 꺼낼 때도 1, 2, 3 순으로 꺼낼 수 있다.

DFS (깊이 우선 탐색, depth first search)

깊이 우선 탐색이란 트리 및 그래프 등을 탐색하는 알고리즘이다. 특정 노드를 출발하여 깊게 들어갈 수 있을 때까지 들어가고 들어갈 곳이 없다면 다시 나오는 알고리즘이다. 스택을 이용하여 구현한다. 

이런 식으로 그래프가 있다면 1에서 2로 가고, 2에서 4로 가고 더 갈 수 없으니 다시 1로 돌아가서 1에서 3으로 간다. 모든 길을 갔다가 막히면 다시 막히기 전으로 돌아오는 것이다. (http://wonwoo.ml/index.php/post/239) 

그래서 가다 막히면 다시 처음으로 돌아간다는 것을 표현하면 이런 식이 된다. (숫자는 다른 문제의 예시이므로 위와는 상관없다.)

처음에 스택에 (1,1)을 넣어준다. 그리고 (2,1)로 이동해서 스택에 넣어준다. 그런데 더 이상 이 길로 갈 수 없다. 그러면 (2,1)을 스택에서 빼낸다 (pop). 그리고 (1,1) 위에 (2,2)를 쌓아준다. 그리고 (3,1)로 이동하여 스택에 넣어준다. 이 길이 갈 수 없으면 (3,1)을 빼낸다. 그 다음 (2,2) 위에 (3,2)를 쌓는다. 또 길이 막히면 (3,2)를 빼준다. 이렇게 스택을 이용해서 찾아갈 수 있다.

그러면 알고리즘은

dfs (n, k)

 for (1~k)

 {  

   dfs (n+1,k) 

 }가 된다.

dfs(1,1)일 때

그 다음 경로로 dfs(2,1)을 보고 안되면 다시 k=2로 넘어간다. 그러면 dfs(2,2)를 보게 된다. 이런 식으로 돌고 막히면 다시 위로 올라가서 dfs(1,2)를 보고...해서 dfs(3,3) 까지 보는 것이다.

예시 문제로 최단경로 구하기 문제를 보면 이렇다. (http://blog.eairship.kr/268)

흰색 칸은 이동할 수 있는 지점, 회색칸은 이동할 수 없는 지점이다. 그러면 길을 가면서 위의 알고리즘을 실행하면 된다.

이런 순열 형태의 문제도 DFS로 풀 수 있다. 1에서 4로 가는 모든 가능한 경우의 수를 구할 수 있다. 

위에 쓴 의사 코드에서

dfs (n,k)

 n==4

 return

   for (1~k)

     dfs(n+1,k)

이런 식으로 넣어주기만 하면 된다. (가능한 경로가 여러개니까 아마 스택은 여러개가 될 것이다. visited 된 곳은 따로 1,1,1,이 들어간 배열로 만들어준다.)

백트랙킹(Backtracking)

백트랙킹은 DFS 알고리즘과 같지만 모든 경우의 수를 다 고려하지 않는다. (그렇게 하면 경우의 수가 어마어마하게! 많기 때문에) 대표적인 문제가 N개의 퀸 문제인데, 퀸을 체스판에 놓는 문제인데, 모든 경우의 수를 계산하면 엄청나게 많아진다. 하지만 같은 행에 놓을 수 없다는 제한점을 활용하면 각 행별로 새로운 DFS문제로 바꿀 수 있다. (https://www.slideshare.net/JaehoSeok/0521-8051381, http://heekim0719.tistory.com/284)

BFS (너비 우선 탐색, Breath First Search)

DFS와는 달리 Queue를 이용한다. (http://www.incodom.kr/BFS)

그리고 다음과 같이 a[5][4]로 이동하는 경우를 생각해본다. 

0	1	2	3
1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

이런 식으로 이동의 가지수가 나올 것이다. 이것을 큐를 이용해서 탐색을 하면

(0,0) → ↓	(0,1) →	(0,2)
(1,0)

이런 식으로 이동을 하게 될 것이다.

처음 큐에 (0,0)을 넣어준다. 그 다음에 (0,0)을 꺼내고 (pop) 거기서 이동할 수 있는 (1,0)과 (0,1)을 넣어준다.

(0,1)을 꺼내면서 거기서 이동할 수 있는 (0,2)와 (1,1)을 큐에 넣어준다. 그리고 (1,0)을 꺼내면서 (2,0)을 큐에 넣어준다.

이것을 이용하면 토마토 문제를 풀 수 있다. 익은 토마토와 인접한 토마토들은 다음날 다 익게 되어서 옆으로 점점 익는 토마토가 퍼져나가서 며칠이면 모든 토마토가 다 익는지 푸는 문제이다. (https://www.acmicpc.net/problem/7576)

		2
	2	1	2
2	1	0	1	2
	2	1	2
		2

이런식으로 퍼져나가는 것이고 역시 큐를 이용해서 풀면 된다. (https://m.blog.naver.com/PostView.nhn?blogId=itkmj&logNo=220606047245&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F)

다익스트라 (Dijkstra algorithm)

다익스트라 알고리즘은 BFS를 기반으로 한다. 

이런 형태의 문제가 일반적이다. opt(n) 해서 각 n까지의 최단 거리를 구할 때 큐를 사용한다. 각 노드 사이마다 다 다른 거리가 있다.

이런 식으로 1번 노드에서 이동할 수 있는 곳이 4번, 2번, 3번이 있다. 그러면 1번 노드를 큐에서 빼고 다음 이동 가능한 4, 2, 3이 큐에 들어간다. 그 다음 3을 빼고 3에서 이동할 수 있는 곳을 다시 큐에 넣어준다. 이게 기본적인 내용이고, 실제로 구현하는 내용은 다음 블로그에 잘 그려져 있다. (http://ehpub.co.kr/11-3-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/) 

바이너리 서치 (이진탐색, binary search)

정렬된 자료를 반으로 나누어 탐색하는 방법이다. 

1 3 6 8 9 12 ...이런 식으로 숫자가 엄청나게 많이 배열이 되어있을 때 하나씩 보면서 내가 원하는 값이 몇 번째에 있는지 찾으면 시간이 오래 걸린다. 그때 전체 데이터 중 절반 지점을 잡아서 내가 찾는 것보다 큰지 작은지를 확인한다. 그리고 남은 것 중에서 다시 절반 지점을 확인한다. 그러면 N=10억개일 때 log_2 N 시행횟수면 찾아낼 수 있다. log_2 10억이 되는 것이다. 시간 복잡도는 O(N)이 아닌 O(log_2 N) 으로 엄청나게 줄어들게 된다. (https://wayhome25.github.io/cs/2017/04/15/cs-16/)

알고리즘 문제 사이트 추천

https://www.swexpertacademy.com/main/main.do

알고리즘 기초 유형_그림 자료.pptx