알고리즘 483

[ 개념 ] 17. 재귀(Recursion)의 기본 개념과 예제1

> Recursion의 기본 개념과 예제 Recursion 우리말로 순환 또는 재귀함수라고 한다. 즉, 자기 자신을 호출하는 함수, 메소드를 뜻한다. void func(){ ... func(); ... } ex1 - 무한루프 public class Code01{ public static void main(String[] args){ func(); } private static void func(){ System.out.println("hello.."); func(); } } ex2 - 항상 무한루프에 빠질까? recursion이 적절한 구조를 가지고 있다면, 항상 무한루프에 빠지는 것은 아니다. Base Case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. Recursive ..

[ 개념 ] 16. Graph - DFS(깊이우선탐색)

> DFS(Depth-First Search, 깊이우선탐색) 이진트리의 순회 방법인 inorder, preorder, postorder 순회방법이 DFS의 이진트리 버전에 해당한다. lever order는 BFS의 이진트리 순회 버전이다. 깊이우선탐색(DFS) 출발점 s에서 시작한다. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 2번을 계속 반복한다. 노드 8에 도달했을 때처럼 인접한 노드들중 invisited 노드가 존재하지 않는다면, unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다. 다시 2번을 계속 반복한다. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 다음과 같은 흐름으로 깊이우선순..

[ 개념 ] 15. Graph - BFS(너비우선탐색)

> BFS(Breadth-First Search, 너비우선탐색) 그래프 순회 순회(traversal) 그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법 BFS (Breadth-First Search, 너비우선순회) DFS (Depth-First Search, 깊이우선순회) 너비우선탐색(BFS) BFS 알고리즘은 다음 순서로 노드들을 방문 L0 = {s}, 여기서 s는 출발 노드 L1 = L0의 모든 이웃 노드들 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ... Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 한마디로 그래프에서 노드들을 동심원의 형태로 순회하는 방법 큐를 이용한 너비우선탐색 출발노드를 check하고 시작한다. 큐에 스타트 노드(1번노드)를 삽입한다. whil..

[ 개념 ] 14.Graph의 개념과 표현

> Graph Algorithm - 개념과 표현 Graph (무방향) 그래프 G = (V, E) V : 노드 혹은 정점(vertex) E : 노드쌍을 연결하는 Edge 혹은 Link Object들 간의 이진관계를 표현 n = |V|, m = |E| 방향 그래프와 가중치 그래프 방향그래프(Directed Graph) G = (V, E) Edge (u, v)는 u로부터 v로의 방향을 가짐 가중치 그래프 Edge마다 가중치(weight)가 존재 그래프의 표현 인접행렬(adjacency matrix) 인접리스트(adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 저장 공간 : O(n + m) 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) ..

[ 개념 ] 13. Hashing에 관하여 - 02 (Hashing in JAVA)

> Hashing - 02 좋은 해시 함수란? 현실에서는 키들이 랜덤하지 않음 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해시함수값이 불규칙적이 되도록 하는게 바람직하다. 해시함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함 해시 함수 Division 기법 h(k) = k mod m 예: m = 20 and k = 91 ==> h(k) = 11 장점: 한번의 mod연산으로 계산, 따라서 빠름 단점: 어떤 m값에 대해서는 해시 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음, 가령 m = 2^p 이면 키의 하위 p비트가 해시 함수값이 됨 Multiplication 기법 ..

[ 개념 ] 12. Hashing에 관하여 - 01 ( Chaning, Open Addressing, ...)

