목록알고리즘 (9)

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

[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
[python] 파이썬의 정렬, Tim Sort

Tim Sort python에서의 정렬 함수 sorted()와 list.sort()에 사용된 정렬 알고리즘은 Timsort, 팀정렬입니다. 팀정렬은 파이썬 핵심 개발자인 팀 피터스에 의해서 Cpython에서 처음으로 구현되었으며 2009년 이후 표준 자바 및 안드로이드, swift 등 여러 언어에서 사용되고 있습니다. 이는 데이터의 정렬된 정도에 따라 삽입정렬과 병합정렬 사이를 전환하는 적응형 알고리즘입니다. 두 정렬방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 병합정렬에 비해 적은 추가메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘입니다. 알고리즘의 원리 위에서 언급했듯이 팀정렬은 삽입정렬과 병합정렬을 함께 사용하고 있습니다. 병합정렬은 추가적인 메..

프로그래밍 언어/Python 2020. 6. 3. 03:20
[Algorithm] 불안정정렬 sort, 안정정렬 stable_sort

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

알고리즘/이론 2020. 3. 25. 21:20
[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011)

문제보러가기 8901번: 화학 제품 문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다. www.acmicpc.net 입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다. bc 혼합물의 수를 0 부터 ..

알고리즘/C++ 2019. 8. 2. 21:10
[C++] BAEKJOON 8895번 막대배치(ACM-ICPC Daejeon 2012)

문제보러가기 8895번: 막대 배치 문제 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. 위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만 www.acmicpc.net 동적계획법을 사용한 문제였습니다. 먼저 점화식을 세워보도록 하겠습니다. dp[n][l][r] 를 n 개의 막대에 대해, 왼쪽에서 보이는 막대가 l 개, 오른쪽에서 보이는 막대가 r 개인 경..

알고리즘/C++ 2019. 7. 31. 16:54