본문 바로가기

분류 전체보기

 (159)
[백준 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긴 하지만, 처음 구상했던 디자인과 별반 차이는 없다. 동작이 중요했는데, 유저와의 상..
[백준 11401] 이항 계수 3 수학에 분할 정복이 더해진 문제다. 이항 계수 문제 자체는 PS에서 자주 등장하는 문제이지만, 보통은 파스칼 항등식 개념을 메모이제이션과 분할 정복으로 구현해서 풀 수 있느냐를 묻는다. 하지만 이 문제는 N과 K의 범위가 커서 메모이제이션을 활용하면 메모리 초과로 풀 수 없게 된다. 그렇다고 메모이제이션 없이 분할 정복만 사용하는 것은 시간 복잡도가 끔찍해지고, 조합론을 활용해서 풀려하면 분모든 분자든 오버플로우가 날 수 있다(모듈러 연산을 분자와 분모에 분배하는 것은 등식이 성립하지 않는다).  그래서 처음 시도했던 것은, 메모이제이션을 2차원 배열로 사용하지 말고 2차원 맵(unordered_map)을 사용해서 불필요한 공간 사용을 줄이는 것이었다. 거기에 이항 계수의 성질을 이용해서 k가 n/2보다..
[백준 10775] 공항 그리디 알고리즘과 분리 집합을 활용하는 문제..이지만 나는 그리디와 자료구조를 이용해서 풀었다. 풀고나서 다른 접근법을 찾아보다가 분리 집합을 이용한 풀이를 봤는데, 저렇게도 접근할 수 있었구나 싶어서 재밌었다.  문제에도 나와있듯이, 비행기 번호는 1번 게이트부터 해당 번호의 게이트까지 도킹할 수 있음을 의미한다. 따라서 각각의 비행기는 가능한 가장 번호가 큰 게이트에 도킹하는 것이 무조건 유리한 상황이고, 그리디 알고리즘을 적용할 수 있음을 생각할 수 있다. 비행기의 수가 최대 10^5대까지 입력으로 들어올 수 있고, 게이트의 수도 최대 10^5개까지 존재할 수 있다. 나이브하게 생각하자면, 비행기 하나하나에 대해 게이트 목록을 선형 탐색해 빈 게이트 중 선택할 수 있는 가장 큰 번호의 게이트를 찾는..
[백준 9527] 1의 개수 세기 수학 기반 구현 문제다. 구간 사이의 모든 이진수 형태의 자연수에 대해 하나하나 1의 개수를 구하면 시간 내에 풀 수 없다. DP를 활용한다고 해도 A가 1이고 B가 10^16를 생각해 보면 시간초과가 발생함을 알 수 있다. 이런 이진수 꼴을 활용하는 문제가 으레 그러하듯이, 최상위 비트가 1이고 나머지가 0으로 채워진 경우나 모든 비트가 1로 채워진 경우를 나열해서 관계식을 찾아내는 것이 중요하다.   나는 연속된 자연수에 대한 각각의 1의 개수와 이전까지 등장했던 1의 개수 합 등을 써보며 관계식을 찾으려 했다. 위처럼 1의 개수 누적합을 나열했을 때, 유의미한 관계식을 찾아냈는데 (2^n)-1의 등장 1 개수 누적합은 (2^(n-1))-1일 때 값의 2배에 2^(n-1)를 더한 값이다. 이렇게 글로..

티스토리툴바