[알고리즘] 재귀 관련 알고리즘 & 문제

치치·2025년 2월 2일

알고리즘

알고리즘C++

목록 보기

22/24

연습문제

https://github.com/desffh/Recursive.git

재귀관련 알고리즘 목록

1. 유니온 파인드
같은 집합인지 판별하는 알고리즘
최상단 root노드를 찾을때 재귀를 사용한다
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Union-FInd

2. 유클리드 호제법
최대공약수를 찾는 알고리즘
GCD(y, x % y) 공식을 따르며, 재귀적으로 진행된다
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

3. 피보나치 수열 (DP)
0 1 1 2 3 5 8 13 ... n = (n - 1) + (n - 2) 공식을 가진 알고리즘
재귀함수 과정을 많이 사용하게 되는데, 메모이제이션을 활용하면 시간 단축 가능
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98-DP

4. 분할 정복
큰 문제를 작게 쪼개서 연산하는 알고리즘
예시로 최대값을 구하는 방법을 재귀를 사용하여 구현했다
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer

5. 순열 구하기 (백트래킹)
{1,2,3}의 모든 수의 순서조합을 출력하는 알고리즘
유망하지 않다면 이전 연산으로 돌아오는 것이 백트래킹이다
깊이를 사용한다 (depth)
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Back-tracking

6. DFS (깊이 우선 탐색)
인접한 노드들을 가장 깊은 쪽으로 먼저 탐색하는 알고리즘
방문되지 않은 노드들이 있다면 방문하여 재귀적으로 탐색한다
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-DFS

7. 이진 탐색
탐색 범위를 반씩 줄여나가면서 원하는 값을 찾는 알고리즘
범위가 갱신되면 그 범위로 다시 재귀함수를 호출한다
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Binary-Search

8. 퀵 정렬
기준값(pivot)을 기준으로 왼쪽은 더 작은값들이, 오른쪽은 더 큰값들로 정렬하는 알고리즘
pivot값의 위치가 변경되면 그 위치를 기점으로 다시 범위를 지정해 재귀함수 호출
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Quick-Sort

9. 병합정렬
분할 + 정복 + 병합
큰 문제를 작게 쪼갠 뒤, 병합하고 임시배열에 저장해두는 과정을 반복하여 정렬하는 알고리즘
분할하는 과정이 재귀적으로 진행된다. 그리고 분할한 뒤 바로 병합함수도 호출
https://velog.io/@yangju058/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Merge-Sort

재귀 문제

재귀함수 특성상, 무조건 함수를 탈출할 수 있는 기저조건이 맨 위에 있어야한다!!

1. 팩토리얼

팩토리얼(Factorial)이란?

자연수의 계승이라는 의미로, 어떤 자연수 이하의 모든 자연수를 차례로 곱한 값
0은 자연수가 아니기 때문에 1까지의 곱임 (다른 관점에서는 자연수로 보기도 함)
-> 0! = 1이다
함수의 형태가 int형이기 때문에 정수값을 반환한다

#include <iostream>
using namespace std;

// 재귀를 사용하여 펙토리얼 구현
// ex) 5! = 5*4*3*2*1 = 120

int Factorial(int n)
{
	if (n <= 1)
	{
		return 1;
	}
	else
	{
		return (n * Factorial(n - 1));
	}
}

int main()
{
	int num;

	cin >> num;

	cout << num << "!의 값은? : " << Factorial(num);
	return 0;
}

출력값 :

2. 10진수 -> 2진수 변환

함수가 반환되면서 재귀가 돌아가는 것이 아니기때문에, 재귀함수가 호출되고 종료되기 전까지 다음 로직을 수행하지 못함
-> n == 0이 될때까지 계속 재귀 실행
-> 맨 마지막에 호출된 재귀함수가 종료되면 이전 재귀함수들의 남은 로직이 출력을 실행한다 (거꾸로 출력되는 거임)

실제 2진수는 0 0 0 0 1 1 0 1 인데, 앞쪽은 어차피 해당하지 않기에 생략하고 출력함

#include <iostream>
using namespace std;

