푸으름

Algorithm 공부 #22 - 최소 공통 조상(Lowest Common Ancestor) 최소 공통 조상(lowest common ancestor) ● 최소 공통 조상 : 임의의 두 노드를 선택 후, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 ● 선택된 누 노드의 깊이가 다른 경우: 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 깊이를 맞춰줌 이때, 두 노드가 같다면 해당 노드가 최소 공통 조상이므로 탐색 종료 최소 공통 조상 빠르게 구하기 ● 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에는 한 단계씩 올려 주는 방식이었다면 이 방식은 2^k씩 올라가면서 맞춰주는 방식 ● 기존에 자신의 부모 노드만 저장해 놓던 방식에서 ..

Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘 ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최대, 최소) / 데이터 업데이트하기의 과정으로 나뉨 ● 트리 초기화하기 1. 데이터의 개수가 2^k일때 start_index=2^k 2. 2^k+1 인덱스부터 리프노드를 제외한 나머지 노드의 값을 채우기 3. 구간 합일 때 : A[N] = A[2N] + A[2N+1] / 최대 : A[N] = max(A[2N], A[2N+1) 최소 : A[N] =min(A[2N],A[2N+1]) ● 질의값 구하기 1. 질의 인덱스를 세그먼트 트리 인덱스로 변환 => 세그먼트 트리 index = 주어진 질의..

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜) 벨만-포드 알고리즘(Bellman-ford-moore Algorithm) ● 그래프에서 최단거리를 구하는 알고리즘 ● 음수 가중치 에지가 있어도 수행가능 ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능 ● 벨만-포드 구현 방법 1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입) 2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화) 3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기 4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트 최단거리 업데이트 ..

Algorithm 공부 #16 - 다익스트라 알고리즘  ✏️ 다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은후에 포스팅을 할 예정이다.  ✏️ 구현 방법출발 노드와 도착 노드를 설정'최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는..