https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업 - 깊이 우선 탐색 5 정점 1번에서 정점 2번을 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 3번에서 정점 4번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 3, 4, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이 우선 탐색 1번 + 3번이라고 볼 수 있습니다. 방문 순서를 체크하는 1번과 깊이를 체크하는 3번을 잘 풀었다면 쉽게 푸실 수 있을 겁니다. 개념 자체는 1-2번, 3-4번과 동일합니다. 오름차순으로 방문할 경우, 방문 순서는 1 -> 2 -> 4 ->..

https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이우선탐색 1, 2번이 몇 번째로 방문했는지를 출력하는 것이라면, 깊이우선탐색 3, 4번은 깊이(depth)를 출력하는 문제입니다. 트리의 경우, 탐색 순서가 어떻든간에 각 노드의 깊이는 모두 동일하겠지만, 해당 문제는 사이클이 존재할 수 있는 그래프에서의 D..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 알고리즘 수업 - 깊이 우선 탐색 1과 비슷한 문제입니다. https://uknowblog.tistory.com/323 [백준 24479번] [Kotlin] 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/p..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 모든 별을 선으로 이어 별자리를 만드는 문제입니다. 별자리를 잇는다는 건, 두 별을 직선으로 이은 것이며, 모든 별자리는 직/간접적으로 서로 이어져 있어야 합니다. 별을 이을 때 거리만큼의 비용이 들 때, 모든 별을 직/간접적으로 이으면서 그 비용이 최소가 되는 경우를 찾아야 합니다. "모든 별(노드)를 선으로 직/간접적으로 이으면서..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 데이크스트라, 0-1 너비 우선 탐색 설명 시작점 (0,0)에서 도착점 (n,m)으로 가려면 얼마나 많은 벽을 부셔야 하는지 구하는 문제입니다. 특이하게도 시작점에서 도착점으로 가는 비용이나 거리가 아닌, 얼마나 많은 벽을 부셔야 하는가를 구하는 문제입니다만, 최단 경로 하면 떠오르는 BFS, 다익스트라를 응용하여 풀 ..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 삼성 기출문제로도 유명한 상어 시리즈 중 상어 중학교 입니다. 다른 상어 시리즈와 마찬가지로 시뮬레이션 + 그래프(탐색 및 백트래킹) + 배열 뒤집기가 인상적이였던 문제였습니다. 계속 테스트케이스가 다르게 나왔는데, 시뮬레이션 문제 특성 상 한 회차당 맵이 어떻게 바뀌는지 확인해야 하기 때문에 엑..

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 각 플레이어 i는 한 턴에 S(i) 거리 만큼 확장을 할 수 있습니다. 각 플레이어 별로, 그리고 한 싸이클씩 그래프 탐색을 진행하는게 포인트라 할 수 있습니다. 예제중 하나를 가져와봤습니다. 초기 상태가 아래와 같고, 플레이어 1이 2칸, 플레이어 2가 1칸씩 움직일 수 있는 경우입니다. 1..1 .... .... ..

https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지 19일차 : 대체 경로 구름톤 알고리즘 챌린지 19일차 문제인 대체 경로 입니다. 1일부터 n일까지, i일에는 i번째 도시가 공사를 한다고 하였을 때, 해당 도시가 공시중일 때 시작 도시에서 도착 도시로 가는 최단 경로를 찾는 문제였습니다. 단순 최단 경로라면 BFS를 사용한 최단경로 찾기 기법을..

https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지 18일차 : 중첩 점 18일차 문제인 중첩 점입니다. 바둑판 모양의 정사각형이 있습니다. 한 사각형을 중심으로 상,하,좌,우로 직선을 그리는데요. 각 직선이 교차하면서 생기는 점들의 총 개수를 구하는 문제입니다. 각 칸의 점의 개수를 구하는 방법은 간단합니다. 바로 해당 칸의 수직선 * 수평선의 ..

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 정수론, 소수판정, 에라토스테네스의채 설명 상당히 어려웠던 문제였습니다 그냥 단순히 입력으로 주어지는 연산을 그대로 했더니 당연하게 시간초과 발생하였고, *, / 연산을 각각 리스트로 만들어 6 -> 2 * 3, 10 -> 2 * 5와 같이 소인수 분해 한 후, 각각에 리스트에 넣어준 뒤 (첫 항은 *로 처리), * 연산이 남아있으면 유리수, / 연산이 남아있으면 유리수로 판단하였습니다. 6 / 4 = (3 * 2) / (2 * ..