byunjaewoo의 PS 블로그

337점으로 1등했다. ^ㅗ^25737 ARC 183 E 24438 34581 로 구성된 셋이었다.0:00 ~ 0:36 (0 0 0 0)1번부터 4번까지 문제를 읽었다. 1번은 왕자구 문제, 2번은 이상한 문제, 3번은 적당한 인터랙티브 문제, 4번은 조건 잘 분석하면 쉬워지는 문제처럼 보였다. 1번부터 건드려봤는데, 생각보다 복잡하고 섭테에서부터 구간 cht 같은 걸 써야 해서 어려운 문제라고 판단하고 2번으로 갔다. 2번에서는 인접한 두 개만 바꿀 수 있는 것이 아니라 아무 두 개나 바꿀 수 있는 것으로 문제를 잘못 읽어서 짧은 풀이를 냈고, 당연히 0점을 받았다. 문제를 다시 읽고 잘못 읽었음을 깨닫고 슬펐다.0:36 ~ 1:09 (0 0 100 0)2번을 다시 보니 잘 모르겠어서 3번으로 넘어갔다..

동적 계획법(DP, Dynamic Programming)이 카테고리 전체에서 다루게 될 동적 계획법 알고리즘이다. 동적 계획법은 solved.ac 태그 기준 3번째로 많은 문제량을 차지하고 있다. 그만큼 다양한 변형과 최적화 방법이 존재하고, 중요한 알고리즘이라고 볼 수 있다. 앞으로 줄여서 그냥 DP라고 하겠다.알고리즘DP의 기본적인 철학은 “작은 문제에서 계산한 값을 이용해 큰 문제의 답을 구한다”는 것이다. 많은 글들에서 피보나치 수열을 예시로 들고 있는데, 이 글에서도 피보나치 수열을 통해 생각해보자.피보나치 수열피보나치 수열은 다음과 같은 점화식으로 정의되는 수열이다:$F_n = F_{n-1}+F_{n-2}, F_0=0, F_1=1$ 점화식이 주어졌기 때문에, $F_{n-1}$와 $F_{n-2}..

정렬(Sorting)자료를 정렬해서 저장하는 것은 꽤 중요하다. 몇 가지 이유가 있는데, 하나는 전 글의 주제였던 이분 탐색을 하기 용이하기 때문이라는 것이고, 그밖에도 그냥 정렬된 자료 자체가 필요할 때가 많다. 본 글에서는 다양한 정렬 방법에 대해 알아보겠다. 두 원소를 비교하는 것은 $O(1)$ 시간복잡도라고 가정한다. 비교 기반 정렬의 경우 시간복잡도에 비교 시간복잡도를 곱해주면 된다. 또한 주어진 자료 $A[1...N]$를 오름차순으로 정렬한다고 가정한다. 내림차순은 오름차순과 본질적으로 동일하다.$O(N^2)$ 시간복잡도 정렬가장 기초적인 정렬 방법들은 시간복잡도가 대체로 최악의 경우 $O(N^2)$이다. 세 가지 알고리즘에 대해 알아보겠다.버블 정렬(Bubble Sort)인접한 두 원소의 대..

이분 탐색(Binary Search)탐색 방법의 기반이 되는 이분 탐색이다. 이분 탐색은 분할 정복 알고리즘의 대표적 활용으로, 같은 글에서 다룰 수도 있었지만 꽤나 중요도가 높다고 생각해 따로 글을 썼다. 자료에 따라 이진 탐색, 이진 검색이라고 부르는 경우도 있다.알고리즘이분 탐색은 기본적으로 정렬된 배열 상에서 특정 원소를 찾는 알고리즘이다. 오름차순으로 정렬된 배열 $A[1 \ldots N]$에서 특정 원소 $X$를 찾는다고 할 때, 다음과 같이 동작한다.처음에는 탐색 구간을 $[1, N]$으로 설정한다.현재 탐색 구간을 $[s, e]$라고 할 때, $m=[(s+e)/2]$라 하고 $A[m]$과 $X$를 비교한다.$A[m]$이 $X$보다 작은 경우, 탐색 구간은 $[m+1, e]$가 되고 다시 2..

