DFS 재활훈련 - return이 있는 DFS 작성하기 연습 + 트리의 경로 유일성 배우기

1. 문제1 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 풀이 A는 B의 친구이다 B는 C의 친구이다 C는 D의 친구이다 D는 E의 친구이다 이 말은 무슨말일까? A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말 주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것 깊이가 4이면 1을 return하고.. 깊이가 4가 아니면.. 탐색을 수행 현재 방문하는 점 x에 대한 방문처리 visited[x] = 1 x와 연결된 점 graph[x]에서 순회해..

• format_list_bulleted DFS BFS 정복기
• · 2023. 2. 13.
• textsms

BFS 최단경로 역추적하는 방법 배우기

1. 문제 24463번: 미로 (acmicpc.net) 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제 2. DFS 풀이 최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다 아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다 n,m = map(int,stdin.readline().split()) maze = [list(stdin.readline()...

• format_list_bulleted DFS BFS 정복기
• · 2023. 2. 7.
• textsms

골드바흐의 추측을 알고리즘 문제에 적용하는 방법

1. 문제 1153번: 네 개의 소수 (acmicpc.net) 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net 임의의 자연수가 소수 4개의 합으로 분해될 수 있는지 구하는 문제 2. 풀이 어떻게 푸는지 모르겠다면.. 브루트 포스로 접근해보는게 가장 현명하다 n이 주어질때 n을 4개의 소수의 합으로 분해하고 싶다면, n보다 작은 소수들로만 분해할 수 있을 것이다 n보다 작은 소수의 리스트를 에라토스테네스의 체로 구하고 이 체에서 4중 for문으로 4개를 선택해서 더해보고 n이 되는지 검사해서 찾기만 하면 바로 break해서 탈출하고 출력해준다 from sy..

• format_list_bulleted 정수론
• · 2023. 2. 6.
• textsms

최소 길이의 실만 사용해서 구슬을 원형으로 배열하는 놀라운 방법

1. 문제 25707번: 팔찌 만들기 (acmicpc.net) 25707번: 팔찌 만들기 N개의 구슬을 모두 사용하여 조건에 맞게 팔찌를 만들 때 사용하는 줄의 길이의 최솟값을 출력한다. www.acmicpc.net 2. 풀이 서로 인접하는 구슬 사이 차이가 최소가 된다면 전체 줄의 길이가 최소가 될 것 같다 구슬의 크기를 담은 리스트를 오름차순 정렬하면 서로 인접하는 값들의 차이가 최소가 될 것 0번 1번 차이 1번 2번 차이 2번 3번 차이 ... n-2번 n-1번 차이들의 합에 원형으로 배열하니까 마지막 n-1번과 0번의 차이도 구해서 더해주면 될 것 from sys import stdin n = int(stdin.readline()) ball = list(map(int,stdin.readline(..

• format_list_bulleted 애드 혹 알고리즘
• · 2023. 2. 4.
• textsms

union find 재활훈련 - union by size 복기하기

1. 문제1 4143번: Bridges and Tunnels (acmicpc.net) 4143번: Bridges and Tunnels The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 100,000. We assume that al www.acmicpc.net 2. 풀이1 서로 연결되는 간선이 주어질때마다 각 노드의 집합 크기를 구하는 문제 find..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 1. 31.
• textsms

게임이론 배우기 -소수 부르기 게임-

1. 문제 25632번: 소수 부르기 게임 (acmicpc.net) 25632번: 소수 부르기 게임 용태가 부를 수 있는 소수는 $11, 13, 17$이고, 유진이가 부를 수 있는 소수는 $13, 17, 19$이다. 둘 다 최선을 다해서 플레이한다면 $13 → 17 → 11 → 19$로 진행될 수 있다. 용태가 더 이상 부를 소수가 www.acmicpc.net 2. 풀이1 두 플레이어가 주어진 범위 a,b와 c,d에서 각각 소수를 찾는다 만약 승리를 위해 최선을 다해서 플레이한다면, 어떻게 해야 할까 핵심 규칙은 이미 부른 소수는 부르지 못한다는 것이다 그러므로 상대가 가지고 있는 소수를 내가 먼저 부른다면, 상대가 가지고 있는 소수를 부르지 못하게 하면서 동시에 나는 턴을 넘기므로 매우 유리해진다 따라..

• format_list_bulleted 게임이론
• · 2023. 1. 30.
• textsms