목록알고리즘 (87)

수학과의 좌충우돌 프로그래밍

[Algorithm] Two Pointers, 투 포인터

이번 포스팅에서는 Two Pointers에 대해서 알아보도록 하겠습니다. Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘입니다. 여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다. Two Pointers 의 동작원리, 시간복잡도, C++로 구현한 코드를 보며 이해해보겠습니다. 동작 원리 적절한 예시를 위해 백준에서 Two Pointers 를 사용하는 문제의 에시를 사용하겠습니다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분..

알고리즘/이론 2020. 10. 26. 15:56
[Algorithm] Counting Sort, 계수 정렬

이번 포스팅에서는 Counting Sort 에 대해서 알아보도록 하겠습니다. Counting Sort의 동작원리, 시간복잡도, C++로 구현한 코드를 보며 이해해보겠습니다. 동작원리 다음과 같이 origin이라는 배열을 Counting Sort를 통해서 정렬 해보도록 하겠습니다. int origin[] = {5, 3, 4, 5, 1, 0, 4, 1, 3, 0, 2, 4, 2, 3, 0}; Counting 첫 번째로 해야할 일은 각 숫자가 몇 번 나왔는지 세야합니다. origin 배열에 등장한 수와 그 수가 몇 번 나왔는지를 기재하였습니다. 수 0 1 2 3 4 5 나온 횟수 3 2 2 3 3 2 Counting Sum 다음으로는 각 수의 누적합을 구해줍니다. 누적합을 통해서 해당 숫자가 어느 인덱스에 위..

알고리즘/이론 2020. 10. 23. 10:53
[Algorithm] 위상정렬

위상정렬이란? 위상 정렬은 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘입니다. 그림을 보며 이해해봅시다. 다음과 같은 그래프에서 앞선 작업 2,3이 끝나야 뒤 작업 4가 이루어질 수 있으며 이 때 둘 중 무엇을 먼저 끝내던 규칙에 위배 되지 않기 때문에 경로는 여러 개가 나올 수 있습니다. 단 위상정렬이 성립하기 위해서는 DAG여야 합니다. DAG란? Directed Acyclic Graph의 줄임말로 사이클이 존재하지 않는 방향 그래프입니다. 만일 위 그림에서 5이 1에 연결되었다면 시작점이 존재하지 않기 때문에 위상정렬이 성립할 수 없습니다. 위상 정렬 원리 위상 정렬이 어떤 원리로 동작하는지 살펴봅시다. 위상 정렬을 스택이나 큐를 사용하여 구현할 수 있지만 큐를 사..

알고리즘/이론 2020. 8. 27. 00:17
[C++] stl container set, multiset

이번 포스팅에서는 C++ stl container인 set과 mutiset에 대해서 알아보도록 하겠습니다. set set 은 데이터를 저장할 수 있는 container입니다. 가장 기본적인 container와 다른 점은 자동으로 정렬이 된다는 점입니다. 새로운 값이 삽입, 삭제 될 때마다 이 정렬 상태를 유지하고 있어야 하므로 set 은 기본적으로 binary search tree로 구현이 되어 있습니다. set 선언 set 을 사용하기 위해서는 헤더 파일을 포함해야합니다. #include 그 후에는 보통 container들과 마찬가지로 다음과 같이 선언할 수 있습니다. set 이름; int 자료형을 저장할 s라는 이름의 set을 만들기 위해서는 다음과 같이 선언해줍니다. set s; 선언 시, 어떠한 ..

알고리즘/C++ 2020. 4. 14. 17:22
[Algorithm] 불안정정렬 sort, 안정정렬 stable_sort

안정 정렬와 불안정 정렬 우선 안정정렬와불안정정렬이 무엇인지 알아봅시다. 안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬을 말하며 불안정정렬은 반대로 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있는 정렬입니다. 아래 그림을 보며 이해를 해봅시다. 기존의 숫자배열은 스페이스 7, 하트 5, 하트 2, 스페이스 5로 구성되어 있습니다. 이를 숫자에 대하여 오름차순으로 정렬한다고 생각해봅시다. 이 때 안정정렬을 하게 되면 앞에 존재하던 하트 5와 뒤에 존재하던 스페이스 5의 순서는 바뀌지않음이 보장됩니다. 반대로 불안정정렬을 보도록 하겠습니다. 이 경우에는 하트 5와 스페이스 5의 순서가 바뀌었지만 불안정이라고 해서 항상 바뀌는 것은 아닙니다. 바뀔 수 도 있고 바뀌지 않을 수 도 있습니다. C++의..

알고리즘/이론 2020. 3. 25. 21:20