스파르타코딩클럽 알고리즘 강의

트리

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형(hierarchical) 비선형(non-linear) 자료구조.

용어

Node: 데이터를 저장하는 기본 요소
Root node: 최상위 노드
Level: 루트의 레벨을 0이라고 할 때 하위 브랜치로 연결된 노드의 깊이를 나타냄
Parent node: 상위 레벨의 노드
Child node: 하위 레벨의 노드
Leaf node: child 노드가 하나도 없는 노드
Sibling node: 같은 parent 노드를 가진 노드
Depth: 노드가 가질 수 있는 최대 레벨

이진 트리의 특징: 각 노드는 최대 두 개의 자식을 가진다.
완전 이진 트리의 특징: 노드 삽입 시 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

완전 이진 트리

높이(중요!)

최대 노드의 개수가 N개일 때 높이는 O(log(N))이다.
WHY?
1. 각 레벨에 노드가 꽉 차 있으면 트리의 노드가 총 몇개일까? -> 2^k
2. 만약 높이가 h일 때 모든 노드가 꽉 차 있는 완전 이진 트리라면 노드가 총 몇개일까? -> 2^(h+1) - 1
3. 최대 노드의 개수가 N이라면 h는 뭘까? -> N = 3^(h+1) - 1 -> h = log2(N+1) - 1
4. 즉 완전 이진 트리 노드의 개수가 N일 때 최대 높이는 log2(N+1) - 1이기 때문에 이진 트리의 높이는 최대 O(log(N))이다.

표현 방법

배열 vs. 클래스 구현

배열

BFS처럼 루트부터 한 줄씩 아래로 내려가고 왼쪽에서 오른쪽으로 이동하며 그 값들을 배열에 넣어주면 된다.

이진 탐색 트리

노드의 왼쪽 자식 노드는 노드보다 작고 오른쪽 자식 노드는 노드보다 크다는 조건이 주어진 완전 이진 트리.

이진 탐색

배열이 정렬되어있을 경우 절반씩 줄여나가면서 탐색하는 기법.

효율성:
예) 1억 개 목록을 선형 탐색할 때 1억 번 연산해야 한다. 반면 이진 탐색으로 탐색한다면 27번 안에 찾을 수 있다. (log2(1억) = 26.575)

페어 프로그래밍

문제풀이

1. 블랙잭

처음에 내가 생각했던 방법은 아래와 같다.

1차 시도:
1. 모든 경우(세 숫자의 합)의 수를 전부 리스트에 삽입
2. 리스트를 순회하며 M보다 큰 값이 나오면 그 이전 값 출력

위처럼 구현을 했고 분명 맞았다고 생각했다. 하지만 시간초과도 아니고 그냥 틀렸다고 나와서 페어 분이 설명해주신 방법으로 해보았다.

2차 시도:
1. 모든 경우의 수를 전부 리스트에 삽입하는 대신 각 경우의 수가 max(처음에는 0)보다 크면서 M보다는 작거나 같은 지 확인.
2. 위 두 조건이 만족하면 max에 현재 값(i+j+k) 저장
3. 반복문이 종료됐을 때 max값 출력

이렇게 하니 통과가 되었다.
.
.
.

나중에 백준 질문게시판에서 1차 시도가 틀렸던 이유를 찾았다. 바로 리스트에 M보다 큰 값이 없는 경우였다. 이 부분을 처리해주니 제대로 통과가 되었다.

전체 코드

# 페어 방법
N, M = map(int, input().split())

lst = list(map(int, input().split()))
max = 0

for i in range(0, len(lst)-2):
    for j in range(i + 1, len(lst)-1):
        for k in range(j + 1, len(lst)):
            tmp = lst[i] + lst[j] + lst[k]
            if tmp <= M and tmp > max:
                max = tmp

print(max)

# 내 방법(통과)
N, M = map(int, input().split())

lst = list(map(int, input().split()))
ans = []

for i in range(0, len(lst)-2):
    for j in range(i + 1, len(lst)-1):
        for k in range(j + 1, len(lst)):
            ans.append(lst[i] + lst[j] + lst[k])

max = 0
ans.sort()
for i in range(len(ans)):
    if ans[i] > M:
        max = ans[i-1]
        break
print(max if max != 0 else ans[len(ans) - 1])

2. 분해합

이 문제는 전 문제보다 훨씬 간단했던 것 같다.

풀이:
1. N-1부터 0까지 반복.
2. sum(num을 이루는 각 자리수의 합) 구하기.
3. num + sum이 N과 같다면 ans에 num 저장.
4. 가장 마지막으로(작은) ans 출력.

이 부분에서 우리 조가 틀렸던 부분은 반복문 설정을 10까지 해줬다는 점이다.
10 이하의 숫자는 생성자가 없다고 생각했는데 (N과 N을 이루는 각 자리수의 합)이니까 4의 생성자를 구할 때 N이 2이고 N을 이루는 각 자리수의 합 역시 2니까 4는 생성자가 있다. 따라서 10 이하 짝수들은 생성자가 존재한다.

전체 코드

N = int(input())
ans = 0

for num in range(N-1, 0, -1):
    sum = 0
    tmp = num
    for j in range(len(str(num))):
        sum += tmp % 10
        tmp /= 10
    if num + sum == N:
        ans = num


print(ans)

주간 목표

화: 3주차 강의 마무리, 문제풀이
수: 4주차 강의, 문제풀이
목: 5주차 강의, 문제풀이
금: 1~5주차에서 구현 부분 혼자 해보기, 문제풀이
토: 문제풀이