티스토리챌린지3 [파이썬, 자바] 백준 - 1167 (BFS) https://www.acmicpc.net/problem/1167 처음 이 문제를 풀 때는 트리의 지름을 구하는 원리를 몰라서 모든 정점에서 탐색을 하여 가장 길이가 긴 것을 찾도록 하였으나 당연히 시간 초과.. 트리의 지름을 구하는 원리는 이 분의 글을 보고 이해했다.https://blogshine.tistory.com/111 HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함" data-og-host="blogshine.tistory.com" data-og-source-url="https://blogshine.tistory.com/111" data-og-url="https://blog.. 2024. 11. 27. [파이썬, 자바] 백준 - 13023 (DFS, 백트래킹) https://www.acmicpc.net/problem/13023 처음에는 그냥 0번부터 탐색을 시작해서 5명이 채워지면 1을 출력하면 된다고 생각했다. 그러나 2번 예제를 보면,5 5 # N, M0 11 22 33 01 40부터 탐색을 시작하면, 0 -> 1 -> 2 -> 3으로 최대 4명밖에 탐색할 수 없다. 그러나 2부터 탐색을 시작한다면, 2 -> 3 -> 0 -> 1 -> 4로 5명을 탐색할 수 있다. 때문에 메인 함수에서 탐색을 할 때, 0번만 탐색하고 끝날 것이 아니라 0번부터 N - 1번까지 모두 탐색을 해줘야 한다. (물론 위의 예제의 경우, 양방향 그래프로 값들을 저장한다면 0만 탐색해도 5명을 탐색할 수 있다. 하지만 그렇지 않은 경우도 있다는 거..) 라고 생각을 했는데.. 문제에.. 2024. 11. 25. [Alogorithm - Python, Java] 백준 2023 - 신기한 소수 (DFS, 백트래킹, 에라토스테네스의 체) https://www.acmicpc.net/problem/2023 이전에 틀렸던 문제를 다시 한 번 풀어봤다. 두 번째라 그런지 풀이법은 금방 생각났다. 1. 첫 번째 자릿수부터 시작해서 다음 자릿수가 추가될 때마다 소수 판별을 한다. -> DFS 사용2. 소수 판별이 끝난 숫자의 자릿수가 N이 되면, 문제 조건을 만족했기 때문에 더 이상 탐색을 진행할 필요가 없으므로 return -> 백트래킹 사용 Code(Python)import sysinput = sys.stdin.readlinedef erato(n): # 소수 판별 함수(소수이면 True, 아니면 False) for i in range(2, int(n**0.5) + 1): # 에라토스테네스의 체를 사용하여 소수 판별 if n %.. 2024. 11. 21. 이전 1 다음