다이나믹 프로그래밍의 사용 조건 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.(분할 정복{퀵 정렬} 의 특징이기도 함) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음. 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. (이미 계산한 부분이 또 호출돼서 또 계산되는 것) - 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. - 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다. 다이나믹 프로그래밍의 적용 가능 예 - 피보나치 수열 메모이제이션(Memoization) -> O(N) 시간 복잡도 - 다이나믹 프로그래밍을 구현하는 방법 중 하나(다이나믹 프로그래밍에 국한된..
이진 탐색이란? - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정하고 찾은 인덱스를 반환한다. 이진 탐색의 시간복잡도 - 단계마다 탐색 범위를 2로 나누므로 연산 횟수는 log(2)N에 비례한다. - 시간복잡도는 O(logN)을 보장한다. # 재귀함수 버전 def binary_search(array, target, start, end): # 탐색할 곳이 안 남으면 None반환 if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 목표값이 중간점의 값보다 작은 경우 왼쪽 확인 el..
정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단함. 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름. 퀵 정렬 O(NlogN) O(N) 대부분의 경우 가장 적합함. 충분히 빠름. 계수 정렬 O(N + K) O(N + K) 데이터의 크기가 한정적인 경우에만 사용가능. 매우 빠름. * 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장함.
계수 정렬이란? - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘. -> 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. -> 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. -> 동일한 데이터가 여러번 등장할 때 효과적. - 각 인덱스에 해당하는 데이터가 몇 번 등장하는지 카운트해주면 됨. - 데이터의 개수 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 O(N + K)의 수행시간을 보장. # 계수 정렬 # 모든 원소의 값이 0보다 크거나 같다고 가정 numbers = [3, 7, 1, 9, 11, 10, 5, 4, 2, 4, 5, 2, 8, 1, 5, 3] # 모든 범위..
퀵 정렬이란? - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법. - 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나. - 정렬 라이브러리의 근간이 되는 알고리즘이다. - 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다. 퀵 정렬의 시간 복잡도 - 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다. - 최악의 경우 O(N^2)의 시간 복잡도를 가진다. -> 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 경우 맨 왼쪽 원소가 자기 자신을 기준으로 나누기 때문이다. -> 이 경우 한 원소 당 한번의 연산이 수행되는 꼴이므로 탐색O(N) * 나누기 N번 = O(N^2)이 나온다. # 퀵 정렬 numbers = [3, 7..
삽입 정렬이란? - 처리되지 않은 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬 알고리즘. - 필요할 때만 위치를 바꾼다. - 데이터가 거의 정렬되어 있을 때 엄청 효율적이다. # 삽입 정렬 numbers = [3, 5, 7, 6, 4, 19, 2, 10, 8] # 0 위치에 있는 항목은 정렬이 되어있다고 가정. for i in range(1, len(numbers)): # i번째 숫자와 그 앞의 숫자들과 비교 for j in range(i, 0, -1): # 뒤의 숫자가 더 작으면 앞과 바꿈. if numbers[j - 1] > numbers[j]: numbers[j - 1], numbers[j] = numbers[j], numbers[j - 1] else: break print(n..
선택 정렬이란? -> 매번 '가장 작은 것'을 선택하는 알고리즘. -> 앞에서부터 차례대로 가장 작은 숫자로 채워나가는 기법이다. -> 가장 작은 숫자를 만나면 그 인덱스와 기존 앞의 인덱스를 바꿔주는 방식을 사용한다. -> 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복. # 선택 정렬 numbers = [3, 7, 1, 9, 11, 10, 5, 4, 2] for i in range(len(numbers)): # 현재 위치(i)와 바꿀 가장 작은 숫자의 인덱스 min_index = i # i까지는 이미 정렬 됐으므로 그 다음부터 검사 for j in range(i + 1, len(numbers)): if numbers[min_index] > numbers..
DFS란? -> 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. DFS의 특징 - 스택 자료구조(또는 재귀 함수)를 이용한다. DFS의 동작 과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리를 한다. 2-1. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 수행할 수 없을 때까지 반복한다. # 재귀함수를 이용한 dfs구현 def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v] = True print(v, end=" ") # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 # 해당 노드의 행의 노드 ..
