cpp
-
[백준 BOJ/C++] 1461 도서관알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:28
1461번: 도서관 전형적인 그리디 알고리즘 문제이며 단순하다면 단순한 편이지만 처음 접했을 때 문제를 정확히 이해하지 못했었다. 쉬운 편의 문제라고 할 수 있겠지만 문제 설명이 자세하고 친절하지는 않은 편이라 헤맬 수 있는 문제다. 1차원 수평선 위 0에서 시작해 음수와 양수 구간을 효율적으로 이동시키도록 하는 문제다. 한번에 옮길 수 있는 책 수의 제한이 있어서 다시 시작점인 0으로 돌아오는 것을 고려해야 하는데 마지막에는 돌아오지 않아도 된다. 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 한번에 이동시킬 수 있는 책의 수 돌아오는 구간과 마지막 구간 선택 음수 구간과 양수 구간의 표현 한번에 이동시킬 수 있는 책의 수 수평선에서 좌,우로의 이동을 이용하는 문제이므로 우선 그림과 같..
-
[백준 BOJ/C++] 1092 배알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:03
1092번: 배 전형적인 그리디 알고리즘 문제이지만 시간 초과 가능성을 고려해야 한다. 특별한 복잡한 스킬이 필요하진 않지만 그리드 적인 접근 방식을 연습하기 좋은 문제다. N대의 크레인에 M개의 박스를 최소 횟수로 옮기는 문제다. 각 크레인에는 무게 제한이 있어서 제한 내의 무게를 가진 박스만 옮길 수 있다. 크레인에 박스를 효율적으로 배분해서 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 그리디 알고리즘 시간초과를 피하는 방법 그리디 알고리즘 Greedy Algorithm은 사실 특별한 기술이나 전형적인 틀이 있는 유형은 아니다. 어찌보면 그만큼 발견이나 아이디어가 중요다고 할 수 있다. 그래도 그리드 알고리즘 문제를 여럿 풀다보면 어느정도 접근 방법에 대한 감을 기를 수 있다. 숫자..
-
[백준 BOJ/C++] 1774 우주신과의 교감알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:48
1774번: 우주신과의 교감 크루스칼 알고리즘을 연습해보기 좋은 문제다. 특별히 복잡하게 꼬아놓은 부분은 없는데 사전에 일부 간선만 주어지고 나머지 가능한 모든 간선을 추가하는 과정만 추가되었다. 입력으로 주어지는 모든 노드들 사이에 가능한 모든 간선들을 list up 하고 각 간선의 길이를 계산해두고 이를 토대로 크루스칼 알고리즘을 이용해 최소 신장 트리를 찾아주면 된다. 단, 입력으로 주어지는 이미 연결된 통로는 최소 신장 트리에 반드시 포함되어야 하며 새로 추가한 간선들의 길이의 합을 출력해야 한다. 문제의 포인트 최소 신장 트리를 구할 수 있는가? 간선의 길이는 주어지지 않는다. 최소 신장 트리 사이클 없이 모든 노드를 연결하는 최소 신장 트리 (MST, Minimum Spanning Tree)만..
-
[백준 BOJ/C++] 5719 거의 최단 경로알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:37
5719번: 거의 최단 경로 다익스트라 알고리즘을 통해 최단 경로를 찾아내는 전형적인 문제에서 살짝 꼬아서 난이도를 높인 문제다. 문제 이름에서 유추할 수 있듯 최단 경로를 제외한 그 다음 최단 경로를 찾아 그 길이를 출력해야 한다. 예를 들어 아래 그림과 같은 입력이 주어졌을 때 굵은 화살표로 표시된 최단 경로가 아니라 점선으로 표시된 그 다음 최단 경로를 찾아야 한다. 주어진 예제와 같이 최단 경로는 여러개일 수 있으며 이 경우 모든 최단 경로가 제외되어야 한다. 문제의 포인트 주어진 입력을 어떻게 그래프로 표현할 것인가? 최단 경로를 어떻게 찾고 어떻게 제외시킬 것인가? 그래프의 표현 입력은 다른 일반적인 그래프 문제와 같이 간선의 정보로 주어진다. 각 간선은 단방향이고 길이라는 가중치를 가지고 있..