유명한 알고리즘 중 하나로 유클리드 호제법(Euclid's GCD Alogirhtm)이 있다. 이는 2개의 자연수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 알고리즘이다.
기하학의 아버지인 유클리드가 기원전 300년쯤에 개발한 알고리즘이다.
알고리즘 자체는 간단한데, 어떻게 이 알고리즘이 성립하는지 그러한 부분들부터 차근차근 한번 정리하면서 알아보자.
유클리드 호제법 증명
//(GCD(x, y)//)를 자연수 //(x//), //(y//)의 최대공약수라고 하자.
만약 //(x=y//)인 경우 아래는 자명하다.
//(GCD(x,y) = GCD(x,x) = x//)
공약수의 성질
그리고 유클리드는 //(x>y//)인 경우, 아래의 성질도 성립함을 알아내었다.
//(GCD(x,y) = GCD(x-y, y)//)
뭔가 감이 안 올 수 있는데, 간단하게 증명된다고 한다.
//(d//)를 //(x//)와 //(y//)의 공약수라고 하자.
그러면 아래의 조건을 만족하는 정수 //(q_1//)과 //(q_2//)가 존재한다.
//(x=q_1d//) , //(y=q_2d//)
//(x-y=q_1d-q_2d=(q_1-q_2)d//)
따라서 //(d//)는 //(x-y//)의 약수이기도 하다.
비슷한 이유로 이 역도 가능하다는 것을 보일 수 있다. //(x-y//)와 //(y//)의 약수는 //(x//)의 약수이기도 하다.
따라서 //(x//)와 //(y//)의 공약수 집합은, //(x-y//)와 //(y//)의 공약수 집합과 일치한다.
따라서 그 집합에서 가장 큰 원소인 최대 공약수 역시 일치하게 된다.
따라서 //(GCD(x,y) = GCD(x-y, y)//)가 성립한다.
Naive한 유클리드 호제법
위의 공약수의 성질을 이용해서 x와 y가 같아질 때 까지, 큰 값에서 작은 값을 빼는 방식으로 알고리즘을 수행해볼 수 있다.
이는 아래 두 가지 성질을 이용한 것이다.
//(GCD(x,x) = x//)
//(GCD(x,y) = GCD(x-y, y)//)
int gcd(const int K, const int M) {
int k = K; // 간단하게 불변식을 표현하기 위해
int m = M; // 인자를 상수로 고정하고
// 계산을 위해 지역변수(사본)을 사용
// loop invariant(불변식): GCD(K,M) = GCD(k,m)
while (k != m) {
if (k > m) {
k = k-m;
} else {
m = m-k;
}
}
// 이 시점에서 k = m 이므로 , GCD(K,M) = GCD(k,m) = GCD(k,k) = k
return k;
}
위와 같은 코드를 통해서 gcd를 쉽게 구해볼 수 있다. 지역변수로 사용한 k와 m은 처음 인자로 들어온 K와 M의 복사본으로 시작이 되며, gcd의 성질을 통해서 큰 값에서 작은 값을 빼더라도 같은 gcd를 갖게 된다.
좀 더 빠른 유클리드 호제법
위와 같은 방식으로, 큰 값에서 작은 값을 빼는 방식으로 유클리드 호제법이 구현이 가능한데, 이를 좀 더 빠르게 구현할 수 있다.
작은 값은 큰 값에서 뺄 수 있을 때 까지는 계속해서 빼기 연산을 수행할 것이므로, 이를 나머지 연산으로 대체하면 여러번 빼는 연산을 한번으로 대체할 수 있게 된다.
int gcd(int K, int M) {
int k = K;
int m = M;
// loop invariant(불변식): GCD(K,M) = GCD(k,m)
while (k !=0 && m != 0) {
if (k > m)
{ k = k % m; }
else
{ m = m % k; }
}
// 이 시점에서, GCD(K,M) = GCD(k,m) = max(k,m)
return max(k,m);
}
빼기를 반복하는 경우의 알고리즘에선 k=m이 될 때 알고리즘이 종료되지만, 나머지 연산을 하는 경우 k=m인 경우 k와 m중 하나의 값이 0이 되어버린다. 따라서 리턴값은 그 중 큰 값이 된다.
이 코드를 좀 더 간편하게 정리하여, k > m 임을 보장하는 방식으로 코드를 짠다면 아래처럼 코드가 된다.
int gcd(int K, int M) {
int k = max(K,M);
int m = min(K,M);
// loop invariant(불변식): k ≥ m ∧ GCD(K,M) = GCD(k,m)
while (m != 0) {
int r = k % m;
k = m;
m = r;
}
// 이 시점에서, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
return k;
}
간결한 코드
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
binary search 알고리즘은 번역해서 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다. 사실 컴퓨터공학을 전공하면, 자료구조 과목을 배울 때 배우는 탐색 알고리즘 중 하나로, 정말 유명하고 자료도 많은 알고리즘 중 하나이다.
학교 전공과목시간에 이진 탐색을 처음 배웠을때는 신기하긴 했지만 나중에 더욱 복잡하고 어렵고 멋져보이는 알고리즘들을 보면 이 이진 탐색은 결국 적당히 재귀로 구현해서 쓰기만 하면 되는 것 같은 별 것 아닌 알고리즘 같아 보인다.
하지만 이렇게 간단하고 비교적 쉬운 기초적인 알고리즘이지만, PS를 할 때 이 이진 탐색의 아이디어를 이용해서 최적화를 하거나, parametric search를 하거나 하는 활용도가 꽤 있는 편이며, 사용할 수 있는 정확한 상황을 판단하고 버그없이 구현하는 것이 생각보다는 어려울 수 있다.
이번 포스팅에서는 기본적인 이진 탐색의 개념에 대해서는 알고 있는 사람이 구현 시, 적용 시 유의해야 할 점들을 한번 씩 짚고 넘어가보도록 하자.
적용할 수 있는 경우
이진 탐색 알고리즘은 항상 적용할 수 있는 것은 아니다. 몇 가지 조건이 필요하다.
원소가 정렬이 되어 있을 것(오름차순이든 내림차순이든)
원소의 Random Access가 가능해야 한다.
원소가 정렬이 되어 있어야지 중간에 한 곳을 딱 집어서, 결과를 본 뒤 그 지점의 이전과 이후의 값을 예측을 할 수 있다. 오름차순이든 내림차순이든 정렬이 되어 있어야 한다. 그리고 만약, 중복되는 원소가 있다면, 일반적인 binary search가 아닌, upper_bound와 lower_bound를 각각 구한 뒤, lower_bound부터 upper_bound직전까지 다 훑으면, 해당 크기의 모든 원소를 확인할 수 있다. 원소가 중복이 있는지 아닌지도 구현시 디테일을 바꾸게 하는 하나의 체크 포인트이다.
그리고 binary_search 자체가 아닌 다른 알고리즘에 녹아들어가거나, parametric search인 경우 정렬은 아니지만, 중간 임의의 값을 look up 했을 때 그 이전과 이후의 값에 대한 예측이 가능한 경우도 정렬이 되어 있는 것과 마찬가지로 볼 수 있다.
원소의 Random Access가 가능하다는 것은, C언어의 배열 처럼, index만 알면 특정 arr[index] 값을 //(O(1)//)의 시간복잡도로 참조가 가능하냐는 것이다. 사실 Random Access가 불가능하더라도 이분탐색은 가능하긴 하지만, //(O(1)//)의 시간복잡도로 Random access가 불가능하다면 이분탐색으로 //(O(lgN)//)의 성능 향상은 기대하기 힘들다. Random access가 불가능하고 sequential access만 가능한 Linked list에서 이분 탐색을 하지 않는 이유도 이러한 이유이다.
구현시 체크할 점
이분 탐색은 크게 두가지 구현방법이 있는데, 재귀(recursion)와 반복(iteration)이다. 그런데 함수 프롤로그와 에필로그의 오버헤드를 줄일 수 있는 반복(iteration)방식으로 구현하는 것이 성능이 일반적으로 더 좋고, 간편하다.
while문을 이용해서 쉽게 구현할 수 있는데, 이때 디테일을 잘못 구현하게 되면 특정 상황에서 무한루프가 돌면서 이분 탐색이 종료하지 않을 수 있다.
잘 구현된 경우
사실 이제부터 이야기하는 코드들은 이진탐색이라기 보다는 parametric search에 가깝다. ok 함수를 만족하는 정수 값 중 가장 끄트머리에 있는 값을 찾는다고 보면 된다. -INF~10까지의 값은 ok 함수에서 true를 리턴하고 11~INF의 값은 false를 리턴한다고 하면 10을 찾는 것이다.
int left, right; // [left, right) range
while (left + 1 < right) {
int mid = (left + right) / 2;
if (ok(mid)) {
left = mid;
} else {
right = mid;
}
}
//return left
위와 같은 방식으로 코드를 짤 수 있다.
left, right는 범위를 반 개구간으로 해서 [left, right)라고 표현을 했는데, 원하는 값은 left보다는 크거나 같고, right보다는 작은 범위 안에 있다는 뜻이다. 중고등학교 수학시간에 아마 배웠겠지만 [와 ]는 inclusive로 이상, 이하에 해당하고 (와 )는 exclusive로 초과, 미만에 해당한다.
그러면 만약 범위가 [2, 3) 처럼 된다면, 해당 범위를 만족하는 정수는 2밖에 없게 된다. 따라서 탐색을 계속 지속하려면 right가 left보다 2이상 커야 한다. 따라서 while문의 진행 조건도 left + 1 < right와 같이 된다.
그리고 중간값인 mid를 구해서, mid가 range안에 포함이 된다고 하면 ok함수가 true를 리턴하게 되고 이때, left값을 mid로 바꾼다. left가 찾는 값이 될 수도 있으므로 inclusive인 left로 들어가도 무방하다.
mid가 range안에 포함이 되지 않는다면 ok함수가 false를 리턴하게 되고, right를 mid로 바꾼다. right 값은 exclusive이므로 찾는 값이 포함되지 않는다는 뜻이 된다.
그렇다면 이 while문이 무한루프를 돌 수 있을까? while문이 무한루프를 돌려면, loop을 한번 돌 때, 범위가 하나도 줄어들지 않는 경우가 생겨야 한다.
mid를 계산하는 것과, ok 함수의 리턴값에 따른 left, right값의 update 시 줄어들지 않는 경우가 있는지를 한번 확인해보자.
사실 범위가 클 때에는 잘 줄어든다. 그리고 탐색이 거의 다 되어서 범위가 매우 줄어들었을 때, off by one error로 값이 줄어들지 않는 경우가 있을 수 있는데 홀수 짝수를 예시로 몇가지 값을 넣어보면 바로 알 수 있다.
[2, 3)이면 종료조건이 되므로 [2, 4)와 [3, 5)를 예시를 들어보자.
[2,4)인 경우 mid=3이 되며, 결과가 어떻든 [3,4)이거나 [2,3)으로 종료가 된다.
[3,5)인 경우 mid=4가 되며, 각각 [4,5)이거나 [3,4)로 종료가 된다.
이 경우는 무한루프가 돌지 않는 코드가 되게 된다.
그리고 최종적으로 리턴하는 값 자체도 inclusive인 left의 값을 리턴하면 우리가 찾는 값이 된다.
잘못 구현될 수 있는 경우
사실 위에서 예시로 든 경우는 C++ STL container들이 흔히 쓰는 방식인 [start, end)의 반개구간으로 하는 식이라서 간단하면서도 에러가 잘 없는 코드 패턴이 나왔다. 하지만 [start, end]와 같은 폐구간으로 설정을 하는 경우 조금 다를 수 있겠다.
비슷하게 아래와 같이 코드를 짜 보았다고 생각해보자.
int left, right; // [left, right] range
while (left < right) {
int mid = (left + right) / 2;
if (ok(mid)) left = mid;
else right = mid;
}
// return left;
완전 폐구간이므로, left == right가 되어야지 하나의 범위로 줄어든다. 따라서 while문의 조건이 left < right로 바뀌었다.
하지만 위의 코드는 잘못 짠 코드이다. 무엇이 잘못되었을까?
일단 값을 잘못 찾을 수 있으며, 무한루프 역시 돌 수 있다.
무엇이 잘못되었고, 어떻게 고쳐야 할 지 한번 고민을 해 보고 아래의 올바른 코드를 한번 확인해보도록 하자.
int left, right; // [left, right] range
while (left < right) {
int mid = (left + right + 1) / 2;
if (ok(mid)) left = mid;
else right = mid - 1;
}
// return left;
일단 ok(mid)가 return false를 한 경우 mid는 범위안에 들어오지 않는다. 근데 right를 mid로 하면 inclusive이므로 mid가 범위에 들어온다는 오류를 범하게 된다. 따라서 mid - 1를 적용해야 한다.
그리고 이런 경우, 무한루프가 돌 수 있는데 범위가 [2, 3]이라고 가정해보자.
그리고 정말 찾는 값은 3이라고 생각해보자. 1~3의 값은 모두 ok함수에서 true를 리턴하고,
4이상의 값은 false를 리턴한다.
이때, mid=(2+3)/2 = 2가 되고, ok(2)=true가 되는데, left=mid=2로 범위가 그대로가 된다.
이 경우 [2,3]라는 범위에서 [3,3]라는 범위로 줄어들지 못하고 평생 저렇게 남게 된다. 즉 무한루프다.
이런경우 결국 left값이 범위를 줄여줘야 하는데, mid계산 시 2로 나누면서 LSB가 날라가게 되므로 나누기 전에 1을 더해서 floor((left+right)/2)가 아닌 ceil((left+right)/2)를 구하도록 해주면 정확하게 구현이 된다. 그리고 left를 리턴하면 된다.
생각나는대로 글을 쓰다 보니 글에 오류나 이해가 가지 않는 부분이 있을 수 있는데, 댓글로 피드백을 준다면 정정하도록 하겠습니다.
이번에는 다른 포스팅과는 다르게 책에 대한 리뷰 겸 홍보를 하려고 합니다. 보통 이런 글은 잘 쓰지 않지만, 지인인 동빈님이 작성하신 첫 종이책이기도 하고, 제가 리뷰어로서 참여한 책이기도 하니 한번 소개해보려고 합니다.
무작정 이 책이 좋다, 아니다 어떻다라기 보다는 객관적인 시선으로 이 책의 특징과 장점을 설명하고, 어떠한 사람들이 이 책을 읽으면 좋을 지에 대해 한번 글을 써 보도록 하겠습니다.
제가 알고리즘을 처음 공부할 때에는...
제가 알고리즘 문제풀이를 본격적으로 시작했던 때가 딱 3년전인 2017년 즈음 이었던것 같습니다. 그때는 컴퓨터공학과 학부에서 내주는 과제수준의 Naive한 다중 for-loop으로 코드를 짜거나, 함수의 재귀 개념에 스택, 링크드리스트라는게 있다 정도만 아는 정도의 수준이었습니다.
그때 알고리즘 분야의 정석 교과서라고 불리던 종만북을 구입을 했었고, 앞에 수십페이지에 달하는 서문을 읽고, 첫번째 문제인 Festival을 알고스팟에서 풀어보려고 했었죠. 당시 종만북 책에는 해당 문제에 대한 해답이 없었던걸로 기억하고, 고로 Festival 문제를 제대로 풀지 못하고 바로 종만북은 책장에 박혀서 먼지가 쌓여갔던 기억이 있습니다.
당시의 저에는 매우 어려운 문제였던 것이지요.
그러다가 학교 선배의 추천으로 정보올림피아드 초등부 문제를 풀었었고, 풀다가 막히면 좌절감에 공부를 쉬기도 했었죠. 그리고 강남역에서 있었던 백준님의 오프라인 강의도 돈을 내고 들었었습니다. 제대로 공부해보겠답시고 학부 4학년에 학교 알고리즘 동아리의 문을 두드렸기도 했고, 그때 들은 코드포스에 참여하면서 혼자서 이것저것 시도해보고 막히면 잠시 쉬었다가 다시 공부하고 이런 과정들의 연속이었습니다.
어쨋든 시간이 지나고 경험이 쌓이면서 지금은 왠만한 국내 기업들의 코딩테스트에서는 떨어지지 않을 정도의 기반이 쌓이긴 했지만, 꽤나 시행착오도 많이 했었고 중간에 어려운 난이도에 부딪혀서 잠시 공부를 포기하며 쉬는 기간들도 꽤 많았습니다.
3년전의 과거의 저에게 지금 이 책이 주어진다면, 좀 더 효율적이고 덜 좌절하면서 공부를 할 수 있었지 않았을까 하는 생각이 듭니다.
그래서 이 책의 특/장점은 무엇이냐면
동빈님이 쓰신 이 책의 특징과 장점이라고 하면, 아마 다음과 같은 항목들이지 싶습니다.
취업용 코딩테스트의 최신 트랜드 반영
알고리즘 문제풀이를 공부하는 사람들은 이유가 다양하지만, 일반적으로는 취미용이나 대회용을 타겟으로 한 책들이 많습니다. 취업용 문제풀이의 경우는 취미용이나 대회용 만큼의 고급/심화 내용을 포함하진 않고, 취업용은 이 대회용 문제들의 부분집합이라고 볼 수 있습니다. 물론 고급 내용들도 공부를 하면 무조건 좋지만, 효율적으로 취직을 타겟으로 공부를 할 때에는 조금 돌아가는 부분이 있을 수 있습니다.
이 책에는 취업용 코딩테스트에서 나올 법 한 것들을 모두 잘 커버하며 잘 짜여진 커리큘럼이 있으며, 최근 기출문제들과 관련 유형들을 잘 커버하고 있습니다.
유명한 종만북과 비교를 하자면, 종만북은 책의 목적이 취업용 코딩테스트를 위한 책이 아니며 책이 쓰인지도 꽤 오래된 편입니다.
알고리즘 문제풀이를 처음 접하는 사람들을 위한 난이도
보통 취업용 코딩테스트를 준비하는 분들은 하나 정도의 프로그래밍 언어를 사용할 줄 알며, 취직 준비를 위해서 알고리즘 문제풀이를 처음 공부하는 사람들이 많습니다. 이미 프로그래밍 대회 등을 준비했던 사람들에게는 따로 준비가 필요없을 수 있거든요. 이렇게 알고리즘 문제풀이에 처음 입문하는 사람들도 쉽게 이해하며 단계별로 계단을 밟아가듯 핵심 개념들을 쉽게 이해할 수 있도록, 이러한 독자들의 눈높이에 맞도록 쓰여진 책이라고 생각합니다.
종만북과 비교를 하자면, 종만북은 예상독자와 책 읽는 목적 자체가 좀 더 향상된 실력에 맞추어져 있어서, 알고리즘 문제풀이를 처음 접하는 사람에게는 진입장벽이 다소 있어서 책을 읽는 처음부터 어느정도 좌절을 할 수 있습니다.
파이썬 및 C++/Java 풀이 제공
코딩테스트 시 3대장 언어가 C/C++, Java, Python입니다. 전통적인 알고리즘 책들은 보통 C++ 코드를 고수하는 경우가 많습니다. 저 역시 알고리즘 문제 풀이 입문을 위해서 PS스타일의 C++와 C++ STL을 따로 공부하며 시간을 투자했습니다. 하지만 요즘에는 컴퓨터 공학 전공자 뿐만 아니라, 그 외의 산업공학과나 수학과 통계학과 경영학과 등 다양한 전공자들이 코딩을 배우는 경우가 많으며, 보통 이 경우 첫 입문 언어로 파이썬을 많이들 배웁니다. 이러한 분들에게 파이썬으로 코딩테스트 문제 풀이를 도와주는 책으로써 가치가 있고, 파이썬 뿐 만 아니라 C++과 Java 풀이 코드도 github를 통해 제공을 하여 공부에 도움을 줍니다.
지속적인 학습을 위한 리소스 제공
저자인 동빈님은 원래 유투브를 통해서 무료 개발과 SW관련 강의들을 많이 찍던 컨텐츠 크리에이터로써, 책과 관련된 강의들도 유투브를 통해 제공을 하고, 정답 코드 들도 친절한 주석과 함께 github에 공개되어 있습니다. 컴퓨터교육과 전공자 출신 답게 전달력있는 강의를 잘 제공하며, 수 많은 교육 경험들이 어우러진 동빈님의 컨텐츠는 공부를 할 방향과 내용들을 쉽게쉽게 이해할 수 있게 해줍니다.
어떤 사람들이 읽으면 좋은가?
3년전의 저에게 추천해주고 싶은 책입니다. 여태까지 알고리즘 문제해결 분야에 발을 담그지 않았다가, 이제 곧 취직 준비를 해야 해서 코딩테스트를 준비를 해야 하는 경우, 이 책에 있는 공부법대로 그대로 실시하면 됩니다. 최신 트랜드도 그대로 반영하고 있기 때문에 지금으로서는 이보다 더 가성비 좋은 선택은 없지 않을까 하는 생각이 듭니다.
작년에 이어서 올해에도 구글 코드잼에 참가했는데, 작년에는 2라운드 진출까지만 하고, 2라운드에서는 그냥 던져버렸었다. 올해에는 좀 더 나아진 모습을 보여주고자 했는데 결국 라운드 1C까지 왔다.
구글 코드잼은 Qualification Round이후 Round 1로 넘어가는데, 1라운드의 경우 A,B,C로 총 3번의 기회가 있다. 각각의 라운드에서 1500등 안에 들면 다음 라운드인 Round 2로 진출하게 되고, A라운드에서 1500등 안에 들어서 다음 라운드로 진출하게 되면 다음 B, C라운드는 참여할 수 없다.
즉 각각 A,B,C 라운드 별 1500명이 다음 라운드로 진출하게 되어 결과적으로는 4500명이 Round 2로 진출하게 된다. 그런데 올해 구글 코드잼의 등록자는 역대급이라고 하며(근데 매년 등록자의 수가 늘어난다고는 한다) 라운드 1A, 1B에서 처참하게 발려버려서 자신감이 꽤나 떨어져있는 상태였다.
대충 처참한 나의 이전 라운드 성적이다.
하지만 이번 라운드에선 아슬아슬하긴 하지만 어째 저째 다음 라운드로 진출하게 될 것 같다.
In review 상태인데, 뭐 부정행위를 한 것도 아니고 1389등을 했으니 Round 2를 체험해볼 수 는 있을 것 같다. 다만 좀 걱정이 되는 것은 Round 2가 DEFCON CTF Qualification Round와 일정이 겹친다는 것... 뭐 코로나 때문에 일정이 더 밀릴수도 있긴 하겠지만 애매한 것은 사실이긴 하다.
어쨋든 기적적으로 라운드 2로 진출하게 되었으니 당분간은, 어차피 이 글을 쓰는 시기로 부터는 열흘밖에 시간이 없긴 하지만 PS 공부를 좀 더 해봐야 겠다.
1. Overexcited Fan
1번 문제인데, 생각보다 너무 쉽게 나왔어서 오히려 걱정이 되었다. 빨리 풀기 대결이 되지 않을까 하는 그러한 우려이다. 어차피 상대평가라 난이도가 너무 쉬우면 오히려 불리하게 작용할 때도 있었다.
움직이는 녀석을 가장 빨리 만날 수 있는 시간대를 찾는 문제인데, 이동 거리를 L1 Distance(맨하탄 거리)로 바로 알아낼 수 있고, 이동하거나 멈추거나 둘 다 가능하므로, 이동경로별로 원점에서의 맨하탄 거리보다 현재 시간이 더 긴 순간이 만나는 순간이 되겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const int dx[] = { +1, -1, 0, 0 };
const int dy[] = { 0, 0, +1, -1 };
int val(char c) {
if (c == 'S') return 3;
if (c == 'N') return 2;
if (c == 'W') return 1;
return 0;
}
void solve() {
int x, y;
string steps;
cin >> x >> y;
cin >> steps;
int ans = -1;
for (size_t i = 0; i < steps.size(); i++) {
int k = val(steps[i]);
x += dx[k];
y += dy[k];
int dist = abs(x) + abs(y);
if (dist <= i + 1) {
ans = i + 1;
break;
}
}
if (ans == -1) {
cout << "IMPOSSIBLE\n";
}
else {
cout << ans << endl;
}
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Overrandomized
꽤나 신박한 내용의 문제였다. TC가 3가지로 나뉘는데, 마지막 TC의 경우 //(Q=-1//)로 고정이라는 것이 어떻게 보면 힌트가 좀 되었다.
문제 조건을 보면, N, R, D가 각각 chosen independently and uniformly at random from~ 과 같은 제약사항이 있다.
따라서 랜덤의 upper-bound역시 랜덤이므로, 이 값들은 순서는 중구난방이겠지만, 결국은 계단과 같은 모양으로 나타나게 될 것이다. //(10^4//)개의 쿼리 값들을 알려주니 대충 아래와 같은 형식으로의 값들이 나타난다고 볼 수 있겠다.
rand() % 10
rand() % 20
rand() % 30
rand() % 40
...
rand() % 100
이렇게 되면 아무래도 맨 앞자리의 수가 1로 시작하는 수의 값이 맨 앞자리의 수가 2로 시작하는 녀석보다는 많을 것이고, 2로 시작하는 녀석은 3으로 시작하는 녀석보다 많을 것이고.. 와 같은 통계적 상관관계가 나타날 것이다.
이러한 점을 이용해서 가장 앞자리에 나타나는 알파뱃의 출연 빈도를 체크해서 내림차순으로 정렬하면 이 알파뱃들이 1부터 9의 숫자를 나타낼 것이다.
또한 0의 경우는 첫번째 자리에서만 나타날 수 없는 수이므로, 전체 나타난 알파뱃 중 맨 앞자리에 나타나는 알파뱃들을 빼면 나오게 될 것이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
#define NUMTC 10000
typedef pair<ll, string> pis;
typedef pair<ll, char> pic;
ll cnt[30];
void solve() {
set<char> occurs;
set<char> nonzero;
occurs.clear();
nonzero.clear();
memset(cnt, 0, sizeof(cnt));
int U;
pis arr[NUMTC + 5];
vector<pic> ans;
ans.clear();
char output[11];
cin >> U;
for (int i = 0; i < NUMTC; i++) {
cin >> arr[i].first >> arr[i].second;
}
for (int i = 0; i < NUMTC; i++) {
auto& s = arr[i].second;
nonzero.insert(s[0]);
//첫번째만 셈
cnt[s[0] - 'A']++;
for (char c : s) {
occurs.insert(c);
}
}
for (int i = 0; i < 30; i++) {
if (cnt[i]) {
ans.push_back(make_pair(cnt[i], i + 'A'));
}
}
for (auto c : nonzero) {
occurs.erase(c);
}
char zero = *occurs.begin();
sort(ans.begin(), ans.end(), greater<pic>());
for (int i = 0; i < 9; i++) {
output[i+1] = ans[i].second;
}
output[0] = zero;
output[10] = 0;
printf("%s\n", output);
return;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Oversized Pancake Choppers
이 문제는 고생을 꽤 했다. 마지막 문제 답게 난이도도 꽤 어려웠던 것 같은 느낌이다.
근데 사실 아이디어는 어느정도 생각을 해서 Middle TC는 맞출 수 있을 것 같았는데 한가지 조건을 빼 먹어서 업솔빙하면서도 많이 틀려먹었다.
결국 wwiiiii님의 코드를 참고한 뒤 힌트를 얻었다.
analysis를 보고 미들 TC를 맞추는 풀이까지만 적용해서 풀어보았다.
조각의 크기를 //(Ai//)중 하나로만 가능하다고 생각한 고정관념에 따라 틀려버렸는데, 조각의 크기는 //(Ai / k//)가 가능하고, 이때 //(k//)는 1과 //(D//)사이의 수가 된다.
analysis에서 Time Complexity가 //(O(D*N^2)//)라고 했을때, D가 왜 들어가나 이해를 못했는데 이것 때문이었다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 305
ll A[MAXN];
void solve() {
ll N, D;
cin >> N >> D;
ll ans = D - 1;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
sort(A, A + N);
// K를 perfect-cut 개수라고 하면 D - K가 정답이 된다.
for (int i = 0; i < N; i++) {
for (ll k = 1; k <= D; k++) {
ll unit = A[i];// 조각의 크기는 unit / k이다.
ll pieces = 0; //조각의 개수
for (int j = 0; j < N; j++) {
ll chunk = A[j];
pieces += chunk * k / unit;
}
if (pieces < D) continue; //다 잘라도 이 조각 개수가 안나오는 경우 skip
pieces = 0;
int K = 0; // 모두 다 떨어지는 조각 개수
for (int j = 0; j < N; j++) {
ll chunk = A[j];
ll add = chunk * k / unit;
if ((chunk * k) % unit == 0 && pieces + add <= D) {
pieces += add;
K++;
}
}
ans = min(ans, D - K);
}
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
TC 3에 대한 솔루션 코드 업솔빙은 나중에 시간나면 해보도록 하겠다..... 나중에 스코어 보드를 보니, 한국인 참가자 중에서는 TC3를 맞춘 사람이 1명도 없었다. 코드를 보니 아이디어는 대충 비슷하게 구현은 한 것 같은데 다들 TLE가 나서 그런듯 하다.
올해 킥스타트 B라운드는 주말 아침8시에 시작을 해서, 어째저째 술먹고 새벽에 퍼질러 자다가 비몽사몽한상태에서 용캐 일어나서 한번 풀어보았다.
코드잼 1Round에서 엄청 발렸던 기분을 Kickstart를 풀면서 조금 달래주려 했는데, 확실히 Kickstart는 Codejam에 비해서는 난이도가 낮은 듯 한 느낌을 많이 받았다.
총 4문제가 나왔고, 예전에는 Large set은 Full feedback을 안주고 Hidden verdict형식이었는데, 이번에는 다 Visible verdict로 진행이 되었다.
Bike Tour
봉우리 갯수를 새는 문제이다. for loop로 순회하면서 좌우 값을 봐서 그 보다크면 봉우리로 갯수를 카운트 하면 되는 간단한 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int arr[105];
void solve() {
int n;
int ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
for (int i = 1; i < n - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ans++;
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Bus Routes
버스가 오는 시간 주기를 알때, 마지막 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다. 배수개념으로 접근하면 될 것 같은데, 파라메트릭 서치를 이용하면 간단하게 풀 수 있다. 쿼리를 바이너리 서치로 확인하는건데, 쿼리 확인시에는 floor(v/x) * x를 해서 가장 가까운 배수를 찾아내면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
ll a[1005];
int n;
ll d;
bool q(ll v) {
for (int i = 0; i < n; i++) {
ll x = a[i];
v = max(v, (v + x - 1) / x * x);
if (v > d)
return false;
}
return true;
}
void solve() {
ll l, r;
l = 1;
//r = (ll)1e12;
cin >> n >> d;
r = d;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
while (l < r) {
ll m = (l + r + 1) / 2;
//printf("%lld %lld %lld\n", l, r, m);
if (q(m)) {
l = m;
}
else {
r = m - 1;
}
}
cout << l << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Robot Path Decoding
문제 내용 자체보다는, Operation code 파싱이 더 어렵다. (를 만나면 같은 depth의 )의 인댁스를 찾아서 재귀로 짜보려다가 //(O(N^2)//)인데 TLE안나려나 궁금했다가 그냥 스택으로 짜는게 더 나을거 같아서 머리를 쥐어 짜면서 스택으로 파서를 만들어 보았다. 생각보다 파서가 간단하게 만들어 졌던 것 같다. 좌표계가 wrap-around되므로 그 부분을 처리해주는 함수를 따로 만들어서 썼다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const ll MOD = 1e9;
ll nor(ll v) {
if (v < 0)
v += MOD;
if (v >= MOD)
v %= MOD;
return v;
}
struct Data {
int op;
ll x, y;
void add(struct Data& rhs) {
x += rhs.x;
y += rhs.y;
x = nor(x);
y = nor(y);
}
void mult(int v) {
x *= v;
y *= v;
x = nor(x);
y = nor(y);
}
};
Data calc(char c) {
if (c == 'N') {
return { 0, -1, 0 };
//return make_pair(-1, 0);
}
else if (c == 'S') {
return { 0, 1, 0 };
//return make_pair(+1, 0);
}
else if (c == 'W') {
return { 0, 0, -1 };
//return make_pair(0, -1);
}
else if (c == 'E') {
return { 0, 0, 1 };
//return make_pair(0, +1);
}
else {
assert(false);
}
}
void solve() {
string s;
cin >> s;
//ll x, y;
//x = y = 0;
stack<Data> ss;
ss.push({ 0, 0, 0 });
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
ss.push({ c - '0', 0, 0 });
ss.push({ 0, 0, 0 });
}
else if (c == ')') {
Data operand = ss.top(); ss.pop();
Data mult = ss.top(); ss.pop();
Data prev = ss.top(); ss.pop();
operand.mult(mult.op);
prev.add(operand);
ss.push(prev);
}
else if (c >= 'A' && c <= 'Z') {
Data cur = ss.top(); ss.pop();
Data delta = calc(c);
cur.add(delta);
ss.push(cur);
}
}
ll y = (ss.top().y + 1);
ll x = (ss.top().x + 1);
cout << y << ' ' << x << endl;
while (ss.size()) ss.pop();
//x++; y++;
//cout << y << ' ' << x << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Wandering Robot
kickstart때는 못풀어서 나중에 Analysis랑 남의 코드들을 보고 업솔빙을 좀 했다. 아이디어 자체는 대충 냈었는데, 어차피 디테일부분을 못따라가서 구현법 팁을 알았어도 당시에는 못 풀었을 듯 하다.
1등한 사람의 코드도 좀 참고를 하고 이해안가는 부분을 동기형한테는 물어보고 해서 도움을 꽤 받았다.(사실 아직도 100%는 이해 안 된 것 같기도하고...)
이항계수를 구하는 부분에서 Precision Error가 많이 날 것 같았는데 결국 요구하는 정확도가 //(10^{-5}//)정도로 낮은 수준이기도 하고, log로 축소시켜서 계산한 뒤 다시 역로그(exp함수)로 되돌려서 계산하는 부분들이 신박했다.
근데 여기서 좀 쟁점이 되는 부분은 대각선이 딱 맞아떨어지지 않는 경우가 쟁점인데, 아래 그림을 보자.
참고로 아래 문단에서 구한다고 하는 것은 시작점을 //((0,0)//)라고 가정하고 도착지점 좌표를 //((x,y)//)라고 가정하면
//(\frac{1}{2}^{x+y}*\binom{x+y}{x}//)를 의미한다. 이를 //(f(x,y)//)라고 하자.
파란색들은 독립적으로 되기 때문에 각자 구해서 더하면 되는데, 파란색 위쪽에 비어있는 칸으로 가는 경우는 쟁점이 된다.
오른쪽 끝에 다다른 경우 무조건 아래로만 가기 때문에 해당 부분에 대한 내용들도 더해줘야 하는데, 이는 빨간색 박스에 도달하는 경우(실제로는 벽을 뚫을 순 없지만 뚫을 수 있다고 가정할 시)를 더해주면 된다. 어차피 벽을 뚫는경우 아래로 내려가는걸로 취급하면 되므로 그러하다.
근데 1등 코드를 확인해보면 노란색으로 가는 확률(f(노랑칸))에 1/2를 곱해서 더해버리는 식이다. 사실 노랑색 바로 아래 파란색(C) 입장에서는 바로 위 노란색(B)에서 아래로 1/2확률로 내려오는 것만 포함되어 있는데, 바로 위 노란색(B)에서 오른쪽으로 가는 경우의 확률도 더해져야 하므로 노란색으로 도달하는 확률에 1/2를 곱해서 더한다.
그리고 마찬가지로 가장 아래 노란색(B)으로 가는 확률은 바로 위 노란색(A)에서 1/2확률로 내려온경우는 포함되지만, 맨 위 노란색에서 오른쪽으로 가서 내려오는 경우확률이 빠져있으므로 이도 더해주는 식이라고 한다.(thanks for jrj) 각 부분의 정의를 명확하게 해줘야지 안햇갈린다고 한다.
설명하면서도 내가 약간 햇갈려서 첨언을 하자면, 대각선으로 구역을 나누는 경우 서로 겹치는 경우가 없으므로(독립이므로) 확률을 구해서 더해버리면 되는데, 노란색(B)의 경우와 아래 파란색(C)의 경우는 겹치는 경우가 있다. 그러므로 겹치지 않는 경우 중에 세어지지 않은 부분만 추가적으로 더해주는 것이다. 노란색(A, B)의 경우에서는 오른쪽으로 갈 확률이 0%이므로 이 부분만 따로 추가로 더해주는 것이고, 아래로 가는 확률이 100%, 오른쪽이 0%인데 이것이 50% 50%으로 더해져 있으므로, 부족한 아래로 가는 50%를 더해주는 것이다.
내가 착각을 했던 것이, A,B의 경우가 무조건 C까지 가야만 한다고 생각을 했는데, 어차피 C에는 A,B 경우의 수 중 절반은 더해져 있는 상황이고, 이 남은 절반만 더해주면 된다는 것이다. 이 남은 절반의 확률은 맨 오른쪽에서는 아래로만 내려가는 선택지만 생긴다는 특수한 상황때문에 생기는 것이기도 하다.
그리고 역으로 전체에서 중간 구멍으로 빠질 확률을 빼줘도 되는데, f(초록칸)을 죄다 구한 뒤 1/2를 곱해서 더하면 된다고 한다. 그리고 1에서 그 값을 빼줘도 될 것 같은데 아직 구현은 안해봤다.
아래 코드는 빨간칸을 구해서 다 더하는 방식의 코드이다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 200005
double lnfact[MAXN];
double bicof(int a, int b) {
return lnfact[a] - lnfact[a - b] - lnfact[b];
}
void solve() {
int W, H, L, U, R, D;
cin >> W >> H >> L >> U >> R >> D;
int dist = L + D - 2;
double ans = 0;
if (D < H) {
for (int i = 1; L - i > 0; i++) {
int x = L - i;
int y = D + i;
double logval = bicof(dist, x - 1);
logval -= dist;
ans += pow(2, logval);
}
}
dist = R + U - 2;
if (R < W) {
for (int i = 1; U - i > 0; i++) {
int x = R + i;
int y = U - i;
double logval = bicof(dist, x - 1);
logval -= dist;
ans += pow(2, logval);
}
}
cout << fixed << setprecision(8);
cout << ans << endl;
}
int main() {
for (int i = 2; i < MAXN; i++) {
lnfact[i] = lnfact[i - 1] + log(i) / log(2);
}
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": ";
solve();
}
}
끝나고 나서 맞은 상황이다. Interactive Problem이라서 디버깅 환경 구축하는 것도 꽤 귀찮고 했었다.
일단 푼 문제들 간단하게 리뷰를 해보자.
1. Vestigium (7pt)
첫번째 문제 답게 매우 쉬웠던걸로 기억한다. Latin square matrix라고 각 오와 열에 1부터 N까지의 수가 1번씩만 나타나는 녀석에서 왼쪽위부터 오른쪽아래로 되는 대각선의 값들의 합이 trace라고 하는데 임의의 matrix가 주어질 때, 이 trace를 구하고, Latin square rule을 위반하는 row와 column의 수를 출력하면 되는 그런문제이다.
하나하나 다 따라가면서 체크하면 답이 나온다. 문제 이해하는데 시간을 더 쓴 것 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int trace = 0, duprow = 0, dupcol = 0;
int matrix[105][105];
int n;
cin >> n;
int check[105];
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int v;
cin >> v;
matrix[i][j] = v;
check[v]++;
if (i == j) trace += v;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
duprow++;
}
}
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int& v = matrix[j][i];
check[v]++;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
dupcol++;
}
}
cout << trace << ' ' << duprow << ' ' << dupcol << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Nesting Depth (5pts, 11pts)
문자열 다루는 문제 같은 문제인데, 숫자가 나오면, 각각의 숫자는 자신을 둘러싼 괄호가 자신의 숫자만큼 나와야 한다. Greedy하게 이전 숫자보다 큰 숫자가 나오면 여는 괄호를 더 열어주고, 더 작은 숫자가 나오면 닫아주고, 마지막에 다 닫아주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
string s;
string ans = "";
cin >> s;
//int opened = 0;
int prev = 0;
for (char c : s) {
int cur = c - '0';
if (cur > prev) {
int diff = cur - prev;
//diff만큼 더 연다
for (int i = 0; i < diff; i++) {
ans += "(";
}
}
else if (cur < prev) {
int diff = prev - cur;
for (int i = 0; i < diff; i++) {
ans += ")";
}
}
prev = cur;
ans += c;
}
if (prev > 0) {
while (prev--) {
ans += ")";
}
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Parenting Partnering Returns(7pts, 12pts)
부모 두명이서 아기 돌보는 스케쥴?을 각자 스케쥴링 하는데, 가능하게 스케쥴링 하면 되는 문제이다. 각각 task가 시작하는 시간 기준으로 정렬을 한 뒤, 그리디하게 지금 일 가능한 녀석들을 스케쥴링 해주면 된다.
소팅하기 전에 원래 Index 기준으로 답을 입력해야 하는 것을 깜빡해서 한번 WA를 받았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
string mark[2] = { "C", "J" };
void solve() {
int fins[2];
fins[0] = fins[1] = 0;
int resp[1005];
memset(resp, -1, sizeof(resp));
int n;
vector<pair<pii, int>> tasks;
tasks.clear();
cin >> n;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
tasks.push_back(make_pair(make_pair(s, e), i));
}
sort(tasks.begin(), tasks.end());
for (auto task : tasks) {
bool alloced = false;
for (int candid = 0; candid < 2; candid++) {
if (fins[candid] <= task.first.first) {
fins[candid] = task.first.second;
//ans += mark[candid];
resp[task.second] = candid;
alloced = true;
break;
}
}
if (alloced == false) {
cout << "IMPOSSIBLE" << endl;
return;
}
}
string ans = "";
for (int i = 0; i < n; i++) {
ans += mark[resp[i]];
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
interactive_runner.py는 -- 기준으로 왼쪽에 있는 command와 오른쪽에 있는 command를 각각 쓰레드로 실행시킨 뒤, stdin/stdout를 각각 연결해주는 역할을 한다.
python3 judge.py 0라고 실행하면 서버가 어떻게 응답하는지를 확인해볼 수 있다. 0을 인자로 넣으면 1번째 test set(b=10)이 나오고, 1를 인자로 넣으면 2번째 test set(b=20)이 적용된다.
맨처음에 문제 내용을 이해하는데에도 꽤나 오래걸렸었다. 문제를 잘 이해못하고 테스팅 툴을 이해못해서, 파이썬 코드를 뜯어서 분석해 보기도 했었다.
문제 내용을 대충 설명해보자면, B bit의 임의의 수를 서버에서 지정한다. 이 값을 우리가 맞추면 되는데, 최대 150번의 쿼리가 가능하다. 각 쿼리를 하기 위해서 1~B에 해당하는 정수 하나를 보내면 그 쿼리 번째 bit값을 리턴해준다. 근데 10번 요청을 할 때 마다 서버에 저장된 B bit가 랜덤한 확률로 값이 바뀌게 된다. 50%확률로 Negation 연산이 일어나고(1이 0이 되고, 0이 1이 된다), 50%확률로 Reverse 연산이 일어나서 1번 비트가 B번 비트로, 2번 비트가 B-1번 비트가 되고 이런식으로 바뀌게 된다.
따라서 25%확률로 Negation만 일어나고 25%확률로 Reverse만 일어나고 25%확률로 Negation과 Reverse가 동시에 일어나고, 25%확률로 아무일도 안일어난다.
서버에 저장된 bit를 맞추는 것은 Negation, Reverse가 일어난것을 다 쳐서, 답을 맞추는 시점에 맞는 bit이기만 하면 정답처리가 된다. 그리고 정답을 제출하는 것은 Query로 안친다고 한다.
1번째 test set는 각 비트별로 값을 한번씩 다 물어본 뒤 이어서 응답을 주면 풀린다. 10번 쿼리를 했지만, 답변하는 것은 쿼리가 아니므로 비트 변조가 안일어난 상태이다.
2번째만을 위한 답 코드 말고 3번째에도 해당되는 솔루션을 생각했는데 대략 다음과 같다.
일단 bit값들을 앞에서부터 5개, 뒤에서부터 5개씩 해서 10개씩 받는다. 그러면 그 10개의 뭉치는 바뀌어도 같은 시점에 바뀌기 때문에 초기 값은 같은그룹들을 모을 수 있다.
첫번째 그룹은 [1~5]비트와 [96~100] 비트가 된다. 두번째 그룹은 [6~10]비트와 [91~95]비트가 된다.
같은 그룹끼리는 Reverse가 되어도 같은 그룹끼리 바뀌게 되므로 같이 움직인다고 볼 수 있다.
그러면 여기서 1번 비트와 해당하는 100번 비트가 둘다 같은 숫자이면 Reverse되어도 그대로이다. 그리고 1번 비트와 100번 비트가 서로 다른 숫자라면 Negation되어도 Reverse되는 것과 같은 효과가 난다.
이러한 점을 이용해서 같은 그룹내에 대칭인 bit와 아닌 bit가 둘 다 있다면, 이 2개의 비트를 확인해서 Negation이 되었는지 Reverse가 되었는지를 확인할 수 있다.
그리고 만약 한 그룹이 모두 대칭인 수로만 이루어져 있거나, 모두 비대칭인 수로만 이루어져 있다면 더욱 쉽다. 대칭인 수로만 이루어져 있으면 Neg만 확인하면 되고, 비대칭인 수로만 이루어져 있으면 Rev랑 Neg랑 동일하게 칠 수 있다.
이를 이용해서 그룹의 수를 모두 알아내고(100번의 쿼리로), 각각 그룹 별 Neg랑 Rev가 일어났는지를 체크를 한다. 각각 그룹당 2번 이하의 쿼리로 일어났는지를 확인할 수 있으므로 10번의 쿼리마다 5개의 그룹을 확인할 수 있다. 그리고 10번의 쿼리가 일어난 뒤는 Bit fliping이 어떻게 일어났는지 알기 위해서 기준이 되는 그룹을 하나 두고(이 그룹은 비대칭과 대칭이 둘다 있어야지 Rev와 Neg를 둘다 확인가능) 그녀석으로 체크를 한다.
그래서 10번의 쿼리마다 최소 4개의 그룹의 상태를 확인가능하다.
그러면 130번 쿼리 내에 모든 그룹의 상태를 확인할 수 있다.
디버깅 할때에는 query 함수를 디버깅용 서버 상태를 알려주는 녀석으로 만들어서 했다.
모두 대칭이거나 비대칭인 경우의 체크를 조금 잘못해서 3번째 set에서 틀리긴 했었는데 고쳐서 이제는 모두 정답이 나온다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define TOTAL_BIT_NUM 105
#define GROUP_NUM 12
int tc, n;
int bits[TOTAL_BIT_NUM];
int mirror[TOTAL_BIT_NUM];
int mirror_cnt[GROUP_NUM];
int neged[GROUP_NUM];
int reved[GROUP_NUM];
int g_neged, g_reved;
void solve10() {
for (int t = 1; t <= tc; t++) {
string ans = "";
for (int i = 1; i <= n; i++) {
cout << i << endl;
cout.flush();
string s;
cin >> s;
ans += s[0];
}
cout << ans << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
pii get_canary(int gnum) {
int neg_canary, rev_canary;
neg_canary = rev_canary = -1;
for (int i = gnum * 5; i < gnum * 5 + 5; i++) {
if (mirror[i] && neg_canary == -1) {
neg_canary = i; //rev 되도 변하지 않음
}
if (!mirror[i] && rev_canary == -1) {
rev_canary = i; //rev 되면 변함
}
}
return make_pair(neg_canary + 1, rev_canary + 1);
}
//debug
/*
int samples[] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1 };
int query(int pos) {
static int count = 0;
int ret = samples[pos - 1];
count++;
if (count == 10) {
cout << "---------------------------------------" << endl;
count = 0;
if (rand() % 2 == 0) {
cout << "Negation !!!" << endl;
for (int i = 0; i < 100; i++) {
samples[i] ^= 1;
}
}
if (rand() % 2 == 0) {
cout << "Reversed !!!" << endl;
for (int i = 0; i < 50; i++) {
swap(samples[i], samples[99 - i]);
}
}
cout << "---------------------------------------" << endl;
}
return ret;
}
*/
int query(int pos) {
cout << pos << endl;
cout.flush();
int ret;
cin >> ret;
return ret;
}
void solve_large() {
while (tc--) {
//입력받기
memset(bits, -1, sizeof(bits));
memset(mirror, 0, sizeof(mirror));
memset(mirror_cnt, 0, sizeof(mirror_cnt));
memset(neged, -1, sizeof(neged));
memset(reved, -1, sizeof(reved));
g_neged = g_reved = 0;
for (int i = 0; i < n / 10; i++) {
// [i*5+1, i*5+5]이랑 [n-5*i-4, n-5*i]
//10개씩 뭉텅이로 받되, 앞에서부터 5개, 뒤에서부터 5개가 하나의 셋트이다.
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] = query(j + 1);
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] = query(j + 1);
}
}
//base group를 찾는다.
//base는 palindrome한 쌍과 palindrome 아닌 것 값 하나를 알아내면 된다.
//팰린드롬은 complement 연산을 했는지를 확인하는 용도이다.
//palindrome아닌 것은 reverse연산을 했는지 확인하는 용도이다.
//base 그룹은 mirror_cnt가 1~4 사이의 값이다.
for (int i = 0; i < n / 2; i++) {
int j = n - i - 1;
if (bits[i] == bits[j]) {
mirror[i] = mirror[j] = 1;
mirror_cnt[i / 5]++; //해당 그룹에 palindrome 인 수 개수.
}
}
// mirror_cnt가 5인 그룹에는 rev 연산이 무의미함
// mirror_cnt가 0인 그룹은 rev 연산과 neg 연산이 같다.
int base_gnum = -1;
for (int i = 0; i < n / 10; i++) {
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
base_gnum = i;
break;
}
}
if (base_gnum == -1) {
//모든 그룹이 palindrome이거나 그 반대인경우
//neg만 체크하면 된다.
for (int i = 0; i < n / 10; i++) {
int k = i * 5 + 1;
int res;
res = query(k);
if (bits[k - 1] != res) {
//real time negation
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) {
s += "1";
}
else {
s += "0";
}
}
cout << s << endl;
cout.flush();
//get response
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
else {
//일반적인 섞여있는 경우
pii base_canary = get_canary(base_gnum); // {neg, reg}
int query_left = 8;
if (query(base_canary.first) != bits[base_canary.first - 1]) {
neged[base_gnum] = 1;
}
else {
neged[base_gnum] = 0;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum])) {
reved[base_gnum] = 1;
}
else {
reved[base_gnum] = 0;
}
(void)0;
for (int i = 0; i < n / 10; i++) {
if (i == base_gnum) continue; //base 그룹은 미리 구해놨으므로 안구해도 된다.
if (query_left < 2) {
if (query_left == 1) query(1);
query_left = 8;
if (query(base_canary.first) != (bits[base_canary.first - 1] ^ neged[base_gnum] ^ g_neged)) {
g_neged ^= 1;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum] ^ reved[base_gnum] ^ g_neged ^ g_reved)) {
g_reved ^= 1;
}
}
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
pii canary = get_canary(i);
query_left -= 2;
if (query(canary.first) != (bits[canary.first - 1] ^ g_neged)) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
if (query(canary.second) != (bits[canary.second - 1] ^ g_neged ^ g_reved ^ neged[i])) {
reved[i] = 1;
}
else {
reved[i] = 0;
}
}
else {
query_left--;
if (query(i * 5 + 1) != ((bits[i * 5] ^ g_neged) ^ (mirror_cnt[i] == 0 ? g_reved : 0))) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
reved[i] = 0;
}
}
//apply answers
for (int i = 0; i < n / 10; i++) {
int cneged = (g_neged ^ neged[i]);
int creved = (g_reved ^ reved[i]);
if (cneged) {
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
if (creved) {
for (int j = i * 5; j < i * 5 + 5; j++) {
int k = n - j - 1;
swap(bits[j], bits[k]);
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) s += "1";
else s += "0";
}
cout << s << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
return;
}
int main() {
cin >> tc >> n;
if (n == 10) {
solve10();
}
else {
solve_large();
}
}
5. Indicium(7pts, 25pts)
마지막 문제인데, Small tc만 풀이법을 알겠고, large는 모르겠다.
원하는 Trace에 해당하는 Latin square matrix를 찾거나, 불가능하다고 말해줘야하는 그런 문제이다.
Backtracking으로 풀 수 있고, 특정 K값을 트레이스로 갖는지 알아야 한다.
만약 K가 주어지면, 1~N의 범위의 수 N개의 합으로 K를 만들 수 있는 조합들을 구해본다.
그리고 그 조합들의 수로 대각선으로 나열한 뒤, 남은 칸에다가 수를 채워서 Latin square matrix를 만들 수 있는지만 확인하면 된다.
이때 만약 수 조합이 1 2 2 3 4 라는 조합으로 12라는게 되는지 확인해야 할 때, 순서는 중요치 않다는 것을 알 수 있는데, 이때 하나의 성질을 활용하면 된다.
즉 1 2 2 3 4로 Latin square 매트릭스를 만들 수 있으면 1 3 4 2 2 로도 만들 수 있는데, Latin square matrix는 행 단위로 순서를 바꾸거나 열 단위로 서로 순서를 바꾸어도 Latin square matrix이다. 왜 그런지는 조금만 생각해보면 알 수 있다.
따라서 조합별로 가능한 라틴 스퀘어 매트릭스가 있는지를 다 체크해보면 Small tc는 맞출 수 있다.
Large tc는 이분매칭을 쓴다는 것 같은데, 나중에 다시 공부해봐야 겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int n, k;
//n개의 숫자(1~n) 합으로 k를 만드는 경우의 수를 다 만들어야한다.
int val[6];
struct Chunk {
int v[5];
};
vector<Chunk> comb[26];
void dfs(int offset) {
if (offset <= n) {
for (int i = val[offset - 1]; i <= n; i++) {
val[offset] = i;
dfs(offset + 1);
}
}
else {
Chunk chunk;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += val[i];
chunk.v[i - 1] = val[i];
}
comb[sum].push_back(chunk);
}
}
int row[5], col[5];
int field[5][5];
bool backtrack(int i, int j) {
if (i >= n) {
//모두 성공한 경우
cout << "POSSIBLE\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << field[i][j] << ' ';
}
cout << endl;
}
return true;
}
if (j >= n) {
//다음줄로 이동
return backtrack(i + 1, 0);
}
if (field[i][j] != -1) {
//이미 지정된 경우(diagonal)
return backtrack(i, j + 1);
}
for (int v = 1; v <= n; v++) {
if (((row[i] & (1 << v)) == 0 && (col[j] & (1 << v)) == 0)) {
//set
field[i][j] = v;
row[i] |= (1 << v);
col[j] |= (1 << v);
//search
if (backtrack(i, j + 1)) {
return true;
}
//unset
row[i] &= (~(1 << v));
col[j] &= (~(1 << v));
field[i][j] = -1;
}
}
return false;
}
void solve() {
cin >> n >> k;
for (int i = n; i <= n * n; i++) {
comb[i].clear();
}
//n에 대한 가능한 모든 숫자 조합들을 만들어냄
dfs(1);
for (int i = 0; i < comb[k].size(); i++) {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(field, -1, sizeof(field));
for (int j = 0; j < n; j++) {
int v = comb[k][i].v[j];
field[j][j] = v;
row[j] |= (1 << v);
col[j] |= (1 << v);
}
if (backtrack(0, 0)) return;
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
val[0] = 1;
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?
그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int A[100005];
void solve() {
int N, B;
cin >> N >> B;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
sort(A, A + N);
int ans = 0;
for (int i = 0; i < N; i++) {
if (B >= A[i]) {
B -= A[i];
ans++;
}
else {
break;
}
}
printf("%d\n", ans);
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Plates
접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.
dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서 dp가 맞는 듯 했다.
2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.
//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수
이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.
for-loop를 돌리는 식으로 구현해보았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
int N, K, P;
cin >> N >> K >> P;
memset(dp, 0, sizeof(dp));
memset(a, 0, sizeof(a));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
cin >> a[i][j];
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= K; i++) {
dp[1][i] = a[1][i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= i * K; j++) {
for (int k = 0; k <= K; k++) {
dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
}
}
}
printf("%d\n", dp[N][P]);
return;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Workout
이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때 수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.
최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.
인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.
그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int M[100005];
int N, K;
bool ok(int v) {
int k = K;
for (int i = 1; i < N; i++) {
int diff = M[i] - M[i - 1];
k -= (diff + v - 1) / v - 1;
}
return k >= 0;
}
int solve() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> M[i];
}
int l = 1;
int r = 1e9;
while (l < r) {
int m = (l + r) / 2;
if (ok(m)) {
r = m;
}
else {
l = m + 1;
}
}
return r;
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
4. Bundling
문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..
K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.
A A A B C C C D E E E F
이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.
솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.
A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.
조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.
Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.
그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 2000006
class Node {
public:
char c;
int num;
int next[28];
Node() {
clear();
}
void clear() {
memset(next, 0, sizeof(next));
num = 0;
c = 0;
}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
auto& cnode = nodes[v];
int ret = cnode.num / k;
for (char c = 'A'; c <= 'Z'; c++) {
if (cnode.next[c - 'A'])
ret += dfs(cnode.next[c - 'A'], k);
}
return ret;
}
int solve() {
int n, k;
cin >> n >> k;
//clear prev data
for (int i = 0; i <= cnt; i++) {
nodes[i].clear();
}
cnt = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int ptr = 0;
for (char c : s) {
auto& next = nodes[ptr].next[c - 'A'];
if (!next) {
next = ++cnt;
nodes[next].c = c;
}
ptr = next;
nodes[ptr].num++;
}
}
return dfs(0, k);
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
방금 작성한 포스팅이 1753번 최단경로 문제(다익스트라 기본문제) 였는데, 이 포스팅을 쓰면서 오랜만에 다익스트라 알고리즘을 다시 한번 생각해보게 되었었다.
근데 곧이어 1854번 문제를 풀었는데 그냥 생각나는대로 푸니 되었어서 좀 얼떨떨한 상태이다.
어쨋든 방금 서술한 것과 마찬가지로 1854번 문제도 다익스트라 최단경로 찾기 알고리즘을 사용하는 문제인데, 기본적인 다익스트라 알고리즘은 shortest path므로 가장 짧은 경로를 찾는 알고리즘이다.
그런데 이 문제를 보면 K번째로 짧은 경로를 찾아야 한다.
그래서 아까 포스팅에서 다익스트라 알고리즘을 이야기 하다가 나왔는데, 우선순위 큐에서 가장 먼저 나와서 해당 정점을 처음 방문한 녀석이 가장 짧은 길이라고 서술했었다.
그리고 큐에는 그 정점을 방문할 만한 다른 path 결과도 있지만 처음 나온 녀석이 가장 짧은 경로이기 때문에 그리디 알고리즘이라고도 이야기를 했었다.
그렇다면 두번째로 그 정점을 방문한 녀석은 두번째로 짧은 경로가 될 것이고, 세번째로 방문한 녀석은 세번째로 짧은 경로가 될 것이다.
이러한 방식으로 K번째 방문한 path로 길이를 설정하면 K번째 최단경로를 구할 수 있을 것이다.
다행히 K값이 100으로 작고 N도 1000로 정점수가 그에 맞게 작은 값이다.
이를 이용하여 다익스트라 알고리즘을 변형하면 문제를 쉽게 풀 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define INF 2000000000
#define MAXN 1003
#define MAXK 102
vector<pii> edges[MAXN]; //dest, weight
int visit[MAXN];
int dist[MAXK][MAXN]; // [i][j] = i번째 최단경로로 j방문하는 길이
int main() {
int discovered = 0;
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dist[j][i] = INF;
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
(void)scanf("%d%d%d", &u, &v, &w);
edges[u].push_back({ v, w });
}
priority_queue<pii> pq; // -dist, index
pq.push({ 0, 1 });
while (pq.size()) {
pii cur = pq.top(); pq.pop();
int distance = -cur.first;
int current = cur.second;
if (visit[current] >= k) continue; //k번째 최단경로를 다 구한경우
int cnt = ++visit[current]; //방문 횟수
dist[cnt][current] = distance;
if (cnt == k) discovered++;
if (discovered == n) break;
for (pii nx : edges[current]) {
int next = nx.first;
int weight = nx.second;
pq.push({ -dist[cnt][current] - weight, next });
}
}
for (int i = 1; i <= n; i++) {
if (dist[k][i] == INF) {
puts("-1");
}
else {
printf("%d\n", dist[k][i]);
}
}
return 0;
}
