BOJ 1022 소용돌이 예쁘게 출력하기

출처 : BOJ Slack

나중에 풀어봐야 겠다.

BOJ 3117 Youtube

이 문제는 LCA를 O(logN)만에 구할 때 쓰는 방법(dp이용)과 비슷하다.

m이 너무 크다는 것이 문제인데, 예를 들어 동영상A의 2의 k제곱번째 뒤 동영상은 동영상A의 2의 (k-1)제곱번째 뒤 동영상의 2의 (k-1)제곱번째 뒤 동영상과 같다는 사실을 이용하면
O(logM)만에 구할 수 있다.

그리고 어떤 수든 이진법으로 나타내보면 2의 k제곱들의 합으로 표현할 수 있다는 것을 알 수 있는데, 즉 (m-1)값을 2의 k제곱들의 합으로 보면서 2의 0제곱, 2의 1제곱, ... 2의 k제곱..이렇게 logM만큼만 뛰어 넘으면 m번째 동영상에 도달할 수 있다.

이분탐색과 비슷한 느낌이기도 하고...
 LCA처럼 미리 전처리를 하는 방법도 있고(나는 이렇게 했다.) 다른 사람의 코드를 보니 그냥 바로바로 계산할 수 있는 방법도 있다.

바로 바로 계산하는 방법은 처음에 2의 0제곱번째 뒤 동영상 정보만 가지고 있는 배열을 이용해서 계산을 시작하고, 2의 0제곱번째 뒤 정보의 배열을 이용해서 2의 1제곱번째 뒤 정보의 배열을 만들고, 그것을 이용해서 2의 2제곱번째 뒤 정보를 가진 배열을 얻고(덮어 씌우고).. 이런 식으로 나아가면 적은 메모리로도 똑같이 계산할 수 있다.

14398 피타고라스 수

엄청난 문제다.
사실 비슷한 문제를 풀어본 적 있지만 전혀 생각 못했다.
일단 풀이는 나중에 적고, 구현중에 자연수의 제곱수인지 아닌지를 판단해야 하는 부분이 있는데, 나는 여태 제곱수 판별할 때 끝자리가 0, 1, 4, 5, 6, 9인지 보고 아니면 O(루트N)만큼 돌리는 정도밖에 몰랐는데... 일단 이분탐색으로 찾아보는 방법이 있고, 또 하나
sqrt를 이용하고 그 값을 정수자료형에 넣고 그 정수를 제곱해서 원래 제곱수가 되는지 확인하는 방법이 있다... 두 번째 방법은 주의할 점이 정수자료형에 넣으면서 데이터 손실이 일어나기 때문에 그리고 오차도 있고 여차저차해서 구한 값이 n이면 n*n 뿐 아니라 (n+1)*(n+1)값도 비교를 해봐야 한다고 한다. 안전하게 하려면 (n-1)*(n-1)..까지도..? 나중에 잘 생각해 봐야겠다. 형변환 할 때 버림 혹은 올림이 되는 것과 연관해서 생각해보면 될 것 같다.

14281 볼록 수열

전체를 다 돌고 또 돌고 하는 방식이 부분 부분에서 다시 앞으로 가서 도는 방식보다 빠르다.
음 확실하게 와닿지는 않지만 일단 시간초과를 받기도 했고 부분 부분 확인하면서 다시 돌아가는 방식은 앞으로 계속 돌아갈 수 있고, 다시 뒤로가면서 불필요한 만큼을 또 지나가게 되는데... 전체를 일단 다 돌고 다시 전체를 돌면서 계속해서 고치면 일단 불필요한 부분을 지나가는 것은 줄어들 것 같긴한데... 나중에 다시 생각해봐야겠다.. 직접 써보면서 하는 것도 좋을 것 같다....

14391 종이 조각 반례

0000
0005
0000
5110

BOJ 14269 전설의 쌍검 용사

