본문 바로가기

분류 전체보기

 (159)
상위 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..
[백준 2143] 두 배열의 합 Map, 투 포인터, 이진 탐색 등 여러 방법으로 접근 가능한 문제. 브루트 포스로 해결하면 O(n^2 * m^2)의 시간 복잡도를 가지기 때문에 시간 내에 풀 수 없다. 핵심 아이디어는 심플한데, 각각의 부 배열 합을 미리 생성해두는 것이다. 모든 부 배열 합을 알아내기 위해서는 O(n^2)이면 충분하므로, n과 m의 최댓값이 1,000인 위 문제에서는 모든 부 배열 합을 미리 구해둬도 상관없다. 이를 어떻게 저장해둘지는 자유인데, 리스트든 맵이든 해시 테이블이든 본인이 사용할 로직에 맞춰 자료구조를 선택하면 된다. 각각의 자료구조와 로직은 일장일단이 있다. 나는 해시 테이블(C++이기에, unordered_map을 사용)을 이용하고, 내장된 해시 탐색 로직을 그대로 활용하기로 했다. 배열B에 대해 모..
[백준 1799] 비숍 백트래킹 문제다. 그래프 이론이나 탐색 유형의 문제는 곧 잘 푸는 편인데, 이건 핵심 아이디어가 바로 떠오르지 않아서 꽤 많은 시간을 소요했다. 브루트 포스를 활용하면 O(2^(n^2))에 해당하므로, 풀 수가 없다.  그래서 처음 시도한 방법은 그리디 알고리즘이었다. 비숍을 놓을 수 있는 빈칸 배열을 저장해 두고, 각각 대각선을 탐색해서, 해당 칸에 비숍을 놨을 때 놓을 수 없게 되는 칸의 수를 셌다. 그리고 이를 우선순위 큐에 집어넣고, 손실이 가장 적은 칸부터 하나씩 채워보는 방법을 썼다. 몇 가지 직접 떠올린 케이스들에 대해서는 꽤나 잘 먹혔지만, 이 방법은 시간복잡도만 우선했을 뿐, 최적해 찾는 것을 보장할 수 있느냐를 스스로 증명하지 못했다. 결과는 아니나 다를까 중간에 틀렸습니다를 받았다. ..
[백준 1647] 도시 분할 계획 심플한 MST(Minimum Spanning Tree, 최소 신장 트리) 문제다. 간선의 수가 최대 1,000,000으로 그리 크지 않아서 O(E logE)인 Kruskal 알고리즘으로 해결했다. Kruskal 알고리즘을 사용하기 위해서는 경로 집합에 해당 간선이 포함되어 있는지를 확인해야 하므로, Union-Find 알고리즘을 구현해서 빠르게 판별할 수 있도록 했다. 일반적인 MST와 조금 다른게 있다면 두 개의 MST를 만들어야 한다는 점인데, 이는 Union의 수가 두 개일때까지만 Kruskal 알고리즘을 진행하는 것으로 구현할 수 있다. 전형적인 MST 유형인데다, 디테일한 구현 요소도 없어서 그 외에는 크게 신경쓸 건 없었던 것 같다. #include #include using namespace..

티스토리툴바