https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어 첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 데이크스트라, 플로이드–워셜 설명 다익스트라 혹은 플로이드 워셜을 응용해 풀 수 있는 문제입니다. 계속 틀렸습니다를 받아서 질문게시판을 들여다봤는데, 아니나 다를까 지문이 불친절하다는 의견이 잔뜩 있었습니다... 질문게시판들을 둘러보며 지문을 몇 번이고 다시 읽어봤는데, 해당 조건을 하나씩 적용하면서 ..
https://www.acmicpc.net/problem/24484 24484번: 알고리즘 수업 - 깊이 우선 탐색 6 정점 1번에서 정점 4번을 방문한다. 정점 4번에서 정점 3번을 방문한다. 정점 3번에서 정점 2번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 4, 3, 2, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 깊이 우선 탐색, 정렬, 그래프 탐색, 그래프 이론 설명 깊이 우선 탐색 1-2번 + 3-4번을 합친 형태면서, 깊이 우선 탐색 5번의 내림차순 방문 버전입니다. 1~5번을 푸신 분들이라면 별로 어렵지 않게 푸실 수 있을 문제입니다. 1번 노드 2번 노드 3번 노드 4번 노드 5번 노드 6번 노드 순서 1 4 2 ..
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/24482 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 트리의 경우, 탐색의 방문 순서에 관계없이 동일한 깊이를 가지겠지만, 문제에서 주어지는 그래프는 사이클이 있을 수 있는 그래프이기 때문에, 깊이 우선 탐색으로 탐색할 경우 탐색 순서(번호가 작은 노드부터 / 번호가 큰 노드부터)에 따라 각 노드의 깊이가 달라질 ..
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..
Github Actions Github Actions란, Github에서 제공하는 DevOps, CI/CD (지속적 통합/지속적 배포) 도구입니다. Github Actions를 사용하여 Github 저장소의 빌드, 테스트, 배포 등을 자동으로 하는 도구입니다. 여러 Workflow를 자동화하고, 다양한 이벤트 트리거에 따라 작업을 처리할 수 있습니다. 커밋이 될 때 혹은 develop branch와 main branch가 병합될 때, 자동으로 테스트 코드를 행하여, 테스트 코드가 성공한다면 배포를 한다거나, 특정 주기마다 스크립트를 실행하는 상황에 쓰이곤 하는데, 저는 이번엔 커밋이 될 때 마다 README.md를 업데이트 하는 용도로 써보겠습니다. Github Action 권한 설정 [Github 레포..
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, 다익스트라를 응용하여 풀 ..