Beelog

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제는 위와 같으며 이 문제의 경우 각각의 숫자를 앞에 있는 숫자들과 순차적으로 비교하며 앞에 존재하는 수보다 큰 경우 앞 수까지 존재하는 수열의 개수 + 1 한 값을 현재 자신의 값과 비교하여 더 큰 경우를 선택하도록 하여 해결할 수 있습니다. 그림으로 살펴보면 다음과 같습니다. 일단 각각의 숫자들은 자기 자신 수 하나로 수열을 이..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제는 위와 같으며 이 문제는 배낭의 무게가 0 ~ K 인 경우를 모두 확인하는 방식으로 문제를 풀 수 있습니다. 예제를 바탕으로 살펴보면 처음에는 0부터 7까지 모두 가치가 0인 배열로 초기화를 하고 이후 무게(w)와 가치(v)가 주어지면 w 보다 작은 무게의 경우는 기존 가치를 그대로 가져가고 w 보다 크거나 같을 때는 w 를 뺀 무게의 가치..

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제는 위와 같으며 이 문제의 경우 작은 단위로 쪼개다 보면 피보나치 수열의 규칙을 따른다는 것을 알 수 있습니다. n 의 크기를 가지는 타일의 조합은 (n - 1) 크기의 타일에 1을 추가하거나 (n - 2) 크기의 타일에 00을 추가하는 방법 밖에 없기 때문에 이를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] 로 피보나치 수열과 일치합니다. 수열을 직접 반환하는 것이 아닌 만들 수 있..

www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net 문제는 위와 같으며, 이 문제의 경우 비트 마스크를 써서 문제를 해결할 수 있습니다. 비트 마스크 알고리즘은 정수의 이진수 표현을 자료구조로 활용하는 방식으로, 숫자를 자리수로 하여 해당 숫자가 포함이 되면 숫자와 같은 자리수를 1로 하고 포함하지 않는 경우는 0으로 하여 빠르게 계산할 수 있는 방식입니다. 위 문제에서는 알파벳을 모두 포함하는지 확인해야 하기 때문에 알파벳 26자리를 비트 마스크로 표현하면 다음과 같습니..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제는 위와 같으며, 이 문제의 경우 위상 정렬에 대해 알고있다면 쉽게 문제를 해결할 수 있습니다. 위상 정렬(Topology Sort) 란, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주기 위해 사용하는 알고리즘입니다. 만약 위와 같은 순서대로 일이 진행되어야 한다면, 순서대로 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이런 순서대로 진행을 하..