𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

1. 누적 합(prefix sum)1.1 개념특정 배열에서 어떠한 구간까지의 합을 구하는 방식. 어떠한 1차원 배열 [ 1, 5, 2, 10, 1, 8 ] 에서 가장 합이 큰 길이가 3인 부분 배열을 고를 때, [ 1, 5, 2 ], [ 5, 2, 10 ], ... , [ 10, 1, 8 ] 을 하나하나씩 반복문을 돌려나가면서 비교해 나가는 것이 아니라 미리 누적합을 계산해둔 배열 [ 1, 6, 8, 18, 19, 27 ] 를 활용하여 계산을 하기 때문에, 계산량에서 큰 이득이 있다. 1.2 1차원 배열알고리즘 작동 방식은 다음과 같다. 1. 길이가 N(또는 N + 1)의 누적합 배열을 선언하고, 각 누적합 배열의 i번째 인덱스에는 원본 배열의 1번째부터 i번째 원소의 합을 저장한다.2. a번째 원소부터..

1. 이분 탐색 ; Binary Search 1.1 개념 범위를 점점 좁혀가며 탐색을 하는 알고리즘으로, 이진 탐색이라고도 한다. 하나씩 찾는 것이 아닌 left와 right 양쪽에서 탐색을 하기 때문에 일반 탐색에 비해 속도가 빠르다. 시간복잡도는 일반 탐색이 O(n), 이분 탐색이 O(log n)이다. 알고리즘이 작동하는 방식은 다음과 같다. 미리 정렬된 배열에서, 정해놓은 인덱스 위치인 left와 right로 mid 값을 정해줌(mid = (left + right) / 2) mid가 가리키는 값과 목표 값(result)을 비교한다. mid > result, right = mid - 1 mid가 가리키는 값보다 목표 값이 더 작을 경우, 목표 값이 절반 아래쪽에 포함된 범위 안에 들어있기 때문에 ri..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 깊이 우선 탐색(DFS) 보러가기 2.2.3 너비 우선 탐색 ; Breadth-First Search 너비 우선 탐색(BFS)은 시작 정점과 가까운 정점부터 반복적으로 탐색해나가는 방식을 의미한다. 다음과 같은 모양의 그래프가 있다고 가정한다. 0번째 정점을 시작으로 작은 값부터 찾아간다고 가정했을 때, BFS 알고리즘을 적용하면 다음과 같은 순서로 진행된다. 1단계 : 0번 정점 방문 2단계 : 0번 정점과 인접한 정점 중 가장 값이 작은 1번 정점 방문 3단계 : 0번 정점과 인접한 정점 중 방문하지 않았고, 가장 값이 작은 2번 정점 방문 4단계 : 0번 정점과 인접한 정점 중 방문하지 않은 3번 정점 방문 5..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 더보기 1. 그래프 ; Graph 1.1 개념 그래프 순회 문제를 들어가기 전 짧게 그래프에 대해 설명하자면, 그래프는 정점(vertex)의 집합과 정점들을 서로 잇는 간선(edge)의 집합으로 구성된 자료구조로 연결되어 있는 객체 간의 관계를 표현할 수 있다. 수학적으로는 G = (v는 정점, e는 간선의 집합) 형태로 표현할 수 있다. 간선 방향의 유무에 따라 방향 그래프(directed graph)와 무방향 그래프(undirected graph)로 나눌 수 있고, 간선의 가중치 유무에 따라 가중 그래프(weighted graph)와 비가중 그래프(unweighted graph)로 나눈다. 2. 그래프 순회 문제..

2. 퀵 정렬 ; Quick Sort 2.1 개념 분할 정복 알고리즘을 이용한 정렬 방법 중 하나로, 병합 정렬과 마찬가지로 전체 집합을 작은 크기의 부분집합으로 나누어 정렬을 수행한 뒤 다시 합치는 정렬 방법을 의미한다. 병합 정렬의 핵심 연산은 병합인 데 비해 퀵 정렬의 핵심 연산은 분할이다. 퀵 정렬은 다음과 같은 단계로 진행된다. 1. 분할(Divide) : 정렬할 집합을 기준값을 중심으로 두 부분집합으로 분할 2. 정복(Conquer) : 부분집합 내에서 기준값의 정렬 위치 선정 이 때 사용하는 기준값을 피봇(Pivot) 이라고 하는데, 첫 번째 원소 / 마지막 원소 / 가운데 원소 등 임의의 순서의 값을 정하면 된다. 이렇게 정한 기준값을 중심으로 왼쪽(L)과 오른쪽(R) 부분집합으로 나누어 ..

1. 병합 정렬 ; Merge Sort 1.1 개념 분할 정복 알고리즘을 이용한 대표적인 정렬 방법 중 하나로, 여러 정렬된 집합들을 병합하여 하나의 정렬된 집합으로 만드는 정렬방법을 의미한다. 병합 정렬은 다음 세 가지의 단계를 통해 진행된다. 1. 분할(Divide) : 큰 집합을 부분집합으로 분할 2. 정복(Conquer) : 부분집합 내의 원소 정렬 3. 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 정렬하여 결합 원리만 생각하면 복잡해 보이지만, 그림과 함께 보면 쉽게 이해할 수 있다. 정렬되지 않은 집합 A는 다음과 같이 구성되어있다. A = { 3, 8, 7, 2, 5, 1, 4, 6 } 집합 A를 오름차순으로 정렬한다고 가정을 해보자. 병합 정렬하는 과정은 아래 그림과 같다...

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 1. 동적 계획법 ; dynamic programming 1.1 개념 분할 정복 패러다임 개념을 확장한 것으로, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 언뜻 문제를 보면 비슷하다 생각될 수 있지만, 분할 정복과 구분되는 동적 계획법만의 특성은 다음과 같다. 1. 중복되는 부분 문제(overlapping subproblem) 2. 최적 부분 구조(optimal substructure) 다음과 같은 속성을 만족해야 동적 계획법을 통해 문제를 해결할 수 있다. 전체 문제가 독립적인 부분 문제로 나뉘는 분할 정복 문제와 달리 동적 계획법에서는 중복되는 부분 문제가 반복적으로 등장한다. 또한 최적 부분 구..