지속 가능한 꾸준함

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 본 문제의 제목은 LCS(Longest Common Subsequence)입니다. 이름만 봐도 유명한 문제라는 느낌이 들어 서칭을 바로 해보았습니다. 역시나 유명한 문제였습니다. LCS는 Longest Common Substring과 Longest Common Subsequence이 존재합니다. 2개는 다른 의미를 가지므로 구분해야합니다. 차이점은 공통되는 부분의 연..

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 본 문제는 동전들이 주어지고, 각각의 동전에 대한 가치(원으로 생각)가 주어집니다. 그리고, 이 동전으로 k 원을 만들어낼 수 있는지, 만들어낼 수 있다면 주어진 동전을 최소 몇개를 써야 k원을 만들어낼 수 있는지를 묻는 문제입니다. k원을 주어진 동전을 최소로 사용하여 만들기 위해서는 k원보다 작은 금액들을 먼저 최소로 사용하여 만들 수 있어야 합니다. 어떤 문제를 작은 문제..

평소 관심있던 기업에 운좋게 서류를 통과하여 코딩테스트를 볼 수 있었다. 주어진 문제는 3문제였고 2시간내로 풀어야했다. 첫번째 문제는 Problem Solving 세계에서 유명한 문제였기에 금방 풀어낼 수 있었다. 두번째 문제와 세번째 문제가 정말 문제였다. 세번째 문제는 도저히 시간내에 못풀겠다 싶어 두번째 문제를 풀었는데 효율성 테스트를 한 케이스도 통과하지 못했다. 사유는 시간초과였다. 반복문을 조금이라도 줄일 수 있는 경우를 생각하여 시도해보긴 했는데 결국 실패로 끝났다. 테스트를 마치고 다시 한 번 진득히 복기의 시간을 가져보았다. 이번이 인생 3번째 코딩테스트였는데 복기를 하는 건 처음이였다. 복기를 하다보니 뭐를 놓쳤는지 생각이 들기 시작했다. 문제를 풂에 있어 탐색 알고리즘이 요구되는 문..