문제 자연수 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..

문제 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 풀이 1. Subtask1 -> 50점 미리 P1, P2..에 대한 정답을 sol만들고 슬라이싱 방법을 통해 루프를 돌며 sol과 같은 부분이 있으면 count하는 방식으로 구현했다. n = int(input()) m = int(input()) data = input() sol = 'I' + 'OI' * n result = 0 for i in range(0, len(data) - len(s..