구간 합 N개의 수에 대해서 M개의 구간 정보로 구간 합을 구해야 하는 경우 구간 합을 완전 탐색을 통해서 구할 경우 O(NM)의 시간 복잡도 결국 N, M이 클 경우 별도의 방법 필요 누적합(Prefix sum) N개의 수는 변하지 않고 그대로이며 M개의 구간 정보만 바뀌는 상황일 때, N개의 수에 대한 누적합을 계산하여 별도의 리스트에 미리 저장해줌 필요한 시간 복잡도 O(N) 이 경우 M개의 구간 정보 L, R에서 구간 합을 구할 경우 P[R] - P[L-1]을 통해서 빠르게 구할 수 있음 인덱싱만 하면 되기 때문에 각 구간 정보당 O(1)의 시간 복잡도를 가지게 됨 따라서 구간 합을 구할 때 누적합을 이용하게 되면 O(N + M)의 시간 복잡도만으로 가능하다. 참고 이것이 취업을 위한 코딩 테스트..

2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 $n \choose m$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000)이 들어온다. 출력 첫째 줄에 $n \choose m$의 끝자리 0의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 나의 풀이 숫자의 범위가 20억이기 때문에 for문을 통해서 N까지 순회하면 시간 초과가 발생한다. 따라서 5, 2의 인수의 개수를 몫의 성질로 빠르게 구한다. 팩토리얼 0의 개수에선 5의 개수만 알더라도..

1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10 예제 출력 1 2 예제 입력 2 3 예제 출력 2 0 나의 풀이 마지막 숫자가 0이려면 10이 곱해져야 함 따라서 팩토리얼 구성 숫자들을 소인수 분해하여 만들 수 있는 10의 개수를 계산하면 됨 N = int(input()) count_2 = 0 count_5 = 0 for i in ra..

문제 확인 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 시간 제한 : 1초 메모리 제한 : 128MB 나의 풀이 못 풀었다. 시도한 풀이는 다음과 같다. 시간 복잡도만 생각하지 말고 메모리도 생각하면서 문제를 풀어야 겠다는 교훈을 얻었다... 여러 타입의 옷이 입력됐을 때 타입의 종류를 조합으로 결정한 뒤 풀이를 시도했다. 타입의 종류가 클 경우 조합 선택 시 메모리 초과가 발생했다. 시간 복잡도 말고 메모리에 대..

1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 시간 제한 0.5초 메모리 제한 128MB 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ ..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 시간 제한 1초 메모리 제한 256MB 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N) 출력 \(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 5 2 예제 출력 1 10 나의 풀이 N과 K의 범위가 크기 때문에 중복된 계산을 줄이기 위해서 memoization을 이용했다. import sys sys.setrecursion..

3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나..

완전 탐색 활용 최대 공약수(GCD) : O(N)의 시간 복잡도 최소 공배수(LCM) : O(N*M)의 시간 복잡도 n, m = map(int, input().split()) # 최대 공약수 for i in range(max(n, m), 0, -1): if n % i == 0 and m % i == 0: print(i) break # 최소 공배수 for i in range(min(n, m), n * m + 1): if i % n == 0 and i % m == 0: print(i) break 유클리드 호제법 : 최대 공약수를 빠르게! 유클리드 호제법을 사용하면 최대 공약수를 재귀적으로 구할 수 있다. 이 경우 최대 공약수를 구하기 위해 필요한 시간 복잡도는 O(logN)이다. 유클리드 호제법은 다음과 같..

Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 앞에 있는 로봇들이 자신의 왼쪽에 위치한 물류 부터 선택하게 하면 결국 최대 로봇 수를 구할 수 있다. import sys line_len, robot_range = map(int, input().split()) line_info = list(input()) count = 0 # 앞에서부터 조회 for idx, obj in enumerate(line_info): if obj == "P": for j in range(idx - robot_range, idx + robot_range + 1): if j line_len - 1: continue elif line_i..

Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 반복이 진행될 수록 작은 지도를 반으로 가르는 직선들이 계속 추가 된다. 따라서 n번 째 시행 때 한 변에 놓인 점의 개수는 다음과 같다. $a_n = 2 + \sum_1^{n}2^{n-1}$ import sys n = int(input()) length = 2 for i in range(n): length += (2 ** i) print(length ** 2) 다른 사람 풀이 반으로 나누면서 중간에 겹치는 점이 발생하기 때문에 1을 빼준다. import sys N = int(sys.stdin.readline()) dp = [0] * 16 # N의 최댓값은 15이기 때문에 0단계..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 레일의 개수가 10 이하기 때문에 가능한 모든 레일 조합을 순열로 구한 뒤 완전 탐색으로 풀었다. import sys from itertools import permutations n, m, k = map(int, input().split()) rail_info = list(map(int, input().split())) # N이 작기 때문에 모든 경우의 수 확인 cases = list(permutations(rail_info, n)) min_sum = 1e9 # 완전 탐색 for case in cases: # 각 탐색마다 k 횟수만큼 시행 case_sum = 0 id..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 문제의 조건에 맞춰 충실하게 구현하면 되는 문제다. 알파벳(A~Z)을 다 쓰기 귀찮아서 ascii_uppercase를 사용하여 남은 알파벳을 계산했다. 최종적으로 암호를 생성할 때 빠르게 접근하기 위해서 알파벳 별 idx 정보를 dict에 저장했다. import sys from string import ascii_uppercase from collections import deque msg = input() key = input() # 중복 제거 및 남은 알파벳 확인 key = deque(set(key)) alpha_left = deque(set(ascii_upperc..