Information of IT

Topological Sort (위상 정렬)Topological sort는 Direct Acyclic Graph의 경우에서 문제를 해결하는 방법이다. 방향이 존재하는 그래프에서 각 vertex의 선행 순서 정보를 유지하면서 모든 vertex를 탐색하는 알고리즘이다. Type of Edges 알고리즘을 알아보기 전에, Direct Acyclic Graph를 알기 위해 방향이 있는 그래프에서 DFS를 실행할 때 나타나는 edge의 종류를 먼저 정리해 보자.  Tree Edge: 새로운 정점을 만났을 때 생기는 edge. Edge는 한 정점에서 다른 정점을 이을 때 발생하게 된다. Tree Edge는 어떤 정점이 새로운 정점과 연결될 때 생기는 edge를 말한다.Back Edge: Back Edge는 트리에서..

계수 정렬 (Counting Sort) - 개념선형 시간에 정렬하는 효율적인 알고리즘  I. 계수 정렬 (Counting Sort)의 개요 가. 계수 정렬의 정의- 선형 시간에 정렬하는 효율적인 알고리즘  나. 계수 정렬의 특징- 입력키가 한정될 때 사용가능 (입력이 0부터 K사이의 수)- 정수나 정수로 표현할 수 있는 자료에 대해서만 동작- Max 값 산출이 선행되어야 함  Ⅱ. Algorithm Concept카운팅 정렬은 다음과 같은 과정으로 수행된다.입력받은 배열 A의 요소값들의 등장 횟수를 저장할 배열 B와 최종적으로 정렬된 값들을 담을 배열 C를 준비한다.입력밭은 배열에서 값을 하나씩 꺼내서 해당 값을 배열 B의 인덱스로 사용해 B의 요소 값을 하나 증가시킨다. (B [A [i]]++)B가 완성..

