문제

입출력 형식 및 출처

length = int(input())
dp = [0] * 100

dp[0] = 1
dp[1] = 1
dp[2] = 1

for i in range(3, len(dp)):
    dp[i] = dp[i-3] + dp[i-2]

for i in range(length):
    ipt = int(input())
    print(dp[ipt-1])

동적프로그래밍(Dynamic Programming) 문제

• 조건에 맞는 삼각형의 변의 길이의 규칙을 찾아내어 이를 구현하는 문제
• dp에 해당하는 변의 길이를 메모하고, 이 값을 계속적으로 이용하며 변의 길이를 구한다
• 해당 index의 변의 길이를 출력

문제

입출력 형식 및 출처

length = int(input())
score = [0]*300

for i in range(length):
    score[i] = int(input())

dp = [0]*300
dp[0] = score[0]
dp[1] = max(score[0]+score[1], score[1])
dp[2] = max(score[0]+score[2], score[1]+score[2])

for i in range(3, length):
    dp[i] = max(score[i]+dp[i-2], score[i]+score[i-1]+dp[i-3])

print(dp[length-1])

동적프로그래밍(Dynamic Programming) 문제

• 밟는 계단의 점수가 주어질 때 이의 최대값을 구현하는 문제
• 계단을 연달아 3개를 밟을 수 없다는 조건이 주어진다
• 내가 밟은 계단의 위치에서 -1칸과 -2칸의 값을 더한 후 비교하여 최대값을 dp리스트에 저장해준다!
• 최종적으로 구해진 dp리스트의 마지막 값을 출력

집합의 데이터 타입. 이넘은 특정 값들의 집합을 의미하는 자료형이다. enum은 열거형(enumerated type)이라고 부른다. 열거형은 서로 연관된 상수들의 집합이라고 할 수 있다.

• 숫자형 enum

• 문자형 enum

• enum의 활용 사례

• enum의 특징

  열거형(enum)의 특성을 정리해보자. 열거형은 연관된 값들을 저장한다. 또 그 값들이 변경되지 않도록 보장한다.

• 참조: 생활코딩

문제

입출력 형식 및 출처

import math


m,n = map(int, input().split())

max_common = math.gcd(m,n)
min_common = abs(m*n)//max_common

print(max_common)
print(min_common)

수학 구현 문제

• 자연수 두 개가 주어질 때, 두 수의 최대 공약수와 최소 공배수를 구하는 문제
• 입력으로 두 개의 자연수가 주어짐
• 파이썬의 math 라이브러리를 이용하여 구현! => Tip!

  "/"는 연산 결과가 float 형태로 나타 내어 진다 "//"는 연산 결과가 int 형태로 나타 내어 진다

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

• 출처: [컴퓨터인터넷IT용어대사전]

자료 1) 깊이 우선 탐색의 예시 출처: 위키백과

2. 깊이 우선 탐색의 장점과 단점

장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

  단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 즉, 탈출 조건을 정해줘야 한다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

3. DFS의 구현

깊이우선탐색은 재귀함수, 혹은 자료구조의 하나인 스택(stack)으로 구현이 가능하다. 그러나 여기서 탈출 조건 없이 재귀함수를 이용할 때 무한정 깊어지는 노드가 있는 경우 에러가 발생 할 수 있다! 따라서 스택을 이용하여 구현하는 것이 좀 더 안정적이다.

스택을 이용하여 DFS를 구현 할 경우 다음의 과정을 고려한다.

1. 루트 노드를 스택에 넣는다.
2. 현재 스택의 노드를 빼서 방문 확인 리스트에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2번의 과정부터 다시 반복한다.
5. 스택이 비면 탐색을 종료한다.

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited_arr = []
    while stack:
        current_node = stack.pop()
        visited_arr.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited_arr:
                stack.append(adjacent_node)
    return visited_arr

자료 2) DFS의 구현

