🍒 Chae-ri Dev 🍒

[Algorithm/Python] 다이나믹 프로그래밍 알고리즘 정리

DP(Dynamic Programming)는 연산 속도와 메모리 공간을 최대한 효율적으로 활용할 수 있게 해주는 알고리즘이다. 대표적인 예시 : 피보나치 수열 피보나치 수열을 점화식으로 표현하면 다음과 같다.프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현(+ dict 자료형)# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현def fibo(x): if x == 1 or ×= = 2: return 1 return fibo(x - 1) + fibo(x - 2)print(fibo(4)) 하지만 위 코드는 n이 커지면 수행 시간이 기하급수적으로 늘어나는 문제가 발생한다.메모이제이션 기법을 사용해서 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메..

BFS(Breadth First Search)BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다. BFS를 구현할 때는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. # 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. deque 라이브러리 사용 => 시간 복잡도 O(N)일반적으로 bfs가 더 빠르다. from collections import deque# BFS 메서드 정의def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 dequ..

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.리스트에 담긴 데이터에 순차적으로 접근해야 할 때, 시작점(start)과 끝점(end) 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기- N개의 자연수로 구성된 수열이 있다.- 합이 M인 부분 연속 수열의 개수를 구해보자.- 수행 시간 제한은 O(N)이다.  위 문제는 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.2. 현재 부분 합이 M과 같다면, 카운트한다.3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.4. 모..

대표적인 탐색 알고리즘인 DFS와 BFS는 스택과 큐, 재귀 함수를 이용하여 정리할 수 있다. DFS(Depth First Search)DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 다음과 같이 두 방식으로 쓰일 수 있다.1. 인접 행렬 방식INF = 999999999 #무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph)# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]2. 인접 리스트 방식# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현graph = [[] for _ in r..

트리 이진 탐색배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있는 알고리즘.탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색을 할때는 시작점, 끝점, 중간점 3개의 변수를 사용한다.# 이진탐색소스코드 구현(재귀함수)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, sta..