크루저의 쉼터

오늘은 수학 문제들로 준비해봤다. 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net 11051번 이항 계수 2 문제는 DP를 적용할 수 있는 문제다. 문제에서는 (N, K) % 10007을 요구하고 있다. 하지만 우리가 알고 있는 공식 (N, K) = N! / K!(N-K..

오늘 문제 1541번은 보통 난이도를 가진 그리디 알고리즘 문제이다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제를 접근하는 방법은 간단하다. 처음 "-"의 위치를 기준으로, 이전에 나타나는 숫자는 더하고, 이후에 나타나는 숫자는 빼면 된다. 다만 C++ 구현에서 입력을 어떻게 처리해야 할지에 대해 고민하는데 시간이 많이 소요됐다. scanf로 전체 스트링을 받는 다음 strtok를 이용하는 방법, 또는 stringstream, sprintf를 활용하는 방법을 생각했지만 코드가 복잡해졌다. 결론..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 오늘은 포도주를 시음해보자. 이 문제는 간단한 점화식으로 해결할 수 있다. DP배열[i]의 의미는 i번째 포도주까지 고려했을 때, 최대한 마실 수 있는 양을 의미하게 된다. 그러면 DP[i]는 3가지 경우에 의해 결정된다. 1) 포도주를 안마신다. ☞ DP[i-1] 2) 포도주를 마시되, 바로 이전 포도주도 마셨다. 그러면 i-2번째 포도주는 마시지 않은 것이다. ☞ 포도주[i] + 포도주[i-1] + DP[i-3] 3) 포도주를 마시되, 바로 이전 포도주를 마시..

이 문제는 DP로 해결할 수 있는 문제이다. 쉬운 문제였지만 나는 고민을 많이 했고, 몇 번 틀렸다. 나와 같은 분을 위해 이 글을 남긴다. 1. 나보다 작은놈 여기여기 붙어라! DP 배열을 arr, 입력받은 배열을 in이라고 하자. arr[i]는 in[0 ~ i]을 고려할 때, 마지막 숫자가 in[i]인 가장 긴 (증가하는) 부분 수열의 길이를 의미하도록 구현한다. 백준의 예제 입력을 예로 들면: Input: 6 10 20 10 30 20 50 DP Array: [1, 2, 1, 3, 2, 4] 2. 마지막 원소가 정답은 아니다. 1과 같이 구현하면 DP배열은 입력 배열 i번째 숫자가 마지막인, 가장 긴 부분 수열의 길이를 담게 된다. 그러므로 DP배열에서 가장 큰 값을 출력해야 한다.

2580번 스도쿠 문제는 전형적인 Backtracking 문제이다. 해결할 때에는 다음을 고려하자. 1. 조작하고, 되돌린다. 이는 Recursive 하다. backtracking의 과정을 tree로 생각하면, 각 노드는 3-4-... 와 같을 것이다. 여기서 4는 (3이 넣어진 상태에서) 다른 빈칸에 넣는 것이므로, 재귀적으로 구현하되, 각 재귀 호출 전과 후에 상태를 조작하고 되돌리는 코드를 작성한다. 2. 시간 초과를 위해 미리 계산한다. 어떤 숫자를 스도쿠 빈칸에 넣었을 때 그 결정이 적절함을 어떻게 확인할 수 있을까? 1차원적인 방법으로는 빈 위치에 숫자를 넣고, 그 위치에 해당하는 가로줄, 세로줄, 박스(3X3)에서 넣은 숫자가 중복되는지 확인할 수 있다. 하지만 이는 반복문의 연속이며, 모든..