문제 이해 단계 문제 자체는 굉장히 심플한 편이었다. 총 N개의 풍선이 있고 안에 있는 종이의 수만큼 이동한다. 여기서 생각해야 할 점은 이미 터진 풍선은 이동 횟수에 포함되지 않는다는 점과 1번째 풍선과 마지막 풍선이 순환 구조를 이룬다는 점이다. 문제 접근 단계 풍선 번호 이동 규칙을 보면, 원형 연결 리스트로 구현하여 풀라는 의도인 것 같다. 근데 솔직히 포인터 그런 걸로는 풀기 싫어서 vector를 사용해서 풀고자 생각했다. 풍선의 번호는 (인덱스 + 1)이고, 그 풍선 배열의 값을 종이라고 생각했다. 종이에는 0이 있을 수 없으니 선택된 풍선(터진 풍선)을 0으로 설정한다. 이렇게 하면 선택된 풍선의 값이 0이라면 이미 터진 풍선이라고 간주할 수 있다. 현재 풍선의 위치를 잡고, 그 위치를 기준..

문제 이해 단계 해당 문제에서 나오는 게임은 옛날에 해봤던 게임이어서 문제를 이해하는 데는 오래 걸리지 않았다. 다만 몇몇 포인트들에 관해서만 유의 깊게 살펴봤는데, 첫 번째는 뱀이 이동하는 과정에서 머리 먼저 움직이고 꼬리가 줄어든다는 점이다. 두 번째는 보드의 크기가 100을 넘지 않는다는 점을 유의 깊게 봤다. 문제 접근 단계 이 문제의 구현을 위해 여러 가지 섹터로 나누어서 생각했다. 1. 실행이 끝나는 경우(게임오버) 게임오버가 되는 경우는 크게 두 가지가 있다. 첫 번째는 벽에 닿았을 때인데, 이걸 구현하는 것 뱀의 머리 위치가 N보다 크면 게임오버 구현하는 것은 간단하다고 생각했다. 두 번째 자기 몸에 닿았을 경우인데, 이 경우가 생각하기에 좀 복잡했다. 왜냐하면 몸길이가 늘어날 수도 있기 ..

문제 이해 단계 해당 문제는 예제 케이스로 주어진 것을 보면 금방 이해된다. 한마디로, *에는 어떤 문자가 몇 개 들어가던지 상관없다. * 앞에 있는 문자열로 시작하고, * 뒤에 있는 문자열로 끝나는 것인지를 판별하는 문제이다. 문제 접근 단계 문제를 푸는 로직을 짜는 법은 간단했다. 패턴 문자를 입력받아 이를 *를 기준으로 잘랐다. 그리고 frontStr, backStr로 분리해서 비교해야 할 문자열이 frontStr로 시작하는지 판단한다. 그리고 backStr과 같은 문자로 끝나는지 비교하여 문제 조건을 만족하는지를 판단했다. 예를 들어 패턴이 a*d였다면 frontStr 문자열에 a backStr 문자열에 d 를 받아 이를 문자와 비교했을 것이다. 로직은 굉장히 간단했던 것 같다. 아마 식별자를 기..

문제 접근 단계 위 문제를 처음에는 오름차순 또는 내림차순 정렬을 해둔 뒤 여러 탐색 기법을 사용해서 풀려고 했다. 그런데 합이 S가 되는 부분수열의 개수가 하나 이상이 나올 수 있어서 이렇게 해결하는 것은 비효율적이라고 생각했다. 예제에서 답이 나올 수 있는 케이스는 부분 수열이 -3,-2,5 일 때이다. 이럴 경우에는 답이 하나여서 반복으로 특정할 수는 있겠지만, 만약 답이 여러 개인 경우에는 구하기가 굉장히 어려워진다. 그래서 접근법을 바꿔서 생각했는데, 각각 수열의 원소를 하나의 요소로 본다는 생각을 가졌다. 예제 케이스에서는 -3,-2,5가 원소이다. 이를 통해서 해당 원소가 포함되는 경우와 안 되는 경우를 전부 나눠서 생각해 보면 이런 식의 그림이 나오게 된다. 예를 들어 가장 위쪽의 화살표만..

