다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 - 대표적인 예: 피보나치 수열 피보나치 수열은 다음과 같은 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 점화식: 인접한 항들 사이의 관계식 피보나치 수열의 점화식 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 𝑛번째 피보나치 수를 f(𝑛)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다 피보나치 함수 소스코드 # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(..

순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 리스트 자료형에서 count() 메서드를 이용할 때도 내부에서 순차 탐색이 수행됨 이진 탐색 : 반으로 쪼개면서 탐색하기 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 - 데이터가 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음 - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함 - 이진 탐색은 탐색하고자 하는 범위의 시작점, 끝점, 중간점으로 위치를 나타내는 변수 3개를 사용함 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾음 이진 탐색 예시 이미 정렬된 10개의..

정렬 - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능 / 정렬 알고리즘은 이진 탐색의 전처리 과정 정렬 알고리즘의 종류 선택 정렬 삽입 정렬 퀵 정렬 선택 정렬 - 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 10개의 데이터 예시에 선택 정렬 알고리즘 적용 1. 초기 단계에서 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다. 2. 정렬된 데이터를 제외한 데이터 중에서 가장 작은 데이터를 처리되지 않은 데이터 ..

그래프 그래프는 노드(정점)와 간선으로 표현됨. 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것 그래프의 표현 방식 1. 인접 행렬 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식 - 2차월 배열에 각 노드가 연결된 형태를 기록하는 방식 - 파이썬에서는 2차원 리스트로 구현 가능 - 연결 되어 있지 않은 노드끼리는 무한의 비용이라고 작성 인접 행렬 방식 예제 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. 인접 리스트 - 리스트로 그래프의 ..

배열(Array) 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장 순서와 물리적 저장 순서가 일치) 형태로 구성된 자료구조 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다. 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다. 데이터 갯수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다. cache hit 가능성이 커져 성능에 큰 도움이 된다. cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우 고정이고 연속적인 만큼 인덱스로 random access가 가능하다. 접근, 수정 O(1)으로 빠르게 조회가 가능하다. 하지만 삽입과 삭제의 경우 연속적인 형태 유지를 위해 shi..

탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘: DFS/BFS 자료구조 - 데이터를 표현 ·관리 · 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 삽입과 삭제 함수로 구성됨. 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 함. 스택 - 스택은 후입선출구조이다. - 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다. stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) #[5,2,3,1] 큐 - 큐는 대기 줄에 비유할..

- 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법 어떠한 문제가 있을 때 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미 - 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 제시해준다. - 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분함 거스름돈 예제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. n = 1260 coun..