본문 바로가기

Dev

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

티스토리툴바