해당 코드를 실행하면 깊이우선탐색을 통해 모든 노드를 순회함을 알 수 있다!

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조. 출처: [천재학습백과]

2. 자료구조에 따른 용법

비선형 구조 => 표현에 초점 선형구조 => 자료를 저장하고 꺼내는 것에 초점 그래프 => 연결 관계에 초점

3. 그래프의 용어 정리

노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertex)이라고도 한다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

4. 그래프의 종류

유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다.

자료 1) 그래프의 종류

5. 그래프의 표현 방법

: 그래프라는 개념을 코드로 표현하는 방법은 두 가지 방법이 있다

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현 2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

이를 예시를 통해 알아보자

자료 2) 표현 방법의 예시

다음과 같은 그래프가 주어질 때 이를 인접행렬, 인접리스트로 나타내면 다음과 같다

• 1. 인접 행렬(2차원 배열)

   0  1  2  3                                graph = [
  0  x  o  x  x                                   [False, True, False, False],
  1  o  x  o  x             =>                    [True, False, True, False],
  2  x  o  x  o                                   [False, True, False, True],
  3  x  x  o  x                                   [False, False, True, False],
                                              ]

• 2. 인접리스트

  graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2],
  }

• 두방식의 차이

  인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다. 그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.

  반면에 인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다. 따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 한다. 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선)만큼의 공간이 사용된다.

문제

입출력 형식 및 출처

length = int(input())
division_arr = list(map(int, input().split()))

print(min(division_arr)*max(division_arr))

수학 구현 문제

• 약수를 보고 해당 숫자를 약수로 갖는 수를 구하는 문제
• 입력으로 약수를 1과 자기 자신을 제외한 약수를 받는다
• 약수의 정의를 통해 약수 중 최소의 수와 최대의 수를 곱셈해준다 => 오랜만에 수학을 접하는중이다😇

유니온 타입(Union Type)이란?

자바스크립트의 OR 연산자(||)와 같이 A이거나 B이다 라는 의미의 타입

예시를 통해 의미를 파악해보자!

자료 1) > Value의 타입이 string인데 number가 들어가서 오류가 남

자료 2) > 이를 해결하기 위해 any로 지정하면 type을 지정하지 않은 것과 같음

자료 3) > 이때 Union type “|” (or 연산자)를 사용 하여 이를 해결 할 수 있음

2. 유니온 타입의 장점

1) 타입을 지정하여 오류로부터 비교적 자유로워 질 수 있다 2) 타입 추론을 통해 자동완성기능을 제공하며 이로 인한 개발 생산성 향상

자료 4) 자동 완성 실패의 예시 자료 5) 추론을 통한 자동완성의 예시

3. 유니온 타입의 특징

getSomeone() 함수는 developer와 person 타입을 모두 가질 수 있다. 따라서 둘의 공통인 name이라는 속성을 사용 가능하다. 그러나 skill과 age는 인자로 들어올 someone의 타입에 따라 정의 되어 질 수 도 있고 정의가 불가능 할 수도 있다. 이를 typescript에서 추론하여 오류를 나타내고 있음.

4. 인터섹션 타입 소개

인터섹션 타입(Intersection Type)이란?

인터섹션 타입(Intersection Type)은 여러 타입을 모두 만족하는 하나의 타입을 의미

자료 6) > 유니온타입과 다르게 인터셉션 타입에서는 skill과 age가 오류 처리 되어 있지 않음. 그 이유는 getSomeone함수에서 사용될 someone이라는 인자는 developer와 person의 속성을 모두 만족하는 하나의 타입을 의미.

이처럼 & 연산자를 이용해 여러 개의 타입 정의를 하나로 합치는 방식을 인터섹션 타입 정의 방식이라고 한다.

자료 7) 인터섹션 타입

문제

입출력 형식 및 출처

import math


length = int(input())

for i in range(length):
    temp_list = list(map(int, input().split()))
    print(math.comb(temp_list[1], temp_list[0]))

수학 문제..😇

