Algorithm/Baekjoon117 13913. 숨바꼭질 4 (Python) 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 통해서 탐색을 하는데 전체적으로는 숨바꼭질 2(풀이 링크)와 비슷하다. 차이점은 숨바꼭질 2는 경우의 수를 카운트하는데 숨바꼭질 4는 하나의 케이스에 대해서 경로를 출력해야 한다. 처음에는 최소힙에 리스트 형태로 경로를 담아두고 최소 시간으로 동생의 위치에 도착했을 때 최소힙에 담겨 있던 경로 정보를 꺼내서 그대로 출력하게 했다. 이럴 경우 시간초과가 발생하는데 이는 수빈이와 동생의 위치가 멀리 떨어져 있을 때 경로.. 2022. 7. 4. 16938. 캠프 준비 (Python) 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 조합을 사용해서 모든 경우의 수를 구하고 조건을 만족하는 경우의 수만 카운트 해주면 되는 간단한 문제였다. 조합을 사용해서 풀면 딱히 설명할게 없음 코드 from itertools import combinations if __name__ == '__main__': N, L, R, X = map(int, input().split()) problems = list(map(int, input().split())) problemNum = [i for i in range(N)] res = 0 for i in range(2, N + 1): selectedProblems = list.. 2022. 7. 4. 2109. 순회강연 (Python) 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 뒤에 날짜부터 앞으로 이동해가며 현재 날짜에 강연할 수 있는 강연 리스트 중 가장 높은 강연료를 받을 수 있는 강연을 선택하도록 구현하면 된다. 이를 위해 두 개의 최소힙을 사용하여 하나의 힙에는 모든 강연을 담아두고 뒤에 날짜에 있는 강연들을 하나씩 꺼내가며 현재 날짜에 강연이 가능한 강연들의 강연료에 대하여 또 다른 최소힙에 담아주고 날짜가 바뀔 때마다 해당 최소힙에서 가장 높은 강연료를 꺼내어 더해나간다. 코드 im.. 2022. 7. 3. 13023. ABCDE (Python) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 dfs를 사용하여 깊이가 5인 경우가 있는지를 체크하면 된다. 방문체크 부분에서 주의할 건 재귀함수 내에서 방문했던 지점에 대해서 False 처리를 해줘야 한다는 것이다. 그렇지 않으면 모든 경로를 탐색할 수 없게 되어 깊이가 5인 경로가 있음에도 해당 경로를 찾지 못하는 반례가 생길 수 있다. 코드 import sys input = sys.stdin.readline # n: 현재 사람 번호, depth: 깊이 def dfs(n, depth): if depth == 5: # 깊이가 5인 지점에 도달하면 1출력하고 프로그램 종료 print('1') sys.exit.. 2022. 6. 30. 4386. 별자리 만들기 (Python) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 모든 별들이 사이클이 없는 그래프로 연결되어 있으면 된다. 즉, N개의 별이 있을 때 N-1개의 간선을 사용하여 연결하는 최소 스패닝 트리를 구하면 된다. 최소 스패닝 트리를 만들기 위해서 사용되는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 일반적으로 크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을 때 사용하면 좋고 프림 알고리즘은 정점에 비해 간선의 개수가 많을 때 사용하면 좋다. 해당 문제는 모든 별들끼리의 길이를 구한 후 최소 스패닝 트.. 2022. 6. 27. 4803. 트리 (Python) 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 dfs를 통해서 연결된 그래프에 사이클이 있는지를 판단한다. 현재 정점과 연결되어 있는 정점 중 이미 방문한 정점이 있다면 이는 사이클이 존재하는 그래프임을 의미하므로 트리가 될 수 없다. 한 가지 주의할 건 dfs 함수를 호출할 때 현재 정점으로 오기 전에 있었던 정점의 정보를 같이 전달해서 사이클 유무를 판단할 때 해당 정점을 제외하고 판별할 수 있게 해야 한다. 코드 import sys input = sys.stdin.readline.. 2022. 6. 26. 이전 1 2 3 4 5 ··· 20 다음
