컴굥일지

문제 https://www.acmicpc.net/problem/12919 문제 내용 문자열 s와 t를 입력받아 아래의 연산들을 수행했을 때 s가 t가 될 수 있는지를 구하면 된다. - 문자열의 뒤에 A를 추가한다. - 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. 문제 풀이 이 문제를 s에서 t로 변환 가능한지로 풀이하면 안 된다. s에서 위의 2가지 연산을 했을 때 t가 되는지 판단하는 것은, t의 길이가 50까지 가능하기 때문에 약 2^50가지의 경우를 체크해야 하기 때문이다. (실제로 이렇게 풀었더니 시간 초과가 발생함) 이 문제는 t에서 s로 변환 가능한지 체크해야 한다. 마지막 글자가 A인 경우와, 첫 글자가 B인 경우를 보며 되돌아오면 된다. 코드 t -> s 방식 #include #incl..

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121685?language=cpp 문제 내용 완두콩의 세대와, 해당 세대에서 몇 번째 개체인지를 입력받아, 완두콩의 형질을 출력하면 되는 문제이다. 문제 풀이 가계도를 자세히 살펴보면, 재귀적인 부분을 찾을 수 있다. 완두콩이 자신의 형질을 알기 위해서는 부모의 형질을 알아야 하고, 부모의 형질은 그 윗세대의 형질을 알아야 한다. 코드 #include #include #include using namespace std; string calcBean(int level, int num){ // 몇레벨의 몇번째 개체 if(level == 1){ return "Rr"; }else if(level=..

문제 https://www.acmicpc.net/problem/1992 문제 내용 배열을 입력받아 규칙대로 압축을 진행하면 된다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 문제 풀이 재귀를 사용하여 문제를 해결할 수 있다. 먼저 범위에 해당되는 부분이 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 4등분으로 분할하여 각각에 대해 같은 과정을 거친다. 만약 다 같은 수로 채워져 있으면 결과에..

문제 https://www.acmicpc.net/problem/1780 문제 내용 아래 문제와 매우 유사한 문제이다. [BOJ/백준 2630][C++] 색종이 만들기 문제 https://www.acmicpc.net/problem/2630 문제 내용 주어진 입력에서 색종이 개수를 구하는 문제이다. 색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반 gyong0117.tistory.com 1780 종이의 개수 문제 역시 색종이의 개수를 구하는 문제이다. 차이는 2630번은 매번 n/2가 되지만 이 문제는 n/3을 해야 한다는 점, 종이의 종류가 다르다는 점이다. 문제 풀이 역시나 재귀를 통해 문제를 풀면 된다. 먼저 종이가 다 같은 수로 채워져 있는지를 체크하..

문제 https://www.acmicpc.net/problem/1074 문제 내용 사진에 보이는 것처럼 방문을 한다고 할 때, r, c를 방문했을 때의 값을 구하면 된다. 문제 풀이 2^N * 2^N 크기의 2차원 배열을 4등분하여 r, c가 어느 사분면에 속해있는지 체크하고 똑같이 재귀적으로 계산해 나가면 된다. 코드 #include using namespace std; int visit(int N, int r, int c) { if (N == 0) { // N이 0인경우 배열 자체가 없음 return 0; } int length = (1 = length) { // 2사분면 return visit(N - 1, r, c - length) + length * length; } else if (r >= le..