지난주 코딩 테스트를 보는데 숫자로 이루어진 한 집합이 다른 집합의 부분집합에 해당하는지 여부를 파악해야 하는 문제가 있었다. 인터넷 검색이 허용되는 시험이어서 다행히 바로 검색해 해결했지만 이정도 함수들은 외워두는게 좋을 것 같아서 이렇게 다시 한 번 정리하게 되었다. 1. 합집합 (Union) 집합 연산에서 합집합에 해당하는 함수는 set.union과 OR연산자 |가 있다. a = {1, 2, 3, 4} b = {3, 4, 5, 6} print(set.union(a, b)) # {1, 2, 3, 4, 5, 6} print(a | b) # {1, 2, 3, 4, 5, 6} 2. 교집합 (intersection) 교집합 연산은 AND 연산자 & 또는 set.intersection 메서드를 사용한다. a ..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 설명만 보면 무언가 흔히 봤던 문제 같지만 배열이 4개로 나누어져 있다. 거기다 입력값은 최대 4000개까지 가능해서 왠만한 방식으로는 그냥 바아아로 시간초과가 나버린다. 여러 방식들을 시도해 보았으나 가장 마음에 드는 방법은 역시 딕셔너리를 쓰는 거였다. 문제를 풀어볼수록 파이썬에 딕셔너리가 있어서 정말 감사하다~ 는 생각이 들었다. 특정 이분 탐색 문제는 조금만 코드를 ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색을 공부하는 중 대표 문제로 지정되어 있어서 들어가 봤더니 이전에 다른 방식으로 해결한 문제였다. 이번엔 이분 탐색을 사용하여 풀어 보았다. 파이썬 이분 탐색 라이브러리: from bisect import bisect_left, bisect_right 이를 이용해서 리스트에 자신이 찾길 원하는 숫자가 존재하는지 확인할 수 있다..! bisect_right(a..

- 최소 힙(min-heap)의 구조 - 삽입/삭제: O(logN) import heapq로 사용 가능 push: heapq.heappush(hq, item) pop: heapq.heappop(hq) import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 12) heapq.heappop(pq) heapify - 리스트 x를 heap으로 변환 x = [4, 3, 1, 2, 5, 6] print(x) # [4, 3, 1, 2, 5, 6] heapq.heapify(x) print(x) # [1, 2, 4, 3, 5, 6] heapq를 사용하는 이유? from queue import PriorityQueue로 일반 우선순위 큐도 사용할 수 있다. 하지만 이..