이 험난한 세상에서어어~

문제 설명 n+1 만큼의 정수를 포함하고 있는 정수형 배열 nums가 있다. 이때 각 정수의 범위는 [1, n] 까지이다. 해당 배열에서 오로지 하나의 정수만 반복이 된다고 할 때, 반복이 되는 정수를 찾아서 반환하라. 이때 배열을 복사해서도 안 되고 정해진(고정된) 추가 공간만 사용하라. https://leetcode.com/problems/find-the-duplicate-number/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledg..

문제 설명 길이가 N인 계단 수열의 수를 구하는 문제인데, 이때 0부터 9까지의 숫자가 모두 한 번 이상 등장해야 한다. 이때 0으로 시작하는 수는 계단수가 아니다. https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 첫 번째 접근 DP 문제이기 때문에 처음에는 직접 손으로 풀어 써봤다. 이때 계단수의 규칙을 발견했는데, 0혹은 9의 옆 자리에는 1과 8밖에 오지 못한다는 점이다. 일단 0의 경우에는 0과 x를 빼서 절댓값이 1이 되는 경우가 1혹은 -1인데, -1은 오지 못하니 1밖에 없다. 9 또한 10과 8이 있지만, 10은 고려 사항이 아니니 8밖에 오..

LCS란? 부분 수열 LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 제일 긴 것을 의미한다. 예를 들어서 abcf와 aebwcd가 있다고 생각해 보자. 그렇다면 여기서 나오는 LCS는 abc이다. abcf aebwcd 위의 굵게 표시된 문자들을 보면 알 수 있을 텐데, 공통 부분 수열은 굳이 문자들의 한 번에 이어질 필요가 없다. 공통된 문자가 얼마나 길게 차례대로 나오느냐를 따지는 문제이기 때문이다. 최장 공통 부분 수열 이제 최장 공통 부분 수열을 구하는 방법을 알아보자. 그러기 전에 아래의 유튜브 비디오를 보고 오는 것을 추천한다. 현재 글도 아래 동영상을 기반으로 작성한 것이다. https://www.youtube.com/watch?v=sSno9rV8Rhg LCS의 ..

간단한 소개 다이나믹 프로그래밍이란 단순하게 말해서 이전에 생성한 값을 가져다가 쓰는 것을 의미한다. 예를 들어서 1과 2만을 가지고 N이라는 숫자를 만든다고 생각해보자. 이때 N이 3이라면 '1+1+1', '1+2', '2+1'이라는 경우의 수가 나올 것이다. N이 4라면 어떻게 될까. '1+1+1+1', '1+2+1', '2+1+1', '1+1+2', '2+2'이라는 경우의 수가 나온다. 이렇게 일일히 세줄 수도 있지만 N이 1억일 경우에는 그 연산의 횟수가 너무 커져 시간이 많이 걸린다. 바로 이럴 때 동적 계획을 이용하면 연산 횟수를 줄이면서 빠르게 문제를 해결할 수 있다. 위의 문제를 동적 계획으로 푸는 방법을 소개한다. N = 1 '1' -> 1개 N =2 '1+1', '2' -> 2개 N =..