Coding Test

1. 문제 설명 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 2. 아이디어 이게 왜 골드4..? 라는 생각이 들 정도로 아이디어나 알고리즘이나 딱히 특출날 게 없는 문제. source와 sink가 고정정으로 좌상단, 우하단으로 정해져 있기 때문에 dfs를 사용하여 각 지점에서 종점으로 갈 수 있는 경우를 dp로 저장해가면서 마지막에 (0,0)에 할당되는 결과값을 출력하면 끝난다. 다만, 내가 여기서 처음 틀렸던 이유는 cache를 0으로 ..

1. 문제 설명 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2. 아이디어 최악의 경우에 1024 * 1024 크기의 표에서 값을 100,000 구해야 하는데 제한 시간은 1초밖에 안 된다. bfs를 사용해서 매번 연산과정을 거쳐 값을 구하는 건 너무 미련한 짓이다. 이런 문제는 곧 dp를 사용해서 풀이해야 함을 알 수 있어야 한다. 우선 N*N 크기의 리스트에 [n-1][n-1]을 기점으로으로 [..

1. 문제 설명 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 2. 아이디어 반복문으로 풀면 무조건 타임에러가 난다. A = 2,147,483,647 / B = 2,147,483,647 / C = 1 인 테스트 케이스가 들어오면 약 21억번의 연산이 들어가기 때문에 O(n)으로는 풀 수 없다. 그래서 분할 정복(O(logn))으로 풀어야 타임 에러에서 벗어날 수 있다. 예를 들어, \(2^{10}\)은 \(2^{5}\) x \(2^{5}\)로 나눌 수 있다. 홀수인 경우에는 \(2^{11} = 2^{5}\)..

1. 문제 설명 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 정말 기억에 오래 남는 문제다. 이 문제를 풀기 위해서 12시간을 스카에 박혀있다가 결국 해결 못 하고 다음날 12시간을 더 할애했던 문제였었다. 순전히 PyPy로 시간 초과를 극복하는 것은 자존심이 허락하지 않는다는 얼토당토 않는 이유에서였다.. 2. 아이디어 이 문제는 풀이 방법이 2가지가 있다. (물론 더 있을 수 있지만, 난 모르겠다.) 하나는 무식하게 진짜 소용돌이를 다 '그려보는 것'이고, 다른 하나는 수학적으로 접근하여 위치를 추적하여 값을 출력하는 것이다. 전자는 당연히 시간초과가 나서..