void decimalToBinary(int n) 
{
    if (n == 0)
    {
        return;  // 기저 조건: n이 0이면 종료
    }

    decimalToBinary(n / 2);  // 먼저 n을 2로 나눈 몫을 재귀 호출
    cout << (n % 2);  // 나머지를 출력 (맨 마지막에 출력됨)
}

int main() 
{
    decimalToBinary(13);
 
    cout << endl;
    return 0;
}

출력값 :

3. 하노이의 탑

기둥에 원반을 쌓아두고 한쪽 기둥에서 다른 기둥으로 원판을 옮기는 게임
-> 작은 원반 위에 큰 원반을 놓을 수 없다는 규칙이 있다

하노이의 탑 재귀함수 호출 과정

우리의 목표는 모든 원판을 A -> C로 옮기는 것이다 (start -> end)
-> 하노이의 탑은 작은 원판이 큰 원판 아래에 올 수 없다
HanoiTower(3, 'A', 'B', 'C'); 호출
-> 만약 원판이 하나 뿐이라면 start -> end로 바로 이동이 가능하다
-> 하지만 지금 원판은 3개 -> 위의 2개 원판을 다른 곳으로 이동해야만 가장 아래 원판을 end로 옮길 수 있다
원판3을 C로 옮기기 위해서는 위의 원판1,2를 B로 옮겨야한다
-> 하지만, 원판 2를 B로 옮기기 위해선 C부터 이동시켜야만 이동이 가능하다
-> 재귀적으로 hanoi(1,A, B, C) 호출
-> hanoi(2, A, C, B)가 모두 종료되면, 이전에 호출했던 hanoi(3, A, B, C)로직을 마저 수행해야함
위의 원판 1, 2가 B로 이동되었기 때문에 가장 아래의 원판3이 start -> end (A -> C)로 이동할 수 있다
원판 1, 2를 B -> C로 이동시키기 위해서는 위의 원판 1을 A로 이동시켜야한다
-> 재귀적으로 hanoi(1, B, C, A) 호출
모든 로직이 완료되어 함수를 종료한다

#include <iostream>

using namespace std;

// 하노이의 탑 (A->C 기둥으로 원판 모두 옮기기)

// n :원판의 갯수
// start : 맨 처음 위치의 기둥
// middle : 보조 기둥
// end : 최종 도착 위치의 기둥

void HanoiTower(int n, char start, char middle, char end)
{
	// 원판의 갯수가 1개면 start->end로 이동
	if (n == 1)
	{
		cout << "[" << n << "] " << start << "->" << end << endl;
	}
	else
	{
		// 1. 재귀함수를 돌려서 작은 원판들 start->middle로 옮기기
		HanoiTower(n - 1, start, end, middle);
		// 2. 큰 원판을 start->end로 이동
		cout << "[" << n << "] " << start << "->" << end << endl;
		// 3. 재귀함수를 돌려서 작은 원판들 middle->end로 이동
		HanoiTower(n - 1, middle, start, end);
	}
}	// 원판의 갯수가 n-1 재귀가 되면서 1개씩 이동이 가능함


int main()
{
	HanoiTower(3, 'A', 'B', 'C');

	return 0;
}

출력값 :

4. 지수 계산

n == 0일때 모든 수의 0승은 값이 1이다
재귀함수를 호출할때마다 x 값을 곱하는 데, 이 값이 지수 형식으로 계속 곱해지는 것
-> n == 0 이 되면 함수를 종료하고 1을 반환

#include <iostream>
using namespace std;

int power(int x, int n)
{
    if (n == 0)
        return 1;
    else
        return x * power(x, n-1);
}

int main()
{
    cout << power(2, 3);


	return 0;
}

출력값 : 2³ = 8

5. 문자열 팰린드롬(회문)

앞 뒤가 같은 문자열을 의미한다
ex)

ABBA
ABABA
AA
앞 뒤 각각의 문자열을 비교한 뒤, 같으면 다음 문자열을 비교하고 두 문자열이 다를 시 0을 반환한다
-> 마지막 문자열 까지 다 재귀적으로 확인하여 같다면 1을 반환한다

`recursion(const char * s, int l, int r)`

