본문 바로가기

Dev/BOJ

 (63)
[백준 28707] 배열 정렬 핵심적인 부분을 떼놓고 보면 그래프 탐색 문제이다. 배열의 상태는 하나의 노드로 생각할 수 있고, 비내림차순 정렬된 상태를 목적 노드로 생각할 수 있다. 목적 노드는 0개일 수도, 여러 개일 수도 있으며, 각 노드에서는 항상 조작의 개수만큼의 간선을 가지게 된다. 이 때 목적 노드까지 최소 비용으로 도달하는 경우를 찾는 것이기 때문에, 이는 결국 최단 거리 문제라고 할 수 있다. 따라서 BFS나 다익스트라 알고리즘을 고려해볼 수 있다.   위 부분은 크게 문제될 게 없으니, 이제 남은 것은 배열의 상태를 노드로 나타내는 것이다. 결국 그래프 탐색을 진행하려면 각각의 노드 방문 여부를 체크할 수 있어야 하기 때문이다. 배열은 최대 길이가 8이고, 이를 각 자릿수의 정수로 인덱싱하면 크기가 76,543,21..
[백준 20303] 할로윈의 양아치 알고리즘 몇 가지를 섞어서 접근해야 하는 재밌는 문제다. 딱 학부수준에서 다루는 알고리즘들을 적절하게 도입해서 해결할 수 있는데, 나 같은 경우에는 Union Find와 0-1 Knapsack Problem을 응용해서 해결했다.   문제를 천천히 읽어보면, 한 아이의 사탕을 뺏는 것은 친구관계로 연결된 모든 아이의 사탕을 한 번에 뺏는 것과 같다. 따라서 친구관계로 연결된 아이들의 집합을 찾아서 미리 소속된 아이 수와 아이들이 가진 사탕의 합을 찾아두면 빠르게 구할 수 있다. BFS같은 그래프 탐색을 이용해도 되고, 나는 Union Find를 사용했다.  그렇게 친구끼리 묶은 집합 정보를 알아내고 나면, 이제 각 집합을 최적으로 선택해서 제한 아이 수 이내로 최대 사탕 수를 획득해야 함을 알 수 있다. ..
[백준 27172] 수 나누기 게임 수학 기반 구현 문제이다. N이 최대 100,000으로 모든 플레이어를 기준으로 브루트 포스를 사용하면 시간초과가 나고, 모든 결투를 기준으로 해도 시간 초과가 난다(n*(n-1)/2). 따라서 모든 경기를 계산하지 않아야 한다. 처음엔 좀 감이 오지 않았는데, 무승부인 경우 점수 변화가 없다는 부분에 주목해서 솔루션을 떠올렸다. 무승부가 아닌 경기만 점수 계산을 하면 되지 않을까? 하는 어프로치였다. 그렇다면 무승부가 아닌 경기를 어떻게 판별할 수 있을까만 생각하면 되었다. 그 해답은 간단한데, 플레이어가 가진 수를 인수로 가질 수 있는 수를 가진 플레이어와만 결투를 하면 된다. 서로소인 경우 무승부가 되고, 플레이어가 가진 수의 인수가 될 수 있는 수를 가진 플레이어와는 결투했을 때 점수의 변동이 있..
[백준 17143] 낚시왕 조금 타이트한 구현 문제다. 낚시 처리나, 상어끼리 잡아먹는 처리, 로직 흐름 등은 금방 떠올릴 수 있는데, 상어의 다음 위치를 구해내는 계산을 섬세하게 작성하지 않으면 틀리기 쉽다.  전체적인 로직의 흐름은 간단한데, 나는 우선순위 큐를 이용했다. 낚시꾼이 열을 하나씩 이동하며 상어를 낚아야하므로, 각 열 별로 상어 인스턴스를 담아둘 우선순위 큐를 만든다. 상어의 우선순위는 더 높은 행에 위치한 상어일수록 높고, 같은 행에 있다면 크기가 클수록 우선순위가 높게 한다. 이렇게 하면, 낚시꾼에게 낚아 올려질 상어를 찾아내는 것도 쉽고, 같은 칸에 위치한 상어 중에서 가장 큰 상어가 다른 상어를 잡아먹도록 하기도 편하다. 낚시꾼의 위치를 기준으로 반복문을 돌리는데, 그 안에서 상어 처리를 위해 모든 우선순위..
[백준 20040] 사이클 게임 문제의 이름에서도 예상할 수 있듯이 Disjoint Set(Union-Find) 문제다.  디테일한 요구 사항은 따로 없어서, 일반적으로 구현하는 Union Find를 그대로 이용하면 된다. 선택된 두 점이 이미 같은 집합 내에 있는 경우, 잇게 되면 사이클이 발생하므로 처음으로 선택된 두 점이 이미 같은 집합인 경우를 찾아내면 된다.  나는 Union 로직에서 이미 두 점의 루트 노드를 Find 하게 되므로 그때 비교한 결과가 같다면 false를 리턴하도록 해 판별했다. 다만 n이 최대 500,000이고 m이 최대 1,000,000이라, 경로 압축 정도는 적용해주어야 한다. 안 그러면 Find 연산이 최악의 경우 O(n)에 근사하기 때문에 제 시간 내에 풀리지 않을 것이다. #include #incl..
[백준 17404] RGB거리 2 DP 문제이다. 직관적으로 떠오르는 DP 로직을 그대로 적용할 수 있다. 집에 칠한 색별로 비용을 나눠서 저장하고, 다음 집을 칠할 때 이것을 참고해서 겹치지 않는 색 구성으로 최소 비용을 도출하는데에 이용한다. 만약 i번 집을 빨강으로 칠하려는 경우의 DP 테이블 값을 구하려 한다면, i-1번 집을 초록으로 칠한 최소 비용과 파랑으로 칠한 최소 비용 중 더 작은 값에 i번 집을 빨강으로 칠하는 비용을 더한 값이 될 것이다.  하나 까다로운 조건이 있다면, 결국 집이 일종의 원순열 형태로 놓여져있다고 생각해야 한다는 점이다. N번 집을 칠할 때는 1번 집의 색을 고려해야 하는데, 위와 같은 DP 테이블의 경우 이전 집의 색은 알 수 있으나 1번 집에 대한 정보는 소실된 상태가 된다.  그래서 나는 애초부..
[백준 16946] 벽 부수고 이동하기 4 그래프 탐색 문제로, 내가 좋아하는 문제 시리즈 중 하나다. 가장 먼저 직관적으로 떠올릴 수 있는 알고리즘은 모든 벽이 있는 칸에서 DFS나 BFS를 돌리는 것이겠지만, 조금만 생각해 봐도 시간 초과가 날 수 있음을 예상할 수 있다. N과 M이 모두 1,000이고, 0번째 행과 999번째 행이 모두 벽, 나머지 공간에는 벽이 없는 경우를 생각해 보면 된다. 혹시나 시간이 초과될만한 예시를 당장 떠올리지 못했더라도, 시간 복잡도가 명확하게 가늠되지 않는 알고리즘은 사용하지 않는 것이 좋다.  해결 방법은 심플한데, 맵을 먼저 탐색하며 빈칸 집합끼리 나눠주고 그 영역에 존재하는 빈 공간 수를 저장해 둔다. 그리고 실제 결과를 출력하기 위한 탐색을 용이하게 만들기 위해서 빈칸이 소속된 영역을 레퍼런싱 할 수 ..
[백준 16724] 피리 부는 사나이 DFS와 Union Find를 활용하는 문제. 각 노드가 진행하는 방향도 단방향이고, 지도 밖으로 나가는 방향의 입력도 주어지지 않는다. N과 M의 크기도 최대 1,000이라서 최대 노드의 수 또한 1,000,000이다. 조건이 꽤나 친절하다.  각 노드를 탐색하면서 방문 체크를 해가며 DFS를 돌리게 되면 사이클이든 아니든 끝에 도달하게 되고, 그 경로 상에 있는 모든 노드는 같은 집합으로 처리해 준다. 집합 내에서는 어디서 출발하든 공통적으로 도달하게 되는 한 노드가 있기 때문에, 한 집합에는 하나의 SAFE ZONE만 두면 된다. 한 노드에 대해 DFS를 끝냈다면 다음 노드를 탐색하는데, 이 때 방문한 노드라면 이전 탐색 과정에서 어떤 집합에 속하게 된 것이므로 DFS를 추가적으로 할 필요가 없다...

티스토리툴바