전체 글
1890번-점프
문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 "반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다." 라는 힌트로 두 가지의 경우로 나뉘며 재귀함수로 코드를 작성하면 구현이 쉬울 거 같은 설명이 적혀있다. 2) 시간 복잡도 다이나믹 프로그래밍을 활용하여 접근하였으므로 O(n)의 시간복잡도를 가진다...
1912번-연속합
문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근방법 1) 접근 사고 처음에는 이분탐색으로 구현을 할 려고 했었다. 그러나 이분탐색 부분을 구현하던 도중 두 개의 값을 더 한것을 어떻게 표현할 것인지에 대해 막혀서 다시 고민을 했었고 두 개를 더할 것인가 말 것인가에서 DP로 점화식을 세우면 될 것 같다고 생각을 하였다. 2) 시간 복잡도 DP로 구현을 하였으므로 시간초과 관련 문제는 없었다. 자료형도 최대 100,000 * 1000 = 1,00..
1463번-1로 만들기
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 이런 형식으로 문제에서 재귀함수로 구현하면 구현하기 쉽게 힌트를 준다. 이런 방식을 완전탐색으로 풀려고 접근하여 각각의 경우에서 수 많개의 경우의 수로 분할 되기 때문에 시간초과가 나므로 시간복잡도를 줄여야 하는 문제임을 알 수 있다. 2) 시간 복잡도 memorization 기법을 사용한 DP로 접근 3) 배운 점 memorization을 활용해서 탑다운 방식의 알고리즘을 구현해..