보노보노의 코딩일지

이 문제는 처음 봤을 때 그냥 간단한 문자열 비교 문제인가 했다. 하지만 범위가 100만 이하라는 것을 보고 다른 알고리즘의 필요성을 느껴 관련한 알고리즘을 찾아봤다. 그런데 이게 왠걸? 이전에 한번 구현하려다 실패한 KMP알고리즘을 쓰는 것이 아니겠는가. 예전에 클래스 3에 있는 실딱이 문제를 풀다가 특정 문자열을 찾는 위와 비슷한 문제를 풀려고 한 적이 있었다. 그 떄 KMP알고리즘에 대해 한번 접한 적이 있었다. 하지만 그 땐 알고리즘에 대한 경험도 적었고 무엇보다도 위 알고리즘에 사용되는 LPS라는 알고리즘이 전혀 이해가 가질 않아 구현 중 포기했던 문제였다. 하지만 진화를 거둔 지금, 다시 한번 이 알고리즘에 도전해보았다. 아이디어는 간단하다. 문자열 매칭을 시키면서 겹치는 부분이 만약에 발생을..

처음 문제를 봤을 땐 '이게 뭐지?' 싶었다. 그러다가 문득 깨달았다. '이게 그 유명한 Convex Hull 문제구나!!' 예전에 고등학교에 다니다가 컨벡스 헐에 대한 정보를 얼핏 들은적이 있었다. 그래서 이 문제에 관해서 어느정도 알고있었다. 그래서 약간의 기대감과 함께 문제에 손을 대기 시작했다. 하지만 처음엔 막막했다. 도저히 어디서부터 손을 대야하는지 모르겠다. 일단 내가 생각한 아이디어는 큰 원을 만들어서 이를 내접시키는 방식으로 진행해보고자 했다. 하지만 이 방식은 너무 어렵다. 그래서 다른 방법을 생각해보려 했으나 마땅치 않아 결국 구글을 켜게 되었다. 그렇게 찾은 결과는, Graham Scan 알고리즘이었다. 정확히 컨벡스 헐을 노리고 만든 알고리즘이었다. 이 알고리즘의 과정은 그리 어렵..

문제의 첫 줄을 읽자마자, 'a번째 정수부터 b번째 정수까지' 이 문구가 눈에 들어왔다. 이 말인 즉슨, 세그먼트 트리를 이용할 가능성이 매우 높다는 뜻. 그리고 뒤에를 읽었더니 최솟값과 최댓값을 구하라는 얘기가 보인다. 그리고 입력되는 수의 범위를 봤더니 N과 M이 모두 10^5 이하의 자연수라는 조건이 보였다. 즉, 만약 시간복잡도가 O(N)인 알고리즘을 써야한다면, 10^10번의 계산을 해야한단 의미였다.  이는 2초라는 시간 내에 절대적으로 불가하므로 처음 생각했던 세그먼트 트리의 개념을 이용해서 문제를 풀기로 했다. 그런데 약간의 고민이 생겼다. 최대와 최소 모두를 출력해야 하는데 어떻게 세그먼트 트리로 나타내지? 그래서 2개의 세그먼트 트리를 이용해 각각 특정 구간에서의 최대와 최소를 나타내는..

이 문제는 이전에 풀었던 BOJ 11689 GCD(n,k) = 1 의 강화버전인 문제이다. 문제에서 구하고자 하는 바와 기본적인 코드 구조는 거의 동일하다고 볼 수 있다.단지, 입력되는 숫자의 범위가 기존 10^12에서 10^18로 늘어났단 점만 제외하면 말이다. 이렇게 범위가 늘어남으로 인해 많은 것이 바뀌었다. 기존에 11689번 문제는 에라토스테네스의 체를 이용해서 소수의 리스트들을 뽑아낸 뒤 (10^6까지의 소수만 뽑으면 된다) 이를 직접 입력된 n에 대입해가면서 인수인지 아닌지를 구분해 낸 뒤, 이를 소인수 리스트에 저장해서 오일러 피 함수를 구하는 방식으로 진행됐다. 하지만 수의 범위가 10^18이 되면서, 에라토스테네스의 체를 사용하는 것이 불가능하게 되었다.에라토스테네스의 체는 10^6을 ..