문자열이 서로 같은지 비교하는 함수

문자열을 const char * 형식으로 받아온다
맨 처음 int l과 int r에 들어올 인자값은 해당 문자열의 가장 앞의 인덱스와 가장 뒤
의 인덱스이다
두 문자열의 값이 다르면 0을 반환
두 문자열이 같다면 다음 인덱스를 확인해야함 ABCDDCBA 에서 AA를 확인했다면 다음은 BB를 확인 할 차례
재귀함수를 종료하기 위한 기저조건을 가장 위에 작성한다
-> 재귀함수를 호출하면 l은 계속 증가하고 r은 계속 감소하기 때문에 서로 같거나 l이 커지면 종료한다 (모든 문자열을 다 확인 한 것)
함수가 호출될때마다 그 갯수를 세기 위한 cnt변수++

`int isPalindrome(const char * s)`

문자열을 매개변수로 받고, 문자열을 비교한 결과값을 반환하는 함수
-> recursion함수에서 문자열이 서로 다르면 0을 반환
-> 같으면 1을 반환
문자열은 const char * 형식으로 받는다

`int main()`

isPalindrome 함수를 호출할때, 매개변수로 해당 문자열S의 c_str()로 넘겨준다

c_str() 함수란?
-> std::string 객체가 저장하고 있는 문자열을 C 스타일 문자열(null로 끝나는 문자 배열)로 변환하여 반환
즉, c_str()을 사용하면 문자열을 const char 으로 가져올 수 있다

여기서 입력받은 문자열을 const char 타입으로 인자값을 넘겨주고 함수 호출

#include <iostream>
#include <cstring>

using namespace std;

int cnt = 0;

int recursion(const char* s, int l, int r)
{
    // 1. 함수가 호출되면 ++
    cnt++;

    // 2. 엇갈리면 1반환 후 종료
    if (l >= r) return 1;

    // 3. 두 문자열이 다르면 0반환
    else if (s[l] != s[r]) return 0;

    // 4. 두 문자열이 같으면, 다음 문자열 확인 (ABBA에서 AA같으면 다음 BB확인)
    else return recursion(s, l + 1, r - 1);
}

int isPalindrome(const char* s)
{
    // 매개변수는 인덱스 값
    return recursion(s, 0, strlen(s) - 1);
}
int main()
{
    string S;
    
    cnt = 0;
    cin >> S;

    // 팰린드롬이 맞다면 1 틀리면 0 / 함수 호출 횟수 출력
    cout << isPalindrome(S.c_str()) << " " << cnt << endl;
    
    return 0;
}

출력값 : 회문 문자열이 맞기 때문에 1 & 문자열 비교 함수 호출횟수 3번
1호출 : AA비교
2호출 : SS비교
3호출 : l >= r 이기 때문에 1반환하고 종료

6. N퀸

다시보면 이해못할 수도 있다 ...
어렵게 이해했으니까 다시 봐도 이해할 수 있도록 꼼꼼히 적었다

체스판에서 N개의 퀸을 서로 공격하지 않는 범위 내에서 모두 배치하는 조합을 구현하는 것

<N-퀸 기본 조건>

체스판에서 퀸은 x축, y축, 대각선 모두 칸 수 상관없이 이동이 가능하다
만약 (0,0)에 퀸이 배치되었을 경우, 퀸이 움직일 수 있는 범위에는 다른 퀸이 배치될 수 없다
한 행에는 한 개의 퀸만 배치 가능하다
-> 한 행에 퀸을 배치하면 다음 행으로 넘어간다

N퀸 문제는 재귀함수를 사용하면서 백트래킹도 활용한다! (재귀적으로 문제를 풀다가 해답이 아니라면 이전으로 돌아가서 수행)

불가능한 경우

가능한 경우

<퀸을 배치할때의 조건 확인>

같은 열에 다른 퀸이 없다
대각선에 다른 퀸이 없다

-> 이 두 조건을 만족해야 퀸을 배치할 수 있다

N-퀸 코드 자세히

변수 생성, 초기화 & 배열 생성

배열의 크기를 최대 15로 잡는다
퀸의 갯수 N은 나중에 입력받을 것이다
전체 경우의 수 초기화

