본문 바로가기

Dev

 (90)
[백준 2618] 경찰차 DP 문제이다. DP를 사용해야 한다는 것은 바로 알아챘지만, 점화식 떠올리는 게 쉽지 않았다. 계속 DP 테이블을 초기 상태부터 순서대로 채우려고 시도해서 그런 것 같다. 확실히 DP 문제에 약한 편이라, 같은 난이도여도 DP 문제는 더 어렵게 느껴진다.  일단 브루트 포스 풀이를 생각해보면, 각 사건에 대해 경찰차1과 경찰차2를 배정하는 두 경우가 존재한다. 따라서 경우의 수가 2^W에 달하며, O(2^W)의 시간 복잡도를 가진다. 당연히 문제를 제 시간 내에 해결할 수 없다. 하지만 브루트 포스 로직을 관찰하면서 어떤 부분에서 비용을 줄일 수 있을지 생각해 볼 수 있다.  특정 i 번째 사건에 경찰차를 배정하려고 할 때, 이전까지 경찰차를 배정하는 경우를 떠올려 보면, { 1, 1, 1, 1, 1 ..
[백준 11505] 구간 곱 구하기 세그먼트 트리 문제이다. 전체적인 맥락은 세그먼트 트리를 이용해 구간 합을 구하고 수정하는 문제와 유사하지만, 곱 연산이 들어가고 입력으로 주어지는 수에 0이 존재할 수 있기 때문에 구간 합 문제보다 까다로운 문제가 된다. [백준 2042] 구간 합 구하기 (tistory.com) [백준 2042] 구간 합 구하기세그먼트 트리 문제이다. 어제의 문제와 같은 유형이기 때문에, 이제 보자마자 알 수 있었다. 대신 어제 푼 문제와 다른 점은 원본 배열이 중간중간 수정될 수 있다는 점인데, 이 때문에 트리를 uwinterry.tistory.com   트리를 초기화하는 부분과 값을 가져오는 함수는 문제 조건에 맞춰 모듈러 연산이 더해진 것 말고는 구간 합 문제와 같다. 위에서 언급했듯이, 까다로운 것은 0의 존재..
[백준 11054] 가장 긴 바이토닉 부분 수열 LIS를 응용한 DP 문제. LIS 알고리즘을 공부했거나 관련 문제를 풀어봤다면 어렵지 않게 풀이 방법을 떠올릴 수 있다. 기준이 될 인덱스를 정해두고, 앞부분에 대한 LIS를 구하고 뒷부분에 대한 LDS를 구해서 더한 값에 1을(기준 값이 포함되어야 하기 때문에) 더해주면 끝이기 때문이다.  다만 내 접근 방식대로 풀려면 수열의 처음부터 끝까지 모두 기준으로 잡고 한 번씩 구해봐야 하기 때문에, LIS와 LDS 구하는 알고리즘은 O(n log n)인 알고리즘을 사용해야 한다. 굳이 이 방법이 아니어도 O(n^2) 알고리즘을 두 번 사용하는 형태로 구해도 될 것 같긴하다. LIS를 기준으로 간략하게 적자면,  - 길이별로 최적 LIS의 마지막 값을 저장해둘 배열(여기선 lis로 지칭)을 생성해 둔다.  ..
[백준 2533] 사회망 서비스(SNS) DP 문제다. 처음에는 트리의 레벨을 홀수 레벨과 짝수 레벨로 나누어 해당하는 노드 수를 센 다음에 더 작은 값을 출력하는 그리디 알고리즘으로 풀 수 있지 않을까 생각했는데, 예제2만 봐도 성립하지 않음을 알 수 있었다. 좀 더 고민해봐도 일반적인 그래프 탐색을 이용해서는 풀 수 없을 것 같아서 다른 알고리즘을 생각하다가 DP를 도입해 해결했다.  문제 해결을 위해 각 노드에 대해 고려해 보아야 하는 상태는 해당 노드가 얼리 아답터인 경우와 아닌 경우다. 문제에서 주어지는 그래프가 트리임을 보장하고 있으므로, 어떤 한 노드를 루트 노드로 설정하면 모든 노드에 대해 부모 노드와 자식 노드를 정할 수 있다.   i번 째 노드에 대해, dp[i][0]를 i번 째 노드가 얼리 아답터일 때 서브 트리의 최소 얼리..
[백준 2042] 구간 합 구하기 세그먼트 트리 문제이다. 어제의 문제와 같은 유형이기 때문에, 이제 보자마자 알 수 있었다. 대신 어제 푼 문제와 다른 점은 원본 배열이 중간중간 수정될 수 있다는 점인데, 이 때문에 트리를 update하는 함수를 따로 구현해 주었다. 그 외에 신경쓰였던 것은 입력으로 주어지는 모든 수의 범위가 long long int의 범위라는 것인데, 정답이 long long int의 범위를 보장하지만 이러면 구간 합을 구해내는 도중에 오버플로우가 나지 않을까 하는 점에서였다. 그런데 잘 생각해 보면 정답이 long long int의 범위를 보장하므로, 중간에 오버플로우가 나더라도 결국에 구간 합을 구해내면 답을 정상적으로 출력되겠구나 싶었다(오버플로우가 범위를 초과하는 순간 무식하게 임의의 쓰레기 값이 들어가는 게..
[백준 2357] 최솟값과 최댓값 풀고 나서야 알게 됐는데 세그먼트 트리 문제다. 세그먼트 트리 개념을 몰랐는데, 이렇게 하면 되지 않을까 싶어서 푼 방법이 세그먼트 트리를 이용하는 방법이었다.   문제를 처음 접했을 때, 대강 계산해도 직관적으로 떠오르는 알고리즘으로는 시간 복잡도가 너무 커지길래 브루트 포스 알고리즘을 그려놓고 조금씩 시간 복잡도를 깎아보기 시작했다. 큼직한 과정들을 그려두고, 어떤 부분을 줄일 수 있고, 어떤 부분이 무슨 짓을 해도 줄일 수 없는 부분이지 판단하는 건데, 이번 문제는 아무리 봐도 주어진 구간에 대해 최솟값과 최댓값을 구하는 O(n) 로직을 줄여야만 했다.  그럴려면 일반적으로 생각해 볼 수 있는 것은, 전처리를 통해 이용하기 좋은 형태로 입력 값을 가공하는 것이다. 만약 모든 시작점과 끝점을 기준으로..
[백준 1019] 책 페이지 구현 문제이다. N이 1,000,000,000까지 들어올 수 있기 때문에 선형 시간 알고리즘으로도 시간 초과가 나고, 규칙을 찾아야 한다.  적당히 작은 숫자를 두고 생각하다 보니, 나는 각 자릿수마다 등장하는 숫자를 카운트 해주는 방법이 가장 먼저 떠올라서 그 방법으로 풀었다.   특정 자릿수에 0~9가 몇 번 나타나는가를 생각하기 위해, 나는 자릿수를 기준으로 숫자들을 세 경우로 나누어 생각했다. 간단하게 N이 555인 경우, 십의 자리에 등장한 숫자들을 세는 것으로 예를 들면 다음과 같다. 1. 더 높은 자리에 위치한 수들이 아직 기존 수에 미치지 못하는 경우. 예시에서는 000~499이다. 이 경우는 더 낮은 자리에 나타날 수 있는 모든 경우 * 높은 자리에 위치할 수 있는 모든 경우만큼 0~9가..
[백준 11689] GCD(n, k) = 1 수학적 개념을 알고 있으면 쉽고, 모른다면 어려운 문제. 오일러 피 함수에 대해 알고 있다면 쉽게 구현할 수 있다. 나는 그 존재에 대해서 잘 몰랐는데, 풀고 나서 찾아보니 오일러 피 함수를 이용해서 푼 상태였다. 일단 문제는 1~n 범위 내에서 최대공약수가 1인 k를 모두 찾는 것인데, 이는 서로소를 찾으라는 것과 동치다(그리고 이것은 오일러 피 함수의 개념 그 자체다..).   나는 n의 범위를 보고, 이게 선형 탐색도 쓸 수 없는 조건이라는 점에서 착안해, 서로소를 하나하나 찾아낼게 아니라 n의 인수들을 이용해 n 값에서 빼면서 서로소 개수만 알아내야겠다는 생각이 들었다. 어떻게 보면 에라토스테네스의 체를 배열 없이 개수에 대한 정보만 남겨 사용하는 느낌이다. 인수 쌍은 sqrt(n)까지만 탐색하면..

티스토리툴바