백준10 [6개월 안에 백준 플래티넘 달성하기] 18. 중간 점검 | 백준 Class 문제 특징 | 문제 풀이 과정 공유 | 코테 팁 2023년 10월 1일부터 시작한 프로젝트가 벌써 3개월이 지났습니다. 현재까지의 진행상태와 풀이 경험에 대해 간단히 글을 남기고자 합니다. 현재 상태 새로운 아이디로 시작하여 0점에서부터 1290점 골드 2까지 점수를 올렸습니다. 물론 완전히 백지상태가 아니기 때문에 초반에는 점수를 빠르게 올릴 수 있었습니다. 하지만 과거에 포기했었던 구간부터는 난이도가 어느 정도 있는지라 하루에 한 문제씩 천천히 점수를 쌓아갔습니다. 78일 동안 매일매일 문제를 풀고 있습니다. 백준 Class 3까지는 그래도 하루에 여러 문제를 풀 수 있었는데 그 뒤로는 난이도 때문에 한 문제씩만 풀고 있습니다. Class 4까지 모든 문제를 풀었고 현재는 Class 5 문제를 풀고 있습니다. Class 단계별로 문제를 풀고 있지만.. 2024. 1. 2. [6개월 안에 백준 플래티넘 달성하기] 12. 최소비용 구하기 11779 최소비용 구하기 2 문제 다익스트라를 조금만 응용하면 간단히 풀 수 있습니다. 풀이 도시 A에서 도시 B까지 최단 거리만 보면 다익스트라로 풀 수 있을 거 같습니다. 하지만 다익스트라만으로는 최소비용을 구할 수 있지만 경로에 포함된 도시의 개수와 경로를 방문하는 도시 순서를 얻지 못합니다. 따라서 어느 정도 응용을 해주면 쉽게 풀 수 있습니다. 제가 생각한 방법은 각 도시별 최소 비용을 가지는 minDist 배열에 최단 거리 정보뿐만 아니라 이전 도시의 정보를 추가하는 것입니다. 해당 방법으로 다익스트라 알고리즘을 진행한 뒤에 minDist를 역추적하면 도시의 개수와 도시 순서를 알 수 있습니다. 구현 방법은 더 간단합니다. 기존 다익스트라에서 최소 비용이 갱신될 경우에 minDist에 갱신된 최소 비용.. 2023. 12. 30. [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 다음 반응형