개 념문자열 탐색 (원시적 탐색, 카프라빈 탐색, KMP탐색, 보이어 무어 탐색) 문자열 데이터 안에서 특정 패턴의 검색 대상이 되는 문자열을 탐색하는 알고리즘  I. 문자열 탐색의 개요 가. 문자열 탐색의 정의- 문자열 데이터 안에서 특정 패턴의 검색 대상이 되는 문자열을 탐색하는 알고리즘  Ⅱ. 문자열 탐색 알고리즘가. 원시적 탐색 * 특정 대상의 문자열에서 찾고자 하는 패턴 문자를 탐색하는 기법* 주어진 텍스트에서 주어진 패턴이 어디에 나타나는지 알아내는 문제BasicStringMatching(A[ ], P[ ], n, m) {/* n: 배열 A[ ]의 길이, m: 배열 P[ ]의 길이 */for (i = 0; i ≤ n-m; i++) { for (j == 0; j if ( P[j] != T[i +..

개념트리 중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진 트리인 힙(Heap)을 만들기 위한 정렬 방법  I. 힙 정렬 (Heap Sort)의 개요 가. 힙 정렬의 정의- 트리 중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진 트리인 힙(Heap)을 만들기 위한 정렬 방법  나. 힙 정렬의 특징 - 힙 구조에서 가장 큰 값의 위치는 루트에 있음.- 배열에 저장하는 것이 효율적임.- 수행시간 복잡도: O(n·log2n)  Ⅱ. 힙 정렬의 삽입∙삭제 과정 및 사례 가. 힙 정렬의 삽입과정 및 사례 새로운 노드의 위치를 정한다.삽입할 데이터를 새로운 노드에 놓는다.새로운 노드와 부모를 비교하여 부모가 더 작으면 바꾸는 과정을 루트에 도달할 때까지 계속한다.⇒⇒⇒void..

백트래킹 알고리즘 - 개 념깊이우선탐색(DFS)기법에 Pruning 기법을 적용하여 Promising 검토와 Back Tracking 을 활용하여 탐색 성능을 개선한 알고리즘  I. 백트래킹(Back Tracking) 알고리즘의 개요 가. 백트래킹 알고리즘의 정의- 깊이우선탐색(DFS)기법에 Pruning 기법을 적용하여 Promising 검토와 Back Tracking 을 활용하여 탐색 성능을 개선한 알고리즘  나. 백트래킹의 특징 특징설명깊이우선탐색 기법- 탐색 트리의 최초의 하위노드 (child node) 를 확장하여 목표상태 (goal state) 가 발견될 때까지 더 깊이 (deeper and deeper) 확장하는 무정보 탐색(Uninformed or Blind Search) 방법Pruning..

최단 경로 탐색 알고리즘 - 개 념최단 경로 탐색 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드(Floyd) 알고리즘, A* 알고리즘) 그래프 내의 한 vertex에서 다른 vertex로 이동할 때 가중치의 합이 최소값이 되는 경로를 탐색하는 알고리즘  I. 최단 경로 탐색의 개요 가. 최단 경로 탐색의 정의- 그래프 내의 한 vertex에서 다른 vertex로 이동할 때 가중치의 합이 최솟값이 되는 경로를 탐색하는 알고리즘  Ⅱ. 최단 경로 탐색 알고리즘 가. 다익스트라 알고리즘 (Dijkstra Algorithm) * 사이클이 없는 방향성에만 적용* 가중치 합 최소* Link State 알고리즘 활용각 vertex들은 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비모든 ..

개 념정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫 번째 요소와 교환하는 정렬 기법  I. 선택 정렬 (Selection Sort)의 개요가. 선택 정렬의 정의- 정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫 번째 요소와 교환하는 정렬 기법  나. 삽입 정렬의 특징 - 수행시간 복잡도 : O(n2)- 안정성을 만족하지 않음.  Ⅱ. 선택 정렬의 단계 및 사례 가. 선택 정렬의 단계 (Pseudo Code)    나. 선택 정렬의 사례 public static int[] doSelectionSort(int[] arr){ for (int i = 0; i { int index = i; for (int j = i + 1; j if (arr[j] index = j; int smalle..

최소신장트리 알고리즘 - 개 념최소신장트리 (Minimum Spanning Tree) 알고리즘 (프림 알고리즘, 크루스칼 알고리즘) 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 I. 신장트리 (Spanning Tree)의 개요 가. 신장 트리의 정의- 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 나. 최소신장트리의 정의- 정점 간 가중치(cost)의 합이 최소인 신장 트리  Ⅱ. 최소신장트리 알고리즘  가. Prim의 알고리즘 * 시작점 기반 최소 가중치* 정점마다 edge 검사* 우선순위 큐 기반 구현임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사최소 가중치를 ..

개 념레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법  I. 기수 정렬 (Radix Sort)의 개요  가. 기수 정렬의 정의- 레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법 나. 기수 정렬의 특징 - O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법- 시간 복잡도 : O(kn) k : 버킷 수- 정렬 레코드 타입 제한  Ⅱ. 기수 정렬의 개념 및 사례  가. 기수 정렬의 개념   나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers)    코드 구현 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 public vo..

개념Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘 I. 퀵 정렬 (Quick Sort)의 개요  가. 퀵 정렬의 정의- Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘  나. 퀵 정렬의 특징 - 분할과 정복 기반- 재귀호출 구조- 정렬을 위한 별도의 스택이 필요- 수행시간 복잡도: O(n·log2n)  Ⅱ. 퀵 정렬의 단계 및 사례 가. 퀵 정렬의 단계 - 정렬할 원소들의 집합에서 Pivot 값을 설정- Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽- 분할된 집합의 크기가 1이 될 때까지 반복  나. 퀵 정렬의 사례 void quicksort(element list[], int left, int rig..

개 념여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법  I. 버블 정렬 (Bubble Sort)의 개요 가. 버블 정렬의 정의- 여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법  나. 버블 정렬의 특징- 간단하지만 느린 속도의 알고리즘- flag를 통해 속도 개선 가능- 수행시간 복잡도: O(n2)  Ⅱ. 버블 정렬의 단계 및 사례 가. 버블 정렬의 단계 - 인접한 두 개의 키 값을 비교함.- 앞의 키 값이 뒤의 키 값보다 크면 교환- 더 이상 비교할 대상이 없을 때까지 처음부터 반복   나. 버블 정렬의 사례 /* list에 대한 기본 버블정렬 알고리즘 */void bubble_sort(element list[], i..

개 념해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘 I. 해시 탐색 (Hash Search)의 개요 가. 해시 탐색 (Hash Search)의 정의 - 해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘 ※ 해시테이블(hash table) : 키 값을 저장하는 테이블 버킷(bucket) : 해시될 키 값의 범위, 테이블의 크기 슬롯(slot) : 한 개의 버킷에 저장될 키 값의 개수 나. 해시 탐색 (Hash Search)의 특징 - 고정길이, One Way- O(1)의 탐색 속도- 충돌처리 매커니즘 필요   Ⅱ. 해시 함수의 기법 가. 해시 함수의 기법 구 분내 용mid-square식별자의 제곱 값의 가운데 값을 취함.division나머지 연산..

합 병 정렬 (Merge Sort)리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법  I. 합병 정렬 (Merge Sort)의 개요  가. 합병 정렬의 정의- 리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법  나. 합병 정렬의 특징 - 분할과 정복 : 분할(Divide) -> 정복(Conquer) -> 결합(Combine) 과정 수행- 재귀적 수행 : 분할을 마친 후 분할된 부분의 반복적 수행- 정렬을 위한 별도의 공간이 필요- 수행시간 복잡도: O(n·log2n)  Ⅱ. 합병 정렬의 단계 및 사례 가. 합병 정렬의 단계  나. 합병 정렬 개념 void mergeSort(int arr[], int l, int r){ if (l { int m =..

개념정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 I. 이진 탐색 (Binary Search)의 개요 가. 이진 탐색의 정의- 정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 나. 이진 탐색의 특징- 분할과 정복 기반- 정렬된 데이터 집합에서 사용- 고속 탐색  Ⅱ. 이진 탐색 단계 및 사례 가. 이진 탐색 단계 및 사례- 데이터 집합의 가운데 있는 기준값과 찾는 키 값 비교 (1) 찾는 키 값 > 기준 값 : 오른쪽 부분 검색 (2) 찾는 키 값 - 키 값을 찾을 때까지 이진 검색을 순환적으로 반복/*searchnum 에 대해 list [0]찾으면 그 위치를 반환하고 못 찾으면 –1을 반환한다.*/int binsearch(int list[],int s..

개념첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법 I. 삽입 정렬 (Insert Sort)의 개요 가. 삽입 정렬의 정의- 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법 나. 삽입 정렬의 특징- 간단하지만 레코드의 이동이 많은 알고리즘- 비교적 크기가 작은 데이터 집합 정렬에 유리함.- 수행시간 복잡도: O(n2)  Ⅱ. 삽입 정렬의 단계 및 사례 가. 삽입 정렬의 단계 - 삽입 대상 위치를 2번째부터 마지막까지 지정- 비교 대상을 처음부터 바로 전까지 지정- 정렬 대상의 값들과 뽑아낸 요소와 비교- 삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동- 새로 생긴 빈 자리에 해당 요소를 삽입- 전체 데..