코틀린11 [6개월 안에 백준 플래티넘 달성하기] 11. 치즈 2638 | 코틀린 치즈 문제 풀이 모눈종이 맨 가장자리에 치즈가 놓이지 않는다는 조건이 있다. 따라서 치즈 외부 공기는 모두 연결되어 있다는 것을 알 수 있다. 이를 이용하여 가장자리에서 bfs를 돌면서 공기가 있는 위치에 2를 넣어준다. 모눈종이 전체 배열을 돌면서 치즈가 있을 경우 치즈의 4방향 중 2의 개수를 체크해 준다. 2의 개수가 2개 이상일 경우 사라지는 치즈이므로 큐에 담아준다. 큐가 빌 때 동안 사라지는 치즈의 위치에서 1번을 실행시켜 준다. 치즈가 전부 사라질 때까지 2번과 3번을 반복한다. 설명은 꽤 복잡하지만 코드로 보면 금방 이해되실 겁니다. import java.io.StreamTokenizer import java.util.LinkedList fun main() = StreamTokenizer(.. 2023. 12. 27. [6개월 안에 백준 플래티넘 달성하기] 10. 웜홀 1865 | 코틀린 웜홀 문제 문제 풀이 해당 문제는 한 지점 N에서 시작하여 다시 N까지 도달하였을 때 걸리는 시간이 음수가 나오는지 체크해 주는 문제이다. 즉 음의 간선이 존재하는 그래프 문제이므로 벨만포드를 응용하면 풀 수 있다. 벨만포드는 음의 간선과 음의 사이클이 존재할 경우 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 유용한 알고리즘이다. 풀이법은 다음과 같다. N(노드개수) 번 동안 모든 간선을 돌면서 최단 거리를 갱신해 준다. 이때 마지막 N번째에도 최단 거리가 갱신되면 음의 사이클이 존재한다고 판명한다. N개의 노드가 있을 때 특정 노드 X의 최대 간선은 N-1개이다. 따라서 최대로 갱신될 수 있는 횟수는 N-1번이다. 하지만 음의 간선으로 인한 사이클이 존재하는 경우 이보다 더 많이 갱신될 수 있.. 2023. 12. 27. [6개월 안에 백준 플래티넘 달성하기] 9. 최소비용 구하기 1916 | 코틀린 Class 4에서 처음으로 접하게 된 그래프 알고리즘인 다익스트라 문제입니다. 다익스트라의 기본 개념을 알고 있고 몇 개의 반례 케이스만 해결한다면 쉽게 풀 수 있습니다. 문제 풀이 사실 다익스트라에 대한 개념이 없어도 bfs + 우선순위 큐 를 잘 활용하면 문제를 풀 수 있습니다. A에서 B까지의 최소 비용을 구하기 위해서는 결국 A에서부터 BFS로 최소 비용을 구하면서 B에 도달하면 됩니다. 추가적으로 주의해야 할 반례 케이스가 두 가지 있습니다. 첫 번째로 버스 비용이 0인 경우가 가능합니다. 따라서 초기화 시점에 값을 0으로 지정하면 안 됩니다. 두 번째로 동일한 버스 노선에 여러 비용을 주는 경우가 있습니다. 이 경우에는 여러 비용 중 최소 비용을 추가하도록 코드를 수정해 주면 됩니다. 반례 모.. 2023. 11. 27. [6개월 안에 백준 플래티넘 달성하기] 8. 테트로미노 14500 | 코틀린 2023. 10. 25 ~ 2023. 11. 19 백준 솔브 CLASS3 문제 풀이 완료, 골드 5 Class 3까지 모든 문제를 클리어했습니다. Class 3에는 새로운 알고리즘 유형의 문제인 bfs, dfs, dp 문제가 많이 보였습니다. 아직까지는 해당 알고리즘 유형의 기본적인 문제만 있기에 큰 어려움 없이 해결할 수 있었습니다. 오히려 구현문제가 더 어려웠던 거 같습니다.결국 코테를 잘하는 방법은 [알고리즘 유형에 대한 이해 + 구현] 이 아닐까 싶습니다. 그런 의미에서 단순한 브루트포스 방법으로도 풀 수 있지만, 더 깔끔한 구현을 통해 더 좋은 해결책을 찾을 수 있는 테트로미노 문제를 가져오게 되었습니다. 문제 첫 번째 풀이 가장 무난한 방법은 N x M를 돌면서 테트리스의 모든 경우를 체크해 .. 2023. 11. 20. 이전 1 2 3 다음 반응형
