mojo's Blog

문제 링크 => 11055번: 가장 큰 증가 부분 수열 (acmicpc.net) 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이 문제는 가장 긴 감소하는 부분 수열에서 증가로 변경되고 길이가 아닌 누적된 합을 구하는 문제이다. 그래서 dp 값을 길이가 아닌 누적합이 되도록 dp[j] + arr[i] > dp[i] 으로 변경만 해주면 그만이다. (이때 arr[j] < arr[i]인 경우에 고려해준다) 풀이 code #de..

문제 링크 => 11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net) 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 다이나믹 프로그래밍 문제이다. dp 값을 어떻게 변경할 것인지에 대해서 약간 까다로운 문제인것 같다. 배열의 어떠한 값을 기준으로 왼쪽에 있는 값들과 비교해가면서 다음과 같은 조건을 만족하는 경우를 찾는다. 왼쪽의 값이 기준으로 둔 값보다 큰 경우를 찾는다. ( arr[j] > arr[i] ) 그때의 dp값..

문제 링크 => 2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 사실 이문제는 n=6 까지만 해봐도 피보나치의 규칙성이 보이는 단순한 문제이다. 이때 n값이 90까지이므로 int형으로 선언할 경우 틀리게 되므로 long long 을 붙여주도록 하자. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #incl..

문제 링크 => 2504번: 괄호의 값 (acmicpc.net) 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net Stack을 활용한 문제이다. 스택 관련 문제중에 좀 어려운 문제여서 잘 안풀렸던 문제인거 같다. 이 문제를 해결하기 위해 최종값을 나타내기 위한 변수 result와 접근해가면서 괄호 안의 값들을 더하는 operation을 처리하기 위한 변수 tmp를 선언하였다. 그리고 '(', '[' 문자일때와 ')', ']' 문자일때의 operation을 다음과 같이 처리해주었다. (1) '(', '[' 문자..

문제 링크 => 5397번: 키로거 (acmicpc.net) 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net Stack을 활용한 문제이다. Stack, Queue 관련 문제를 해결하다 보면 런타임에러가 종종 일어나기 마련인데 이번에도 한번에 패스하지 못했다. 일단, '' 와 같은 화살표로 커서를 움직여서 문자를 받아올때 해당 커서의 위치에서 문자가 들어오는게 핵심이다. 또한 '-' 와 같은 문자가 들어오는 경우, 커서의 왼쪽에 위치하는 문자를 제거해준다. 이때 내가 놓쳤던 부분은 '-' 를 받아올 때,..

문제 링크 => 19637번: IF문 좀 대신 써줘 (acmicpc.net) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이분탐색 문제이다. 이문제에서 Input 은 n 개의 (string, long long) 형태로 주어지는데 long long 값이 오름차순으로 주어지는 것에 대해서 눈여겨 볼 필요가 있다. 즉, 벡터에다가 값을 push한 후에 정렬하는 operation을 하지 않고 바로 이분탐색을 할 수 있다는 것이 핵심이다. 풀이 code #define _CR..