본문 바로가기

Dev/BOJ

 (69)
[백준 1006] 습격자 초라기 DP 문제인데, 구현도 굉장히 빡빡한 문제. 문제를 천천히 읽다 보면 DP를 사용해야겠다는 것은 금방 떠오르는데, 그 이후가 말랑하지 않은 문제이다. 먼저 배치된 소대의 최소 개수를 구하는 점화식을 생각해주어야 하는데, 거꾸로 생각을 해보는 것이 편하다. 일단 원타곤이 원형 배열이라는 것은 인지만 한 상태로 점화식부터 빠르게 찾기 위해 직선의 2차원 배열로 생각한다. 그렇게 되면, N 및 2N번째 구역이 위치한 열까지 소대를 배치했을 때 그 최솟값을 도출해야 하는 하는 문제가 된다. 이때, 마지막 열을 채우는 케이스는 아래와 같다.  두 구역에 걸쳐 소대를 배치 가능한지 여부는 매번 W값과 인접한 적의 합을 통해 판별할 수 있고, 결국 매번 메모이제이션을 통해 저장해두어야 하는 것은 이전까지 소대가 배치..
[백준 17144] 미세먼지 안녕! 구현 문제다. 크게 복잡하거나 어려운 부분은 없는데, 오히려 메모리 아끼겠답시고 포인터를 이용하다가 for문 안에서 선언해 둔 로컬 레퍼런스를 그대로 이용해서 갱신하는 바람에 문제가 좀 생겼다. for문 안에서 일반 vector타입으로 선언해도 힙 영역에 할당된 메모리 공간은 따로 릴리즈 해주지 않는 이상 계속 살아있을 줄 알았는데, 디버깅하면서 메모리 공간을 보니까 vector 레퍼런스가 날아가면서 힙 영역도 같이 릴리즈 되는 것 같았다. 그래서 그 임시 vector를 for문 밖으로 빼버리고 아예 그쪽도 포인터로 선언해서 new로 직접 메모리를 할당해줬더니 문제없이 돌아갔다.  문제에 대한 로직은 나와있는 그대로 구현했다. R과 C의 크기가 최대 50이고, T도 최대 1,000이기 때문에 매 초마다 ..
[백준 12850] 본대 산책2 수학과 분할 정복을 이용하는 문제. D의 크기가 최대 1,000,000,000이기 때문에 O(n)인 DP로 해결하려고 해도 시간초과가 날 것이다. 그래서 다른 방법을 생각해보아야 한다.  먼저 특정 건물 i에서 특정 건물 j로 이동하는 경로 수를 matrix[i][j]에 저장하겠다고 생각했다. 이걸 1분을 소모했을 때를 기준으로 만들게 되면 이는 인접 행렬이 된다. 그렇다면 2분을 소모해서 특정 건물 i에서 i로 돌아오는 방법은 어떻게 구할 수 있을까를 생각해보았다. 이는 가능한 모든 j에 대해, 1분에 걸쳐 건물 i에서 j로 이동하는 경로 수 * 1분에 걸쳐 건물 j에서 i로 이동하는 경로 수를 모두 합친 것으로 생각할 수 있다. 가만히 보고 있으면 알 수 있듯이, 이는 행렬 곱 형태이다. 이후의 n분..
[백준 13913] 숨바꼭질 4 BFS 문제. 같은 시리즈인 숨바꼭질 3 문제를 풀고, 뭔가 아쉬워서 다음 넘버링이 있는지 찾아보니 있어서 이것도 풀었다. 문제가 단순해서 그냥 BFS를 사용하면 바로 풀린다. 숨바꼭질 3 같은 경우에는 순간이동에 걸리는 시간만 0초라서 우선순위 큐와 다익스트라를 이용했었는데, 이 문제는 모두 같은 시간이 걸리므로 일반적인 큐와 BFS를 사용했다. 이동 경로를 출력해야 하는 부분이 있어서, 직전 노드를 저장해두는 prev 배열을 따로 선언해서 BFS 내에서 처음 노드 방문 시에 함께 갱신해주었다.  사실 위 문제를 풀면서 다른 부분에서 애를 좀 먹었는데, prev 배열을 이용해서 최종 경로를 역추적 하는 과정에서 살짝 미스가 있어서 원인을 한참 찾았다. 혹시 본인이 작성한 BFS를 사용하는 본 로직에는 ..
[백준 1865] 웜홀 그래프 이론 문제다. 그래프 이론이나 탐색 문제는 내가 좋아하는 유형이라서 재밌게 풀었다. 웜홀은 비용이 음수인 간선으로 생각할 수 있고, 다시 출발지로 돌아왔을 때 비용 총합이 음수가 되는 경우라면 그래프 내에 음수 사이클이 존재할 때임을 쉽게 짐작할 수 있다. 따라서 그래프 내의 음수 사이클을 쉽게 찾아낼 수 있는 벨만-포드 알고리즘을 채택해서 문제를 해결했다. 간선 정보는 정점의 개수가 작고, 경로가 중복되는 간선을 쉽게 처리하기 위해서 인접 행렬을 이용해 저장했다. 그리고 문제에서 연결 그래프임을 보장하고 있지 않으므로 모든 정점을 시작점으로 해봐야 하는데, 그렇게 되면 정점의 수와 연결 상태에 따라 시간 초과가 날 우려가 있다. 나는 이를 막기 위해서, 각 정점별 벨만-포드 알고리즘 과정에서 한..
[백준 16566] 카드 게임 원래 분리 집합이랑 이진 탐색으로 푸는 문제인데, 나는 Red-Black Tree 이용하는게 먼저 떠올라서 C++의 set으로 풀었다. 전에 풀었던 공항 문제와 큰 차이가 없다. 정석으로 풀자면, 카드를 정렬해두고 이진 탐색으로 조건에 맞는 값을 찾는 방법이지싶다. 사용한 카드는 다음 인덱스에 위치한 더 큰 카드와 Union 처리해서, 원래 오래걸리는 삭제 처리 대신에 Union Find 로직의 시간 복잡도만 이용하게 될테니 얼핏 생각해도 타당하다.  내가 Red-Black Tree, 그러니까 C++ set을 사용하게 된 건 이론상 가능할 것 같아서였다. set에서 upper_bound를 찾아내는 것은 O(logM)만큼 걸릴 것이고, 찾은 노드를 삭제하는 과정도 O(logM)만큼 걸릴 것이다. 그리고 이..
[백준 28707] 배열 정렬 핵심적인 부분을 떼놓고 보면 그래프 탐색 문제이다. 배열의 상태는 하나의 노드로 생각할 수 있고, 비내림차순 정렬된 상태를 목적 노드로 생각할 수 있다. 목적 노드는 0개일 수도, 여러 개일 수도 있으며, 각 노드에서는 항상 조작의 개수만큼의 간선을 가지게 된다. 이 때 목적 노드까지 최소 비용으로 도달하는 경우를 찾는 것이기 때문에, 이는 결국 최단 거리 문제라고 할 수 있다. 따라서 BFS나 다익스트라 알고리즘을 고려해볼 수 있다.   위 부분은 크게 문제될 게 없으니, 이제 남은 것은 배열의 상태를 노드로 나타내는 것이다. 결국 그래프 탐색을 진행하려면 각각의 노드 방문 여부를 체크할 수 있어야 하기 때문이다. 배열은 최대 길이가 8이고, 이를 각 자릿수의 정수로 인덱싱하면 크기가 76,543,21..
[백준 20303] 할로윈의 양아치 알고리즘 몇 가지를 섞어서 접근해야 하는 재밌는 문제다. 딱 학부수준에서 다루는 알고리즘들을 적절하게 도입해서 해결할 수 있는데, 나 같은 경우에는 Union Find와 0-1 Knapsack Problem을 응용해서 해결했다.   문제를 천천히 읽어보면, 한 아이의 사탕을 뺏는 것은 친구관계로 연결된 모든 아이의 사탕을 한 번에 뺏는 것과 같다. 따라서 친구관계로 연결된 아이들의 집합을 찾아서 미리 소속된 아이 수와 아이들이 가진 사탕의 합을 찾아두면 빠르게 구할 수 있다. BFS같은 그래프 탐색을 이용해도 되고, 나는 Union Find를 사용했다.  그렇게 친구끼리 묶은 집합 정보를 알아내고 나면, 이제 각 집합을 최적으로 선택해서 제한 아이 수 이내로 최대 사탕 수를 획득해야 함을 알 수 있다. ..

티스토리툴바