캠프 문제인데, 참 멋있는 문제다. 일단 문제 설명과 풀이는 나중에 정리하기로 하고 모범답안을 보고 풀었는데 시간초과가 나서 이것 저것 찾아보고 생각 좀 해봤더니 나는 vector에서 erase연산을 사용하는데 이 것이 문제였다. 직접 테스트를 해봤는데 10만번 erase하는 데도 시간이 꽤 걸렸다...그래서 찾아보니 vector가 배열 기반 컨테이너라고 한다... 그래서 erase나 insert를 하게 되면 요소를 밀어내거나 당겨야 하고, 매우 오래 걸리는 것 같다.
->근데 확실치는 않다. 다시 생각해보니 수정전 코드도 erase를 이용했는데, 그 당시에는 시간 초과없이 50퍼센트까지 갔었다. 그런 것을 보면 시간 초과가 난 이유가 꼭 erase때문은 아닌 것 같기도 하고... 여튼 erase를 사용하지 않고 구현해 봐야겠다.

이 문제는 그리디 알고리즘이 핵심인 문제이다. 간략하게 풀이를 적자면, 오른손에 들어야 할 검들은 꼭 가지고 있어야 한다. 그리고 왼손에 들어야 할 검의 범위들에서 오른손에 들 검들로 커버할 수 있는 범위들은 제외하고 나머지 범위들에서 최소의 검의 개수를 구하면 되는데 이 부분이 핵심이다. 여기서 최소의 검을 구하는 방법은 회의실 배정 문제를 푸는 방식과 똑같다. 즉 겹치지 않는 범위의 최대 개수를 구하면 그것이 그 범위들을 커버할 수 있는 최소의 검의 개수가 된다.

처음에는 잘 이해가 안 갔지만 생각해보니 이해가 됐다. 간단히 설명하면, 겹치지 않는 각 범위들을 커버하기 위해서는 각 겹치지 않는 범위당 검이 꼭 한 개씩 필요하다. 그렇기 때문에 겹치지 않는 범위의 최대개수가 곧 모든 범위를 커버할 수 있는 검의 최소 개수가 되는 것이다. 겹치지 않는 각 범위들의 최대 개수를 각 범위당 검 하나로 커버하고 나면  나머지는 자연히 커버가 된다. 혹시 커버가 안되는 범위가 있다면 겹치지 않는 범위가 더 있다는 것인데 이 것은 겹치지 않는 각 범위들의 최대 개수를 구했다는 것에 모순이므로 말이 안된다.

그런데 문제가 있다. 일단 핵심 알고리즘은 그리디 알고리즘이긴 한데, 쌍검 용사가 검을 왼손, 오른손에 들어야 하므로 즉 동시에 2개를 들고 있어야 하므로 만약 별 생각 없이 구했다가는 입력이 1 1 1과 같이 들어오는 경우는 틀리게 될 것이다. 오른손의 검으로 왼손검을 커버가능해도 왼손검도 하나 들고 있어야 하므로 두 개가 필요하다.

이 부분을 해결하는 것이 정말 골치 아팠고 결국 해결 못하고 풀이를 봤다.
하지만 의외로 당연(?)한 방법이었다...
왼손검의 범위들을 오른손 검으로 커버할 수 있는지 검사하는데, 만약 어떤 오른손 검으로 커버가 가능한 경우 그 오른손 검이 그 왼손검 범위와 같은 짝이었던 오른손 검인지 아니면 다른 오른손 검인지 확인한다. 다른 오른손 검이라면 그 왼손검 범위는 커버가능한 것이지만 만약 같은 오른손 검이라면 커버할 수 없으므로 다음 크기의 오른손 검을 살펴본다. 만약 다음 크기의 오른손 검으로 커버가 가능하다면 괜찮지만 그게 안된다면 그 왼손검 범위는 커버할 수 없다는 것이된다...

여기서 조금 헷갈릴 수 있는데 꼭 기억해야할 것이 오른손 검, 왼손 검 모두 오름차순 정렬이 되어있다는 사실이다. 그리고 왼손검은 중복이 제거되어 있다. 그렇기 때문에 바로 다음 인덱스의 오른손 검만 살펴보면 되는 것이다.

그리고 풀이에서는 erase를 쓰지 않고 커버가 불가능한 왼손검 범위들을 따로 저장해서 모으는 식으로 했는데, 둘 다 비슷한 방법이긴 해도 풀이의 방법이 훨씬 나아보인다.
또한 오른손 검으로 커버할 수 없는 왼손검 범위들을 조사할 때, lower_bound를 쓰는게 코드가 훨씬 깔끔해지는 것 같다. 나는 그냥 인덱스를 늘려가면서 하나씩 비교해가는 식으로 했다.

