문제 (링크) 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 <..
파이썬의 heapq 라이브러리를 통해 손 쉽게 최소힙과 최대힙을 구현할 수 있다. 우선, heapq는 기본적으로 최소힙으로 구현되어있다. 즉, heapq의 heappush를 통해 값들을 삽입하면 해당 값들은 숫자가 가장 작은 순서대로 트리 구조로 값이 저장된다. heapq의 연산을 사용하기 위해선 각 연산의 파라미터로 큐로 사용할 리스트와 원소를 넘겨주면 된다. 1. heappush - 값 추가 import heapq heap_q = [] heapq.heappush(heap_q, 3) heapq.heappush(heap_q, 10) heapq.heappush(heap_q, 1) heapq.heappush(heap_q, 0) heapq.heappush(heap_q, 4) print(heap_q) # [0,..
시간 제한 메모리 제한 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..
사담지원하고 싶은 회사의 지원자격 중 영어 말하기 공인시험 점수가 있었다. 토익 스피킹과 오픽 중 하나로 제출이 가능했는데, 토익 스피킹은 스크립트를 달달 외우는 시험이라고 해서 쿨하게 버리고 오픽으로 보기로 했다. 사실, 오픽 시험을 본 건 이번이 처음이 아니다. 군 생활 중 특별 외박 받으려고 공부해서 응시해본 적이 있었고, 당시에는 IH가 나왔다. 같이 공부했던 친구는 AL이 나와서 약간 자존심이 상하긴 했지만 여튼 특별 외박을 받긴 했었다. 이번 시험은 왜 갑자기 그랬는지는 기억이 안나지만 정말 급발진해서 시험 일주일 전에 신청했다. 심지어 채용 공고가 나오기도 전이어서 좀 천천히 해도 되겠다는 생각을 했을법한데 왜 그랬는지 모르겠다. 뭐에 홀렸었나보다. 아찔했던 건 시험을 본 직후 채용 공고가..