문제 이해 단계 https://www.acmicpc.net/problem/1874 이해하는데만 엄청 오래 걸렸던 문제 같다. 처음에 힌트가 있는 줄도 모르고 예제 케이스 입력이랑 출력 비교해 가면서 어떻게든 이해해 보려고 고생을 했다. 내가 잘못 이해했던 점은 입력으로 들어간 수열로 계산을 하는 게 아니라 입력으로 들어간 수열이 최종적으로 나오는 것이었다. 문제를 간단히 표현하면, 맨 처음 수열의 개수 n이 주어지고 스택에 1부터 n까지를 순차적으로만 넣을 수 있다. 스택에서 꺼낸 숫자는 수열에 추가된다. 이 방식으로 입력에서 넣은 수열을 만들어야 한다. 이때 이뤄지는 과정을 출력하는 건데, push(+), pop(-)로 처리하고 만약 입력 수열을 만들 수 없다면 No를 출력한다. 문제 접근 단계 당연히..

문제 이해 단계 https://www.acmicpc.net/problem/2630 문제 이해 자체는 간단했다. 정사각형의 종이가 색이 같지 않다면, 이를 4 등분하여 다시 정사각형을 만든다. 또 만들어진 정사각형에서 종이의 색이 모두 같지 않다면 4등분을 하는 과정을 반복하는 것이다. 이때 파란 색종이와 흰 색종이가 총 몇 장 나오는지 구하는 문제 문제 접근 단계 일단 문제 자체가 재귀함수의 대표문제로 보였다. 4 등분하는 과정을 반복하는데 줄어드는 건 색종이의 크기밖에 없었기 때문이다. 색종이의 각 색깔을 이차원배열에 넣어 판단하는 것이 가장 빠르다고 생각했다. 각 재귀마다 이차원 배열을 생성하는 것은 왠지 메모리 초과나, 시간 초과가 뜰 것 같아, 이차원 배열을 전역변수로 설정했다. 그리고 x좌표와 ..

문제 이해 단계 해당 문제는 간단해서 이해하는 데는 크게 어려움이 없었다. 그냥 자료구조 '큐' 안에 우선순위가 있는 문서들이 있는데, 우선순위에 따라 출력한다.그중 인덱스 M에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제. 첫 줄에는 이 테스트케이스를 실행할 횟수를 입력한다. 이후에는 문서의 개수 N, 타깃 문서의 인덱스 M, 다음 줄에는 각 자리에 있는 문서의 우선순위를 입력한다. (숫자가 높을수록 우선순위가 높음) 문제 접근 단계 문제 자체는 명료해서 포인트를 우선순위가 중복될 수 있다는 점을 생각했다. 해당 테스트 케이스를 참고하여 문제를 구현하였다. 문제를 해결하기 위해 여러 가지 포인트들이 있었다. 포인트 1. "내가 찾는 문서와 같은 우선순위 문서들을 어떻게 구분할까?" 내가 찾은 방법은..

문제 이해 단계 해당 문제는 이해하는데만 해도 30분 정도 걸렸다. 요약하자면 N일 동안 용돈 관리를 하는데, 그날 사용해야 할 금액이 존재한다. 용돈 관리를 하다가 돈이 부족하면 금액 K를 인출한다. 이때, 인출은 M번까지만 가능하다. 이때 조건을 만족하는 최소 금액 K를 구하는 것 문제 접근 단계 1. 위 문제 조건에 부합하는 금액 K를 찾는 것이기 때문에 K의 범위를 점점 줄여나가면서 찾는 탐색을 할까?라고 생각했고, 그중에서 1초라는 짧은 제한시간 때문에 "빠르게 탐색해야 하는 이진탐색 문제가 아닐까 생각했다. 2. 금액 K의 범위를 생각해 봤는데, 그날 써야 하는 금액보다 인출금액 K가 작으면 조건이 성립을 안 한다. 그렇기 때문에, 각 날의 써야 하는 금액 중 가장 높은 금액보다는 무조건 크거..