문제https://www.acmicpc.net/problem/15650 시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하..
문제 시간 제한메모리 제한solved.ac 티어1초256MB골드 3풀이이번에도 밀린 문제 정리하기다. 저번에는 두 용액이었지만, 이번엔 세 용액이다. 두 용액에 대한 문제는 다음 글을 참고하자.https://codejin.tistory.com/270 백준 2470번 C++ 풀이문제https://www.acmicpc.net/problem/2470 시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이밀린 문제 정리하기 2탄이다. 이번 문제는 투포인터 문제이다. 직관적으로 떠올릴 수 있는 방법은 중첩반복codejin.tistory.com 용액이 세개로 늘어났다고 해서 쫄 필요가 없다. 이 문제도 투포인터로 풀이가 가능하다. 이 문제를 브루트포스로 푼다면 O(N^3)이 나올 것이다. 5000^3은 ..
문제https://www.acmicpc.net/problem/2470 시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이이번에도 밀린 문제 정리하기이다. 이번 문제는 투포인터 문제이다. 직관적으로 떠올릴 수 있는 방법은 중첩반복문을 통해 브루트포스를 하는 것이지만, 시간복잡도가 O(N^2)가 나오고, N은 최대 10만이기 때문에 불가능한 방법이다. 따라서 투포인터를 통해 O(N)의 시간복잡도로 탐색하면 될 것이다. 용액의 특성값을 오름차순으로 정렬하고, 포인터를 각각 맨 앞과 맨 뒤에 둔다. 입력은 세가지 경우로 나뉜다. 모두 양수인 경우모두 음수인 경우음수 양수 섞인 경우어떻던 간에 모두 양수라면 오른쪽 포인터(맨 뒤에 있던 포인터)를 왼쪽으로 당겨올수록 0에 가까워 질 것이고, 모두 음..
문제https://www.acmicpc.net/problem/1019시간 제한메모리 제한solved.ac 티어2초128MB플래티넘 5풀이밀린 문제 정리하기의 첫 단추를 끼울 문제이다. 이 문제는 사실 알고리즘이라기보단 수학적인 규칙을 찾는 문제에 가까웠다. 아는 지인이 이걸 풀었길래 나도 시도해봤다가 며칠동안 고민했던 문제이다. 이 문제를 이해하기 위해 예제를 하나씩 분석해보자. 예제입력 2부터 보자. 입력이 7이다. 페이지를 나열하면 다음과 같을 것이다.1, 2, 3, 4, 5, 6, 71~7까지 모두 1번씩 나왔기 때문에 답은 0 1 1 1 1 1 1 1 0 0이 될 것이다. 여기까지만 보면 잘 모르겠다. 예제입력 3을 보자. 입력은 19이다. 나열해보면1, 2, 3, 4, 5, 6, 7, 8, 9,..
문제https://www.acmicpc.net/problem/16953시간 제한메모리 제한solved.ac 티어2초512MB실버 2 풀이1이 문제는 정말 생각할 수 있는 부분이 많은 좋은 문제라고 생각한다. 일단 문제를 보고 바로 든 생각은 그래프 문제구나 싶었다. 실제로 두 과정을 통해 a를 b로 만드는 최소 연산 횟수 + 1(a에서 b로 이동하는 최단경로)을 구하는 것이기 때문이다. a, b의 최댓값이 10^9로 약 2^30에 근접하고, 두 연산이 모두 곱하거나(2x), 곱하고 더하는 연산(10x + 1)이기 때문에 아무리 큰 케이스를 주더라도 연산은 30번에 근접할 것이다. 그리고, 나름의 최적화를 시도하여 큰 값부터 우선 처리하면, 더 빠르게 구할 수 있을거라고 생각하여 우선순위큐를 사용하여 bf..
문제https://www.acmicpc.net/problem/11660(25.01.14 현재 백준사이트의 미리보기 블록이 만들어지지 않는다.) 시간 제한메모리 제한solved.ac 티어1초256MB실버 1풀이본래 구간 합 구하기 문제들은 세그먼트 트리를 사용하는 문제들이 꽤 있는데, 이번 문제는 누적 합 알고리즘을 사용하는 것 만으로도 충분한 문제이다. 각 행에 대해 누적합 배열로 변경한 후, 입력받는 쿼리에 대해 누적합 배열을 이용하면 시간복잡도 안에 끝낼 수 있을 것이다. 문제의 표를 누적합 배열로 바꾸면 다음과 같을 것이다.1361025914371218491522 예제입력1의 첫번째 쿼리는 다음과 같다.2 2 3 4 원래라면 해당 쿼리를 처리하기 위해서 다음의 영역의 각 숫자들을 더해야 할 것이다...
https://www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1 초 128 MB 골드 5 문제 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 K(1 ≤ K ≤ 10^9)가 주어진다. 출력 첫째 줄에 창영이가 좋아하는 숫자 중 K번째 작은 수를 출력한다. 4와 7로만 이루어진 숫자중에서 k번째로 작은 숫자를 구하는 문제이다. 처음 봤을때는 DP일거 같긴 했지만, 마땅한 방법이 생각이 나..
https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1초 128MB 실버 4 문제 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ ..
