Doby's Lab

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제는 백트래킹 알고리즘의 대표 문제라고 할 만큼 백트래킹하면 N-Queen 문제를 사람들이 많이 떠올린다. 하지만, 백트래킹을 이제 막 배우고, 겨우 구현할 수 있는 시점이라면 백트래킹을 공부하는 데에 있어서 당장 이 문제를 추천하고 싶진 않다. 백트래킹을 대표하는 문제이기는 하되 접근성이 쉬운 문제는 아니기 때문이다. 처음에 접근할 때는 2차원 배열로 접근을 했다. goQueen이라는 함수를 선..

https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 이 문제는 저번에 풀었던 문제와 똑같다고 생각했다. (https://www.acmicpc.net/problem/10826) 당연히 포인트도 똑같이 수를 문자열로 바꾸어 합을 구하는 함수를 구현하는 게 포인트라고 생각했다. 똑같은 풀이를 제출했으나 '메모리 초과'라는 오류를 받는다. 메모리가 크게 발생할 곳은 배열 밖에 없다고 생각했지만 배열을 안 ..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 이번 문제 또한 스택을 사용해야 할 거 같다는 확신이 들었다. 하지만, 스택을 이용해서 트릭을 만들어낼 수 있는 능력이 이번 문제의 포인트다. 솔루션 "IOIOI"라는 문자열에 n이 1이라면 답은 2가 출력되어야 한다. 내가 만든 트릭은 첫 "IOI"가 발생할 때, 이를 스택에 담고 n이 1인 경우를 만족시켰으므로 하나를 coun..

https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net DFS로 구현을 하려 했던 문제이다. 26가지 경우의 수(알파벳 개수) 중에 모든 경우를 따져보며 하나씩 더해갈 때마다 지금 문자열이 팰린드롬인가?를 따져보려 했었다. 하지만, 이전에 반복되었던 DFS 관련 실수가 다시 일어났다. 답을 구현하는 종료 조건이 명확하지만 다른 리커시브 콜은 계속 무한 루프를 돌리고 있었던 점을 반복 실수했다. (DFS로 구현하려 했던 코드는 맨 아래에) (DFS 무한 루프..

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++..