본문 바로가기

코딩 테스트 준비5

[알고리즘] 최단 경로 알고리즘 * 최단 경로 문제 : 가장 짧은 경로를 찾는 알고리즘 - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현, 지점 간 연결된 도로는 그래프에서 간선으로 표현 [다익스트라 최단 경로 알고리즘] : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 방법 - 음의 간선이 없을 때 정상적으로 동작 - 그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복) - 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않음 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 (자기 자신과의 거리 0, 나머지는 INF) 3. .. 2022. 11. 20.
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programing) * 다이나믹 프로그래밍 (동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 ** 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.** [다이나믹 프로그래밍의 조건] 1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 가능 2. 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다. Ex. 피보나치 수열 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , ... 점화식을 활용 -> a1 = 1 , a2 = 1 , an = a(n-1) + .. 2022. 11. 19.
[알고리즘] 이진 탐색 * 이진 탐색 알고리즘 - 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘 - 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 - 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점 - 끝점 - 중간점 : 인덱스) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target, start , .. 2022. 11. 19.
[알고리즘] 정렬 알고리즘 * 정렬 알고리즘 - 데이터를 특정한 기준에 따라 순서대로 나열하는 것 [선택 정렬] : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1,len(array)): if array[min_index] > array[j]: min_index = j array[i] , array[min_index] = array[min_index] , array[i] print(array) - 매번 선형 탐색을 하는 것과 동일 -> 이중 반복문 활용! - 시간 복잡도 : O(N**2) [삽입 정렬] : 처리되지 않은 데.. 2022. 11. 19.

티스토리툴바