본문 바로가기

분류 전체보기

 (159)
[백준 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를 사용했다.  그렇게 친구끼리 묶은 집합 정보를 알아내고 나면, 이제 각 집합을 최적으로 선택해서 제한 아이 수 이내로 최대 사탕 수를 획득해야 함을 알 수 있다. ..
[백준 27172] 수 나누기 게임 수학 기반 구현 문제이다. N이 최대 100,000으로 모든 플레이어를 기준으로 브루트 포스를 사용하면 시간초과가 나고, 모든 결투를 기준으로 해도 시간 초과가 난다(n*(n-1)/2). 따라서 모든 경기를 계산하지 않아야 한다. 처음엔 좀 감이 오지 않았는데, 무승부인 경우 점수 변화가 없다는 부분에 주목해서 솔루션을 떠올렸다. 무승부가 아닌 경기만 점수 계산을 하면 되지 않을까? 하는 어프로치였다. 그렇다면 무승부가 아닌 경기를 어떻게 판별할 수 있을까만 생각하면 되었다. 그 해답은 간단한데, 플레이어가 가진 수를 인수로 가질 수 있는 수를 가진 플레이어와만 결투를 하면 된다. 서로소인 경우 무승부가 되고, 플레이어가 가진 수의 인수가 될 수 있는 수를 가진 플레이어와는 결투했을 때 점수의 변동이 있..
[백준 17143] 낚시왕 조금 타이트한 구현 문제다. 낚시 처리나, 상어끼리 잡아먹는 처리, 로직 흐름 등은 금방 떠올릴 수 있는데, 상어의 다음 위치를 구해내는 계산을 섬세하게 작성하지 않으면 틀리기 쉽다.  전체적인 로직의 흐름은 간단한데, 나는 우선순위 큐를 이용했다. 낚시꾼이 열을 하나씩 이동하며 상어를 낚아야하므로, 각 열 별로 상어 인스턴스를 담아둘 우선순위 큐를 만든다. 상어의 우선순위는 더 높은 행에 위치한 상어일수록 높고, 같은 행에 있다면 크기가 클수록 우선순위가 높게 한다. 이렇게 하면, 낚시꾼에게 낚아 올려질 상어를 찾아내는 것도 쉽고, 같은 칸에 위치한 상어 중에서 가장 큰 상어가 다른 상어를 잡아먹도록 하기도 편하다. 낚시꾼의 위치를 기준으로 반복문을 돌리는데, 그 안에서 상어 처리를 위해 모든 우선순위..
Compose 내에서 ConstraintLayout 사용하기, 컴포넌트 크기가 제약 범위 초과할 때 📌 필요했던 레이아웃 대략 이런 형태의 컴포넌트가 필요했는데, 이게 자식 컴포넌트 measuring과 실제 배치의 순서 때문에 만들기가 까다로웠다. 처음 시도한 것은 왼쪽의 책 컴포넌트와 오른쪽의 코멘트 및 작성 날짜가 담긴 Column을 한 Row에 배치하는 형태였는데, 이게 어디하나 사이즈를 고정해놓은 것이 아니라서 쉽지 않았다. Row의 height이 책 컴포넌트의 height을 wrap 하는 크기로 고정되고 우측의 column은 그 크기까지만 펼쳐지길 바랐는데, column에 fillMaxHeight()을 쓰면 바로 최대 높이로 커져버리고, 내부의 내용 Text에만 weight를 1f로 주는 방법도 사용해보았지만 결과는 같았다. 저 날짜는 제일 아래 쪽에 위치해야 하고, 내용은 위에서부터 날짜를..

티스토리툴바