분류 전체보기 (247) 썸네일형 리스트형 [Algorithm] Insertion Sort (삽입 정렬) 1. Insertion Sort (삽입 정렬) 삽입 정렬은 N개의 원소 배열을 정렬 시에 배열을 정렬이 되어있는 부분과 정렬이 되지 않는 부분 두 부분으로 나누어 비교를 하여 정렬하는 알고리즘이다. 매 정렬 시에 정렬을 하지 않은 부분의 한 원소를 선택해서 정렬이 된 부분과 비교하여 원소의 위치를 찾아서 해당 위치에 삽입하는 방식으로 정렬한다. 삽입 정렬을 통해서 오름차순으로 정렬 시에 다음과 같은 순서를 거친다. 배열의 정렬을 1부터 N까지 반복한다. i-1까지의 값이 정렬되어 있을 때 정렬을 하는 대상이 되는 값이 i번째 값이 된다. 이때 먼저 i-1 번째 값과 비교하여 i-1 번째 값이 더 큰 경우 자리를 바꾼다. 이 과정을 i-1부터 0번까지 비교를 진행하게 되는데, 이때 한칸 앞의 값이 더 작은.. [Algorithm] Bubble Sort (거품 정렬) 1. Bubble Sort (거품 정렬) 거품 정렬은 N개의 원소를 가진 배열을 정렬 시에 인접한 두 원소를 비교하여 정렬하는 방법이다. 시간복잡도는 크지만 구현이 간단하기 때문에 자주 사용된다. 크기 N의 배열을 정렬할 때, 인덱스 0번과 1번, 1번과 2번, ... N-2번과 N-1번의 원소들을 비교하여 자리를 교환해준다. 인접한 원소들의 교환을 한번 수행할 때마다 가장 오른쪽에 배치되는 원소는 올바르게 정렬되어진 값이 된다. 예를 들어 오름차순으로 정렬하는 경우 매 회차마다 가장 큰 수가 오른쪽으로 정렬되어진다. 이를 통해서 매 회차마다 가장 오른쪽으로 정렬된 값은 다음 회차의 정렬의 대상에서 제외된다. 2. Bubble Sort 구현 Bubble Sort는 첫 원소부터 N-i 까지의 원소에 대해서.. [Algorithm] Selection Sort (선택 정렬) 1. Selection Sort (선택 정렬) 선택 정렬은 in-place 비교 정렬 중의 하나로 정렬되지 않은 부분에서 매번 최소값을 가지는 요소를 찾아서 가장 앞으로 자리를 옮기는 방식을 반복하여 정렬을 진행한다. 이 방법을 진행하는 중에는 배열이 최소값들이 순서대로 정렬된 부분과 아직 정렬되지 않은 두 부분으로 나뉘어진다. 정렬되지 않는 리스트에서 최소값을 찾는다. 최소값을 리스트의 가장 앞에 위치한 값과 자리를 바꾼다. 첫번째 값을 제외하고 두번째 값부터 리스트를 지정해서 정렬을 진행한다. 매 정렬마다 정렬되지 않은 리스트의 최소값이 정렬된 리스트 이동하는 방식으로 구현된다. 추가적으로 값을 저장하는 메모리가 필요하지 않기 때문에 공간 복잡도에서 이점을 가지게 된다. 2. Selection Sor.. [Algorithm] BFS 1. BFS (Breadth First Search, 너비 우선 탐색) 그래프 탐색 방법 중의 하나로 하나의 정점으로부터 시작해서 인접한 정점을 먼저 탐색하는 방법이다. 해당 정점과 연결되어있는 정점들 중 하나의 방향으로만 우선 탐색했던 DFS와 달리 BFS는 인접한 정점들을 먼저 탐색하고 이어서 다음으로 인접한 정점들을 탐색하는 방식으로, 깊이가 아닌 너비를 우선으로 탐색하는 방법이다. 주로 특정 정점까지의 최단 경로를 찾고 싶을 때 사용한다. BFS는 인접한 노드들에 대해서 우선적으로 탐색하고 이어서 다음으로 인접한 노드들을 탐색하는 것이 트리 탐색의 level order traversal 과 유사한데, 그래프에서는 사이클이 발생할 수 있기에 방문한 노드를 확인하는 visited 를 구현하여 방문 여.. [Algorithm] DFS 1. DFS (Depth First Search, 깊이 우선 탐색) 그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로 탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다. DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder tr.. [Algorithm] Binary Search Algorithm Binary Search Algorithm (이진 탐색 알고리즘) 이진 탐색 알고리즘은 탐색 알고리즘의 하나로 이미 정렬되어 있는 배열을 대상으로 원하는 값을 찾는 알고리즘이다. 정렬되어 있는 배열의 중간의 값과 타겟이 되는 값을 비교해서 탐색을 진행한다. 중간값과 타겟이 동일하다면 해당 값을 반환한다. 만약 타겟이 되는 값이 중간값보다 큰 경우 중간 값을 기준으로 우측, 작다면 중간 값을 기준으로 좌측의 부분 배열을 대상으로 반복적으로 탐색을 진행한다. 이때 대상이 되는 배열의 왼쪽 인덱스가 오른쪽 인덱스보다 크다면 값이 없는 것으로 판단하여 탐색을 중단한다. 위의 예제 이미지는 정렬되어있는 배열에서 타겟 값인 23을 탐색하려고 한다. 첫번째 과정에서 중간값은 16 이다. 16은 타겟 값인 23 보다 .. [DS] Hashing 1. hash table hash table은 hashing을 통해서 데이터를 저장하는 데이터 구조이다. hashing은 내부적으로 hash function 을 사용하여서 key와 value를 mapping 하여 hash table에 저장하여 데이터 구조를 형성하는 것을 의미한다. hash table에 데이터의 key와 value가 mapping 되어 저장되기 때문에 탐색에서 average case에 대해서 시간 복잡도가 O(1)이 된다. collision이 발생하는 경우에는 O(1)의 시간 복잡도를 보장할 수 없다. 그렇기 때문에 hash table에서의 성능은 hash function과 collision 발생 시의 정책에 따라 달라진다. 다음 예제는 hash table의 크기가 6이고 hash fun.. [DS] Graph MST & Shortest path - 이전 글: [DS] Graph 개념과 탐색방법 3. MST (Minimum Spanning Tree) 최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다. 최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 1) Kruskal algorithm greedy 한 방법으로 간선을 선택하여서 .. 이전 1 ··· 22 23 24 25 26 27 28 ··· 31 다음
