문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 풀이 앞에서 풀었던 구간 합 구하기 4와 같이 prefixsum을 미리 구해서 리스트에 넣고, 나중에 필요한 좌표에서의 누적합을 print 하면 된다! import sys N..

문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 시간 제한 : 0.5초 풀이 일단 시간 제한이 0.5초이고 입력으로 받는 수가 21억이므로 최대 O(N)으로 21억번을 곱하면 시간 초과가 날 것이다. 여기서 잠깐 대략적으로 왜 시간 초과가 나는지 짚고 넘어가자. "수행 시간 짐작을 위한 주먹구구 법칙"이라는 것이 있는데 이다! 자 그럼 만약 O(N)으로 알고리즘을 짜면 21억 -> 21억초이므로 시간 안에 돌아갈 가능성이 없다. 그러므로 이 문제는 "분할 정복" 알고리즘으로 접근해야한다. 만약 2^5을 계산하면 2 * 2 * 2 * 2 * 2로 ..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 예제 입력 1 복사 6 5 1 2 2 5 5 1 3 4 4 6 풀이 이 문제는 단순히 subgraph의 수를 찾는 문제이다. 모든 node를 돌면서 인접한 노드들은 방문처리를 하고 count하는 방식으로 문제를 풀었다. import sys sys.setrecursionlimit(10000) def dfs(i): visited[i] = True for j in array[i]: # i번째 노드와 인접한 노드를 방문해서 방문처리 if not visited[j]: dfs(j) N, M = map(int, sys.stdin.readline().split()) array = [[] fo..

문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 풀이 구간합을 구하는 단순한 문제이다. 이 문제의 경우 미리 구간합을 구해놓고 필요한 구간마다 SUM[right] - SUM[left - 1]로 구간합을 계산할 수 있다. 처음에 시간초과 떠서 다른 정답 코드와 비교했는데 거의 똑같았고 다른 점은 데이터를 입력받을 때 input으로 받았는지 sys.readline으로 받았는지에 대한 차이였다. 후자가 빠른 것을 알고 있었으나 영향을 크게 주지 않을거라 생각해서 input으로 풀었는데 시간초과가 나버렸다! import sys N, M = map(int, sys.stdin.readline().split()) data = list(map(int, sys.stdin.r..