[코드트리 조별과제] 3회차(7/29 ~ 8/04)

3주 차는 Backtracking에 대해 학습했습니다.

 

생각하지도 못했는데 굉장히 취약했던 유형이었습니다.

 

자주 풀었을 땐, 선택하거나 선택하지 않거나의 개념이 그려졌었는데 그래프 유형이나 시뮬레이션, 구현류의 문제들만 풀다 보니 감이 사라져서 대부분의 문제를 정답을 확인했던 주입니다.

 

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

굉장히 기본적인 유형의 문제입니다. 막 알고리즘을 공부할 땐, 직접 구현하며 문제를 풀었는데 단순 숫자 선택의 경우 라이브러리를 사용하면서 감이 떨어졌다고 생각합니다.

k, n = map(int, input().split())
answer = []

def dfs(cnt):
    if cnt == n:
        for num in answer:
            print(num, end=" ")
        print()
        return
    
    for i in range(1, k + 1):
        answer.append(i)
        dfs(cnt + 1)
        answer.pop()

dfs(0)

1. 숫자를 선택하지 않은 상태로 시작
2. 1 ~ k까지 숫자를 하나씩 선택
3. 선택된 숫자 추가 후 다음 숫자를 선택하기 위해 함수 호출
4. n개의 숫자가 선택되면 출력 후, 함수 종료
5. 호출한 함수의 반환이 끝나면 선택된 숫자 제거

https://www.codetree.ai/missions/2/problems/beautiful-number?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

쉬움이었지만 쉽게 풀 수 없었습니다. 이전 문제를 풀었던 터라 재귀 자체가 어렵진 않았고 해당 수가 아름다운 수인지 판별하는 것이 까다로웠던 문제입니다.

n = int(input())
answer = 0

def check(num):
    i = 0
    while i < n:
        cnt = 1
        while i + 1 < n and num[i] == num[i + 1]:
            i += 1
            cnt += 1
        if cnt % int(num[i]) != 0:
            return False
        i += 1
    return True

def dfs(num):
    global answer

    if len(num) == n:
        if check(num):
            answer += 1
        return

    for i in range(1, 5):
        dfs(num + str(i))
    
dfs("")
print(answer)

1. 1 ~ 4까지 숫자를 순차적으로 선택
2. 숫자가 선택되면, 다음 숫자를 선택하기 위해 함수를 호출
3. 함수 호출을 통해 만들어진 숫자가 n개이면 아름다운 수인지 확인
   1. 선택된 숫자에 대해 처음부터 검사
   2. 모든 숫자는 최소 하나의 아름다운 숫자를 가진다고 가정
   3. 이후 숫자를 두개씩 검사하며 연속적인지 확인
      1. i + 1을 검사하므로 i의 다음이 마지막인지 우선 검사를 수행
   4. 숫자를 확인하며 인덱스와 연속된 수의 개수를 늘림
   5. 연속된 수의 개수가 검사하는 숫자의 배수가 아니라면 아름다운 수가 아니므로 False 반환
      1. n = 3이고 222라는 숫자가 만들어졌을 때, cnt = 3(연속된 숫자의 수가 3)이 됩니다.
      2. 하지만 해당 숫자는 2로 시작하므로 22만 가능하므로 해당 수는 아름다운 수가 될 수 없습니다.
   6. 다음 숫자로 갱신
      1. 다음 숫자는 연속된 숫자를 검사하는 과정에서 계속 갱신이 이루어짐
      2. 2222333일 경우 2222에 대한 검사가 끝났으니 새롭게 3을 검사하기 위해 넘어가는 과정