• 다리 짓기 문제
• 강의 서쪽과 동쪽의 다리를 지을 수 있는 '사이트'의 갯수를 확인
• 이때 한 '사이트'에는 최대 한개의 다리만 연결 될 수 있다
• 다리끼리는 서로 겹쳐질 수 없으며 최대한 많은 다리를 지어야 한다 => 수학에서 "조합"의 개념을 알면 쉽게 해결 할 수 있다!

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. – 위키백과

동적 계획법 vs 재귀 알고리즘

문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있다.

그러나

• 동적 계획법은 그 결과를 기록(Memoization)하고 이용한다는 점
• 여러 개의 하위 문제(Overlapping Subproblem)를 기록한 결과를 이용하여 해결한다는 점

이를 통해 동적 계획법은 성능적 향상뿐만 아니라 부분 문제를 해결함으로써 전체 문제를 해결할 수 있게 된다!

자료1) 동적 계획법 예시 (피보나치 수열)

1. 재귀함수

   input = 20
   

def fibo_recursion(n): if n == 1 or n == 2: return 1 return fibo_recursion(n - 1) + fibo_recursion(n - 2)

print(fibo_recursion(input))

2. 동적 계획법

input = 50

memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장한다

memo = { 1: 1, 2: 1 }

def fibo_dynamic_programming(n, fibo_memo): if n in fibo_memo: return fibo_memo[n]

nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
fibo_memo[n] = nth_fibo
return nth_fibo

print(fibo_dynamic_programming(input, memo))

