알고리즘 공부 썸네일형 리스트형 LCA(Lowest Common Ancestor) 최소 공통 조상 찾기 LCA란, 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드입니다. 트리의 특성상 싸이클이 없으므로, 두 정점 u와 v의 LCA를 w라 했을 때 u-w-v는 두 정점의 최단 경로라고도 할 수 있겠죠 :) LCA를 찾는 방법은 여러가지가 있는데, 세그먼트 트리를 사용하는 방법도 있지만, 저는 각 정점의 모든 정보들(깊이, 부모 정보, 부모의 부모 정보 등..)을 미리 저장해두고 LCA문제를 해결해보았습니다. 이렇게 하면 O(logN)만에 LCA를 찾을 수 있습니다. LCA를 가장 단순하고 쉽게 찾는 방법을 생각해보면, 모든 간선 정보를 저장한다. 각 정점의 깊이를 파악한다. (-> 완전 탐색 사용) 더 깊이가 깊은 정점에서 깊이가.. 더보기 BFS 공부 BFS(너비 우선 탐색)은 깊이가 작은 노드부터 차례대로 방문하는 전체 탐색 방식이라고 말할 수 있다.보통 BFS는 큐로 많이 풀게 되는데, queue를 이용하여 문제를 푸는 순서는 다음과 같다. 1. queue의 가장 앞에 있는 노드 pop2. 현재 노드에 인접한 모드 노드 중 아직 방문하지 않은 노드를 queue에 push3. queue 가 비어있지 않으면, 1번부터 다시 실행 큐의 작동원리를 알고 계신다면, 깊이가 낮은 순서대로 탐색하는 것을 이해하실 수 있으실 겁니다 :) 위의 논리구조로 코드를 구현하게 된다면, queue에 방문 node offer();방문 배열[노드] = true;while(!queue.isEmpty()){v = q.poll();if(v와 인접한 노드 && 미방문 노드){que.. 더보기 DFS(깊이 우선 탐색) 알고리즘 오늘 공부할 알고리즘은 깊이 우선 탐색, 흔히 DFS(Depth-First Search)로 알려져 있는 알고리즘이다. 이 알고리즘은 모든 노드를 방문하고자 하는 경우에 사용하게 된다. (cf. 맹목적 탐색(blind search)란, 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법)짧게 설명하자면 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 1. 깊이 우선 탐색의 특징1. 자기 자신을 호출하는 순환 알고리즘의 .. 더보기 그리디 알고리즘 그리디 알고리즘이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘은 매 선택이 그 순간에 대해서는 최적이지만, 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 사용되는 알고리즘문제에는 거스름돈 문제, minimum spanning tree, 다익스트라 알고리즘, 허프만 코딩 등이 있습니다. 그리디 알고리즘 중 가장 많이 사용되는 거스름돈 문제에서 동전 단위가 달라져 버리면, 최적의 조건을 구하기 어려워지는데, 이럴 때는 다이나믹 알고리즘을 사용해야 합니다. 그리디 알고리즘을 풀기 위해서는 '정렬' 이 필수입니다. 매 순간 최적(최저) 조건을 만족하기 위해서는 정렬이 당연히 필수겠죠? 그리.. 더보기 동적계획법 - 다익스트라 알고리즘 최단거리 알고리즘으로 알려진 다익스트라 알고리즘에 대해서 공부해보았습니다. 다익스트라 알고리즘을 푸는 방법에는 최소 우선 큐를 사용하느냐와 안사용하느냐 두 가지 방법이 있다.최소 우선큐를 사용하지 않으면 시간복잡도가 O(V2)가 나오는 반면, 최소 우선 큐를 쓰면 O(E+VlogV) 시간복잡도가 나오기 때문에 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이라고 한다. 알고리즘 간략 요약 1. 모든 꼭짓점을 미방문 상태로 표시 - 모든 미방문 꼭짓점의 집합을 만든다.2. 모든 꼭짓점에 시험적 거리 값을 부여한다. 초기점은 0으로, 다른 모든 꼭짓점은 무한대로 설정한다. (초기점은 현재 위치)3. 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 시험적 거리를 현재 꼭짓점에서 계산4. 새로 계산한 시험적 거.. 더보기 이전 1 다음
