재귀

📖 문제 https://www.acmicpc.net/problem/12919   💡  풀이 방식• 재귀S에서 T를 만드는 재귀를 수행하는 게 아니고,T에서 문자열을 지우면서 S를 만드는 재귀를 수행하는 것이다.[재귀 함수]- (종료 조건) 첫 번째 문자열과 두 번째 문자열의 길이가 같고, 두 문자열이 같다면, 1을 출력한다. (같지 않다면 0을 출력한다.)- 두 번째 문자열의 마지막 글자가 A인 경우> 마지막 글자를 하나 뺀 값을 재귀함수의 인자로 갖고 가 재귀를 수행한다.- 두 번째 문자열의 맨 앞 글자가 B인 경우 > 맨 앞 글자를 하나 빼고, 뒤집은 값을 인자로 가져가 재귀를 수행한다.   🔺 코드123456789101112131415161718192021222324252627282930313..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡  풀이 방식• 재귀 (분할정복)1. (0,0) 좌표에서부터 재귀를 시작한다.2. 만약 해당 좌표에서 범위까지 있는 모든 수들이 같다면 압축이 가능하므로 압축하고, 0/1의 갯수에 +1한다. 압축이 불가능하다면, 4분할 재귀를 시작한다.divide(x, y, size/2);divide(x, y + size/2, size/2);divide(x + size/2, y, size/2);divide(x + size/2, y + size/2, ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 구현, 재귀 문제에서 말한 순서대로 구현하면 된다.. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. → int형 변수 open의 값을 통해 분리한다. 여는 괄호를 만나면 갯수+1, 닫는 괄호를 만나면 갯수 -1한다. 이 때 여는 괄호 수 = 닫는 괄호 수인 경우, "균형잡힌 괄호 문자열"이므로 현재..

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    💡  풀이 방식• 재귀필요 자료구조- (시작점, 도착점) 값 저장용 리스트 List ⭐- 정답 출력용 2차원 int형 배열 answer . 재귀 함수를 활용해 하노이의 탑을 구현한다.Hanoi(이동할 원판 갯수, 시작점, 경유지, 도착지)  1) (n - 1)개의 원판을 1번째 > 2번째 기둥으로 옮긴다. ▷ Hanoi(n - 1, 1, 3, 2) 2) 남은 1개 원판을     1번째 > 3번째 기둥으로 옮긴다.  3) (n - 1)개의 원판을 2번째 > 3번째 기둥으로 옮긴다. ▷ Hanoi..

📖 문제  20164번: 홀수 홀릭 호석호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게www.acmicpc.net  💡  풀이 방식• 재귀, 브루트포스재귀 함수의 인자로 (현재 숫자, 여태껏 나온 홀수의 갯수)를 갖는다. [1] 재귀 함수 cut(int num, int total)1. 한 자리 숫자인 경우, 여지껏 나온 홀수의 갯수와 최솟값 최댓값을 비교해 갱신한다.2. 두 자리 숫자인 경우, 두 숫자를 분해한다. (재귀 함수 사용)3. 세 자리 이상의 숫자인 경우, 완전탐색을 통해 해당 숫자를 3등분할 인덱스 2개를 구한다.그리고 나서 해당 인덱스들에서 잘랐을 때..

📖 문제  10994번: 별 찍기 - 19예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.www.acmicpc.net  💡  풀이 방식• 재귀. 재귀함수의 인자로는 (시작 행 위치, 가로줄 길이)를 가져간다. . 반복문을 통해 시작 위치부터 가로줄 길이까지 사각형 위치에 있는 칸을 별로 채운다.  (맨 위 가로줄, 맨 아래 가로줄, 왼쪽 세로줄, 오른쪽 세로줄). 반복문이 끝나면, 시작하는 행의 위치는 2 더하고, 가로줄의 길이는 2씩 줄여 재귀함수를 돌린다. (그래야 안쪽에 줄어든 길이만큼 별을 생성할 수 있다.)   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import ..

📖 문제 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 💡 풀이 방식 • 재귀 재귀 메소드 zoac에서 (처음 시작 부분, 끝나는 부분)을 인자로 받는다. 그리고 시작하는 부분과 끝나는 부분 사이에 있는 글자들 중에서 사전식 정렬했을 때 가장 앞에 오는 글자를 방문처리한다. 그리고 방문한 적 있는 idx들을 출력한다. 아까 발견한 idx에서 +1한 위치와 끝나는 문자열 위치를 넘기며 메소드를 호출한다. (재귀) 이어서 시작하는 문자열 위치와 idx에서 -1한 위치를 넘기며 메소드를 호출한다. 💥 유의..

📖 문제  16637번: 괄호 추가하기첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가www.acmicpc.net 💡  풀이 방식• DFS + 백트래킹1. 이전 연산 결과 순차적으로 계산2. 이전 연산 결과 오른쪽의 2개의 값을 괄호로 처리해 계산하고, 이전 연산 결과와 합침 DFS 통해 맨 뒤에서부터 괄호를 묶을 수 있는 경우 묶으면서 연속적으로 계산연산자 인덱스 기준 접근 - 숫자 리스트와 연산자 리스트를 따로 두어야 한다.  🔺 코드12345678910111213141516171819202122232425262728293031323334353..