col[MAX] 배열은 퀸이 몇번째 열에 있는지를 저장한 것
각 행에 퀸이 있는 열을 저장

2. 해당 위치가 유효한지 체크하는 bool check(int level)함수

해당 행의 열 위치가 유효한지 확인하기 위해서는 위에서 말한 퀸의 배치 조건을 따라야한다
-> col[i] == col[level] 서로 다른 행의 열의 위치가 같다 -> 같은 열에 있다

-> col[level] - col[i]열의 차 == level - i행의 차의 절대값이 같다 -> 같은 대각선에 위치한다

위의 조건을 만족하면 false -> 유효한 위치가 아니다

행을 입력받고 가능한 열에 배치하는 nqueen(int x)함수

x == N이면 모든 행에 퀸이 배치되었다는 것 (행에 퀸은 1개만 배치 -> 배치되면 다음 행으로 넘어가기 때문)
행을 반복문으로 순회하면서 퀸을 배치한다
-> x행에 i번째 열에 퀸을 배치하고 그 위치가 check함수를 통해 유효하다고 판단되면 배치가 맞다고 판단한 뒤, 다음 행을 재귀호출

int main()함수
퀸의 갯수를 입력받고 nqueen함수로 0번째 행부터 호출
이 부분 조심하자! (열의 차는 절대값이야 코드 제대로 봐)
-> 열의 차, 행의 차 모두 절대값으로 계산해도 둘이 값이 같아

N-퀸이 백트래킹인 이유

퀸을 배치할 수 있을때까지 배치한 뒤, 만약 해당 행에 더이상 배치할 수 있는 상황이 전혀 안나온다면, 현재 함수를 종료하고 이전 재귀함수로 돌아간 뒤, 아직 수행하지 않은 로직을 마저 수행한다 (아직 for문 다 수행하지 않았음)
-> 퀸이 배치되는 즉시, 그 행의 다른 열들은 확인하지 않고 지나왔기 때문에, 다시 함수로 돌아와서 다른 열에 배치할 수 있다!!

N-퀸의 재귀함수 종료 기저조건

N-퀸 함수도 재귀함수를 사용하기 때문에 종료조건이 필요하다고 생각했다. 하지만 따로 return하는 조건문이 없다. 왜일까?

또한, 경우의 수는 여러가지가 나올 수 있는데, x == N이 되면 카운트를 증가시킨다. 경우의 수가 여러개가 어떻게 나오는지 몰랐다. 어떻게 나오는걸까?

N-퀸은 재귀함수를 사용하지만 종료되는 기저조건문이 없다 (return)
-> 모든 경우의 수를 다 탐색하기 때문이다
-> 모든 행, 모든 열을 다 탐색하여 경우의 수를 도출해내기 때문에 다 탐색해야 종료되는 것

2. 경우의 수가 여러개가 나오는 이유가 바로 백트래킹 때문이다!
-> 퀸을 배치하고 난 뒤, 현재 행의 나머지 열을 다 탐색하고 넘어가는 것이 아니기 때문에 나중에 경우의 수를 증가시키고 난 뒤, 이전 재귀함수로 돌아가서 다른 열에 배치하게 되면 또 다른 경우의 수를 도출해낼 수 있다!!

N-퀸 전체코드

#include <iostream>
#define MAX 15
using namespace std;

int col[MAX];

// 퀸 갯수
int N = 0;

// 전체 경우의 수
int total = 0;

// 해당 위치 체크 (level = 행)
bool check(int level)
{
    for (int i = 0; i < level; i++)
    {
        // 서로 다른 행의 열이 같다면 && 열의 차 == 행의 차
        if (col[i] == col[level] || abs(col[level] - col[i]) == level - i)
        {
            return false;
        }
    }
    
    return true;
}

