재귀

[프로그래머스 Lv.2] 피보나치 수 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이피보나치 문제는 전형적인 DP(Dynamic Programming) 문제이다. DP의 메모이제이션을 활용하여 재귀함수 속에서 이미 계산된 n에서의 피보나치를 저장해두고, n에서의 피보나치 재귀 함수를 호출하면 재귀함수 없이 즉각적으로 저장이 된 해당 수를 반환하도록 하여 재귀함수의 호출 수를 줄임으로써 시간 초과 없이 문제를 해결할 수 있다. import syssys.setrecursi..

[프로그래머스 Lv.4] 호텔 방 배정 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 4의 난이도를 자랑하는 문제답게 정말 아이디어를 떠올리기가 어려운 문제였다.우선 필자는 처음에 배열에다가 배정 여부를 저장하고 이를 사용하여 문제를 해결하고자 하였다. 하지만 이렇게 하면 k의 크기가 최대 "1조"이기 때문에 시간 초과는 물론이고, 어마무시한 배열의 크기 때문에 메모리 부족으로 인한 런타임 에러가 발생한다. (int를 담는 배열이라고 가정하면 int형이 4바이트이므..

[프로그래머스 Lv.2] 모음사전 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 단순히 수학적으로 개수를 계산해 푸는 방법이나 등비수열의 합을 이용해 해당 자리에 어떤 모음이 위치하는지에 맞춰 풀이할 수도 있으나 쉽게 생각하기 어려운 방법이었다.그래서 재귀를 활용하여 실제로 A, E, I, O, U를 사용한 모음사전을 생성하고 이를 전체적으로 순회하면서 일치하는 단어가 나타나는 그 인덱스 + 1을 반환하는 방식으로 문제를 풀이하였다. 물론 이 방법은 앞서..

[프로그래머스 Lv.2] 하노이의 탑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이그 유명한 하노이의 탑을 풀기 위한 방법을 순서대로 배열에 넣어 출력하면 되는 문제이다.재귀를 활용해 풀이하면 되는 문제인데, 재귀 문제가 모두 그렇듯이 재귀 과정에서 어떤 연산을 거쳐야 하는지 정의해야 하고, 종료 조건도 정의해야 한다.우선 재귀 과정을 거치면서 어떤 연산을 거쳐야 하는지 고민을 해봐야 한다. 연산에서의 규칙을 찾을 수 있게 "/"로 단계를 분리해서 적어보면 아래와 같..

(C++) 백준 1074번 - Z

풀이 재귀를 이용하여 풀이하였다. 2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다. 그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다. #include using namespace std; int calZ(int n, int r, int c){ if(n == 1){ // 2 * 2 일 때 if(r == 0 and c == 0) return 0; else if(r == 0 and c == 1) return 1; else if(r == 1 and c == 0) return 2; else return 3; } int half = (1= half and ..

(C++) 백준 11729번 - 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 재귀 문제의 대명사격인 하노이 탑 문제이다. s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다. 1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다. 2. 제일 큰 판을 s에서 l로 이동시킨다. 3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 이 과정을 재귀로 반복하여 문제를 풀이하였다. #inc..

(C++) 백준 1629번 - 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 재귀를 활용하여 풀이하였다. "n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k = (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다. #include using namespace std; using ll = long long; int power(ll a, ll b, ll c){ if(b == 0) return 1; // 모든 수의 0승은 1 if(b == 1) retur..