[Python/파이썬] 백준 1043번: 거짓말

문제 풀이 진실을 알고 있는 사람의 집합을 knowList 파티에 참석한 사람의 집합을 party party를 원소로 갖는 배열 parties 1. 만약 party, knowList의 교집합이 하나라도 있으면 knowList = knowList.union(party) (파티에 진실을 아는 사람이 한 명이라도 있다면, 그 사람으로 인해 파티에 참석한 모든 사람이 진실을 알게 됨) 2. 위 과정을 파티의 수만큼 반복 why?? 5개의 파티가 있고 진실을 아는 사람이 A라고 가정하자. 이 경우 5개의 파티 중 A가 참여한 파티가 있는지 확인하면 된다. 확인하던 도중 A가 3번째 파티에 참여한 것이 발견되어 B 역시 진실을 알게 되었다고 가정하자. B에 대해서도 마찬가지로 5개의 파티 중 B가 참여한 파티가 있..

[Python/파이썬] 백준 10830번: 행렬 제곱

문제 풀이 행렬 곱셈을 구하는 함수만 작성하면 분할 제곱을 이용한 거듭제곱 알고리즘을 통해 쉽게 풀 수 있다. 행렬 곱셈을 구하는게 좀 까다로웠다... 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 9) n, b = map(int, input().split()) matrix = [] for _ in range(n): matrix.append(list(map(int, input().split()))) def mulMatrix(m1, m2): tmpArr = [[] for _ in range(n)] for i in range(n): for j in range(n): tmp = 0 for k in range(n): tmp += m1[..

[Python/파이썬] 백준 13116번: 30번

문제 풀이 완전 이진트리 및 LCA 문제이다. 완전 이진트리의 레벨은 log2를 통해 구할 수 있고 부모는 /2를 해주면 된다. 즉 두 노드의 레벨을 구한 뒤, 레벨을 서로 같게 맞춰준 뒤, 두 노드가 서로 같을 때까지 각 노드에 /2를 해주면 된다. (이진트리와 LCA를 공부하면 쉽게 풀 수 있다.) 코드 import sys, math input = sys.stdin.readline t = int(input()) def getLevel(n): return math.floor(math.log2(n)) for _ in range(t): a, b = map(int, input().split()) while True: levelA, levelB = getLevel(a), getLevel(b) if levelA..

[Python/파이썬] 백준 11054번: 가장 긴 바이토닉 부분 수열

문제 풀이 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 구하면 된다. (부분 수열 시리즈를 풀었다면 쉽게 풀 수 있다.) 코드 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dpMax = [1] * n dpMin = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: dpMax[i] = max(dpMax[i], dpMax[j] + 1) for i in range(n - 1, -1, -1): for j in range(i, n): if arr[i] > arr[j]: dpMin[i] = max(dpMin..

[Python/파이썬] 백준 14002번: 가장 긴 증가하는 부분 수열 4

문제 풀이 수열의 최대 크기가 1000이므로 N2 으로 풀면 된다. dp 값을 갱신하는 방법과 동일하게 dp 수열도 갱신해주면 된다. (아래 코드 참고) 코드 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dpMax = [0] * n dpArr = [[] for _ in range(n)] dpArr[0] = [arr[0]] maxIdx = 0 for i in range(1, n): for j in range(i - 1, -1, -1): if arr[i] > arr[j]: if dpMax[j] + 1 > dpMax[i]: dpMax[i] = dpMax[j] + 1 dpArr[i] = dp..

[Python/파이썬] 백준 2263번: 트리의 순회

문제 풀이 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 후위 순회는 최상위 루트를 맨 마지막에 방문하며, 중위 순회는 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문한다. 따라서, 후위 순회의 맨 마지막 원소는 최상위 루트이며 이를 기준으로 중위 순회를 나누면, 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리임을 알 수 있다. 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이때 중위 순회에서 왼쪽 서브 트리의 범위는 시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1) 중위 순회에서 오른쪽 서브 트리의 범위는 (끝 인덱스 - 오..

[Python/파이썬] 백준 9372번: 상근이의 여행

문제 풀이 문제에서 주어진 정보를 잘 활용해야 한다. 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 따라서 아무 노드나 선택해도 그 노드에서 모든 노드로 갈 수 있음을 의미한다. (아래 그림 참고) 또한 연결 그래프를 유지하기 위한 간선의 최소 개수는 (노드의 수 - 1)이다. 이를 신장 트리라 한다. https://terms.naver.com/entry.naver?docId=837730&cid=42344&categoryId=42344 신장 트리 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리. 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. terms.naver.com 즉, 비행기의 종류 = 간선 수 여행 갈 나라의 수 = 노드의 수 간선의 최소..

[Python/파이썬] 백준 5639번: 이진 검색 트리

문제 풀이 전위 순회한 결과 50 30 24 5 28 45 98 52 60 첫 번째 원소가 루트 노드 (전위 순회의 성질에 의해) 왼쪽 서브 트리 = 루트 노드보다 작은 원소인 경우 오른쪽 서브 트리 = 루트 노드보다 큰 원소의 경우 전위 순회를 했으므로 루트 노드보다 큰 원소가 나오는 지점이 왼쪽 서브 트리와 오른쪽 서브 트리를 나누는 지점과 같다. 50 30 24 5 28 45 98 52 60 초록 = 루트 노드, 빨강 = 왼쪽 서브 트리, 파랑 = 오른쪽 서브 트리 위 결과를 활용해 후위 순회를 해주면 된다. 코드 import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline pre = [] while True: try: pre.appen..

[Python/파이썬] 백준 1417번: 국회의원 선거

문제 풀이 기호 1번을 제외한 나머지 표를 최대 힙에 넣는다. 힙을 pop()했을 때 나온 후보의 표가 기호 1번의 표보다 많다면, 그 후보를 한명 매수하고 다시 힙에 넣는다. 위 과정을 기호 1번의 표가 제일 많을 때까지 반복한다. 코드 import sys, heapq input = sys.stdin.readline n = int(input()) win = int(input()) nums = [] for _ in range(n - 1): num = int(input()) heapq.heappush(nums, (-num, num)) cnt = 0 while nums: num = heapq.heappop(nums)[1] if num >= win: num -= 1 win += 1 cnt += 1 heapq...

[Python/파이썬] 백준 11779번: 최소비용 구하기 2

문제 풀이 다익스트라 알고리즘을 사용하되, 최단경로 값이 갱신될 때 그때의 노드 값도 함께 기록한다. 시작 노드가 1번 일 때, 1. 초기값 distance : 1번 노드에서 다른 노드로 갈 수 있는 최단 경로 1 2 3 4 5 6 0 4 2 INF INF INF nearnest 값 : 방문한 노드({1}) 중에서 가장 가까운 노드 1 2 3 4 5 6 1 1 1 1 1 1 2. 갱신 distance : 1번 노드에서 n번 노드로 가는 비용보다 1~3, 3~n으로 가는 비용이 더 작으면 갱신 1 2 3 4 5 6 0 4 2 INF 6 (갱신) INF nearnest 값 : 방문한 노드({1, 3}) 중에서 가장 가까운 노드 1 2 3 4 5 6 1 1 1 1 3 (갱신) 1 3. 2번 반복 문제에서 주어..