본문 바로가기

Algorithm

 (151)
232. Interactive 일곱 번째로 인터랙티브(Interactive)에 대해서 다룬다. 형용사 'Interactive'는 '상호 작용의'라는 의미를 가지며 이를 알고리즘 문제에 적용하면 인터랙티브 문제는 상호 작용을 하는 문제라고 생각할 수 있다. 그렇다면 당연히 무엇과 무엇이 상호 작용을 하는지 알아야 할 것이다. 알고리즘 문제에서 상호 작용을 하는 대상은 사용자의 프로그램과 테스트 데이터인데, 이 상호 작용을 위해 인터랙터(Interactor)라는 종류의 파일이 존재한다. 인터랙터는 초기 데이터를 프로그램에 입력하거나, 프로그램이 출력한 쿼리의 결과를 전달하는 등의 역할을 수행한다. 이를 통해 인터랙티브 문제의 특징을 몇 가지 파악할 수 있다.인터랙터가 존재한다.입력되는 값이 사용자 프로그램의 출력에 따라 달라질 수 있다...
231. Ad-Hoc 여섯 번째로 애드 혹(Ad-Hoc)에 대해서 다룬다. 애드 혹은 굉장히 정의하기 어려운 용어인데, 이름이 '애드 혹'인 어떤 알고리즘이 존재하는 게 아니라 그 문제를 풀기 위해 필요한 일반적인 자료 구조나 알고리즘 지식이 존재하지 않고 그 문제만을 풀기 위한 방법을 필요로 할 경우 그런 문제를 애드 혹 성격의 문제라고 한다. 따라서 사람마다 체감 난이도가 매우 큰 차이를 보일 가능성이 다른 유형의 문제들에 비해 높고, 어떤 문제들은 애드 혹에 속하는지를 두고도 의견이 갈리기 쉽다. 그밖에 '풀이가 간단하다'와 '문제가 쉽다'의 차이를 잘 느낄 수 있는 유형이기도 하다. 이런 문제들은 관찰이나 증명이 문제 풀이의 대부분일 가능성이 높다. 증명을 하지 않고 찍어 맞추기(Proof By AC, PBA)를 시..
230. Randomization 다섯 번째로 무작위화(Randomization)에 대해서 알아본다. 무작위화는 쉽게 설명하면 풀이 중간에 무언가를 선택하는 상황이 있을 때 그것을 정해진 규칙에 따라 하지 않고 무작위로 하는 것이다. 이때 무작위로 선택한 대상으로 문제를 풀면 틀릴 확률이 유의미하게 작아야 한다. 아래의 문제를 예시로 들어 보자. BOJ 2912. PATULJCI (Platinum II) 길이가 $N$인 수열이 주어진다. 이때 $A$번째 ~ $B$번째 원소로 이루어진 구간에 절반 넘게 등장하는 원소가 존재하는지 확인하는 쿼리를 $M$번 처리하라.$N$은 $3 \times 10^5$, $M \le 10^4$이므로 나이브 풀이는 시간 안에 통과할 가능성이 거의 없다. 여기서 무작위화를 사용하면 다음과 같은 풀이를 낼 수가 ..
229. Precomputation 네 번째로 전처리(Precomputation)에 대해서 알아본다. 전처리는 프로그램 실행 중(Runtime)에 구해야 하는 값을 실행 중에 구하는 대신 코드로 직접 넣어서 컴파일 단계(Compile Time)에 구하게 하는 방법이다. 구해야 하는 값의 수는 많지 않은데 구하는 데 오래 걸리는 값들을 보통 전처리해서 사용하며, 제곱근 분할법의 아이디어를 이용하면 구해야 하는 값의 수가 많고 각 값이 이전 몇 개의 값에 의해서만 결정될 때 일부 간격 단위로 값을 전처리하는 방식으로 구해야 하는 범위 전체를 커버할 수도 있다. (그렇게 풀리는 문제가 연습문제에도 있다.) 아래 문제를 예시로 들어 살펴보자. BOJ 6794. What is n, Daddy? (Bronze III)$n$이 주어졌을 때, $n$을 ..
228. Constructive 세 번째로 살펴볼 것은 구성적(Constructive) 알고리즘이다. 이 이름은 다른 알고리즘 이름들과 비교하면 약간 다른 특징이 있는데, 이름이 알고리즘 자체를 나타내기보다는 알고리즘의 성격을 드러낸다는 것이다. 즉 문제에서 조건이 주어지고 그 조건에 맞는 해(Solution)를 찾아내는 과정을 통틀어 구성적 알고리즘이라고 한다. 따라서 이 알고리즘의 정해진 절차는 없으며 때때로 증명조차 하지 않는다. 단어 '구성적'이 그렇게 친절한 단어는 아니지만, 편의상 이 블로그에서는 그런 것에 신경쓰지 않는다. 이 알고리즘에 정해진 절차가 없다고 했지만, 일반적으로 이런 종류의 문제를 풀 때 잘 통하는 전략과 주의사항은 존재한다.기저 사례가 있고 재귀적으로 해를 구성할 수 있는 형태인지 확인한다. (특히 트리나..
227. Case Work 두 번째로 케이스워크(Case Work)에 대해서 살펴보기로 한다. 케이스워크라는 단어는 PS를 오랫동안 했다면 별다른 어색함 없이 받아들이기 쉽지만, 자세히 생각해 보면 꽤 묘한 단어이다. 먼저 케이스(Case)는 직관적으로 번역할 수 있다. 여러 가지 경우를 말하는 것이다. 다음으로 워크(Work)의 간단한 번역 중 가장 나은 것은 '처리'라고 할 수 있다. 즉 케이스워크를 풀어서 설명하면 여러 가지 경우를 처리하는 것이 된다. 그러면 '여러 가지 경우'가 어느 정도를 의미하는지 생각해 보자. '여러 가지'는 추상적인 단어이기 때문에 이것을 모든 사람이 동일하게 받아들이도록 정의할 수는 없다. 대신 다수의 사람들이 동의할 만한 기준을 세울 수는 있다. 예를 들어 이런 문제가 케이스워크에 해당하는지 묻..
226. Offline Query 이제부터는 익숙해져야 하는 $7$가지 주제를 차례로 소개하려고 한다. 이 주제들은 대회나 코딩 테스트를 가리지 않고 언제든지 등장할 수 있으며 어떤 유형의 문제와도 결합이 가능하다.그중에서 첫 번째로 살펴볼 유형은 오프라인 쿼리이다. 그러면 먼저 쿼리가 무엇인지부터 살펴보자. 알고리즘 문제에서 쿼리(Query)는 데이터에 행해지는 반복되는 연산을 의미한다. 이때 데이터는 그래프, 집합, 선형 등 특정한 형태를 가지며 여러 값이 아닌 정수나 실수 하나의 형태로도 존재할 수 있다. 또한 연산은 종류에 따라 추가(Create), 조회(Read), 수정(Update), 삭제(Delete) 등으로 구분할 수 있다. 넓은 의미에서 SQL의 쿼리와 유사한 측면도 있으나 실제 데이터베이스를 건드리는 것이 아니기 때문에..
213. IMOS Method 펜윅 트리를 설명하면서 연습문제로 수열과 쿼리 21을 소개했다. 그리고 문제 해설에 구간 업데이트 + 점 쿼리를 점 업데이트 + 구간 쿼리로 변형할 수 있다고 했는데, 이 아이디어를 정형화한 IMOS법(IMOS Method)에 대해서 알아보기로 한다. IMOS법은 구간을 시작점과 끝점으로 분리하여 구간 처리를 점 처리로 대체하는 트릭으로, 구간이 여러 개 주어지고 특정 시점을 포함하는 구간의 수를 빠르게 구할 수 있는 방법이다. 수식을 써서 표현하면 다음과 같이 나타낼 수 있다.구간 $n$개가 존재하며, $i$번째 구간을 $[l_i, r_i]$로 나타낼 수 있다. $(l_i \le r_i)$$k$를 포함하는 구간의 수를 구하는 쿼리가 주어진다.여기서는 $l_i$와 $r_i$가 모두 $1$ 이상 $2n$ ..

티스토리툴바