문제 이해 단계 https://www.acmicpc.net/problem/20365 문제 자체는 이해하기 쉽다. 이웃한 번호까지 한 번에 같은 색으로 칠한다. 예를 들어 1번 7번을 선택하면, 1~7번까지 모두 같은 색으로 칠해진다는 뜻이다. 이런 식으로 했을 때, 모든 번호를 원하는 색으로 칠하는 최소 횟수를 구하라는 것이 문제이다. 문제 접근 단계 어떻게 하면 최소로 할 수 있을까? 라고 생각을 하다가 예시에 나와있는 BBRBRBBR로 생각을 했다. 첫 번째로 B로 최대한 많은 색을 칠한다.(1~7번) 이후 사이사이 박혀있는 R을 칠하는데 이웃한 것이 있다면 같은 횟수로 간주한다. 하지만 여기서는 R이 다들 떨어져 있기 때문에, 하나씩 간주했다. 그래서 (1~7번), (3번), (5번), (8번) 총..
문제 이해 단계 문제 자체는 굉장히 단순하다. 운동을 2개씩 짝지어하는데, 하나가 남을 경우 그건 따로 진행한다. 이런 식으로 진행하는데 2개의 숫자의 합과 남은 하나의 숫자를 최소 값으로 하는 수를 찾는 것이다. 문제 접근 단계 이 문제의 포인트는 주어진 운동의 수가 홀수인가 짝수 인가로 나뉜다. 운동 수가 짝수라면, 무조건 두 수의 합이 최소가 되는 값을 찾아야 한다. 하지만 홀수라면 무조건 하나가 남게 되기 때문에, 최솟값을 산출하기 위해 남을 1개의 수를 찾아야 한다. 일단 최솟값이 되기 위한 방법을 생각해 보자. 당연히 (높은 수) + (낮은 수)를 하는 것이 값을 최소화하는 방법이다. (가장 높은 수 + 가장 낮은 수), (그다음 높은 수 + 그다음 낮은 수)... 이런 식으로 모두 계산했을 ..
문제 이해 단계 문제는 아주 단순하다. AAAA와 BB 두 개의 타일을 가지고 있는데, 주어진 X를 타일로 대체하는 것이다. 같은 경우는 구분하지 않고 그대로 출력하는 것인데, 이건 입력 예제를 보다 보면 바로 이해가 되는 것이기 때문에 자세히 다루지는 않겠다. 문제 접근 단계 이 알고리즘을 푸는 데에는 3가지 포인트가 있다. 1. "."을 기준으로 문자열 X를 나누는 구현 2. AAAA와 BB 타일을 배치하는 방법 구현 3. "-1"을 도출하는 방법 구현 Point 1 . 을 기준으로 문자열을 구분해야 하므로 문자열을 모두 받아 글자 하나하나씩 읽어가는 방식을 선택했다. "X" 일 때와 "." 일 때를 구분하여 행동을 다르게 하였다. "X"일 때는 문자열을 순차적으로 읽다가 "."을 만나면 그때까지의 ..
문제 이해 단계 https://www.acmicpc.net/problem/5639 문제 자체는 자료구조 트리의 정석적인 문제이다. 전위 순회, 중위 순회, 후위 순회를 잘 알고 있나에 관한 문제이다. 간단히 말해서, 전위 순회로 입력이 들어온 트리 구조를 후위 순회로 출력해라는 뜻이다. 문제 자체는 굉장히 심플하다. 하나, 완전 이진트리는 아니기 때문에 여러 가지 디테일이 필요했다. 문제 접근 단계 위 문제를 풀기 위해서는 여러 가지 전위 순회로 들어오는 입력의 특징을 잘 잡아서 해결해야 한다. 일단 이진트리의 특성상 하나의 자식 노드는 다른 서브 트리의 부모 노드가 될 수 있다. 그렇기 때문에 이를 재귀함수로 서브 트리를 호출해 주면서 풀어줘야 한다는 생각을 했다. 일단 전위 순회에서 한 트리를 구성할..
문제 이해 단계 문제 자체는 굉장히 심플한 편이었다. 총 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가 원소이다. 이를 통해서 해당 원소가 포함되는 경우와 안 되는 경우를 전부 나눠서 생각해 보면 이런 식의 그림이 나오게 된다. 예를 들어 가장 위쪽의 화살표만..