본문 바로가기

Dev

 (90)
[백준 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)를 더한 값이다. 이렇게 글로..
상위 Composable이 관리하는 State 주입 받아 이용하는 Modifier 내 로직이 계속 초기 값을 레퍼런싱 할 때 개인 프로젝트에 드래그 가능하고 탭도 가능한 RatingBar가 필요해서 커스텀 중인데, 꽤 쉽지가 않았다. 안드로이드 View 위젯들을 사용할 때는 RatingBar가 따로 있었으나, Compose에는 유사한 기본 Composable이 제공되지 않아 커스텀해야 했다. 그래도 얼추 드래그와 탭을 모두 구현해 두고, 이를 블로그에 쓰려고 테스트해보고 있었는데 문제가 발생했다.   구조 및 증상  일단 RatingBar Composable에 rating 값과 onRatingChanged 콜백이 전달되는데, 이 rating 값은 하위 컴포넌트들에 전달되어서 적절하게 별점을 그리기 위해 사용되며, 드래그 제스처와 탭 제스처는 onRatingChanged를 트리거한다.    이를 테스트해 보기 위해서 Previe..
[백준 2568] 전깃줄 - 2 DP 문제다. 문제를 보다 보면 스토리를 만들어둔 LIS 문제임을 알 수 있다. 전깃줄을 A 전봇대와 연결되는 위치 순으로 정렬해서, B 전봇대에 연결되는 위치를 기준으로 LIS를 찾는 것과 같은 맥락이니까.  [백준 12015] 가장 긴 증가하는 부분 수열 2 (tistory.com)  [백준 12015] 가장 긴 증가하는 부분 수열 2아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 DP 문제인데, 직관적으로 떠올릴 수 있는 형태의 DP 알고리즘의 시간복잡도winterry.tistory.com  [백준 14003] 가장 긴 증가하는 부분 수열 5 (tistory.com)  [백준 14003] 가장 긴 증가하는 부분 수열 5일전에 풀었던..
[백준 2342] Dance Dance Revolution DP 문제이다. 순수한 브루트 포스는 O(2^n)에 해당하기 때문에 문제를 풀 수 없다. 처음엔 그리디를 이용할까 했으나, 1 4 3 4 와 같은 케이스서는 최적해를 보장할 수 없기 때문에 택할 수 없었다. 결국에는 모든 경우에 대해서 탐색을 진행해야 하는 케이스이며, 나는 DP를 이용하기로 했다. 지시 사항을 하나씩 순회하며, 이전의 발 상태 및 비용 값들로부터 발을 옮기는 케이스들을 하나씩 계산해 DP 테이블을 채우면 되겠다는 생각이 들었다. 지시 사항이 100,000개를 넘지 않고, 처음을 제외하곤 각 발판에 발이 하나씩만 놓일 수 있으므로 발판에 발을 둔 상태를 비트마스크로 표현한다면 5bit면 충분하다. 따라서 DP 테이블은 최대 2^5 * 100,000인 int 테이블이 되고, 시간 복잡도와 ..
[백준 2162] 선분 그룹 기하학 알고리즘 문제. 로직도 또렷하게 떠오르고, 여러 개념을 버무릴 줄 알아야 하는 문제라 좋은 문제였다고 생각한다. 일단, 저번에도 한번 다룬적 있는 벡터의 외적을 활용한 CCW 알고리즘을 핵심으로 활용한다. 해당 알고리즘을 활용해서 두 선분이 만나는지 판별하는 것은 쉬운 일이지만, 이 문제에서는 만나는 선분끼리 그룹으로 분할한 정보를 알아내야 한다. 그러다보니 주의해야 할 케이스가 예제 1번과 같은 케이스이다.   저런 케이스의 경우 1번 선분과 2번 선분만 입력되었을 때는 서로 다른 집합에 속하지만, 3번 선분이 더해지면서 같은 집합에 속하게 된다. 따라서 단순하게 앞서 등장했던 선분 집합에 대해, CCW를 통해 겹치는 선분이 존재하는 경우를 하나 찾아 그 집합에 해당 선분을 더해주는 방법은 적절..
Compose TextField 이용할 때 소프트 키보드와 포커스 처리하기 혼자 진행 중인 프로젝트를 한참 만들어 나가다가, 오랜만에 사소하게나마 새로 알게 된 것이 생겼다. 프로젝트 내에서 TextField를 이용해 커스텀한 SearchBar composable을 만들게 되었는데, 막히는 부분이 생겼다.   나는 위의 상태였던 SearchBar가 포커스를 얻으면(정확히는 처음 포커스를 얻는 순간이다) 아래의 형태로 바뀌어야 하고, 또 저 백버튼을 누르면 다시 위의 형태로 돌아가는 형태로 디자인을 하려고 했다. 그 과정에서 몇몇 동작처리를 직접해주어야 했는데, 처음 포커스를 얻을 때 트리거 되는 부분은 TextField 내의 modifier에 clickable 값을 줘서 해결했지만 나머지가 문제였다.  XML 및 바인딩 기반 View였다면, EditText 객체와 InputMe..

티스토리툴바