목록분류 전체보기 (105)
yoongrammer
목차 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity) 알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다. 시간 복잡도: 알고리즘의 수행시간을 평가 공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가 시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다. 이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다. 시간 복잡도(Time Complexity) 알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다. 수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다. 기본 연산은 다음과 같습니다. 데이터 입출력 - copy, move... 산..
목차 점근 표기법 (asymptotic notation) 알아보기 점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다. 점근 표기법 (asymptotic notation) 컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다. ex) 하드웨어, 운영체제, 언어 등 실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다. 연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다. ex) \(f(n) = n^2+..
목차 보간 탐색 (Interpolation Search) 개념 및 구현 보간 탐색 (Interpolation Search)은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화부에서 이름 (책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다. 동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다. 이진 탐색과 보간 탐색의 탐색 위치를 결정하는 공식은 다음과 같습니다. arr [] : 데이터가 들어있는 배열 low : arr [] 배열에 시작 index high : arr[] 배열에 마지막 index x : 검색 값 pos : 탐색 위치 index 이진 탐색 \( pos = (low + high) / 2 \) 보간 탐색 \( pos = low + (x - ..
목차 점프 탐색(Jump search) 개념 및 구현 Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다. 정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다. 이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다. 동작 방식 배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다. m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다. m = √n 한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다. 값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다. 블록 최적 사이즈 구하는 과정 m에 최적 값을 구하는 공식은 다음과 같습니다. ..
목차 이진 탐색 (Binary search) 개념 및 구현 이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작 방식 이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다. 중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다. 이진 탐색의 동작 방식은 다음과 같습니다. 배열의 중간 값을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값과 같다면 종료합니다. (mid = key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다..
목차 순차 검색(Sequential Search) 개념 및 구현 순차 검색(Sequential Search)은 선형 검색(Linear Search)으로도 불리며 리스트에서 순차적으로 탐색하면서 원하는 값을 찾아내는 알고리즘입니다. 순차 검색은 구현이 쉽고 리스트의 정렬 여부와 상관없이 동작하는 장점이 있지만, 리스트의 모든 요소를 확인해야 하기 때문에 검색할 리스트의 길이가 길면 비효율적이라는 단점이 있습니다. 시간 복잡도(Time complexity) Operation Best Average Worst Search O(1) Θ(n) O(n) *n = 데이터 수 종료 조건 순차 검색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 검색을 종료합니다. 1. 검색을 실패할 경우 검색할 값을..
목차 다원 탐색 트리 (Multiway search tree) 다원 탐색 트리(Multiway search tree)는 m-원 탐색 트리 (m-way search tree)라고도 합니다. 다원 탐색 트리는 한 노드안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있습니다. 이진 탐색 트리는 m=2 인 다원 탐색 트리입니다. 다원 탐색 트리의 특징 다원 탐색 트리는 다음과 같은 특징이 있습니다. 1. 각 노드는 아래의 개수만큼 서브 트리를 갖습니다. \(0 ≤ 서브트리 개수 ≤ m\) 2. k 개의 자식 노드를 가지는 노드는 k-1개의 요소를 갖습니다. (k ≤ m) 3. 각 노드 안에 있는 키는 오름차순으로 정렬되어 있습니다. \(key_1 ≤ key_2 ≤ ... ≤ key_{(k-1)}\) 4. 다..
목차 AVL 트리(Tree) 개념 및 구현 AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다. 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다. AVL트리는 다음과 같은 특징을 가집니다. AVL 트리는 이진 탐색 트리의 속성을 가집니다. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다. 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다. AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다. Balance Factor(BF) B..
목차 이진 탐색 트리 (BST, Binary Search Tree) 이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다. 중복된 키를 허용하지 않습니다. 이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능합니다. 생성 예시 50, 15, 62, 80, 7, 54, 11 주어진 요소를 사용하여 BST를 생성하는 과정은 다음과 같습니다. 50을 트리의 루트로 트리에 삽입합니다. 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다. 그렇지 ..
목차 트리 순회 (Tree Traversal) 트리의 모든 노드들을 방문하는 과정을 트리 순회(TreeTraversal)라고 합니다. 선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 합니다. 일반적으로 트리 순회에는 다음과 같은 방법들이 있습니다. 전위 순회 (Preorder) 중위 순회 (Inorder) 후위 순회 (Postorder) 이러한 순회는 보통 재귀로 쉽게 구현할 수 있습니다. 전위 순회 (Preorder Traversal) 전위 순회는 깊이 우선 순회(DFT, Depth-First Traversal)이라고도 합니다. 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용됩니다. 트리를 복사할때 전위 순회를 사용하는 이유는 트리..