코딩테스트/백준 코틀린31 [6개월 안에 백준 플래티넘 달성하기] 19. 스도쿠 2239 스도쿠 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 풀이 처음에 문제를 딱 보았을 때 막막하고 내가 모르는 어떤 수학 공식으로 풀어야 되는 건가 싶기도 하였습니다. 하지만 다행히도 해당 문제는 스도쿠의 크기가 9로 제한되어 있습니다. 따라서 가장 단순하게 모든 경우를 따져서 완전한 스도쿠를 만들어주기만 하면 됩니다. 0의 위치에 알맞은 숫자를 넣었다가 알맞은 숫자가 아니면 도로 빼줘야 되기 때문에 백트래킹 방식으로 코드를 구현해 주면 됩니다. 9의 제곱승의 시간 복잡도를 가지고 있기 때문에 시간.. 2024. 1. 4. [6개월 안에 백준 플래티넘 달성하기] 18. 중간 점검 | 백준 Class 문제 특징 | 문제 풀이 과정 공유 | 코테 팁 2023년 10월 1일부터 시작한 프로젝트가 벌써 3개월이 지났습니다. 현재까지의 진행상태와 풀이 경험에 대해 간단히 글을 남기고자 합니다. 현재 상태 새로운 아이디로 시작하여 0점에서부터 1290점 골드 2까지 점수를 올렸습니다. 물론 완전히 백지상태가 아니기 때문에 초반에는 점수를 빠르게 올릴 수 있었습니다. 하지만 과거에 포기했었던 구간부터는 난이도가 어느 정도 있는지라 하루에 한 문제씩 천천히 점수를 쌓아갔습니다. 78일 동안 매일매일 문제를 풀고 있습니다. 백준 Class 3까지는 그래도 하루에 여러 문제를 풀 수 있었는데 그 뒤로는 난이도 때문에 한 문제씩만 풀고 있습니다. Class 4까지 모든 문제를 풀었고 현재는 Class 5 문제를 풀고 있습니다. Class 단계별로 문제를 풀고 있지만.. 2024. 1. 2. [6개월 안에 백준 플래티넘 달성하기] 17. 도시 분할 계획 1197 도시 분할 계획 문제 풀이 문제의 조건은 다음과 같습니다. 양방향이다. 마을을 두 개의 분리된 마을로 분할한다. 마을과 마을 사이에는 길이 존재하지 않는다. 마을 내부의 임의의 두 집 사이에는 경로가 항상 존재한다. 마을 내부에는 최소 하나 이상의 집이 있다. 위 조건을 만족하면서 유지비의 합이 최소여야 한다. 조건이 다소 많아 처음에는 흠칫하였지만 임의의 두 집 사이에는 경로가 항상 존재하며 최소 유지비를 만들어야 된다는 것에서 쉽게 최소 신장 트리 알고리즘을 생각할 수 있었습니다. 풀이 방법은 다음과 같습니다. 전체 집을 대상으로 최소 신장 트리를 구합니다. (= 경로 최소화 작업) 간선들 중에 가장 큰 유지비를 가진 가중치를 하나 제거해 줍니다.(= 마을 분리 작업) 위의 두 단계만으로 문제를 해결.. 2024. 1. 2. [6개월 안에 백준 플래티넘 달성하기] 16. 최소 스패닝 트리 1197 최소 스패닝 트리 문제 풀이 최소 스패닝(신장) 트리 문제입니다. 모든 노드를 지나면서 사이클이 존재하지 않는 트리 중 간선의 합이 가장 낮은 트리를 찾으면 됩니다. 백준 class 4 문제를 모두 해결하신 분이라면 다익스트라 알고리즘을 살짝 응용하면 충분히 푸실 수 있을 겁니다. 저 또한 이처럼 해당 문제를 풀었고 이후 해당 풀이가 최소 신장트리를 구하는 프림 알고리즘이라는 것을 알게 되었습니다. 이 밖에도 크루스칼 알고리즘도 존재하는데 이 둘을 간략하게 설명드리겠습니다. 프림 알고리즘 최소 신장트리를 구하는 알고리즘입니다. 음의 간선이 존재하고 사이클이 존재할 때도 사용할 수 있습니다. 프림 알고리즘은 단순하게 노드를 하나씩 돌면서 최소 간선을 추가해 주는 방식입니다. 따라서 주로 문제에 주어진 간선.. 2024. 1. 1. 이전 1 2 3 4 5 6 7 8 다음 반응형
