본문 바로가기

Dev/BOJ

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

티스토리툴바