본문 바로가기

Algorithm202

BOJ 1920 - 수 찾기 문제 백준 온라인 저지 - 1920번 풀이 과정 주어진 배열에서 특정 수들이 존재하는지 판단하는 문제입니다. 배열의 길이와 찾는 수들이 각각 최대 10만이기 때문에 완전 탐색을 진행할 경우 시간 초과가 발생합니다. 따라서 검색용 배열을 미리 정렬한 뒤에 이분 탐색 을 이용해서 O(MlogN) 의 시간 복잡도로 해결할 수 있습니다. 코드 import sys def find(arr, target): lo, hi = 0, len(arr) - 1 while lo 2021. 7. 5.
BOJ 13700 - 완전 범죄 문제 백준 온라인 저지 - 13700번 풀이 과정 시작 지점에서 목표 지점에 도달하는 최소 이동 횟수를 구하는 문제입니다. 문제 조건에서 경찰서에 중간에 방문하면 안된다는 조건이 있기 때문에 BFS 를 이용하여 탐색을 진행하기 전에 모든 경찰서 지점을 방문처리 해준 뒤 탐색을 수행하도록 해줍니다. 코드 import sys from collections import deque INF = 2e9 def bfs(start, goal): q = deque() visit = [0] * (N + 1) q.append([start, 0]) visit[start] = 1 for office in police_office: visit[office] = 1 while q: here, click = q.popleft() i.. 2021. 6. 29.
BOJ 14950 - 정복자 문제 백준 온라인 저지 - 1번 풀이 과정 모든 정점을 잇는 최단 경로를 찾는 문제입니다. 즉, 최소 스패닝 트리를 구현하면 되기 때문에 크루스칼 알고리즘 을 활용해서 문제를 해결했습니다. 다만 각 경로를 선택할때마다 모든 간선의 비용이 증가하기 때문에 t * 이전까지 선택된 간선의 개수 만큼 추가적인 값을 누적해줍니다. 코드 import sys def union(u, v): pv, pu = find(u), find(v) if pv != pu: if rank[pv] > rank[pu]: parent[pu] = pv else: if rank[pv] == rank[pu]: rank[pu] += 1 parent[pv] = pu def find(u): if parent[u] == u: return u paren.. 2021. 6. 25.
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.

티스토리툴바