본문 바로가기

전체글118

[Baekjoon-Python] 1504 : 특정한 최단 경로 https://www.acmicpc.net/problem/1504 접근 다익스트라 알고리즘으로 1, u, v의 정점에서 모든 정점까지의 최단 경로를 구한다. 1 -> u -> v -> N, 1 -> v -> u -> N 경로 중 최솟값을 구한다. 경로가 없을 때는 두 개 이상의 네트워크가 존재할 때이다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start): distance = [1e9] * (N + 1) distance[start] = 0 q = [] heappush(q, (0, start)) while q: dist, node = heappop(q) if distance[node] < dist: continue.. 2024. 1. 15.
[Baekjoon-Python] 1238 : 파티 https://www.acmicpc.net/problem/1238 접근 다익스트라 알고리즘을 사용한다. 정방향 그래프를 탐색해서 X에서 각각의 노드까지 가는 최단 경로를 구한다. 역방향 그래프를 탐색해서 각각의 노드에서 X까지 가는 최단 경로를 구한다. 두 경로를 더한다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start, graph): distance = [1e9] * (N + 1) distance[start] = 0 q = [] heappush(q, (0, start)) while q: dist, node = heappop(q) for next, next_dist in graph[node].items(): c.. 2024. 1. 15.
[Baekjoon-Python] 1167 : 트리의 지름 https://www.acmicpc.net/problem/1167 접근 임의의 노드 x에서 가장 먼 노드 y를 찾은 후, 노드 y에서 가장 먼 노드 z까지의 거리를 구한다. 트리 구조는 중간 경로를 공유하기 때문에 두 번의 탐색으로 트리의 지름을 구할 수 있고, 첫 탐색은 어떤 노드를 선택해도 상관없다. 풀이 from sys import stdin def dfs(now, diameter): for next, d in graph[now].items(): if visited[next] == -1: visited[next] = diameter + d dfs(next, visited[next]) V = int(stdin.readline()) graph = [{} for _ in range(V + 1)] for .. 2024. 1. 15.
[Baekjoon-Python] 1005 : ACM Craft https://www.acmicpc.net/problem/1005 접근 위상 정렬 알고리즘을 사용한다. 이전 순서의 건설 시간을 메모이제이션해서 현재 건물의 건설 시간을 계산한다. 현재 건물은 이전 순서의 건설 시간의 최댓값이 지난 후 건설이 시작된다. 풀이 from sys import stdin from collections import deque def topological_sort(target): q = deque() for i in range(1, N + 1): if in_degree[i] == 0: q.append(i) # (1) dp = [0] * (N + 1) while q: now = q.popleft() dp[now] += time[now - 1] # (2) if now == target.. 2024. 1. 15.
[Baekjoon-Python] 1043 : 거짓말 https://www.acmicpc.net/problem/1043 접근 진실을 아는 사람과 파티에 오는 사람들에 교집합이 있으면 합집합을 구한다. 진실을 아는 사람과 교집합이 없는 파티의 수를 구한다. 풀이 from sys import stdin N, M = map(int, stdin.readline().split()) truth = set(stdin.readline().split()[1:]) party = [] for _ in range(M): party.append(set(stdin.readline().split()[1:])) for _ in range(M): for p in party: if truth & p: truth = truth.union(p) cnt = 0 for p in party: if.. 2024. 1. 14.
[Baekjoon-Python] 2252 : 줄 세우기 https://www.acmicpc.net/problem/2252 접근 위상 정렬 알고리즘을 사용한다. 풀이 from sys import stdin from collections import deque def topological_sort(): q = deque() for i in range(1, N + 1): if in_degree[i] == 0: q.append(i) # (1) while q: node = q.popleft() print(node, end=" ") for i in graph[node]: # (2) in_degree[i] -= 1 if in_degree[i] == 0: q.append(i) N, M = map(int, stdin.readline().split()) graph = [[] .. 2024. 1. 14.
소마 14기 합격 후기 2023년에 작성한 내용입니다. 1. 지원 비전공자이고 개발을 시작한지 약 1년정도 되었다. 6개월의 부트캠프를 수료하고 나서 취업을 바로 할지, 역량을 더 쌓을지 고민이 많았다. 첫 직장이 중요하다고 생각하기도 하고, 지금 실력으로 원하는 기업에 들어가기엔 많이 부족하다는 것을 알기에 긴 고민 끝에 나의 가치를 더 높이는 쪽을 선택했다. 목표는 싸피, 우아한테크코스, 소프트웨어 마에스트로 중 하나였다. 작년 말에 싸피와 우아한테크코스에 지원했고 싸피는 광탈, 우테코는 마지막 전형까지 가게 되었다. 2:1의 경쟁률이었는데 아쉽게도 떨어졌고, 2인 프로젝트와 취업 준비를 병행하면서 시간을 보냈다. 마지막으로 남은 것은 소마, 1월 9일 모집 공고가 올라왔고 간절한 마음으로 서류를 제출했다. 2. 자기소개서.. 2024. 1. 14.
[Baekjoon-Python] 11779 : 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 접근 다익스트라 알고리즘을 사용하여 출발 도시에서 도착 도시까지 가는데 발생하는 최소 비용을 구한다. 현재 노드에서 다음 노드로 갈 때 최소 비용이면 다음 노드에 현재 노드 번호를 저장한다. 풀이 from sys import stdin from heapq import heappush, heappop def dijkstra(start): q = [] heappush(q, (0, start)) while q: dist, now = heappop(q) for next, next_dist in graph[now].items(): cost = dist + next_dist if cost < distance[next]: distance[next],.. 2024. 1. 14.
[Baekjoon-Python] 2805 : 나무 자르기 https://www.acmicpc.net/problem/2805 접근 나무 높이는 최대 10억이므로 이분 탐색으로 높이를 구해야 한다. low를 1, high를 N개의 나무 중 최대 길이로 설정한다. low와 high의 중간 값인 mid로 나무를 잘라서 M보다 크거나 같은지 확인한다. M미터를 만들 수 있으면 low = mid + 1, 만들 수 없으면 high = mid - 1로 설정한다. low가 high보다 작거나 같을 때까지 반복한다. N개의 나무 중 최대 높이를 L이라고 할 때, 시간복잡도는 O(NlogL) 풀이 from sys import stdin from collections import Counter _, M = map(int, stdin.readline().split()) trees =.. 2024. 1. 14.
[Baekjoon-Python] 1874 : 스택 수열 https://www.acmicpc.net/problem/1874 접근 수열을 순회하면서 해당 값까지 스택에 push한다. 스택을 pop하여 같은지 확인한다. 풀이 from sys import stdin def get_operator(nums): stack = [] operator = [] i = 1 for num in nums: while i 2024. 1. 14.

티스토리툴바