BOJ 14265 영선 수열

이 문제는 k부터 시작해서 거꾸로 올라가면서 X를 찾으면 되는데, 짝수인 경우 두 갈래(*2, +1) 로 갈리므로 일일이 찾게되면 시간이 너무 많이 걸린다.
k부터 시작해서 2k, k+1,... 쭉 적어나가다 보면 규칙이 있다.

바로 (2^i * k)  ~ (2^i * k + 2^i - 1) 의 형태만 존재하게 된다.
그래서 이 것을 이용해서 구할 수 있는데, 문제가 있다. 혹시 저렇게 나가다 보면 겹치지 않을까? 결론부터 말하면 겹치지 않는다. 왜냐하면 원래 문제에서 주어진 연산 자체가 짝수이면 이것, 홀수이면 저것으로 갈래가 두 갈래 이상이 아닌 딱 한 갈래이기 때문에 거꾸로 올라가면서 겹친다는 것은 원래 연산으로 내려올 때 갈래가 두 갈래 이상이 된다는 것이므로 모순이다.

그리고 저 위에 적은 형태는 엄밀히 말하면 k가 홀수일 경우에 완벽히 적용되고, k가 짝수이면 조금 다르다. k가 짝수인 경우는 해보면 처음부터 두 갈래로 갈리는데, 2*k갈래를 따라가면 저위의 형태만 존재하게 되지만 k+1갈래 쪽은 저렇지 않다.
여기서 방법이 두 가지가 있는데, k+1을 k'로 보는 것이다. 그럼 위의 형태와 똑같이 된다.
그래서 계산할 때 k가 짝수인 경우는 두 갈래를 따로 구해서 더해주는 방법이 있고,
또 하나는 백준님의 코드를 보고 알게된 것인데, k+1갈래 쪽도 더 그려보면 규칙이 있다.
바로 (2^i * k + 2^i) ~ (2^i * k + 2^(i+1) -1) 의 형태만 존재한다는 것. 즉 두 갈래 전체를 보면 (2^i * k) ~ (2^i * k + 2^(i+1) -1) 의 형태로 존재하게 된다.
이 것을 구현하는 것은 그렇게 어렵지는 않다. 그냥 lo=k, hi=k에서 시작해서 lo에는 *2, hi에는 *2 + 1을 해주는데, k가 짝수인 경우는 처음 시작할 때 ㅣlo=k, hi=k+1에서 시작하면 된다.

그리고 나는 2의 n제곱수들을 미리 계산해서 배열에 넣어놓고 썼는데, 굳이 그럴 필요가 없다. 그냥 lo, hi에 각각 *2, *2+1을 해주면서 나가면 된다...

그리고 또 나는 문제에서 주어진 X의 범위, a, b에 맞는 경우만 개수를 세느라 구현이 좀 더 복잡해지기도 하고 실수도 해서 계속 틀렸었는데, 그냥 (0~b까지의 경우) - (0~a까지의 경우)를 해주면 된다... 이렇게 하면 정말 구현도 편해지고 나처럼 실수할 가능성도 적을 것이다.

BOJ 12015 가장 긴 증가하는 부분 수열 2, 3

가장 긴 증가하는 부분 수열 2 문제를 좌표압축으로 풀어봤다.
내가 만든 segment tree의 경우 query 나 update를 할 때, 처음에 주어진 배열의 크기 n이 있으면 0부터 n-1까지를 nodeLeft, nodeRight로 놓고 탐색한다. 배열의 크기가 n이니 즉, 수가 n개 있으니 0번 index부터 n-1번 index라고 생각하는 것이다.

하지만 좌표 압축을 할 때나 좌표 압축 없이 풀 떄나 이 문제에서 주어진 값이 1이상 100만 이하였고, 좌표 압축시에도 첫번째 원소 쿼리를 할 때 query(0, -1)인 쿼리를 피하기 위해 항상 index를 1부터 사용했다. 그렇기 때문에 100만+1 을 크기로 해주거나 좌표압축시에는 cnt+1을 크기로 segment tree 초기화가 수행되어야 한다.

그리고 이 문제는 좌표압축할 때 map을 쓰니 시간초과가 나서 대신 이분탐색을 직접 구현해서 이용했다.