본문 바로가기

알고리즘3

[최단경로] 다익스트라(Dijstra) 알고리즘 30. 최단 경로 알고리즘 BFS와 구현방법이 상당히 비슷하다. 다익스트라 알고리즘 다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다. d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다. 아이디어는 BFS와 비슷한데, 가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다. 매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다. 이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다! 그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다. 이렇게 해서 직접 코드를 .. 2019. 9. 27.
11729 하노이 탑 접근 장대 1, 2, 3이 있고, 1에 원판 3개가 있을 때, 이 원판을 모두 크기 순에 맞게 장대 3에 옮겨야 한다. 그 과정을 살펴보자. a b 는 a의 맨위의 원판을 b의 맨 위로 옮긴다는 뜻이다. 자 머리속으로 상상해보자. 그러면서 일반화 해보자.(n개의 원판으로!) 1 3 1 2 3 2 ---------- 1) 지금 이상황은 1에서 제일 큰 원판이, 2에 n-1개의 원판이 순서대로 있는 상황이다. 1 3 ---------- 2) 1에 있는 가장 큰 원판을 3으로 보낸다. 2 1 2 3 1 3 ---------- 3) 2에서 n-1개의 원판을 3으로 보내는 상황이다. 함수 f(a, b, n_disk)를 정의하고 맨처음 상황을 f(1, 3, 3)으로 생각해보자. 1)의 상황을 다시 한번 보자. f(.. 2019. 6. 28.
[백트래킹] 1987 알파벳 1. 알파벳 보드 b 생성 2. 알파벳 모음 alphabets 생성 - 이미 찾은 알파벳 확인용 3. 방향 설정 상 하 좌 우 dx = {-1, 1, 0, 0} dy = {0, 0, -1, 1} 이 보드의 (0, 0) 부터 시작해서, 상하좌우 매번 탐색하면서 - 보드의 바깥으로 가는 경우는 다시 돌아옴(백트랙). - 새로운 알파벳을 탐색했으면 기록하고, 다음 경로 탐색. - 이미 기록된 알파벳을 탐색했으면 백트랙. ex) 2 4 CAAB ADCB 이와 같은 알파벳 보드에서, 재귀함수가 어떻게 진행되는지 보자. C : 알파벳 체크. 1 상 : 없음, 돌아옴 2 하 : A 체크 2-1 상 : C가 이미 체크 되어있음, 돌아옴 2-2 하 : 없음, 돌아옴 2-3 좌 : 없음, 돌아옴 2-4 우 : D 체크 2.. 2019. 6. 27.
728x90