// 행을 입력받고 가능할 열에 배치
void nqueen(int x)
{
    // 모든 행에 퀸이 배치되면 카운트++
    if (x == N)
    {
        total++;
    }
    else
    {
        for (int i = 0; i < N; i++)
        {
            col[x] = i; // 해당 위치에 퀸을 배치
            if (check(x)) // 유효한 위치라면, 다음 행을 판단 (나머지 열은 판단안하고 넘어감)
            {
                nqueen(x + 1);
            }
        }
    }
}
int main()
{
    cout << "배치할 퀸의 갯수 : ";
    cin >> N;
    nqueen(0);
    cout << "경우의 수 : " << total;
}

출력값 :

7. 순차 탐색

배열안의 내가 원하는 값이 들어있는 인덱스를 찾는 탐색과정
재귀함수를 사용하여 값을 찾지 못했으면 범위를 줄여나가면서 탐색한다 (n - 1씩)

-> 인덱스의 값을 n - 1로 지정한 이유
: 인덱스는 0부터 시작한다. 배열의 원소가 5개 들어있을 경우, 가장 마지막의 인덱스는 5 - 1
-> 값을 반환하는 게 아닌 인덱스를 반환하는 것이기 때문에 마지막 원소까지 확인하려면 n - 1로 지정해야한다

사이즈의 값은 int size = sizeof(list) / sizeof(list[0]); 이렇게도 가능
#define SIZE 5 로도 가능하다

#include <iostream>
using namespace std;

int search(int data[], int n, int target)
{
    if (n <= 0)   // 못찾았다면 
    {
        return -1;
    }
    else if (target == data[n - 1])  // 찾았다면 리턴하고 끝내기
    {
        return n - 1;
    }
    else  // 찾은건 아닌데 아직 끝에 도달한게 아니라면
    {
        return search(data, n - 1, target);
    }
}
int main()
{
    int list[] = { 1,2,3,4,5};
    int size = sizeof(list) / sizeof(list[0]);
    int n;

    cin >> n;

    if (search(list, size, n) != -1)
    {
        cout << "찾은 값이 존재하는 인덱스 : " << search(list, SIZE, n);
    }
    else
    {
        cout << "찾고자 하는 값이 없다" << endl;
    }

    return 0;
}

8. 배열의 합

순차 탐색과 거의 유사하다 (나중에 한번 구현하기만 해도 알정도)

#include <iostream>
using namespace std;

// 배열의 합을 계산하는 재귀 함수
int sumArray(int arr[], int size) {
    // 기저 조건: 배열의 크기가 0이면 합은 0
    if (size == 0) {
        return 0;
    }
    return arr[size - 1] + sumArray(arr, size - 1);  // 마지막 원소 + 나머지 합
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    cout << "배열의 합: " << sumArray(arr, size) << endl;
    
    return 0;
}

9. 삼각수

삼각수란?
-> 정삼각형 모양을 만들기 위해 나타내는 숫자의 수
수학에서 n번째 삼각수는 정수1부터 n까지의 합

#include <iostream>
using namespace std;

int TriAngle(int n)
{
	if(n == 1)
    {
    	return n;
    }
    else
    {
    	return (n + TriAngle(n - 1));
    }
}
int main()
{
	cout << TriAngle(3);
	return 0;
}

치치

뉴비 개발자

이전 포스트

알고리즘 복습

다음 포스트

[알고리즘] 재귀 관련 알고리즘 & 문제

알고리즘C++

연습문제

재귀관련 알고리즘 목록

재귀 문제

재귀함수 특성상, 무조건 함수를 탈출할 수 있는 기저조건이 맨 위에 있어야한다!!

1. 팩토리얼

2. 10진수 -> 2진수 변환

3. 하노이의 탑

하노이의 탑 재귀함수 호출 과정

4. 지수 계산

5. 문자열 팰린드롬(회문)

`recursion(const char * s, int l, int r)`

`int isPalindrome(const char * s)`

`int main()`

6. N퀸

<N-퀸 기본 조건>

불가능한 경우

가능한 경우

<퀸을 배치할때의 조건 확인>

N-퀸 코드 자세히

N-퀸이 백트래킹인 이유

N-퀸의 재귀함수 종료 기저조건

N-퀸 전체코드

7. 순차 탐색

8. 배열의 합

9. 삼각수

알고리즘 복습

[알고리즘] 강한 결합 요소 (SCC)

0개의 댓글