5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 읽기 문제를 딱 읽고 나니 든 생각은 숫자가 크다!는 거였다. 그거 말고는 크게 어렵지 않아 보였다. 시간초과를 어느정도 해결하면서 구현하는 문제로 생각했다. 문제 풀기 말했듯이 시간 초과를 해결하며 구현했다. 시간 초과를 생각하지 않고 정말 단순하게 구현하면 다음과 같다. 테스트 개수 T만큼 반복문을 돌린다. 수행할 함수 묶음을 입력 받는다. 초기 배열의 크기 N을 입력 받는다. 초기 배열 arr를 입력 받는다. 함수 묶음을 for문 돌리며 실행한다. 함수가 R이면 배열을 뒤집는다. 함수가 D이면 첫 번째 수를..

13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 읽기 해당 문제는 가장 빨리 갈 수 있는 시간, 그리고 그 때의 루트를 출력해야 한다. 이전에 가장 빨리 갈 수 있는 시간을 문제는 풀어봤던 기억이 있다. 하지만 이 문제는 루트까지 출력해야 한다! 즉, BFS + 루트 출력 문제라 볼 수 있다. 문제 풀기 BFS를 쓰는 이유는, 당연하겠지만 최소 시간을 구하기 때문이다. 이 문제는 완전 탐색을 해야 하는데, DFS, BFS 중에서 고르라면 최소 시간만 얻으면 되기 때문에 주..

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 읽기 이 문제는 일단 입력 값이 너무 컸기 때문에 바로 이분 탐색을 써야 겠다고 생각이 들었다. 입력 값을 한번 보자. 나무의 수 N : 1~1,000,000(백만) 필요한 나무 길이 M : 1 ~ 2,000,000,000(이십억) 나무의 높이 : 0~1,000,000,000(십억) 만약 완전 나이브하게 풀이한다면, 나무를 자를 높이를 0에서부터 십억까지 1씩 증가시키면서, N개의 나무를 다 잘라보고, 총합이 필요한 ..

9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 문제 읽기 문제를 처음에 읽었을 때에는 모든 경우의 수를 따지는 방법을 생각했다. 단순하게 생각하면 dfs가 직관적이라 dfs를 생각했지만, 복잡도를 생각했을 때 단어의 길이가 200이기 때문에 dfs를 수행하면 지수 시간이기 때문에 불가능했다. 그래서 bfs로 접근했다. 문제 풀기 bfs로 풀었는데, 사실 처음에는 visited가 필요 없다고 생각했다. 처음에 다음 그림을 그렸었다. 이렇게 오른쪽, 아래쪽 두 방향으로 내려가면 경우의 수를 구했을 때 방문 처리는..

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 읽기 LCS, 즉 최장 공통 부분 수열의 길이를 찾으면서, 동시에 수열까지 구해야 하는 문제이다. 이전에 한 번 풀어봤지만 잘 기억이 나지 않아 다시 공부하면서 풀어보았다. 한 마디로 DP를 활용하면 된다. 문제 풀기 LCS 수열 길이 구하기 일단 점화식을 찾기 위해 그려봤다. 이런 식으로 구할 수 있다. 즉, 두 문자열에서 str1의 i번째 문자, str2의 j번째 문자가 같은지, 같지 않은 지에 따라서 점..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 읽기 일단 해당 문제는 흔히 LIS라고 하는 가장 긴 증가하는 부분 수열을 찾는 문제이다. 처음에 봤을 때는 tree모양이 생각났지만, 그려보니 아닌 것 같았다. 찾다 보니 DP라는 것을 알았다. 문제 풀기 N이 최대 1000이기 때문에 이중 for문을 통해 탐색해도 복잡도에 걸리지 않는 시간이다. 다음과 같은 과정을 통해 문제를 해결할 수 있다. 주어진 숫자 배열을 입력 받는..