본문 바로가기

👨‍💻📱✍️🎢314

BOJ 1197 - 최소 스패닝 트리 문제 백준 온라인 저지 - 1197번 풀이 과정 최소 스패닝 트리 를 구하는 문제입니다. 기본 문제이기 때문에 별도로 복잡한 로직이 추가되지는 않았습니다. 오랜만에 MST 문제를 한번 풀어보고 싶어서 가장 기본이 되는 문제를 한번 풀어봤습니다. 😄 코드 import sys def union(u, v): pu, pv = find(u), find(v) if pu != pv: if rank[pu] > rank[pv]: parent[pv] = pu else: parent[pu] = pv if rank[pu] == rank[pv]: rank[pv] += 1 def find(u): if parent[u] == u: return u parent[u] = find(parent[u]) return parent[u] de.. 2021. 6. 18.
BOJ 4963 - 섬의 개수 문제 백준 온라인 저지 - 4963번 풀이 과정 섬과 바다의 지도가 주어질 때 섬의 개수를 구하는 문제입니다. BFS 를 이용해서 컴포넌트의 개수를 구해주면 됩니다. 코드 import sys from collections import deque dx = [1, -1, 0, 0, -1, -1, 1, 1] dy = [0, 0, 1, -1, -1, 1, -1, 1] def in_range(x, y): return 0 2021. 6. 15.
LeetCode 300 - Longest Increasing Subsequence (Medium) 문제 LeetCode - 300번 풀이 과정 가장 긴 부분수열을 구하는 LIS 문제입니다. 동적 계획법 을 이용해서 문제를 해결할 수도 있지만 이분 탐색 을 이용하면 Nlog(N) 의 시간 복잡도로 해결할 수 있습니다. 코드 /** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function (nums) { const memo = []; for (const num of nums) { if (memo.length === 0) { memo.push(num); continue; } if (memo.length > 0 && memo[memo.length - 1] < num) { memo.push(num); } else { const idx .. 2021. 6. 14.
BOJ 5568 - 카드 놓기 문제 백준 온라인 저지 - 5568번 풀이 과정 N 개의 카드뭉치에서 K 개의 카드를 뽑아 만들 수 있는 모든 수를 구하는 문제입니다. 입력 값이 크지 않기 때문에 모든 수열을 만들어보고 집합을 이용해서 중복된 값을 제거한 뒤 총 개수를 구하면 됩니다. 코드 from itertools import permutations def solution(): number_set = set() for candidate in permutations(cards, K): num = &#39;&#39;.join(map(str, candidate)) number_set.add(num) return len(number_set) if __name__ == &#39;__main__&#39;: N = int(input()) K = .. 2021. 6. 14.
BOJ 5972 - 택배 배송 문제 백준 온라인 저지 - 5972번 풀이 과정 특정 시작 지점에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다. 다익스트라 알고리즘 을 이용해서 한 정점에서 모든 정점까지의 최단 비용을 구하면 ElogV 의 시간 복잡도로 구할 수 있습니다. 코드 import sys import heapq INF = 2e9 def dijkstra(frm, to): dist = [INF] * (N + 1) pq = [] dist[frm] = 0 heapq.heappush(pq, [0, frm]) while pq: cost, here = heapq.heappop(pq) if dist[here] < cost: continue for there, there_cost in graph[here]: next_cost = .. 2021. 6. 10.
BOJ 1613 - 역사 문제 백준 온라인 저지 - 1613번 풀이 과정 역사의 한 지점을 그래프의 정점으로 나타내면 각 사건의 전후 관계는 정점의 도달성 문제로 생각할 수 있습니다. 따라서 정점의 최대 개수가 400개 이하이므로 O(N^3) 의 시간복잡도를 가지는 플로이드 와샬 알고리즘 을 활용하여 문제를 해결했습니다. 모든 정점간의 도달성 여부를 계산해준 뒤, 문제에서 주어지는 입력의 전후 관계를 출력해주도록 했습니다. 다만 Python3 의 속도 한계로 인해 PyPy로 제출해야 시간제한 이내에 수행이 가능했습니다. 코드 import sys n, k = list(map(int, sys.stdin.readline().split())) adj = [[0]*n for _ in range(n)] for _ in range(k): f.. 2021. 6. 9.

티스토리툴바