문제링크 18227 - 성대나라의 물탱크 문제 성대나라에는 각 도시별로 가뭄을 대비하기 위한 물탱크가 하나씩 존재한다. 이 물탱크들은 모두 연결되어있으며, 루트(성대나라의 수도)가 있는 트리의 형태를 가진다. 지금 성대나라는 물탱크의 물을 사용하여 가뭄을 버텨냈으나, 그 영향으로 모든 물탱크에 물이 비어버리고 말았다. 성대나라의 물관...

문제링크 12967 - pqr 문제 N개의 수로 이루어진 배열 A과 정수 K가 주어진다. 0 ≤ p < q < r < N 이면서, A[p] * A[q] * A[r]이 K로 나누어 떨어지는 (p, q, r) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 2,000,...

문제링크 1801 - 직사각형 만들기 문제 막대 N개를 가지고 있다. 이 막대를 이용해 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 막대는 이어 붙일 수 있고, 조각낼 수는 없다. 예를 들어, 길이가 2인 막대와 3인 막대를 합쳐 5인 막대를 만들 수 있다. 예를 들어, 가지고 있는 막대의 길이가...

문제링크 10806 - 최솟값 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은...

문제링크 2749 - 피보나치3 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1...

문제링크 1328 - 고층 빌딩 문제 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼...

서론 P와 NP를 처음 마주하는 전공생들은 대부분 어질어질함을 느낄 것이다. 이곳 저곳 찾아봐도 이해할 수 없는 이야기들, 뭔가 추상적이고 뭔가 이치에 맞지 않는 듯한 느낌 혹은 내가 그 단어를 이해할 수 없어서 무슨 말을 하고자 하는 것인지 모르는 느낌. 나도 그런 느낌을 겪어 본 터라, 이 글을 통해 P와 NP의 정의와 NP-Hard, 그리고 ...

문제링크 16565 - N포커 문제 정연이는 트럼프 카드 (Playing Card)로 할 수 있는 새로운 게임을 만들기로 결심했다. 우선 이 게임은 딜러와 플레이어가 1:1로 플레이한다. 그리고 플레이어는 놓여진 52장의 트럼프 카드에서 N장의 카드를 뽑는다. 뽑은 카드들로 "포카드 (four of a kind)" 족보를 만들 수 있...

문제링크 1102 - 발전소 문제 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지...

문제링크 3954 - Brainf**k 인터프리터 문제 Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오. 무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다. Brainf**k 인터프리터는 정수를 담는 하나의 배열(unsigned 8-...