늦깎이 IT

[ LCS란? ] LCS란 Longest Common Subsequence의 약자로 최장 공통 부문 문자열이다. 여기서 Subsequence란 연속적이지 않은 부분 문자열이다. 다음과 같은 문자열 A와 B가 있다고 하자. A = { ABCBDAB } // B = { BCDB }이때 문자열 B는 문자열 A의 Subsequence이다. 위처럼 연속적이지는 않지만, 순서는 맞는 문자열을 Subsequence라고 한다. LCS는 두 개의 문자열이 주어졌을 때, Common Subsequence들 중 가장 긴 문자열을 뜻한다. [ 생각해보기 ] 아래 그림과 같이 문자열 A와 B가 있다고 가정하자.LCS의 마지막 문자가 A라고 한다면, 문자열 X와 Y 어딘가에도 문자열 A를 포함하고 있을 것이다. 그렇다면, 아래 ..

[ 해시 테이블이란? ] 해시 테이블이란 데이터의 효율적으로 관리하기 위한 자료구조이다. 해시 테이블은 검색하고자 하는 키(Key) 값을 해시 함수를 통해 해시 값으로 변환하고 그 해시 값을 가지고 데이터에 접근하는 것이다. [ 해시함수란? ] 해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시 코드(hash code) 혹은 해시 값(hash value)라고 하며 매핑하는 과정 전체를 해싱(hasing)이라고한다. [ 충돌 발생 ] 해시 함수는 서로 다른 키(key) 값에 대해서 서로 다른 해시 코드(hash code)를 생성한다고 했다. 하지만, 꼭 그렇지 않을 가능성이 있다. 예를 들어, 임의의 해시 함수..

이전 포스팅 [이진탐색트리] 와[배열로 이진탐색트리 만들기]를 먼저 참고하시기 바랍니다. [ 이진트리인지 확인하기 ] 주어진 트리가 이진트리인지 확인하는 가장 간단한 방법은 주어진 트리를 중위순회하면서 나온 데이터들이 모두 오름차순으로 정렬되는지 확인하면 된다. 이유는 이진탐색트리의 전제조건때문인데, 이는 이전 포스팅을 확인하기 바란다. 아래와 같은 트리가 있을 때, 이 트리가 이진탐색트리인지 확인하는 함수를 작성한다. [ 배열을 사용해서 확인하기 ] 1. 주어진 트리를 중위순회하며 데이터를 임의의 다른 배열에 저장한다.2. 저장된 데이터들이 모두 오름차순으로 정렬되어있는지 확인한다.3. 저장된 데이터가 모두 오름차순으로 정렬되어있으면 True, 아니라면 False를 반환한다. [ JAVA 코드 ]123..

이 내용을 보기전에 이전 포스팅 [배열로 이진탐색트리 만들기]와 [AVL 트리]을 확인하자. [ 트리의 Balance 확인하기 ] 어떤 이진트리가 주어졌을 때, 이 이진트리의 Balance가 맞는지 확인하는 함수를 구해보자. 이 개념은 AVL트리를 구성할 때 나오는 개념이다. 또한, 여기서 말하는 Balance가 맞다는 의미는 어떤 노드의 양쪽 서브트리의 길이 차이가 1을 넘지 않는다는 것을 의미한다. 아래의 그림을 살펴보자. 각각의 노드에 대한 Balance 값을 계산한 그림인데, Balance 값은 해당 노드를 기준으로 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. 노드 7에 대한 Balance 값이 +2임을 확인할 수 있는데 이는 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 2 크다는..

이번 시간에는 배열을 이진트리로 변환하는 방법에 대해서 설명한다.정렬이 되어있고, 정수로만 이루어진 배열이 있을 때 이 배열로 이진검색트리로 변환해보자. 아래와 같이 숫자 0부터 9까지 정렬된 배열이 있다고 가정하자. 이 배열을 이진탐색트리로 변환할 때 알아야 할 것은 이진탐색트리의 전제조건이다. [ 이진탐색트리의 조건 ]모든 키는 유일하다.왼쪽 서브트리의 키 값은 부모노드의 키 값보다 작다.오른쪽 서브트리의 키 값은 부모노드의 키 값보다 크다.루트노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다.이진탐색트리의 연산에는 크게 삽입, 삭제, 탐색이 있는데 각각의 연산은 이진트리의 높이에 따라 시간 복잡도 효율성을 갖게된다. 즉, 트리의 높이가 낮을 수록(logN에 가까울 수록) 좋은 연산속..

이전 포스팅 [이진탐색트리]를 참고하시기 바랍니다.이 포스팅은 윤성우 저자의 '자료구조'를 참고했습니다. [ AVL 트리란? ] AVL트리는 이진탐색트리의 단점인 불균형 트리를 보완하기 위한 방법으로써 데이터가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.AVL 트리의 핵심 개념중 하나가 균형인수, Balance Factor(BF)이다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. 두 서브트리의 높이가 같다면 BF 값은 0이다. 아래 그림에서 각 노드에 대한 균형인수 값을 확인해보자. 노드 7의 왼쪽 서브트리의 높이는 3이고, 오른쪽 서브트리의 높이는 1이므로 균형인수 값은 2가된다. 각 노드들의 균형인수의 절대값이 1보다 크..

이 포스팅은 이전의 [이진탐색트리] 내용을 보완하여 다시 작성된 포스팅입니다. [ 이진탐색트리란? ] 이진탐색트리란 이진 트리 기반의 탐색을 위한 자료구조로써 아래와 같은 특성을 만족한다. 모든 키는 유일하다.왼쪽 서브트리의 키값은 루트노드의 키값보다 작다.오른쪽 서브트리의 키값은 루트노드의 키값보다 크다.왼쪽과 오른쪽 서브트리도 이진탐색 트리이다. 아래 그림은 이진탐색트리로써 각각의 모든 노드들에 대해서 위의 전제조건을 모두 만족시킨다. [ 탐색 ] 이진탐색트리의 특징을 활용한 탐색 알고리즘을 알아보자. 이진탐색트리에서 임의의 데이터를 찾을 경우에는 다음과 같은 과정을 거친다. 루트노드의 키값과 찾고자하는 값을 비교한다. 찾고자하는 값이 루트노드의 키값이라면 종료한다.찾고자하는 값이 루트노드보다 작을 ..

[최단 경로란?] 최단 경로 (shortest path)는 정점 u와 v를 잇는 경로 중, 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.노드 u에서 v까지의 최단 경로의 값을 δ(u, v)라고 하자. [최단 경로의 유형] 1. Single-Source ( One-to-All )하나의 출발 노드 s로부터 그래프 내의 모든 노드들까지의 최단 경로를 찾는 문제.2. Single-Destination 그래프내의 모든 노드로부터 하나의 목적지 노드 d까지의 최단 경로를 찾는 문제.만약, 그래프가 무방향 그래프라면 Single-Source 문제와 Single-Destination 문제는 똑같은 문제가 된다.그러나, 그래프가 방향 그래프라면 모든 간선들의 방향을 거꾸로 뒤집는다면, Single-Source..