전체 글

문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.      제한 사항      풀이문제를 요약하면 LCS를 구하는 것이다.LCS는 최장 공통 부분 수열을 의미한다. 최장 공통 부분 수열은 두 개의 문자열 혹은 배열에서 가장 긴 공통된 부분을 의미한다.예를 들어 보자.ACAYKP, CAPCAK 두 개의 문자열의 LCS는 ACAK이다. 그렇다면, 이를 어떻게 구해내는지 알아보자.LCS는 DP를 이용하여 간단하게 구해낼 수 있다.이차원 배열을 통해 메모이제이션을 한다.두 문자열의 각 위치를 비교하며 같을 때와 다..

문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.      제한 사항      풀이문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열을 뽑는다.그 길이와 요소를 출력해야 한다. 우선, 가장 긴 증가하는 부분 수열을 뽑는 과정은 다음과 같다.배열을 하나씩 탐색하며 해당 요소 이전에 나온 자신보다 작은 요소 중 가장 긴 부분 수열을 뽑은 뒤 자신을 추가하면 가장 긴 증가하는 부분 수열이 된다.예를 들어 보자.30을 탐색하는 과정에서 20은 [10, 20]으로 가장 긴 증가..

문제 설명색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 ..

문제 설명피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.      제한 사항      풀이피보나치 수열을 구하는 문제는 간단하다.설명에 나온대로 i-1, i-2를 더하면 된다. 하지만, 해당 문제에서는 N이 굉장히 크다.즉, $O(N)$만에 답을 구해도 시간초과라는 것이다. 해당 문..

문제 설명알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성..

문제 설명0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.1 ≤ i 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.      제한 사항      풀이문제를 요약하면, N의 각 자릿수를 K번 교환하여 만들 수 있는 최댓값을 구하는 문제이다. 처음에는 N의 각 자릿수를 정렬하여 최대한 비슷하게 만드는 방식으로 문제를 풀려했었다.k번의 교환을 통해 0번째부터 k번째 수를 확정해가면 된다 생각했다.하지만, 이 방법은 반만 정답이다.만약 k가 N의 자릿수보다 많다면 곤란해진다.따라서, 해당 방법이 아닌 다른 방법이 필요하다. k-1번째 교환에서 큰 수를 만들었다 하여도 k번째에 더 작아질 수 있다.반대..

문제 설명각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.각 공항들간 티켓가격과 이동시간이 주어질..