코딩 테스트/개념34 다익스트라 다익스트라 dijstra 그래프에서 최단 거리를 구하는 알고리즘출발 노드와 모든 노드 간에 최단 거리 탐색( = 특정 노드와 다른 노드 사이 최단 거리를 구하는 경우 효율적)에지는 모두 양수1. 그래프 구현하기2. 최단 거리 리스트 초기화하기최단 거리 리스트 생성출발 노드 0, 이외 노드 모두 무한으로 초기화3. 값이 가작 작은 노드 고르기최단 거리 리스트에서 현재 값이 가장 작은 노드 선택4. 최단 거리 리스트 업데이트 하기선택 노드에 연결된 에지 값을 바탕으로 다른 노드 값 업데이트Min(선택 노드의 최단거리 리스트 값 + 에지 가중치, 연결 노드의 최단 거리 리스트 값) 5. 3, 4반복 2024. 7. 20. 트리 트리 tree 노드와 에지로 연결된 그래프의 특수한 형태- 순환 구조(cycle)를 갖고 있지 않고, 1개의 루트 노드가 존재- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐- 트리의 부분트리(subtree) 역시 트리의 모든 특징을 따름 구성 요소노드: 데이터의 index와 value룰 표현하는 요소에지: 노드와 노드의 연결 관계를 나타내는 선루트 노드: 트리에서 가장 상위에 존재하는 노드부모 노드: 두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드: 두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드: 트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)서브 트리: 전체 트리에 속한 작은 트리 2024. 7. 13. 위상정렬 위상정렬 topology sort 사이클이 없는 방향 그래프에서 노드 순서가 찾는 알고리즘 항상 유일한 값으로 정렬되지 않음사이클이 있으면 명확한 순서 정의 불가 아래의 과정을 반복하여 값을 구한다.진입차수가 0인 노드를 선택하고 저장함인접 리스트에서 선택된 노드가 가리키는 진입차수 -= 1 2024. 7. 6. 유클리드 호제법 유클리드 호제법 (euclidean - algorithm) 두 수의 최대공약수 구하는 알고리즘 핵심이론: MOD 연산: 두 값을 나눈 나머지를 구하는 연산1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.2. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.3. 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대공약수로 선택한다. def GCD(x , y): min_num = min(x, y) max_num = max(x, y) if min_num == 0: return max_num else: return GCD(min_num, max_num%min_num) 2024. 6. 23. 확장 유클리드 호제법 (수정 필요) 확장 유클리드 호제법 목적: 방정식의 해 구하기 ax + by = c 의 방정식은 c % gcd(a, b) = 0인 경우에만 정수 해를 가짐!즉, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가짐 추가 설명 및 사진 필요 2024. 6. 16. 오일러의 피 오일러의 피 P[N] : 1부터 N까지 범위에서 N과 서로소인 자연수의 개수 원리1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기자신의 인덱스 값으로 초기화한다.2. 2부터 시작해 현재 리스트의 값과 인덱스가 같으면 (소수) 현재 선택된 숫자(k)의 배수에 해당하는 수의 리스트를 끝까지 탐색하여 P[i] = P[i] - P[i] / k 연산을 수행한다. (i는 k의 배수)3. 리스트의 끝까지 2를 반복하여 오일러의 피 함수를 완성한다. 2024. 6. 9. 이전 1 2 3 4 5 6 다음 728x90
