본문 바로가기

Dev/BOJ

 (65)
[백준 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)까지만 탐색하면..
[백준 1006] 습격자 초라기 DP 문제인데, 구현도 굉장히 빡빡한 문제. 문제를 천천히 읽다 보면 DP를 사용해야겠다는 것은 금방 떠오르는데, 그 이후가 말랑하지 않은 문제이다. 먼저 배치된 소대의 최소 개수를 구하는 점화식을 생각해주어야 하는데, 거꾸로 생각을 해보는 것이 편하다. 일단 원타곤이 원형 배열이라는 것은 인지만 한 상태로 점화식부터 빠르게 찾기 위해 직선의 2차원 배열로 생각한다. 그렇게 되면, N 및 2N번째 구역이 위치한 열까지 소대를 배치했을 때 그 최솟값을 도출해야 하는 하는 문제가 된다. 이때, 마지막 열을 채우는 케이스는 아래와 같다.  두 구역에 걸쳐 소대를 배치 가능한지 여부는 매번 W값과 인접한 적의 합을 통해 판별할 수 있고, 결국 매번 메모이제이션을 통해 저장해두어야 하는 것은 이전까지 소대가 배치..
[백준 17144] 미세먼지 안녕! 구현 문제다. 크게 복잡하거나 어려운 부분은 없는데, 오히려 메모리 아끼겠답시고 포인터를 이용하다가 for문 안에서 선언해 둔 로컬 레퍼런스를 그대로 이용해서 갱신하는 바람에 문제가 좀 생겼다. for문 안에서 일반 vector타입으로 선언해도 힙 영역에 할당된 메모리 공간은 따로 릴리즈 해주지 않는 이상 계속 살아있을 줄 알았는데, 디버깅하면서 메모리 공간을 보니까 vector 레퍼런스가 날아가면서 힙 영역도 같이 릴리즈 되는 것 같았다. 그래서 그 임시 vector를 for문 밖으로 빼버리고 아예 그쪽도 포인터로 선언해서 new로 직접 메모리를 할당해줬더니 문제없이 돌아갔다.  문제에 대한 로직은 나와있는 그대로 구현했다. R과 C의 크기가 최대 50이고, T도 최대 1,000이기 때문에 매 초마다 ..
[백준 12850] 본대 산책2 수학과 분할 정복을 이용하는 문제. D의 크기가 최대 1,000,000,000이기 때문에 O(n)인 DP로 해결하려고 해도 시간초과가 날 것이다. 그래서 다른 방법을 생각해보아야 한다.  먼저 특정 건물 i에서 특정 건물 j로 이동하는 경로 수를 matrix[i][j]에 저장하겠다고 생각했다. 이걸 1분을 소모했을 때를 기준으로 만들게 되면 이는 인접 행렬이 된다. 그렇다면 2분을 소모해서 특정 건물 i에서 i로 돌아오는 방법은 어떻게 구할 수 있을까를 생각해보았다. 이는 가능한 모든 j에 대해, 1분에 걸쳐 건물 i에서 j로 이동하는 경로 수 * 1분에 걸쳐 건물 j에서 i로 이동하는 경로 수를 모두 합친 것으로 생각할 수 있다. 가만히 보고 있으면 알 수 있듯이, 이는 행렬 곱 형태이다. 이후의 n분..
[백준 13913] 숨바꼭질 4 BFS 문제. 같은 시리즈인 숨바꼭질 3 문제를 풀고, 뭔가 아쉬워서 다음 넘버링이 있는지 찾아보니 있어서 이것도 풀었다. 문제가 단순해서 그냥 BFS를 사용하면 바로 풀린다. 숨바꼭질 3 같은 경우에는 순간이동에 걸리는 시간만 0초라서 우선순위 큐와 다익스트라를 이용했었는데, 이 문제는 모두 같은 시간이 걸리므로 일반적인 큐와 BFS를 사용했다. 이동 경로를 출력해야 하는 부분이 있어서, 직전 노드를 저장해두는 prev 배열을 따로 선언해서 BFS 내에서 처음 노드 방문 시에 함께 갱신해주었다.  사실 위 문제를 풀면서 다른 부분에서 애를 좀 먹었는데, prev 배열을 이용해서 최종 경로를 역추적 하는 과정에서 살짝 미스가 있어서 원인을 한참 찾았다. 혹시 본인이 작성한 BFS를 사용하는 본 로직에는 ..

티스토리툴바