본문 바로가기

🏃 algorithm/boj105

BOJ 9094 - 수학적 호기심 문제 백준 온라인 저지 - 9094번 풀이 과정 가능한 모든 조합을 만들어본 다음 주어진 조건을 만족하는 조합의 개수를 구하는 문제입니다. 처음에 a 와 b 의 조합의 개수가 10000개를 넘지 않기 때문에 단순 조합개수를 만들어서 시도했는데 테스트 케이스의 개수 T 를 고려하지 못해서 시간 초과가 발생했습니다. 이를 위해 a, b, m 을 상태변수로 하는 메모이제이션을 적용해서 중복된 계산을 줄이는 방식으로 해결할 수 있습니다. 코드 import sys def solution(): ret = 0 for a in range(1, n): for b in range(a + 1, n): if memo[a][b][m] != -1: ret += memo[a][b][m] continue numerator, deno.. 2021. 9. 12.

BOJ 5076 - Web Pages 문제 백준 온라인 저지 - 5076번 풀이 과정 HTML 문자열을 입력으로 받아서 해당 문자열이 유효한지 판단하는 문제입니다. 열린 태그와 닫힌 태그는 서로 쌍을 이루어야 하기 때문에 (self-closing 태그 제외) 스택 을 이용해서 유효성을 판단하면 됩니다. 이때 주어진 문자열에서 태그를 추출하기 위해 파싱하는 함수를 구현합니다. 태그 정보는 태그 이름, 태그 타입 으로 구성됩니다. 코드 import sys def parse_tag(html): parsed_tags = [] start_parsing = False tag_name = '' tag_type = '' for idx in range(len(html)): if html[idx] == '': tag.. 2021. 7. 19.

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.

이전 1 2 3 4 ··· 18 다음

티스토리툴바