Doby's Lab

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 저번에는 안 풀리던 문제였는데 오랜만에 시도해보니 풀렸다. 저번 코드는 잘 기억나진 않지만 이번에 한 거보다 더 복잡했던 거 같은데 기억이 안 난다. 여러 가지 경우를 계속 생각했었던 거 같다. 기억나는 건 이런 경우? 하지만, 구현한 코드에서는 상관없다! 주사위를 굴렸을 때 나오는 모든 경우(1 ~ 6)를 다 따지기 때문이다! 이번 문제는 '응용력'..

[문자열 더하기] string strSum(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); while (a.length() > b.length()) { b += '0'; } while (a.length() < b.length()) { a += '0'; } int alone; int carry = 0; string result; for (int i = 0; i < a.length(); i++) { alone = ((a[i] - '0') + (b[i] - '0') + carry) % 10; result += to_string(alone); carry = ((a[i] - '0') + (b[i] - '0') + car..

https://www.acmicpc.net/problem/2139 2139번: 나는 너가 살아온 날을 알고 있다 우리는 일상생활에서 휴가 일수를 계산하는 것 처럼 두 날짜 사이의 기간을 계산해야 하는 경우가 많다. 이때, 계산을 하는 가장 간단한 방법은 적당한 날짜를 잡은 뒤 계산할 날짜가 될 때까지 www.acmicpc.net 문제 제목에 끌려서 들어갔다가 오랜만에 윤년 문제였다. 윤년이 무슨 소리인지는 알겠으나 문제를 또 보고 구현하려니 헷갈리고 그냥 윤년 조건은 통째로 외워버려야겠다. ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0) [전체 코드] #include using namespace std; int month[13] = { 0, 31, 28, 31,..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이번 문제는 문자열을 통으로 받아서 수와 연산자들을 분리하고, 또 받은 수에 앞이 0이 붙어있을 경우 앞에 0을 제거해주는 작업을 한 뒤 그리디하게 괄호를 붙여주면(논리 작업) 풀리는 문제다. (구현 어려울까봐 미루던 문제) 우선 입력을 받고 문자열을 다음과 같은 포인트에서 수로 변환하는 작업을 거친다. 1. 연산자가 나올 때 2. 끝날 때 수를 받고서 예를 들어, "00085"인 경우 앞에..

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 무한 루프..