코테준비 (2) / 2024.08.11

 

이번주 문제는 재귀함수였다. 재귀는 예전에 아이들을 가르쳤을 때 미리 공부해둔 게 있어서 그때의 지식을 조금 참고해보면서 코드를 작성했다.

 

# 재귀함수 : 함수가 자기 자신을 호출하는 프로그래밍 기법

# 장점 : 문제를 작은 부분 문제로 나누어 해결하는 데 유용

 

# 재귀함수 적용하기 포인트 3가지

# 1. 함수가 끝나는 지점에서 어떤 작업이 이루어지는가

# 2. 함수가 끝나게 되는 조건이 무엇인가

# 3. 반복적으로 하고 있는 작업이 무엇인가

 

추가로 이 문제를 풀이하면서 주로 어떤 문제가 재귀함수로 풀 수 있는 지를 조금? 알게 되었다.

그것은 동일 동작을 무수히 반복하지만 작업을 하는 대상이 그때그때 달라질 때 & "조합"문제 (중복은 없이, 여러가지 경우의 수를 고려해 봐야할 때) 에서 많이 사용한다는 것이다. dfs와 다른 점이라면 재귀는 깊이까지 들어가 결국 중간에 끝내지 않고 다 훑어본다는 거고. 아마 dfs는 중간에 최적의 값을 찾으면 끝낸다는 거 아닐까 싶다...? dfs는 이번주에 하기 때문에 좀 더 집중해서 보겠다

---

1번. 백준 4779번 칸토어 집합

 

https://www.acmicpc.net/problem/4779

 

- 문제 이해 및 풀이 과정 가이드라인

1. 전체 길이만큼 빈 문자열 만들기 -> 가운데에 해당 안 되는 곳은 '-'로 채우기

2. 재귀함수 종료 조건 = 길이가 1인 경우 (재귀함수 인수로 start&end 넣기)

 

 

- 문제 풀이과정

 

특별히 어렵지 않아서 무난하게 문제를 풀었다

 

 

# 재귀 사용
# 전체 길이만큼 빈 문자열 만들기
# 가운데에 해당하는 부분이 아닌 곳에는 '-'로 채우기
# 재귀함수의 종료 조건은 길이가 1인 경우 (재귀함수 인수로 star와 end 넣기)

import sys
sys.setrecursionlimit(10**7)

sentence = []


def cantor(start, end):
    global sentence

    length = end - start + 1 #이건 그때그때의 길이

    if length == 1 :
        sentence[start] = "-"
        return
    
    else:
        head = [start,start + length//3 - 1] # 앞부분에 대한 start와 end 설정
        tail = [end - length//3 + 1, end] # 뒷부분에 대한 start와 end 설정
        
        cantor(head[0], head[1]) #앞부분에 대한 함수
        cantor(tail[0], tail[1]) #뒷부분에 대한 함수


def main():
    global sentence

    input_data = sys.stdin.read().strip().split()
    numbers = [int(num) for num in input_data if 0 <= int(num) <= 12]

    for n in numbers:
        lens = 3 ** n #이건 전체 길이

        sentence = [" "] * lens

        start = 0
        end = lens - 1

        cantor(start, end)
        result = ''.join(sentence)
        print(result)
        

if __name__ == "__main__":
    main()

 

 

---

 

2번. 백준 1182번 부분 수열의 합

https://www.acmicpc.net/problem/1182

 

 

- 문제 이해 및 풀이 과정 가이드라인

1. 길이는 고려하지 않아도 되고, 꼭 연속일 필요 없음 (start&end 넣는 것은 무의미)

2. 모든 조합된 경우의 수를 다 고려해야 함.... (dfs로 가야할 거 같은데 재귀로 어떻게 풀지가 핵심)

 

 

 

- 문제 풀이과정

 

Q1) 조합 문제를 재귀함수로 어떻게 해결할 것인가?

A1) 재귀함수로 풀기 위해서는 해당 원소가 포함되는 경우, 포함되지 않는 경우를 나누어서 재귀함수를 2번 사용해주어야 한다.

 

 

코드

n, s = map(int,input().split(" "))
num_list = list(map(int,input().split(" ")))

count = 0


def plus(num, case, sum, total_num):
    global num_list
    global count
    global s
    global n

    if case == 1 : #포함의 경우
        sum += num_list[num]
        total_num += 1

    if num != (n-1) :
        plus(num+1, 1, sum, total_num)
        plus(num+1, 2, sum, total_num)

    if num == (n-1) :
        if sum == s and total_num != 0 : #끝까지 다 봤고 그때의 합이 일치하는 경우, count에 추가
            count += 1
        return


plus(0,1,0, 0)
plus(0,2,0, 0)

print(count)

 

 

---

3번. 백준 1759번 암호 만들기

https://www.acmicpc.net/problem/1759

 

 

 

- 문제 이해 및 풀이 과정 가이드라인

1. 문자들을 받을 때부터 모음과 자음을 구분한다. -> 알파벳 순으로 sort
2. 빈 문자열을 만들어서 사전처럼 사용 (이중 문자열) -> 최종 출력할 때 sort 하고 내보내기
3. 빈 문자열 만들어서 사전에 넣을 단어 조합에 사용 -> 만들어진 거 sort 하고 사전에 넣기
4. 제시된 알파벳에서의 모음 개수 = len(mo) 거기서 뽑을 수 있는 모음의 개수 : (만들어야 하는 암호의 길이가 모음 개수보다 짧은 경우 : l까지만 진행 / 만들어야 하는 암호의 길이가 모음의 개수보다 긴 경우 : len(mo)까지만 진행

5. 이 문제도 결국 조합 문제이기 때문에 재귀함수로 해결 가능 : 모음과 자음 모두 같은 재귀함수를 사용하게 된다면 인수로 문장, 위치, 포함인지 미포함인지, 여태까지 포함된 문자 개수(반복문꺼랑 같이 비교해야 함), 반복문에서 길이가 어느정도에 해당하는지 / 길이가 다양한 거는 for문을 이용해서 해야 할 듯

 

 

- 문제 풀이과정

 

Q1) 왜 전역변수가 아닌 지역 변수로 들어갔는데, 변수가 동기화가 되는 것인지....

 

A1)

• 불변 객체 (Immutable Object): 정수(int), 문자열(str), 튜플(tuple) 등은 불변 객체입니다. 이들에 대해 함수에서 값을 변경하려고 하면, 파이썬은 새로운 객체를 생성합니다.
• 가변 객체 (Mutable Object): 리스트(list), 딕셔너리(dict) 등은 가변 객체입니다. 함수에서 이들을 전달할 때, 함수 내에서 객체의 값을 변경하면 원래 객체에 영향을 미칩니다.

리스트는 가변 객체이므로, 재귀 호출에서 리스트를 직접 수정하는 경우, 리스트의 상태가 예상치 못한 방식으로 변경될 수 있음 => 리스트의 복사본을 만들어서 전달