Doby's Lab

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 문제에서 요구하는 질투심의 최솟값을 알아내기 위해 이분 탐색으로 질투심의 최솟값을 도출할 수 있는 방법이 떠오르지 않아서 '다른 값을 도출해야 하나'라고 생각했다. 나에게는 기존에 항상 이분 탐색에서 썼던 틀(?) 같은 게 있었다. while (low > 이상으로 나누어주면 이분탐색에서 최대한 많은 사람에게 // 나누어주려하기 때문에 결과값이 도출 될 수 없다. return n >= cnt; } [..

문제를 풀다 보면 어떤 한 변수를 자료형이 가질 수 있는 최댓값 혹은 최솟값으로 선언할 일이 생긴다. 일일이 선언하는 경우는 까다로워 그와 관련된 헤더 파일이 있다는 것을 알게 되었다. https://docs.microsoft.com/ko-kr/cpp/c-language/cpp-integer-limits?view=msvc-160 C 및 C++ 정수 제한 자세한 정보: C 및 C++ 정수 제한 docs.microsoft.com

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이번 문제는 논리도 한 번에 나오고, 구현에도 막힘이 없었고, 반례도 스스로 찾아 넣으면서 엄청 성취감을 줬던 문제다. 다음 도형에서 보라색을 제외한 4가지 도형은 DFS로 구할 수 있지만 보라색은 BFS로 하기엔 번거로워서 아이디어를 내서 구현했다. 즉, 이 문제에서는 4가지 도형과 보라색 도형을 따로 구분할 줄 아는 분석력과 보라색 도형의 경우를 구현하는 능력을 필요로 한다. DFS로 생각했던..

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net (미루고 미뤄왔던 문제) 기존에 사용하던 방식의 DP를 사용하는 문제는 맞지만 계속 오버플로우가 나는 현상이 발견된다. 이유는 피보나치 10000이 다음과 같은 값을 가진다. 즉 C++에서 가장 큰 정수 자료형 unsigned long long으로 풀려고 시도할지라도 오버플로우가 나타난다. 유독 C++로 PS 하는 사람들이 이 문제를 겪는다. 처음으로 C++..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이 문제를 처음 보자마자 BFS를 떠올릴 수 있었지만 '제일 포인트가 되는 부분이 벽은 어떻게 세우지'가 고민거리였다. 하나하나 다 따지기엔 경우의 수가 너무 많아서 괜찮을까 싶었지만 주어진 평면의 크기는 8x8이라서 8^6(582144)로 큰 시간을 따지지는 않겠다는 생각이 들었다. (벽이 한 좌표에 몰빵 되는 경우도 계산한 것 >> 중복을 따지기엔 시간 계산에 너무 많은 시간을 쏟고 싶지 않았음.) 재귀 ..

이 문제는 크게 고민할 필요 없이 백트래킹으로 쌍 구하고, 최대공약수를 구해 더해나가면 되는 문제였다. 하지만 이를 구현했을 때, 시간 초과가 발생한다. 코드 (시간 초과) 백트래킹에서 발생하는 것인지, 최대공약수를 구하는 함수에서 발생하는 것인지 알 수 없었다. 하지만, 1,000,000을 넘지 않는 수라면 그에 근접하는 엄청 큰 수들이 100개까지 있다고 생각해보면 몇 쌍들이 생길지 모를뿐더러 거기다가 곱하기 1,000,000을 해준다면 엄청 큰 값이 나와서 시간 초과를 유발하는 것을 알 수 있었다. >> 최대공약수를 구하는 함수가 문제다. #include #include #include using namespace std; bool visited[101] = { 0, }; vector two; //..

이번 문제 논리는 굉장히 어려울 줄 알았다. 어떻게든 솔루션을 발견하려고 각 값의 연관성을 찾으려 했다. 그 결과 TC에서 논리를 찾을 수 있었다. Input 10 12 3 9 Output 33 10과 12 즉, M과 N의 차이는 +2다. x와 y의 차는 +6이다. 이를 보고, +6은 +2의 3배니까 3바퀴 정도 돌면 차이가 3배만큼 벌어질 거 같다는 생각에 10을 기준으로 3바퀴를 돌려보니 30과 30 각각의 M과 N으로 나눈 나머지는 0과 6이 나온다. (정확히 말하면 10은 3바퀴, 12는 2바퀴 돌고 6번의 해가 지난 것이다.) 여기서 3번의 해가 더 지나면 3 9가 x, y값과 일치하면서 맞아떨어진다. (10을 기준으로 3바퀴 돌렸으므로) 10 * 3 + (3번의 해가 지났으므로) 3 = 33 ..

백준 15094번 문자열 관련 문제를 풀다가 VS 컴파일러에서는 오류가 없지만 백준에서는 Segfault Error가 나서 문제점을 찾았었다. 전에도 이런 비슷한 문제를 풀다가 똑같은 오류가 났었는데 두 문제의 공통점이 있었다. 문자열 문제 스택을 이용하여 풀려했다 문자열은 문제가 없는 거 같아서 스택을 살펴보았다. 아래 코드는 VS 컴파일러에서는 문제가 없지만 백준에서 에러가 발생한다. #include #include #include using namespace std; int main() { char idx[1001]; cin.getline(idx, 1001, '\n'); stack s; for (int i = 0; i < 1001; i++) { if (idx[i] == 'U') { if (s.emp..