WEEK01 알고리즘 TIL(3월20일 목요일)

https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.

오늘은 한주의 마지막날이다. 왜냐하면 정글에서 새 주차는 금요일부터 시작이기 때문이다. 사실 일요일 같은 느낌이라서 일찍 갈려했는데, 새벽 1:30에 벨로그를 작성하고 있다.

오늘은 한주를 마무리했기 때문에 코치님들과의 티타임을 가졌는데 거기서 나온 질문이 도움이 될 것 같아 정리했다.

1. 코딩 테스트 시 주의할 점은?
   패키지를 쓰면 나중에 면접 시에 물어볼 수 있다. 예를 들어 콤비네이션을 함수가 아닌 코드로만 구현할 수 있는가? 그러니 패키지 함수도 돌아가는 이론은 알아야한다.
2. 이번주의 백트래킹이나 재귀함수 같은경우 100퍼센트 이해못하고 담주로 넘어갈 수도 있는데, 그럴 경우 오늘같은 날에 최대한 보충을 하는 방법말고는 없는지, 대비할 방법은 없는지 알고 싶습니다.
   그리고 차주에서 재귀를 또 쓸것이다. 그러니 과거에 쓴걸 다시 체크하면서 배운다면 실력이 늘어날 것이다.
   재귀나 백트래킹의 대표문제만 하나만 자력으로 풀어보는 면 개념이 잡힐 것이라고 하셨다.

37번 (1110) 더하기사이클

해당 문제는 직접 수식을 그리면 이해하기 편하다. 전 값과 현재 값의 일부분으로 새로운 수를 만들어낸다. 결국 언젠가 맨처음 숫자로 되돌아오는데, 거기까지의 시도횟수를 출력하는 문제이다.

N = input()  # 각각의 숫자를 분리해서 받기 위해 string 변환

if len(N) == 1:   # 초기에 일의 자리일 경우 대비
    N = "0" + N  # 한 자리 숫자는 앞에 0을 붙여서 두 자리로 맞춤
        
old_N = N   # 과정을 통과한 출력값이 처음 값이랑 같을시
count = 0   # 카운트는 0으로 초기화

while True:
    add = str(int(N[0])+int(N[1]))   # add는 더해진 결과값
    
    if len(add) == 1:   # 만약 주어진 수가 10보다 작다면
        add = "0" + add  # 한 자리 숫자일 경우 앞에 0 추가

    N = N[1] + add[1]  # 새로운 숫자 생성
    count += 1 # 시도할 때마다 카운트하는 함수에 +1을 한다.
    
    if N == old_N:
        break
print(count)

38번 (9095) 1,2,3 더하기

어떤 11보다 작은 정수를 1,2,3의 합으로만 나오는 경우의 수를 구하는 것이다. 이 문제는 점화식을 통해 해결한다. 대략 정수 5까지 적어보면 전에 나온값을 합치면 나온다는 것을 알 수 있다.

T = int(input())

arr = [0]*11        # n은 양수이고 11보다 작으므로 해당부분만 리스트로 만든다.(공간만들기)
arr[1] = 1    # n=1이면 1이다.
arr[2] = 2    # n=2이면 2이다.
arr[3] = 4    # n=3이면 4이다.

# 방법의 수를 구해내는 핵심 코드이다.
for i in range(4,11):    # 4부터 11까지는 해당 과정을 사용한다.
    arr[i] = arr[i-1] + arr[i-2] + arr[i-3]   # n=(n-1)+(n-2)+(n-3)이며 점화식에 해당한다.
    # 예를 들어 5의 경우는 4과 3,2의 결과값의 합과 같다.
    
# T만큼 정수 n을 입력 받는다.
for _ in range(T):
    test_num = int(input())
    print(arr[test_num])    # 입력된 정수 n에 대해 계산한 결과를 출력한다.

39번 (1182) 부분수열의 합

해당 문제는 푸는 방식이 두가지 있습니다. 파이썬 함수의 combination를 사용해서 수열의 모든 경우의 수 조합으로 우리가 원하는 S에 도달할 때의 개수를 출력하는 방법. 또는 재귀함수와 백트레킹을 활용하여 0번째 인덱스부터 시작해 n-1번째 인덱스까지 각 원소의 값들을 넣고 해당 값을 지금까지 구해온 sub_sum에 더하는 경우와 더하지 않는 경우를 각 가지로 나누어 재귀함수를 호출하는 방법.

# combination 방식
import sys
from itertools import combinations  # combination패키지를 불러옵니다

input = sys.stdin.readline    # readline으로 빠르게 입력을 받아옵니다.
n, s = map(int, input().split())    # 입력값을 받습니다.
arr = list(map(int, input().split()))
cnt = 0    # 횟수는 0으로 초기화합니다.

for i in range(1, n+1):  # 첫값부터 N까지 모든 경우의 수를 확인합니다.
    comb = combinations(arr, i)   # combination으로 수열의 모든 조합을 확인합니다. 그러나 순서가 바뀐 것은 같은 취급을 합니다.

    for x in comb:    # 조합이 맞을 시 처리
        if sum(x) == s:   # x즉 수열의 수의 합이 입력된 s와 값이 같다면
            cnt += 1   # 부분수열의 개수를 +1 합니다.

print(cnt)   # 결과를 출력합니다.

# 재귀와 백트래킹 방식
import sys

input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def subset_sum(idx, sub_sum):   # 재귀를 위한 함수입니다.
    global cnt  # 지역변수로 횟수를 불러옵니다.

    if idx >= n:   
        return

    sub_sum += arr[idx]

    if sub_sum == s:   # 요소의 조합이 조건에 맞을시 처리
        cnt += 1    # 부분수열의 개수를 +1 합니다.
    
    # 현재 arr[idx]를 선택한 경우의 가지 수
    subset_sum(idx+1, sub_sum)

    # 현재 arr[idx]를 선택하지 않은 경우의 가지 수
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)
print(cnt)

이 문제는 combination방식으로 풀어서 밑의 재귀와 백트래킹은 참고용으로 알자.