분할 정복(DnC, Divide and Conquer)분할 정복은 굉장히 많은 알고리즘이나 자료구조의 기원이 되는 기본적인 알고리즘으로, 직접적으로 사용할 때가 꽤나 있다. 또한 시간복잡도에 붙는 $\log$는 분할 정복적인 발상으로부터 나오는 경우가 많다. 본 글에서는 분할정복 알고리즘과 예시들에 대해 알아보겠다.알고리즘분할 정복의 기본적인 철학은 큰 문제를 작은 문제들로 나눠(분할) 해결하고 그 답들을 합치는(정복) 것이다. 일반적으로 분할 과정과 정복 과정으로 이루어지고, 정복 과정은 생략되는 경우도 있다. 다음 예시를 통해 분할 정복 알고리즘이 어떤 식으로 동작하는지 알아보자.최대 부분합 문제문제 상황은 BOJ 10211와 같지만, 배열의 크기 $N$이 더 클 때 분할 정복을 이용해 문제를 해결해..

완전 탐색(Brute Force)무차별 탐색이라고도 하며, 가능한 모든 경우를 시도해보는 알고리즘이다. 사실 알고리즘이라고 보기도 뭐하고, 그냥 간단하게 생각할 수 있다. 물론 단순한 만큼 시간 복잡도가 크다는 단점이 있고, 실제 문제 상황에서 많이 쓰지는 않는다. 그럼에도 제한이 작거나 간단한 문제들은 완전 탐색만으로도 풀리는 경우가 많고, 어려운 문제들에서 Naive 솔루션으로 규칙을 찾거나 서브태스크를 풀 때 사용되기도 한다.본 글에서는 시간 복잡도의 정의, 완전 탐색의 간단한 예시와 활용에 대해 다루려고 한다.시간 복잡도(Time Complexity)시간 복잡도란 프로그램의 입력값과 수행 시간의 상관관계를 나타내는 척도이다.for(int i=1; i 가령 위와 같은 프로그램은 $n$에 비례하는 연..

CP(Competitive Programming), 혹은 PS(Problem Solving)에서 알고리즘을 제대로 아는 것이 얼마나 중요할까? 사실 정보올림피아드가 수학, 물리 등 다른 분야에 비해 공부해야 하는 내용은 적다고 생각한다. 처음 C언어 문법을 공부한지 오래 지나지 않아 국가대표 급의 실력을 가지게 되는 경우를 적지 않게 볼 수 있기 때문이다. 그렇지만 처음 공부할 때 알고리즘을 제대로 배우는 것은 어려운 문제들을 풀 때 필요한 직관을 가지는 것에 좋은 영향을 줄 수 있다. 또한 문제를 풀면서 다양한 테크닉을 사용하는 경우가 많은데, 몇몇은 사전지식으로 알지 못하면 떠올리기 굉장히 어려운 경우도 많다. 따라서 이 카테고리의 글에서는 각 알고리즘을 기초부터 시작해서 활용하는 방법, 그들만의 웰..

0. 서론완전 탐색분할 정복이분 탐색정렬그리디순열, 조합페르마 소정리그래프깊이 우선 탐색너비 우선 탐색트리백트래킹동적 계획법에라토스테네스의 체투 포인터비트필드 DP연결 리스트스택, 큐, 덱셋, 맵비트셋우선순위 큐다익스트라플로이드-워셜밸만 포드, SPFA위상 정렬이진 탐색 트리균형 잡힌 이진 탐색 트리함수형 그래프, 순열 사이클 분할오일러 피함수중국인의 나머지 정리유클리드 호제법, 확장 유클리드 호제법분리 집합최소 신장 트리누적합, 차분 배열좌표 압축세그먼트 트리펜윅 트리희소 배열느리게 갱신되는 세그먼트 트리스위핑자료 구조를 이용한 DP 최적화(셋, 세그, 덱)삼분 탐색중간에서 만나기KMP매내쳐라빈 카프 해시트라이접미사 배열, 최장 공통 접두사 배열아호-코라식Z오일러 경로조화수오일러 지표생성 함수밀러 라..