동전 0문제인 11074번과 유사한 문제입니다만, 동전의 종류가 가장 작은 동전의 배수가 아닌 경우가 존재합니다. 이 경우에는 Greedy하게 풀 수 없습니다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std; int dp[10001], n, k;const int MAX = 987654321; int main() { scanf("%d %d", &n, &k); //모든 방법의 개수를 MAX개로 초기화해줍니다. for (int i = 1; i
ACM-ICPC 2017 Nationalwide Internet 예선에서 나왔던 문제입니다.나왔던 문제들 중 가장 쉬웠던 문제입니다. 문제는 피자박스가 다음과 같이 쌓여있을 때, 앞에서 본 모양과 옆에서 본 모양을 유지한 채로, 최대한 피자박스를 많이 치우면 몇 개나 치울 수 있는지를 찾는 것입니다. 단, 피자박스의 높이는 모두 유일하다고 문제에 나와있습니다. 이 부분을 주의해서 읽지 않으면 피자박스의 높이가 같을 때 예외처리를 해야한다는 생각에 시간을 날릴 수 있습니다. The boxes are stacked in piles, forming a three- dimensional grid where the heights are all different. 해법은, Side에서 관찰할 때 가장 높은 피자박스..
이 문제는 BFS(너비 우선 탐색)을 이용한 풀이입니다. 약간의 memoization도 포함되어 있습니다. 보통 아시기엔, BFS는 그래프 위에서 사용하는 것이라고 알고 있습니다. 그래프가 없는데 BFS를 어떻게 사용해야 할까요? 풀이는 다음과 같습니다. 주는 상태에 따라 그래프를 생성하면 되는 것입니다. 인접행렬이 아닌 Vertex와 Vertex의 연결 관계를요! 자 그럼 예제를 통해 방법을 소개하겠습니다.예제 입력 복사5 17 예제는 5에서 출발할 때, 17을 찾는 가장 빠른 방법을 물어보고 있습니다. 5에서 출발하니 처음 정점을 다음과 같이 생성합니다. 4초가 걸려서 17로 이동할 수 있었습니다 ! 다른 간선들도 그려보면 좋지만, 그래프가 너무 복잡해져서 그리지 않았습니다. 이 그래프는 인접행렬이나..
대표적인 분할 정복 문제입니다. 3^n by 3^n으로 이루어진 타일 중, 3^a by 3^a (a= 1,2,3,4. ..)로 이루어진 타일이 몇 개가 있는지 세어보는 문제입니다. 분할정복 문제는 대부분 재귀호출로 해결해야 합니다. 이에 대한 구체적인 알고리즘은 예제로 알려드리도록 하겠습니다. 처음엔, 파란색 네모의 모든 칸을 조사해서 같은 색깔인지 판단합니다. 당연히 아니니, 멈추지 않고 다음 단계로 넘어갑니다. 다음 단계는 파란색 네모를 9개의 칸으로 나눈 다음, 각 칸에 대한 문제를 해결합니다. 각 빨간색 네모에 대해, 문제를 해결해 봤더니 6개의 종이를 얻었습니다. (3 by 3 size 종이 6개)-1로 채워진 종이는 1개, 1로 채워진 종이는 2개0으로 채워진 종이는 3개 입니다. 찾은 종이는..
말 그대로 수를 정렬하는 문제입니다. 문제의 조건을 잘 읽어보면, N이 10,000,000이라 O(NlgN)의 정렬 방법을 사용하면 시간 안에 풀 수 있을거라는 추측을 할 수 있습니다. 하지만, 문제의 메모리 사용 조건이 8MB이기에, 1000만개의 수를 모두 배열 안에 저장할 수는 없습니다. 그럼 어떤 방법을 생각할 수 있을까요? 문제에서 제시하는 수의 범위를 유심히 살펴봐야 합니다. 입력이 1000만개가 주어지는데, 입력으로 주어지는 수는 1부터 1만까지밖에 없습니다. 1만개를 초과하는 수가 입력으로 주어지면, 비둘기 집의 원리(서랍원리?)에 의해 반드시 중복이 존재할 수 밖에 없습니다. 따라서, 모든 수를 배열에 저장하는게 아닌수의 개수를 길이가 10000인 배열에 저장하면 됩니다. 입력이 종료된 ..
이 문제는, N개의 지형 높이가 주어졌을 때,오르막길의 최대 높이 차이를 찾는 문제입니다. 해결 방법은 간단합니다. 저는 2가지 변수를 처음과 끝을 가리키는 화살표처럼 사용해 문제를 해결했습니다. 처음에 first와 last는 동일하게 arr[0]입니다. 예제를 통해 진행을 알아볼까요 8 12 20 1 3 4 4 11 1입력이 다음과 같이 주어집니다.for문을 통해 다음 원소가, 현재 last가 가리키고 있는 원소보다 크지 않을때까지 진행합니다.```1) first = 12, last = 12 - 12 < 20? TRUE2) first = 12, last = 20 - 20 < 1? FALSE 2-1) answer = max(answer, last-first);3) first = 1, last = 1.....
2016년 ACM-ICPC 한국 인터넷 예선 D번 문제였던 Message Passing 입니다. 규칙을 찾고, 길이가 몇차든, 항이 M개인 선형 점화식의 N번째 항을 O(M^3 logN)에 구하는 방법을 알고 있다면 풀 수 있는 문제였습니다. 문제에 쓰여 있는규칙을 n=2, n=3일때 몇 번 나열해본다면, 위의 규칙은 모두 피보나치 수열과 유사한 형태의 규칙을 띈다고 생각하시면 됩니다. 위의 규칙을 깨달았다면?문제의 70%는 해결 되었습니다. 이 문제를 설명하기 위해선 여러가지 문제를 거쳐야 합니다.먼저 BOJ 2749번 피보나치 수 3문제입니다. 이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,..
아주 유명한 분할 정복 문제입니다. Stack을 사용해서 풀 수 있는 문제이기도 하지만, 문제 테마가 분할정복이니 분할정복을 이용한 풀이로만 소개하겠습니다. 분할 정복 (Divide and Conquer)이란?문제를 같은 속성을 지닌 부분 문제로 쪼개서 각개격파 하는 방법으로, BruteForce(모든 경우의 수를 다 탐색하는 방법)로 푸는 것 보다 일반적으로 매우 빠릅니다. 그럼 이 문제는 어떻게 분할 정복을 해야할까요? 분할 정복을 사용할 부분 문제를 찾기 위해서는, 먼저 가장 큰 문제를 봐야합니다. 가장 큰 문제는 무엇일까요? "입력으로 주어진 히스토그램에서, 가장 큰 직사각형을 구하는 프로그램을 작성하시오" 입니다. 결국 우리가 풀어야 할 문제는 [0,n) 사이의 히스토그램에서 최대 넓이의 직사각..
주어진 수열에서, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 알고리즘 문제를 많이 접해 보지 못했던 사람들은, 이 문제를 보면 이걸 다이나믹 프로그래밍 풀어야지 하는 생각을 한번에 떠올리기란 쉽지 않습니다.보통 이러한 문제는 모든 경우의 수를 다 따져볼 수 있는 방법으로부터 접근하곤 합니다. 예제를 볼까요? 예제로 주어진 수열의 길이는 6이고, 주어진 수열은 {10, 20, 10, 30, 20, 50} 입니다. 이 수열에서 존재하는 부분 수열의 개수는 아무것도 없는 수열(공수열이라고 하겠습니다.)을 제외하고 6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6으로 이항정리에 의해 2^5-1 = 31개입니다. Brutforce로 해결하면, 총 2의 n-1승개의 부분수열이 존재하고,..
@markdownACM-ICPC 2016년 대한민국 인터넷 예선에 출제되었던 문제입니다. Q-Index라는 개념을 이용해 문제를 푸는 것이었는데요. 번역문보다 원문을 보는게 이해가 빠른 문제라 푸는데 조금 시간이 걸렸던 문제입니다. 문제를 해설해보면 "Q 인덱스가 k이다" 라는 말은 " n개중에 k개의 논문이 k번 이상 인용되었고 n-k의 논문이 k번 미만 인용되었다." 라는 의미입니다. 논문의 개수와 인용회수의 범위를 살펴보면,논문의 개수 n은 1 이상 1000이하,논문의 인용 회수(편의상 m)은 0이상 10000이하 라고 되어있습니다. 제가 생각하는 간단한 문제 풀이 방법은, 논문의 인용 횟수를 통해, 존재하는 논문을 전부 탐색해서, q-index의 최대값을 구하는 방법입니다. Psuedo Code를..