👨💻📱✍️🎢314 BOJ 2252 - 줄 세우기 문제 백준 온라인 저지 - 2252번 풀이 과정 위상 정렬 을 활용한 해법으로 해결할 수 있는 문제입니다. 다양한 방법이 있지만 DFS 를 활용해 위상 정렬 을 구현하는 것이 가장 간단해서 이 방법을 사용했습니다. 코드 import sys n, m = list(map(int, sys.stdin.readline().split())) adj = [[] for _ in range(n+1)] for _ in range(m): frm, to = list(map(int, sys.stdin.readline().split())) adj[frm].append(to) def dfs(here, visit, ans): visit[here] = 1 for there in adj[here]: if not visit[there]:.. 2021. 6. 7. BOJ 2231 - 분해합 문제 백준 온라인 저지 - 2231번 풀이 과정 어떤 분해합 결과가 자연수 N일때 이에 대한 생성자는 N보다 절대 클 수 없다는 점을 이용해 브루트 포스로 해결할 수 있는 문제입니다. 이는 한 자연수와 그 자릿수들의 합으로 N을 만들어야하기 때문입니다. 따라서 가능한 모든 수를 탐색하면서 가장 처음 발견되는 생성자를 반환해주면 됩니다. 코드 import sys N = int(input()) def separate_sum(N): temp = 0 for c in str(N): temp += int(c) return N + temp def solution(): answer = 0 for num in range(N): if N == separate_sum(num): answer = num break return.. 2021. 6. 7. BOJ 1916 - 최소비용 구하기 문제 백준 온라인 저지 - 1916번 풀이 과정 한 정점으로부터 다른 모든 정점까지의 경로 정보를 사용해 최단 거리를 구하는 문제입니다. 최악의 경우 V = 1000이고 E = 100,000 이므로 O(ElgV) 의 시간 복잡도를 가지는 다익스트라 알고리즘 을 사용해서 답을 구할 수 있습니다. 코드 import sys import heapq N = int(input()) M = int(input()) adj = [[] for _ in range(1001)] for _ in range(M): frm, to, cost = list(map(int, sys.stdin.readline().split())) adj[frm].append([to, cost]) start, goal = list(map(int, sys... 2021. 6. 7. BOJ 15684 - 사다리 조작 문제 백준 온라인 저지 - 15684번 풀이 과정 DFS 와 백트래킹 을 활용한 최적화가 필요한 탐색 문제입니다. 이때 사다리의 위치를 검사하는 과정에서 인덱스 범위에 대한 고려를 안해주기 위해 board 양쪽에 padding 을 추가했습니다. 이렇게 안하면 양쪽 사다리 위치 인덱스가 board 를 벗어나는지에 대한 조건문에 추가해줘서 코드가 복잡해집니다. 사다리를 2차원 배열로 표현했으므로 각 시작점에서 타고 내려올때는 왼쪽, 오른쪽에서 만나는 경우를 고려해줘야 합니다. 주의할 점은 수평 방향으로 이동했을 경우에는 바로 한칸 밑으로 전진시켜줘야합니다. (안그러면 무한 루프에 빠집니다.) DFS 를 수행하는 과정에서 만약 만족하는 조합을 찾았을 경우에는 이후 탐색을 수행하지 않고 바로 True 를 반환하.. 2021. 6. 7. BOJ 1781 - 컵라면 문제 백준 온라인 저지 - 1781번 풀이 과정 마감일을 고려하여 가장 많은 컵라면을 얻을 수 있는 방법을 찾는 그리디 문제입니다. 데드라인의 마지막 날부터 순회를 하면서 해당하는 날 이상의 날짜에 대해서 가장 많은 컵라면을 얻을 수 있는 것을 선택하면 됩니다. 이를 위해 우선 순위 큐 를 두 개 사용해서 하나는 데드라인의 내림차순으로, 다른 하나는 컵라면의 내림차순으로 정렬하여 사용합니다. 코드 import sys import heapq N = int(input()) questions = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] def init_queue(): pq = [] for deadline, cups in question.. 2021. 6. 7. BOJ 6118 - 숨바꼭질 문제 백준 온라인 저지 - 6118번 풀이 과정 시작 정점에서 다른 모든 정점까지의 거리 중 가장 긴 경로를 찾는 문제입니다. 다익스트라 알고리즘 을 활용하여 한 정점으로부터 다른 모든 정점까지의 최단 거리를 구한 다음, 가장 거리가 먼 정점을 찾아주면 됩니다. 이때 구현의 편의를 위해서 dist 배열을 거리값과 정점 번호순으로 정렬하여 답을 구했습니다. 코드 import sys import heapq INF = sys.maxsize N, M = list(map(int, sys.stdin.readline().split())) adj = [[] for _ in range(N+1)] for _ in range(M): frm, to = list(map(int, sys.stdin.readline().split(.. 2021. 6. 7. 이전 1 ··· 18 19 20 21 22 23 24 ··· 53 다음
