Every step counts

23)분할정복과 백트래킹 분할정복 분할(devide): 해결할 문제를 여러개의 작은 부분으로 나눔 정복(conquer): 나눈 작은 문제를 각각 해결 통합(combine): 해결된 해답을 모음(if necessary) 병합 정렬(Merge Sort) 여러개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘 활용 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 top-down 방식 시간 복잡도 O(n log n) def merge(left, right): pass def msort(m): if len(m) == 1: return m left = [] right = [] middle = len(m)//2 for x in range(m[0:m..

탐욕 알고리즘 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 됨 한번 선택한 것은 번복하지 않음. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용됨 동작과정 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가함 실행 가능성 검사: 새로운 부분 해 집합이 실행 가능한지를 확인. 곧, 문제의 제약 조건을 위반하지 않는지 검사 해 검사 예) Knapsack에 대한 탐욕적 방법 값이 큰 것부터 채움 무게가 가벼운 물건부터 채움 def solve(r, c, sum_v): global min_v if 0 > r or r >= N o..

반복과 재귀 반복과 재귀는 유사한 작업을 수행 가능 반복은 수행하는 작업이 완료될 때 까지 계속 반복(for, while) 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합 재귀함수로 구현 반복구조 초기화 반복되는 명령문을 실행하기 전에 조건 검사에 사용할 변수의 초기값 설정 조건검사(check control expression) 반복할 명령문 실행(action) 업데이트(loop update) 무한루프(infinite loop)가 되지않게 조건이 거짓이 되게함 def SelectionSort(A): n = len(A) for i in range(0, n-1): minI = i fo..

문제해결 과정 문제를 읽고 이해 문제를 익숙한 용어로 재정의 어떻게 해결할지 계획을 세움 계획을 검증 프로그램으로 구현 풀이를 돌아보고 개선 방법 여부 확인 복잡도 분석 Big-Oh 표기 O-표기는 복잡도의 점근적 상한을 나타냄 복잡도가 f(n) = 2N2-7n+4라면, f(n)의 O-표기는 O(n2)임 먼저 f(n)의 단순화된 표현은 n2 단순화된 함수 n2에 임의의 상수 c를 곱한 cn2이 n이 증가함에 따라 f(n)의 상한이 됨 자주 사용하는 O- 표기 O(1) 상수시간 constant time O(logn) 로그(대수)시간 logarithmic time O(n) 선형시간 linear time O(nlogn) 로그 선형시간 log-linear time O(n2) 제곱시간 quadratic time ..

힙이란, 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모노드의 키값 > 자식노드의 키값} 루트 노드: 키값이 가장 큰 노드 최소 힙(min heap) 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모노드의 키값 < 자식노드의 키값} 루트 노드: 키값이 가장 작은 노드 힙 연산 - 삭제 힙에서는 루트 노드의 원소만을 삭제 할 수 있음 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있음 힙 연산 - 삽입

수식 트리 수식을 표현하는 이진 트리 수식 이진 트리(Expression Binary Tree)라고 부르기도 함 연산자는 루트 노드이거나 가지 노드 피연산자는 모두 잎 노드 이진 탐색 트리 탐색작업을 효율적으로 하기위한 자료구조 모든 원소는 서로 다른 유일한 키를 가짐 key(왼쪽 서브트리)

트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 트리 - 정의 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다. 노드 중 최상위 노드를 root라 함 나머지 노드들은 n(≥0)개의 분리 집합 T1, T2,…,TN으로 분리될 수 있음 이들 T1,….,TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 함 정점(node, vertex), 단말노드 혹은 잎노드(terminal node, leaf node) 트리 - 용어 Node - 트리의 원소 Edge(간선) - 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 Root Node - 트..

버퍼(Buffer) 데이터를 한곳에서 다른 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미 버퍼의 자료 구조 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용됨 순서대로 입력/출력/전달 되어야 하므로 FIFO 방식의 자료구조인 큐가 활용됨 BFS(Breadth First Search) 그래프를 탐색하는 방법에는 크게 두가지가 있음 깊이 우선 탐색(Depth First Search) 너비 우선 탐색(Breadth First Search) 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을..

큐의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출(FIFO) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제됨 큐의 선입선출 구조 큐의 기본 연산 삽입: enQueue 삭제: deQueue 큐의 주요 연산 enQueue(item): 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 deQueue(): 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 createQueue(): 공백 상태의 큐를 생성하는 연산 isEmpty(): 큐가 공백상태인지를 확인하는 연산 isFull(): 큐가 포화상태인지를 확인하는 연산 Qpeek(): 큐의 앞쪽(front)에서 원소를 삭제없이 반환하..

부분집합의 합(subset) 집합 {1,2,3}의 원소에 대해 각 부분집합을 사용하기 def f(i, k, key): if i == k: # 하나의 부분집합 완성 s = 0 for j in range(k): if bit[j]: s += A[j] # 부분집합의 합 if s == key: # 합이 key와 같은 부분집합을 출력 for j in range(k): if bit[j]: print(A[j], end= ' ') print() else: bit[i] = 1 f(i+1, k, key) bit[i] = 0 f(i+1, k, key) A = [1,2,3,4,5,6,7,8,9,10] N = len(A) bit = [0] * N key = 10 f(0, N, key) 다른 방법 def f(i, k, s, t):..