Oneulog

개요 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. -> 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 플로이드 워셜 알고리즘 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. -> a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. 점화식 플로이드 워셜 알고리즘 : 동작 과정 살펴보기 [초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다. 기본 점화..

개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작 그리디 알고리즘으로 분류된다. -> 매상황에서 비용이 가장 적은 노드를 선택해 임의의 과정을 반복 동작 과정 출발 노드 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 위 과정에서 3과 4를 반복 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다. 처리 과정에서 더 짧은 경로를 찾으면 '이제부터는 이 경로가 제일 짧은 경로야'라고 갱신한다. 동작 과정 살펴보기 [초기 상태] 그래프를 준비하고 출발 노드를 설정한다. 노드 번호 ..

우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조 힙(Heap) 우선 순위 큐를 구현하기 위해 사용하는 자료 구조 중 하나 최소 힙(Min Heap)과 최대 힙(Max Heap) 이 있다. 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다. 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙 라이브러리 사용 예제 : 최소 힙 import heapq # 오름차순 힙 정렬 def heapsort(iterable) : h = [] result = [] for value in iterable : # 모든 원소를 차례대로 힙에 삽입 heapq.heappush(h, value) for i in range(len(h)) :..

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 피보나치 수열 다이나믹 프로그래밍을 활용하여 해결할 수 있는 대표적인 문재 피보나치 수열은 다음과 같은 형태의 수열 1, 1, 2, 3, 5, 8,..

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 1. 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누므로 연산 횟수는 log2N에 비례 -> 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장 2. 소스코드(재귀적 표현) # 이진 탐색 소스코드 구현 def binary_search(array, target, start, end) : if start > end : return None mid = (stat + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target : return m..

BFS(Breadth-First Search) 1. BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘 2. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다. 1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3) 더 이상 2)의 과정을 수행할 수 없을 때까지 반복한다. 3. BFS 동작 예시 [Step 0] 그래프를 준비한다.(방문 기준 : 번호가 낮은 인접 노드부터) -> 시작 노드 : 1 [Step 1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다. [Step 2] 큐에서 노드 '1'을 꺼내 방문하지..

그래프 탐색 알고리즘 : DFS/BFS 1. 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 2. 대표적인 그래프 탐색 알고리즘을는 DFS와 BFS가 있다. 3. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. DFS(Depth-First Search) 1. DFS는 깊이 우선 탐색이라고도 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 2. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드거 ..

1. 재귀 함수란 자기 자신을 다시 호출하는 함수 2. 단순한 형태의 재귀 함수 예제 - '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다. - 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다. def recursive_function() : print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 3. 재귀 함수의 종료 조건 (1) 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. (2) 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. (3) 종료 조건을 포함한 재귀 함수 예제 def recursive_function(i) : # 100번 째 호출을 했을 때 종료되도록 ..