good_da22

분할 정복(Divide and Conquer) 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. 통합(Combine) : (필요하다면) 해결된 해답을 모은다. 거듭 제곱 반복(Iterative) 알고리즘 시간 복잡도 : O(n) Iterative_Power(x, n) result n result

스택 (stack) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 자료는 선형 구조를 갖는다. 선형 구조 : 자료 간의 관계가 1대 1의 관계를 갖는다. 비선형 구조 : 자료간의 관계가 1대 N관계를 갖는다. ex) 트리 스택에 자료를 삽입하거나 자료를 꺼낼 수 있다. 후입선출구조(LIFO - Last In First Out) 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 주요 연산 top : 저장된 원소 중 마지막 원소 push : 저장소에 자료를 저장한다.(삽입) pop : 저장소에서 자료를 꺼낸다.(삭제) peek : 스탯의 top에 있는 item(원소)를 반환한다. 삭제가 일어나지 않는다. java.util.Stack push() pop() isEmpty() size() Func..

힙(heap) 완전 이진 트리 에 있는 노드 중에서 키 값(data)이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) 키 값이 가장 큰 노드를 찾기위한 완전 이진 트리 부모 노드의 키 값 >= 자식 노드의 키 값 - 트리의 모든 노드에 성질 적용 루트 노드 : 키 값이 가장 큰 노드 최소 힙(min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키값

너비 우선 탐색(Breadth First Search, BFS) 비선형 자료구조를 완전탐색 너비 - 루트에서 자신까지 오는 간선 수 (각 노드에서의 높이), 높이가 낮은 순서에서 높은 순서로 너비 우선 탐색은 루트 노드의 자식도드를 먼저 모두 차례로 방문한 후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식 인접한 노드들에 대해 탐색 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용 BFS() 큐 생성 루트 v를 큐에 삽입 while(큐가 비어 있지 않은 경우) { t L 현재 노드 T의 오른쪽 서브트리로 이동 -> R preorder_traverse(T) if (T is not null) visit(T) preorder_..

트리(tree) 비선형 구조 원소들 간에 1:N 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 노드(node) - 트리의 원소 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다. 노드 중 최상위 노드를 루트(root)라고 한다.(상위 노드가 없는 유일한 노드) 나머지 노드들은 n(>=0)개의 분리 집합 T1, T2, ... ,TN 으로 분리될 수 있다. 단말노드(leaf node) : 더 이상 하위 노드를 가질 수 없는 노드 T1, T2, ... ,TN 이들은 각각의 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(sub tree)라고 한다. 용어 정리 노드(node) - 트리의 원소 간선(edge) ..

순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개중 r개를 선택하는 순열 nPr nPr = n * (n-1) * (n-2) * ... * (n-r+1) nPn = n! = n * (n-1) * (n-2) * ... 2 * 1 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다. N 개의 요소들에 대해서 n!개의 순열이 존재 12! = 479,001,600 n > 12 인 경우, 시간 복잡도 폭발적으로 증가 순열과 조합의 차이 - 순서가 의미가 있는가? 순서가 의미가 있으면 : 순열 순서가 의미가 없으면 : 조합 재귀 호출을 통한 순열 생성 numers[] // 순열 저장 배열 isSelected[] // 인덱스에 해당..

완전 검색(Exhaustive Search) 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기업 brute-force 혹은 generate-and-test 기법이라고도 한다. 모든 경우의 수를 테스트한 후, 최종 해법을 도출 상대적으로 빠른 시간에 문제 해결(알고리즘 설계) 가능 일반적으로 경우의 수가 상대적으로 작을 때 유용 시간적으로 불리, 시간 복잡도 계산 필요 중복 계산(호출)이 있을 경우, 메모이제이션, 가지치기 고려 그외 경우 아이디어 바꾸기 수행 속도는 느리지만 해답을 찾아낼 가능성이 크다 완전 검색으로 접근하여 해답을 도출, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직 많은 종류 문제들이 특정 조건을 만족하는 경우나 요소를 찾는것 순열(pe..

반복(iteration) 과 재귀(recursion) 반복과 재귀는 유사한 작업을 수행 반복은 수행하는 작업이 완료될 때까지 계속 반복, 단위 반복 같은 내용, 같은 작업을 일반화를 통해서 단위 반복 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다. 반복문이 아닌 재귀 함수 구현으로 메소드 호출 재귀 함수(recursive function) 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수 자신을 통해 자신을 정의한다. 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현 기본 부분(basic part)와 유도 부분(inductive part)로 구성 재귀적 프로그램..

반복(iteration) 과 재귀(recursion) 반복과 재귀는 유사한 작업을 수행 반복은 수행하는 작업이 완료될 때까지 계속 반복, 단위 반복 같은 내용, 같은 작업을 일반화를 통해서 단위 반복 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다. 반복문이 아닌 재귀 함수 구현으로 메소드 호출 재귀 함수(recursive function) 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수 자신을 통해 자신을 정의한다. 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현 기본 부분(basic part)와 유도 부분(inductive part)로 구성 재귀적 프로그램..

리스트(List) 순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type) 동일한 데이터를 가지고 있어도 상관 없다. 데이터 중복 허용 순서 -> index 관리(offset) 구현 방법에 따라 크게 두 가지로 나뉜다. 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트 순차 리스트 구현 방법 1차원 배열에 항목들을 순서대로 저장 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다. 데이터 접근 : 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. 삽입 연산 : 삽입 위치 다음의 항목들을 뒤로 이동해야 한다. 삭제 연산 : 삭제 위치 다음의 항목들을 앞으로 이동해야 한다. 순차 리스..