문제 (링크) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나의 풀이 import sys from itertools import combinations input = sys.stdin.readline n, s = map(int, input().split()) arr = list(map(int, input().split())) cnt = 0 for i in range(1, n+1): comb = combin..
알고리즘
문제 (링크) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n, c = map(int, input().split()) arr = [] for _ in range(n): arr.append(int(input())) arr.sort() end = arr[-1] - arr[0] start = 1 ans = 0 whil..
문제 (링크) https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline seq_1 = input().rstrip() seq_2 = input().rstrip() seq_3 = input().rstrip() x = len(seq_1) y = len(seq_2) z = len(seq_3) arr = [[[0] * (z+1) for _ in range(y+1)] for _ in range(x+1..
문제 (링크) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline seq_1 = input().rstrip() seq_2 = input().rstrip() n = len(seq_1) m = len(seq_2) arr = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): ..
문제 (링크) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 나의 풀이 import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr = deque(arr) while arr: current = arr.popleft() exist = False for x in arr: if current <..
시간 제한 메모리 제한 0.1 초 128MB 문제 (링크) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 나의 코드 import heapq import sys input = sys.stdin.readline n = int(input()) left_heap = [] right_heap = [] for _ in range(n): x = int(input()) if len(left_heap) == len(right_heap): he..
똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다. 흔히 우리가 말하는 2의 4제곱(2^4=16), 5의 3제곱(5^3=125) 등은 거듭제곱을 표현한 것이다. 당연히 코드를 통해서 이를 빠르게 계산할 수 있다. 반복문 사용 a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 다음과 같은 코드를 작성할 수 있다. def power(a, n): ans = 1 for _ in range(n): ans *= a return ans 재귀함수 사용 반복문이 아닌 재귀적 방식으로도 위 코드를 구현할 수 있다. a의 n제곱을 쭉 풀어보면 다음과 같다. 위 식은 부분문제로 나눌 수 있다. 만약 a의 n제곱이 아닌 a의 n+1제곱을 구하고자 할 땐 a^n의 값에 a를 한 번 더 곱해주면 되는데, ..
문제 (링크) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 나의 풀이 # 오답 import sys from collections import deque input = sys.stdin.readline move = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] r, c = map(int, input().split()) dist = [[int(1e9)] * c for _ in range(r)] q_jihun =..