> Hashing - 01 Hash Table 탐색과 삽입, 삭제를 지원하는 자료구조를 dynamic set이라고 부른다. 4장에서는 검색트리를 가지고 dynamic set을 구현했고, 또다른 한가지 구현 방법이 Hashing을 이용하는 것이다. 해시 테이블은 dynamic set을 구현하는 효과적인 방법의 하나이다. "적절한 가정"하에서 평균 탐색, 삽입, 삭제시간 O(1) 보통 최악의 경우 O(n) 해시 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 h : U -> {0, 1, 2, … , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합 키 k가 h(k)로 해싱되었다고 말한다. 즉, h() 해시 함수는 각 키에 대한 해시함수값을 그 키를 저장할 배열 ..

[ 개념 ] 11. 이진탐색트리(Binary Search Tree)

> 이진탐색트리(BST) Dynamic Set 집합이다. 여러개의 데이터의 집합인데, 그것들의 내용이 고정되지 않고, 생성과 삭제를 반복하면서 유동적인 집합이다. 아래와 같은 특징을 가진다. Dynamic Set, Dictionary 또는 Search Structure라고 불린다. 여러 개의 키(key)를 저장 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARCH - 키 탐색 DELETE - 키의 삭제 예: 심볼 테이블 일반적으로 구현할 때 배열 or 연결리스트를 사용한다. 각 동작에 있어서 다음과 같은 시간복잡도를 가진다. 정렬된 배열의 이진탐색 - O(logn) 정렬된 배열에서 원소를 insert, delete하면 나머지 원소들을 한칸식 shift - O(n) 정렬된 ..

[ 개념 ] 10. 트리(Tree)와 이진트리(Binary Tree)

> 트리와 이진트리 기본 트리(Tree) 계층적인 구조를 표현하기 위해 사용하는 자료구조 조직도 디렉토리와 서브디렉토리 구조 가계도 용어 루트(Root) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다. 맨 위의 노드를 루트라고 한다. 부모-자식(parent-child) 관계 각 노드들의 상하 관계를 부모-자식(parent-child)관계로 나타낸다. 형제 관계(sibling) 루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가진다. 부모가 동일한 노드들을 형제관계라고 부른다. 리프(leaf) 노드 자식이 없는 노드들을 leaf 노드라고 부른다. 리프노드가 아닌 노드들을 내부(internal)노드라고 부른다. 조상-자손(ancestor - descendant) 관계 부모..

[ 개념 ] 09. 멱집합( Recursion )과 조합

> 멱집합 (Recursion 응용) PowerSet 어떤 집합의 모든 부분집합을 멱집합이라고 부른다. 임의의 집합 data = {a, b, c, d}의 모든 부분집합은 2^n =16개이다. Recursion을 이용하여 모든 부분집합 나열 {a, b, c, d, e, f}의 모든 부분집하을 나열하려면 먼저 a를 포함하지 않는 부분집합과 a를 포함하는 부분집합으로 나눌수 있다. 따라서 아래와 같이 표현할 수 있다. a를 포함하지 않는 부분집합 a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열하고 a를 포함하는 부분집합 {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. => 이 두가지를 합치면 경우의 수가 2^n개가 되는 것이다. 그렇다면, {b, c, d, ..

[ 개념 ] 08. 이미지 픽셀 세기( Recursion )

> Counting Cells in a Blob (Recursion 응용) 입력으로 Binary 이미지가 주어진다. 각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다. 서로 연결된 image pixel들의 집합을 Blob이라고 부른다. 상하좌우 및 대각방향으로도 연결된것을 Blob으로 간주한다. 따라서 위 그림에서는 총 4개의 Blob이 존재한다. 특정 좌표가 속한 Blob의 크기 count 입력 N * N 크기의 2차원 그리드(grid) 하나의 좌표 (x, y) 출력 픽셀 (x, y)가 포함된 blob의 크기 (x, y)가 어떤 blob에도 속하지 않는 경우에는 0 Recursive Thinking 현재 픽셀이 속한 Blob의 크기를 카운트하려면 현재 픽셀이 i..

[ 개념 ] 07. 미로찾기( Recursion )

> 미로찾기(Recursion 응용) (n-1, n-1)의 좌표를 출구로 가정 흰색이 지날 수 있는 길, 파란색이 벽 입구에서 출구까지의 경로를 찾는 문제 Recursive Thinking 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구이거나(이미 내가 출구에 와 있거나). 혹은, 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가능경로가 있꺼나, 위의 경우를 Recursive하게 생각한다. 전체 문제를 해결하려고 하면 부분 문제의 해결이 이루어지면서 전체문제가 해결된다. => 위의 둘중에 하나가 성립해야 출구까지 가는 경로가 있다고 할 수 있다. 미로찾기(Decision Problem) - 답이 Yes or No 출발점에서 출구까지 가능 경로가 있느냐 없느냐?의 문제로 생각한다..

[ 개념 ] 06. 알고리즘을 위한 자바 IO

알고리즘을 위한 자바 IO codeplus - 프로그래밍 대회에서 사용하는 Java 참고 System.out System.out.println(); System.out.printf("%d", n) 실수형, 문자형 자료 출력 가능 Scanner next[자료형]을 이용해서 입력을 받을 수 있고, hasNext[자료형]을 이용해서 입력받을 수 있는 자료형이 있는지 구할 수 있다. 두 수 입력 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a, b; a = scanner.nextInt(); b = scanner.nextInt(); System.out.println(a..

[ 개념 ] 05. N-Queens(Back Traking)

> N-Queens (Back tracking) (n = 8) 아래의 예(n=8)에서는 8x8 체스보드에 8개의 말을 놓는데 그 중에 어떤 말들도 동일한 행, 동일한 열, 동일한 대각선 상에 오지 않도록 n개의 말을 놓을 수 있는가에 대한 문제이다. 위의 방법대로 n개의 말을 놓으려면, 결국 조건을 만족하면서 하나의 행에 하나의 말이 와야한다. Back Tracking 내가 지나온 길을 다시 되돌아 가면서 문제를 해결한다 어떠한 결정들을 내려가다가, 결정이 막다른 길이다. 즉, 그 결정을 내려서는 안된다라는 것이 분명해지면, 가장 최근에 내렸던 결정을 번복한다. 이런식으로 문제를 해결한다. 상태 공간트리 1번말이 (1,1)에 위치했을 때, 그리고 그 때 2번말이 (2,1), (2,2), (2,3), (2..

[ 개념 ] 04. Locality 관점에서 Quick Sort가 Merge Sort보다 빠른 이유

> Locality의 관점에서 Quick sort가 Merge sort보다 빠른이유 Quick sort와 Merge sort는 nlogn의 시간복잡도를 가지는 대표적인 정렬 방법이다. 일반적으로 Quick sort가 Merge sort보다 크다. 그 이유는 Locality와 관련이 있다. Locality의 개념을 알아보고 왜 Quick sort가 더 빠른지 알아보도록 하자. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. 메모리 내의 정보를 균일하게 엑세스 하는게 아닌, 짧은 시간내에 특정 부분을 집중적으로 참조하는 특성이다. void f() { //간단한 작업을 수행 } void g() { int arr[1000]..

[ 개념 ] 03. Tail Call Recursion

> Tail Call Recursion C++ 제가 이번에 설명할 것은 제가 검색하다가 발견한! Tail Call Recursion 이라는 새로운 재귀?적인 방법의 코딩입니다. 기존의 재귀함수와 비교하면서 설명하도록 하겠습니다. 1. 기존의 재귀함수 먼저 기존의 재귀함수를 보도록합니다. 여기서는 가장 대표적인 피보나치 수열을 이용한 재귀함수를 살펴보겠습니다. #include using namespace std; int f(int n){ if(n < 0) return 0; if(n < 2) return n; return f(n-1) + f(n-2); } int main(void){ cout