다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 다이나믹 프로그래밍의 원리가 적용된 문제다. 다양한 다익스트라 알고리즘이 많지만 대표적으로 최단 경로 문제를 설명한다. 방문하지 않은 노드 중에서 가장 최단거리 비용이 작은 것을 선택해야 하는데 2번과 5번이 비용이 같다. 어느 것을 선택해도 상관없지만 보통 숫자가 작은 것을 선택한다. 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인 탐색(순차 탐색)한다. import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().s..

효율적인 화폐 구성 N X M 만큼의 시간 복잡도가 소요된다. # 정수 N, M을 입력 받기 n, m = map(int, input().split()) # N개의 화폐 단위 정보를 입력 받기 array = [] for i in range(n): array.append(int(input())) # 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [10001] * (m + 1) # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) d[0] = 0 for i in range(n): for j in range(array[i], m + 1): if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우 d[j] = min(d[j], d[..

다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운(하향식)과 보텀업(상향식))으로 구성된다. 시간복잡도를 획기적으로 줄일 수 있다! 프로그래밍 분야에서 동적이란 어떤 의미일까? 자료 구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용한다. 1. 최적 부분..

이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. # 이진 탐색 소스코드 구현 (재귀 함수) 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: retu..

계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다. # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 for i in r..

캐글에서 열린 [Tabular Playground Series - Apr 2021]대회에 참가했다. www.kaggle.com/c/tabular-playground-series-apr-2021 'The dataset is used for this competition is synthetic but based on a real dataset (in this case, the actual Titanic data!) and generated using a CTGAN. The statistical properties of this dataset are very similar to the original Titanic dataset, but there's no way to "cheat" by using publi..