```

이를 비교하여 코드를 실행하면, 동적 계획법을 이용 하였을때 연산이 훨씬 빠름을 확인 할 수 있다.

그 이유는

1. 재귀 알고리즘의 경우 실행했던 작업을 계속 다시 한다. 즉, 이미 시켰던 똑같은 작업을 다른 곳에서 다시 새롭게 하고 있는 것.

2. 동적 계획법의 경우 메모를 통해 만약 메모에 그 값이 있다면 바로 반환하고, 없다면 피보나치 값을 메모에 기록하여 원할때 찾아서 사용하면 되기 때문.

문제

입출력 형식 및 출처

ipt_number = int(input())

for i in range(1, ipt_number+1):
    construct_num = sum((map(int, str(i)))) + i

    if construct_num == ipt_number:
        print(i)
        break
    if i == ipt_number:
        print(0)

브루트포스 알고리즘 문제

• 입력으로 주어진 수를 만족하는 생성자중 최소값을 찾는 문제
• 먼저 입력값을 받는다
• 반복문을 이용하여 생성자의 정의를 통해 생성자를 찾는다
• 조건문을 이용하여 생성자가 존재할 경우, 그 최소값을 반환한다
• 만약 생성자가 없을경우, 0을 출력한다

문제

입출력 형식 및 출처

m,n = map(int, input().split())
number_arr = list(map(int, input().split()))
sum_arr = []
number_arr.sort(reverse=True)

for i in range(len(number_arr)-2):
    for j in range(i+1,len(number_arr)-1):
        if number_arr[i]+number_arr[j] > n:
            continue
        for k in range(j+1, len(number_arr)):
            if number_arr[i]+number_arr[j]+number_arr[k] > n:
                continue
            sum_number = number_arr[i]+number_arr[j]+number_arr[k]
            sum_arr.append(sum_number)

print(max(sum_arr))

브루트포스 알고리즘 문제

• 입력으로 주어진 수를 조건으로 이를 초과하지 않는 최대의 값을 만들어야한다
• 먼저 내림차순으로 리스트를 정리한다
• 조건문을 통해 기준을 초과한다면 다음 배열값으로 이동
• 더한 값을 합의 배열에 담아두고, 마지막에 최대값을 찾아낸다

타입 별칭은 특정 타입이나 인터페이스를 참조할 수 있는 타입 변수를 의미 string, number와 같은 간단한 타입 뿐만 아니라 interface 레벨의 복잡한 타입에도 별칭을 부여할 수 있다

자료 1) 타입 별칭을 사용한 타입 정의

자료 2) interface(인터페이스)에서의 타입 별칭을 사용한 타입 정의

2. 인터페이스와 타입별칭의 비교

자료 3) 인터페이스를 이용한 타입 정의

자료 4) 타입 별칭을 이용한 타입 정의

• 두가지를 비교해보면 타입별칭을 사용할때 좀 더 상세하게 사용 되어야 할 속성들이 주어진다.

• 타입 별칭과 인터페이스의 가장 큰 차이점은 타입의 확장 가능 / 불가능 여부다. 인터페이스는 확장이 가능한데 반해 타입 별칭은 확장이 불가능하다. 따라서, 가능한 type 보다는 interface로 선언해서 사용하는 것을 추천 : 좋은 소프트웨어는 언제나 확장이 용이해야 한다는 원칙에 따라 가급적 확장 가능한 인터페이스로 선언하면 좋다👏

3. 타입 별칭을 사용 할 때의 장점

일일이 지정하면 복잡해 보일 수 있는 부분을 타입 별칭을 사용하여 간단히 작성 가능 이로 인해 코드가 간결해지고 따라서 코드의 가독성이 올라감 또한 타입별칭을 한 파일에 묶어두고, 함수를 import하여 사용하는 것처럼 사용 할 수 도 있다

문제

입출력 형식 및 출처

series_number = int(input())
title_number = 665
count = 0

while count <= series_number:
    if "666" in str(title_number):
        count += 1

    if count == series_number:
        print(title_number)
        break
    title_number += 1

브루트포스 알고리즘 문제

• 영화의 넘버링은 666을 통해서만 한다
• 해당 시리즈가 몇번째인지 입력받은 후 title_number를 지속적으로 1씩 증가시켜준다
• 이때 몇번째롷 나타난 666인지 count를 통해 확인 후, 일치한다면 탈출
• 누락 된 케이스(예외)가 없도록 하는것이 중요

인터페이스는 상호 간에 정의한 약속 혹은 규칙을 의미한다. 타입스크립트에서의 인터페이스는 보통 다음과 같은 범주에 대해 약속을 정의할 수 있다.

• 객체의 스펙(속성과 속성의 타입) • 함수의 파라미터 • 함수의 스펙(파라미터, 반환 타입 등) • 배열과 객체를 접근하는 방식 • 클래스

2. 변수를 정의하는 인터페이스

자료 1) 변수에 활용한 인터페이스 예시

User라는 인터페이스를 정의하고, 그 속성의 타입을 정의함

3. 함수의 인자를 정의하는 인터페이스

자료 2) 함수에 활용한 인터페이스 예시

friend2에 address가 정의 되어 있지 않기때문에 오류가 뜨고있다

4. 함수 구조를 정의하는 인터페이스

자료 3) 함수구조에 활용한 인터페이스 예시

5. 인덱싱 방식을 정의하는 인터페이스

자료 4) 인덱싱 => index의 타입은 number, 배열(array)의 타입은 string으로 지정

배열의 타입은 string으로 정의 되어있는데 숫자 10을 변수에 담으려 했기에 문제가 발생함

6. 인터페이스 딕셔너리 패턴

자료 5) 딕셔너리 패턴 예시

StringRegexDictionary는 key로 'string', 값으로 '정규표현식'이 지정되어있다. 그러나 obj['cssFile']에 string을 담으려 했기에 문제가 발생함

7. 인터페이스 확장(상속)

자료 6) 인터페이스의 상속 예시

Developer는 Person을 상속받았다 => 즉 name과 age도 Developer에 명시 해줘야한다

8. appendix

자료 6) 인터페이스 사용 조건

인터페이스를 인자로 받아 사용할 때 항상 인터페이스의 속성 갯수와 인자로 받는 객체의 속성 갯수를 일치시키지 않아도 된다. 다시 말해, 인터페이스에 정의된 속성, 타입의 조건만 만족한다면 객체의 속성 갯수가 더 많아도 상관 없다는 의미. 또한, 인터페이스에 선언된 속성 순서를 지키지 않아도 된다.

문제

입출력 형식 및 출처

length = int(input())
ipt_data = list(map(int, input().split()))
ipt_data.sort()
total_time = 0
waiting_time = 0

for need_time in ipt_data:
    waiting_time += need_time
    total_time += waiting_time

print(total_time)

그리디 알고리즘 문제

• 최적의 선택이 어떠한것인지 생각해본다 => 인출시간이 짧은 이용자부터 먼저 이용한다
• sort메소드를 이용하여 오름차순으로 정렬 후 인출시간과 대기시간을 얻는다
• 구해진 대기시간을 더해준다
• 개별적 선택이 최적의 선택이 되는지 확인한다

: 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조. [네이버 지식백과] 트리 [tree] (천재학습백과 초등 소프트웨어 용어사전)

앞서 보인 큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

자료 1) 트리의 구조 (출처)

트리 용어 설명

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

트리의 종류

: 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 되게 다양한 종류가 있다.

이진트리(Bionary Tree)

: 각 노드가 최대 두개의 자식을 갖는 것을 특징으로 하는 트리

자료 2) 이진트리 예시

자료에서 위의트리는 level 0의 자식 노드가 3개. 따라서 이진트리가 아니다.

• 완전 이진 트리(Complete Binary Tree) : 노드가 최하단 왼쪽 노드부터 차례대로 삽입된 형태의 트리 자료 3) 완전 이진트리 예시

트리를 배열로 표현하는법

: 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다 => null값을 배열에 넣고 시작

자료 4) 트리의 표현 방법 - 배열을 이용

이때,

1. 현재 인덱스 * 2 => 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 => 오른쪽 자식의 인덱스
3. 현재 인덱스 / 2 => 부모의 인덱스

문제

입출력 형식 및 출처

input_arr = input().split("-")
sum = 0

for i in range(len(input_arr)):
    temp_sum = 0
    temp_arr = input_arr[i].split("+")

    for j in range(len(temp_arr)):
        temp_sum += int(temp_arr[j])

    if i==0:
        sum += temp_sum
    else:
        sum -= temp_sum

print(sum)

그리디 알고리즘 문제

• 최적의 선택이 어떠한것인지 생각해본다 => "-"부호를 고려하여 괄호를 치면 된다
• 조건문을 이용하여 분기를 통해 "+"와 "-"연산을 해준다
• 문제 이해가 중요

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. - 위키피디아

자료 1) 탐욕 알고리즘 예시 (그림자료출처)

• 위의 자료를 보면, 이진트리에서 매 순간 최대값을 구하여 도출 한 최대값 결과는 12지만 실제 최대값은 99임을 알 수 있다.

탐욕 알고리즘의 조건

• 탐욕스런 선택 조건(greedy choice property)

  앞의 선택이 이후의 선택에 영향을 주지 않는다는 것

• 최적 부분 구조 조건(optimal substructure)

  문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것

위의 두가지 조건이 만족되지 않는다면 탐욕 알고리즘은 최적해를 구하지 못한다.

그러나

1. 근사 알고리즘으로 사용이 가능하다 2. 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용 가능하다

문제

입출력 형식 및 출처

m,n = list(map(int, input().split()))
change_arr = []

for i in range(m):
    change = int(input())
    change_arr.append(change)

change_arr.reverse()

change_sum = 0
for change in change_arr:
    if n == 0:
        break
    if change > n:
        continue

    change_sum += n//change
    n %= change

print(change_sum)

그리디 알고리즘 문제

• 가장 큰 숫자의 거스름돈부터 나누어 차례로 몫을 더해준다
• 남은 돈을 좀 더 작은 숫자의 거스름돈으로 나누어 몫을 더해준다
• 2번의 과정을 반복한다