11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 조건에 보면 동전의 가치는 배수 관계라고 되어있다. 배수 관계이면 그리디 알고리즘으로 풀 수 있다. # 한 줄에 입력 여러개 받아서 변수에 할당하기 N, K = map(int, input().split()) coins = [int(input()) for i in range(N)] coins.reverse() totalCoins = 0 for coin i..
알고리즘 문제풀이
9명의 난쟁이 중에서 7명을 뽑아야 하니까 조합을 사용해야 한다. 조합은 combianations 모듈을 가져다 쓰면 된다. from itertools import combinations heights = [int(input()) for i in range(9)] for candis in combinations(heights, 7): if sum(candis) == 100: for real_dwarfs in sorted(candis): print(real_dwarfs) break 9개의 입력을 받아서 heights에 넣은 다음 heights 리스트에서 7개를 선택해서 candis에 넣는다. candis의 합이 100일 때만 리스트의 각각의 원소를 출력해주면 되는데, 오름차순으로 출력하라고 했으니 cand..
책 이름 : 팔린 권수 => key : value 로 매칭할 수 있기 때문에 딕셔너리 구조를 이용한다. d = dict() for i in range(int(input())): book = input() if book in d: d[book] += 1 else: d[book] = 1 # print(d.keys()) # print(d.values()) # print(d.items()) m = max(d.values()) candi = [] for k, v in d.items(): if v == m: candi.append(k) candi.sort() print(candi[0]) 딕셔너리 구조는 .keys()를 통해 키만 뽑아낼 수 있고 .values()를 통해 values만 뽑아낼 수도 있고 .items(..
일단 파이썬의 heapq 모듈은 min-heap이기 때문에 루트노드에 최소값이 위치하게 된다. **튜플 정렬을 이용. 예를 들어 arr = [(3, 4), (3, 1), (8, 5), (3, 2), (8, 7)] 이 있으면 arr.sort() 했을 때 튜플들의 0번째 기준으로 오름차순으로 먼저 정렬한 다음 1번째 인덱스 기준으로 정렬한 다음 보여준다. print(arr) >>> [(3, 1), (3, 2), (3, 4), (8, 5), (8, 7)] 이다. (적용과 해결) import heapq as hq, sys N = int(sys.stdin.readline()) pq = [] for i in range(N): x = int(sys.stdin.readline()) if x: hq.heappush(pq..
N = int(input()) stk = [] for i in range(N): stk.append(N-i) while stk: if len(stk) > 1: stk.pop() stk.insert(0, stk.pop()) else: print(stk.pop()) 이렇게 풀었는데 시간 초과였다. 스택이라고 생각하고 만들었지만 실상은 배열이기 때문에 시간복잡도가 N^2이 넘는다. 2초 안에 절대 안풀림. deque 모듈을 써보자. from collections import deque N = int(input()) dq = deque(range(1, N+1)) while len(dq) > 1 : dq.popleft() dq.append(dq.popleft()) print(dq.pop()) 이렇게 하면 224m..
T = int(input()) for i in range(T): stk = [] isVPS = True for ch in input(): if ch == '(': stk.append(ch) else: if len(stk) > 0: stk.pop() else: isVPS = False break if len(stk) > 0: isVPS = False print('YES' if isVPS else 'NO') 괄호가 쌍을 이루면 VPS다. 스택구조로 생각해야 한다. 여는 괄호가 무조건 먼저 들어가야 VPS를 이룰 수 있다. 여는 괄호가 들어가 있는 상태에서 닫는 괄호를 만나면 스택에 들어있는 여는 괄호를 삭제해준다. 스택이 비어있는데 닫는 괄호가 들어오면 isVPS를 False로 바꿔주고 반복문을 탈출하면 된..
1. Priority queue 파이썬은 min-heap이다. root-node에 최소값이 위치한다는 뜻. 삽입/삭제 시간복잡도는 logN이다. heapq 모듈은 thread-safe한 모듈은 아니지만 빠르다. import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 10) heapq.heappush(pq, -7) heapq.heappush(pq, 15) heapq.heappush(pq, -4) heapq.heappush(pq, 0) print(pq) while pq: heapq.heappop(pq) print(pq) 보면 최상단에 최소값이 위치할 뿐 나머지는 정렬이 되어있지 않다. 2. Dictionary key, value의 쌍을 이루는 구조. 다..
1. 배열 (Array) *삽입/삭제의 시간복잡도 O(N) -N개의 인덱스가 있을 때 맨 앞에 삽입할 경우 하나씩 전부 뒤로 밀려야 하기 때문에 N *탐색의 시간복잡도 O(1) -원하는 인덱스에 바로 접근이 가능하기 때문에 상수. *파이썬에서는 size 변경이 가능. 2. 연결 리스트 (Linked list) 두 부분으로 이루어진 리스트. data가 저장되어 있는 부분과 다음 데이터를 가리키는 포인터가 저장되어있는 link 부분으로 나뉘어 있다. 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. *삽입/삭제의 시간복잡도는 O(1) - 연결부분만 명시하면 된다. *탐색의 시간복잡도 O(N) - 어떤 자료를 찾으려면 링크를 타고타고 들어가야 한다. 3. 스택 (Stack) - 후입선출 구조 ..
