매 순간마다 최선의 경우만 고르는 알고리즘 완전 탐색은 모든 경우를 살펴보지만, 탐욕법은 현재 가장 최선의 경우만 고른다.

모든 경우를 다 살펴보지 않기 때문에 완전탐색보다 빠른 알고리즘이다. 어떤 것이 최선인지 알기 위해서 규칙성을 찾아야 하기도 한다.

그러나 그리디 문제(탐욕법을 그리디라 부르기도 함)는 이 문제가 그리디로 풀 수 있는지 아닌지 판별하는 것 부터가 어렵다. 왜냐 반례가 있을 수 있기 때문이다. 그런데 그 반례를 찾기가 어렵기 때문에 문제를 판별하는데 있어서 생각을 할 수 밖에 없다.

동전 문제일 경우 동전의 가치가 A_i가 A_i-1의 배수일 때 그리디로 문제를 풀 수 있게 된다.

ex) 1 5 10 50 100 ...

이렇게 동전의 가치가 배수가 될 경우 그리디로 문제를 풀 수 있다.

백준 온라인저지 관련 문제

모든 경우의 수를 순서대로 살펴볼 때 사용한다.

Python

from intertools import permutations

v = [1, 2, 3, 4]

for i in permutation(v, 4): # 인자가 2개 들어감. 리스트, 몇 개를 할지 숫자
    print(i)

↓ 출력 값 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 .... 4 3 1 2 4 3 2 1

조합(combination)

파이썬에서 사용할 수 있는 모듈

from itertools import combinations

v = [1, 2, 3, 4]

for i in combinations(v, 2):
    print(i)

↓ 출력값 1 2 1 3 1 4 2 3 2 4 3 4

완전탐색의 장점은 반드시 답을 찾을 수 있다는 것 -> 최소한 1개 이상의 답을 찾아낸다. 전부 살펴보았는데도 없다면 답이 없다는 것을 찾아낸 것! 그러나 단점은 당연히 모든 것을 봐야 하기 때문에 오래 걸린다는 것이 단점. => 리소스를 많이 잡아 먹는 다는 것

브루트 포스(Brute-force)

무차별 대입

다른 사람의 4자리 비밀번호를 해킹하기 위한 경우의 수가 10000가지가 있는데, 이걸 컴퓨터로 계산하여 0~9999까지 넣어보면 그 중 한 가지는 맞을 것이다. 그렇게 모든 경우의 수를 다 넣어 정답을 찾아내는 방법이 무차별 대입이다. 가장 확실한 방법이라 많이 쓰이는 방법이기도 하다.

우리는 문제를 풀 때 종종 어려운 문제를 만나곤 한다. 어려운 문제란 무엇일까? 컴퓨터의 연산으로 생각해보면, 연산이 많아서 사람의 힘으로 풀기 어려운 문제를 컴퓨터는 빠르게 연산하여 답을 찾아낸다. 그러나 그 컴퓨터도 연산하는데 시간이 오래걸린다면,, 그 문제는 '어려운' 문제가 된다.

*1 ~ N 까지의 합을 출력하라는 문제가 주어졌다고 해보자. *

이 문제를 풀기 위해 코딩을 한다면 가장 빠르게 생각해 볼 수 있는 것은 -> 반복문일 것이다. 반복문을 돌려 1~N까지 더해주게 되면 결과를 얻을 수 있다. 그러나 이 코딩은 N 값이 크면 클수록 덧셈의 횟수도 증가하게 된다. 즉, 계산하는 횟수가 많아지면서 그만큼 시간이 오래 걸리게 되는 것이다.

그러나 이 문제를 시간을 단축시키는 방법으로 풀 수 있다. N(N+1)/2 연산으로 풀게 되면 컴퓨터는 한 번의 연산으로 문제의 정답을 낼 수 있게 된다.

즉, 알고리즘에 따라서 답을 구하는 시간이 다르게 되고, 이 시간이 짧을수록 성능 좋은 알고리즘이라 할 수 있게 된다.

시간 복잡도 (Time Complexity)

시간 복잡도란 알고리즘의 최악의 경우의 실행 시간을 말한다.

빅오 표기법 (Big-O notation)

연산에서 가장 크게 증가하는 항을 나타내는 표기법이다.

• $12 + 3N$ 연산의 솔루션은: $O(12 + 3N) = O(N)$
• $2N^2$ + 4N + 8 연산의 솔루션은: $O(2N^2 + 4N + 8) = O(N^2)$
• $k2^N$ 연산의 솔루션은: $O(k2^N) = O(2^N)$

시간 복잡도는

• $O(1)$ 상수 시간
• $O(logN)$ 로그 시간
• $O(N)$ 선형 시간
• $O(NlogN)$ 로그 선형 시간
• $O(N^2)$ 이차 시간
• $O(N^3)$ 삼차 시간
• $O(2^N)$ 지수 시간

순서대로 시간이 더 오래 걸리게 된다.

코딩 테스트 문제를 풀면서 해당 알고리즘의 정확한 시간을 계산할 수는 없을 것이다. 그렇기에 '1초 = 1억'이라는 개념을 가지고 가면 좋을 것이다! 1초에 연산이 1억번이 넘어간다면 알고리즘 문제에서 주어진 시간을 초과할 수도 있다.

공간 복잡도 (Space Complexity)

프로그램은 메모리를 많이 쓸수록 걸리는 시간이 적고, 메모리를 적게 쓸수록 시간이 오래 걸린다. 그래서 메모리를 아낄지, 시간을 줄일지는 선택해야 한다.

시간 제한이 1초가 있고, 메모리 제한이 128MB가 있고, 입력 값이 -1000 ≤ N ≤ 1000 일 때, 가능한 시간 복잡도/공간 복잡도는 어떻게 될까

N의 범위는 2000이다. O(N)은 시간 제한이 1초=1억번 이기 때문에 2000번 연산은 가능할 것이다. O($N^2$)는 $2000^2$ = 4,000,000 (4백만)이기 때문에 1억번 보다 작아 연산이 가능할 것이다. 공간 복잡도를 계산하면, int를 기준(4Bytes)으로 $2000^2$를 계산해 16MB가 나와 충분히 가능하게 된다.

Baekjoon Online Judge --> 알고리즘 문제들이 있는 페이지""

실전 알고리즘 문제는 문제를 어떻게 풀지 알려주지 않는다고 한다. (뭐 당연한 이야기겠지만...ㅠㅠㅠ)

이때까지 배운 것들을 가지고 어떤 알고리즘을 사용하면 좋을지 생각해 보고 문제를 풀어보자!!

실전문제

Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. ⠀ 조건은 다음과 같다. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. ⠀ 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다 ⠀ c = 11 # 코니의 처음 위치 b = 2 # 브라운의 처음 위치

• Queue를 실전에서 사용하려면?

• 코딩테스트에서 큐는 collections.deque를 사용해야 한다. (성능차이 때문에..!!)

>>> from collections import deque
>>> queue = deque()
>>> queue.append(3)
>>> queue.append(4)
>>> print(queue.popleft())
3

코니의 위치 변화 : 1초마다 1씩 증가, 그다음 조건인 '이전 이동 거리 + 1' => 즉, 증가하는 속도가 1초마다 1씩 증가한다는 소리이다. 1, 2, 3, 4, 5, 6, .....

브라운의 위치 변화는 선택할 수 있다. 1-1. 2-1 = 1 1-2. 2+1 = 3 1-3. 2x2 = 4

1-1-1. 1-1 = 0 1-1-2. 1+1 = 2 1-1-3. 1x2 = 2

1-2-1. 3-1 = 2 1-2-2. 3+1 = 4 1-2-3. 3x2 = 6

이런 식으로 무수한 갈래로 계속해서 뻗어 나갈 수 있어서 구하기 어렵다..

규칙성이 없고, 모든 경우의 수를 다 제고해 봐야 한다면, 바로 --> BFS 를 사용해야 한다는 것을 알아채야 한다!

코니가 브라운을 잡는다는 의미는 같은 시간에 같은 위치에 있어야 한다는 것을 의미한다. 그렇기에 규칙적인 '배열' 과 자유자재로 데이터를 넣을 수 있는 '딕셔너리'를 함께 사용한다. [{ }]

from collections import deque

c = 11
b = 2


def catch_me(cony_loc, brown_loc):
    # 구현해보세요!
    time = 0    # 항상 시간을 점검해야 하니 time 변수 필요
    queue = deque()
    queue.append((brown_loc, 0))    # 위치와 시간을 함께 queue 에 포함시켜 준다. [브라운위치][시간]

    # 성공조건을 위한 배열 (코니와 브라운의 위치와 시간이 동일해야 한다.)
    visited = [{} for _ in range(200001)]   # 방문한 시간와 위치를 저장하기 위해 배열을 만든다.
                                            # 위치마다 브라운이 방문한 시간을 적기 위해 배열 안에 딕셔너리를 넣는다.
    # 5 in visited[3] 는 5초에 위치 3을 방문했는지 여부를 저장하고,
    # 9 in visited[3] 는 9초에 위치 3을 방문했는지 여부를 저장한다.
    # visited[위치][시간]
    # visited[cony_loc][time]

    while cony_loc <= 200000:
        cony_loc += time    # +1 +2 +3 +4 +5 .... 시간만큼 가속도가 붙기 때문에
        if time in visited[cony_loc]:
            return time     # 코니와 브라운이 만나는 시점 return

        for i in range(0, len(queue)):
            current_position, current_time = queue.popleft()
            new_time = current_time + 1

            new_position = current_position - 1
            if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position + 1
            if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position * 2
            if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))
        time += 1

    return -1   # 코니 위치가 조건에 부합하지 않는다면 -1을 return 한다.


print(catch_me(c, b))  # 5가 나와야 합니다!

print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))

2번문제

Q. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. ⠀ 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. ⠀ 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다. ⠀ 예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. ⠀ 다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다. ⠀ 압축할 문자열 input이 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 string_compression 함수를 완성해주세요. ⠀

• 문자열의 길이는 1 이상 1,000 이하입니다.
• 문자열은 알파벳 소문자로만 이루어져 있습니다. ⠀ 이 때, 문자열은 항상 제일 앞부터 정해진 길이만큼 잘라야 합니다. 입출력 예 #5 처럼 xababcdcdababcdcd 이 입력되어도, 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다. ⠀ "aabbaccc" # -> 7 "ababcdcdababcdcd" # -> 9 "abcabcdede" # -> 8 "abcabcabcabcdededededede" # -> 14 "xababcdcdababcdcd" # -> 17

['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e']
['ab', 'ca', 'bc', 'ab', 'ca', 'bc', 'de', 'de', 'de', 'de', 'de', 'de']
['abc', 'abc', 'abc', 'abc', 'ded', 'ede', 'ded', 'ede']
['abca', 'bcab', 'cabc', 'dede', 'dede', 'dede']
['abcab', 'cabca', 'bcded', 'edede', 'dede']
['abcabc', 'abcabc', 'dedede', 'dedede']
['abcabca', 'bcabcde', 'dededed', 'ede']
['abcabcab', 'cabcdede', 'dededede']
['abcabcabc', 'abcdedede', 'dedede']
['abcabcabca', 'bcdededede', 'dede']
['abcabcabcab', 'cdedededede', 'de']
None

# 주석으로 설명 작성
input = "abcabcabcabcdededededede"

def string_compression(string):
    n = len(string)
    compression_length_array = []

    for split_size in range(1, n // 2):     # 문자열을 나누는 기준을 구하는 반복문, 1 ~ n // 2(반까지만 구하면 됨)
        splited = [string[i:i+split_size] for i in range(0, n, split_size)]
        # 0부터 n까지 split_size 만큼
        # print(splited)
        compressed = ""     # 압축할 수 있는 문자열인지 비교하기 위해 저장해두는 변수
        count = 1           # splited 에서 자른 문자열을 비교하기 위해 사용
        for j in range(1, len(splited)):
            prev, cur = splited[j-1], splited[j]  # 첫 문자열과 다음 문자열 비교
            if prev == cur:     # 0번째와 1번쨰
                count += 1
            else:       # 이전 문자와 다르다면
                if count > 1:
                    compressed += (str(count) + prev)
                else:       # 문자가 반복되지 않을 때
                    compressed += prev
                count = 1       # 초기화
        if count > 1:       # splited 배열의 마지막 문자까지 앞 문자와 동일하다면
            compressed += (str(count) + splited[-1])
        else:               # 동일하지 않다면 그냥 문자열 추가
            compressed += prev
        compression_length_array.append(len(compressed))
    return min(compression_length_array)


print(string_compression(input))  # 14 가 출력되어야 합니다!

print("정답 = 3 / 현재 풀이 값 = ", string_compression("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression('BBAABAAADABBBD'))

문제 3

문제 설명 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. ⠀ 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다. 반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다. ⠀ '(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다. ⠀

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 4-3. ')'를 다시 붙입니다. 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 4-5. 생성된 문자열을 반환합니다. ⠀ 균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 반환하시오. ⠀ "(()())()" # -> "(()())()" ")(" # -> "()" "()))((()" # -> "()(())()"

from collections import deque

balanced_parentheses_string = "()))((()"


def is_correct_parentheses(string): # 올바른 괄호 문자열인지 확인해 주는 함수
    stack = []
    for s in string:
        if s == '(':
            stack.append(s)
        elif stack:
            stack.pop()
    return len(stack) == 0      # stack에 아무것도 남아있지 않다면 올바른 괄호 문자열임을 알 수 있다.


# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
# 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
def separate_to_u_v(string):
    queue = deque(string)
    left, right = 0, 0
    u, v = "", ""
    while queue:
        char = queue.popleft()
        u += char
        if char == '(':
            left += 1
        else:
            right += 1
        if left == right:
            break
    v = ''.join(list(queue))
    # print(u, v)
    return u, v


# 4번 - else에서 빼온 함수
def revers_parentheses(string):
    reversed_string = ""
    for char in string:
        if char == '(':
            reversed_string += ")"
        else:
            reversed_string += "("
    return reversed_string


def change_to_correct_parentheses(string):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if string == "":
        return ""

    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    u, v = separate_to_u_v(string)

    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    if is_correct_parentheses(u):
        return u + change_to_correct_parentheses(v)    # 재귀함수 사용

    # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
    #  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
    #   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
    #   4-3. ')'를 다시 붙입니다.
    #   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
    #   4-5. 생성된 문자열을 반환합니다.
    else:
        return "(" + change_to_correct_parentheses(v) + ')' + revers_parentheses(u[1:-1])  # 4-1 ~ 4-3


def get_correct_parentheses(balanced_parentheses_string):
    if is_correct_parentheses(balanced_parentheses_string):
        return balanced_parentheses_string
    else:
        return change_to_correct_parentheses(balanced_parentheses_string)

    # ')' 가 나오면 queue 에다가 넣어놨다가, '(' 가 나오는 것을 확인하면, '('의 개수별로
    # queue 에 있던 얘들을 popleft() 시키면 된다.


print(get_correct_parentheses(balanced_parentheses_string))  # "()(())()"가 반환 되어야 합니다!

문제 4

Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. ⠀ 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. ⠀ 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다. ⠀

1. A번 말이 이동하려는 칸이 1) 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.

     - A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
     - 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.

   2) 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.

     - A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
     - A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.

   3) 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. 4) 체스판을 벗어나는 경우에는 파란색과 같은 경우이다. ⠀ 다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다. ⠀ ⠀ 체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 반환하시오. ⠀ 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 반환한다. ⠀

입력 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다. 말의 개수와 체스판의 정보, 현재 말의 위치와 방향을 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 인덱스, 이동 방향이다. 행과 열의 번호는 0부터 시작하고, 이동 방향은 0, 1, 2, 3 이고 0부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다. ⠀

k = 4  # 말의 개수
⠀
chess_map = [
    [0, 0, 2, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 2],
    [0, 2, 0, 0]
]
start_horse_location_and_directions = [
    [1, 0, 0],
    [2, 1, 2],
    [1, 1, 0],
    [3, 0, 1]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!

⠀

K = 4  # 말의 개수
⠀
chess_map = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start_horse_location_and_directions = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
# 이 경우는 2 을 반환해야 합니다!

========

k = 4  # 말의 개수

chess_map = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start_horse_location_and_directions = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]

# 동 → 서 : 0 → 1
# 서 → 동 : 1 → 0
# 북 → 남 : 2 → 3
# 남 → 북 : 3 → 2
# ==> 홀 수 = -1 / 짝수 = + 1


def get_d_index_when_go_back(d):
    if d % 2 == 0:
        return d + 1
    else:
        return d - 1

# 말은 순서대로 이동한다. -> 말의 순서에 따라 반복문
# 말이 쌓일 수 있다. -> 맵에 말이 쌓이는 걸 저장해놔야 한다.
# 쌓인 순서대로 이동한다. -> stack 사용
# 현재 맵에 어떻게 말이 쌓일지 저장하기 위해서 리스트를 만들어 준다.


def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
    n = len(chess_map)
    current_stacked_horse_map = [       # 3차원 배열
        [
            [] for _ in range(n)
        ] for _ in range(n)
    ]
    for i in range(horse_count):
        r, c, d = horse_location_and_directions[i]      # row, column, direction
        current_stacked_horse_map[r][c].append(i)
    turn_count = 1

    while turn_count <= 1000:
        for horse_index in range(horse_count):
            r, c, d = horse_location_and_directions[horse_index]
            new_r = r + dr[d]
            new_c = c + dc[d]

            # 파란색이거나 맵을 나갔을 때
            if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
                new_d = get_d_index_when_go_back(d)
                horse_location_and_directions[horse_index][2] = new_d
                new_r = r + dr[new_d]
                new_c = c + dc[new_d]

                # 가기로 한 곳이 막혀 있으면 안감
                if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
                    continue

            # 2가 이동한다고 하면 2랑 3만 이동한다.
            # 즉, 자기자신의 인덱스보다 큰 애들만 데리고 간다.
            moving_horse_index_array = []   # 이동할 말만 넣어주는 변수
            for i in range(len(current_stacked_horse_map[r][c])):
               current_stacked_horse_index = current_stacked_horse_map[r][c][i]

               if horse_index == current_stacked_horse_index:  # 현재 이동하고 있는 말과 위치에 저장되어 있는 말의 index가 같은지 확인한다.
                    moving_horse_index_array = current_stacked_horse_map[r][c][i:]  # 위로 쌓여 있는 index 애들을 업고 함께 움직이기 때문
                    current_stacked_horse_map[r][c] = current_stacked_horse_map[r][c][:i]   # 현재 위치에는 남은 애들 (첫 인덱스와 i번째 까지의 말)을 다시 저장해준다.
                    break   # 현재 이동하려고 하는 말을 알았으면 반복문을 중단한다.
            if game_map[new_r][new_c] == 1:     # 이동하려는 칸의 위치가 1이면 방향(direction)을 변경해야 한다.
                moving_horse_index_array = reversed(moving_horse_index_array)
            for moving_horse_index in moving_horse_index_array:
                current_stacked_horse_map[new_r][new_c].append(moving_horse_index)
                horse_location_and_directions[moving_horse_index][0], horse_location_and_directions[moving_horse_index][1] = new_r, new_c
            # 턴이 진행되는 중 말이 4개 이상 쌓이는 순간 게임이 종료된다.
            if len(current_stacked_horse_map[new_r][new_c]) >= 4:
                return turn_count
        turn_count += 1

    # print(current_stacked_horse_map)    # 현재 각 체스 말들이 어떻게 쌓여져 있는지 저장해 놓는 공간이 된다.

    return -1


print(get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))  # 2가 반환 되어야합니다

문제 5

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. ⠀ 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. ⠀ 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. ⠀ 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다. ⠀ 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오. 입력 보드를 나타내는 2차원 배열 game_map이 주어진다. 이 때, 보드의 행, 열의 길이는 3이상 10 이하다. ⠀ 보드 내에 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. ⠀ 입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다. ⠀ 출력 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다. ⠀

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]  # -> True를 반환해야 한다.
⠀
game_map = [
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    ["#", "R", "#", ".", ".", ".", "#", "#", "B", "#"],
    ["#", ".", ".", ".", "#", ".", "#", "#", ".", "#"],
    ["#", "#", "#", "#", "#", ".", "#", "#", ".", "#"],
    ["#", ".", ".", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", "#", "#", "#", "#", "#", ".", "#"],
    ["#", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", ".", "#", ".", "#", ".", ".", "#"],
    ["#", ".", ".", ".", "#", ".", "O", "#", ".", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]  # -> False 를 반환해야 한다

============

from collections import deque
# 모든 경우를 탐색해야함으로 BFS 사용

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]
    # 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
# 방문 저장 여부인 visited 배열을 만들어야 하는데,
# red, blue 구슬로 구슬이 2개 이다.
# 이때는 4차원 배열을 사용하면 된다.
# visited[red_marble_row][red_marble_col][blue_marble_row][blue_marble_col]


def move_until_wall_or_hole(r, c, diff_r, diff_c, game_map):
    move_count = 0

    while game_map[r + diff_r][c + diff_c] != '#' and game_map[r][c] != 'O':
        r += diff_r
        c += diff_c
        move_count += 1
    return r, c, move_count


def is_available_to_take_out_only_red_marble(game_map):
    n, m = len(game_map), len(game_map[0])
    visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    red_row, red_col, blue_row, blue_col = -1, -1, -1, -1
    queue = deque()
    for i in range(n):
        for j in range(m):
            if game_map[i][j] == "R":
                red_row, red_col = i, j
            elif game_map[i][j] == "B":
                blue_row, blue_col = i, j
    # 탐색을 10번까지만 할 수 있다.
    queue.append((red_row, red_col, blue_row, blue_col, 1))     # 1 == 탐색 횟수
    visited[red_row][red_col][blue_row][blue_col] = True

    while queue:
        red_row, red_col, blue_row, blue_col, try_count = queue.popleft()
        if try_count > 10:
            break
        for i in range(4):
            next_red_row, next_red_col, r_count = move_until_wall_or_hole(red_row, red_col, dr[i], dc[i], game_map)
            next_blue_row, next_blue_col, b_count = move_until_wall_or_hole(blue_row, blue_col, dr[i], dc[i], game_map)

            if game_map[next_blue_row][next_blue_col] == 'O':
                continue
            if game_map[next_red_row][next_red_col] == 'O':
                return True
            if next_red_row == next_blue_row and next_red_col == next_blue_col:
                if r_count > b_count:
                    next_red_row -= dr[i]
                    next_red_col -= dc[i]
                else:
                    next_blue_row -= dr[i]
                    next_blue_col -= dc[i]
            if not visited[next_red_row][next_red_col][next_blue_row][next_blue_col]:
                visited[next_red_row][next_red_col][next_blue_row][next_blue_col] = True
                queue.append((red_row, red_col, blue_row, blue_col, try_count + 1))
    return False


print(is_available_to_take_out_only_red_marble(game_map))  # True 를 반환해야 합니다

문제 6

Q. 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. ⠀ 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. ⠀ 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. ⠀ 예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자. ⠀

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

⠀ 0은 빈 칸, 1은 집, 2는 치킨집이다. ⠀ (2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다. ⠀ (5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다. ⠀ 이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다. ⠀ 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 반환하시오. ⠀ 입력 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 또한 도시의 정보가 주어진다. ⠀ 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다. ⠀ 출력 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다. ⠀

n = 5
m = 3
⠀
city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]  # 5 가 출력되어야 합니다

==================

import itertools, sys

n = 5
m = 3

city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]
# 여러 개 중에서 M 개를 고른뒤, 모든 치킨거리의 합이 가장 작게 되는 경우 반환
# -> 여러 개 중에서 특정 개수를 뽑는 경우의 수 + 모든 경우의 수를 다 구해야 함
# ==> "조합" 사용


def get_min_city_chicken_distance(n, m, city_map):
    chicken_location_list = []
    home_location_list = []
    for i in range(n):
        for j in range(n):
            if city_map[i][j] == 1:     # 집
                home_location_list.append([i, j])
            elif city_map[i][j] == 2:   # 치킨 집
                chicken_location_list.append([i, j])
    chicken_location_m_combinations = list(itertools.combinations(chicken_location_list, m))
    min_distance_of_m_combinations = sys.maxsize

    for chicken_location_m_combinations in chicken_location_m_combinations:
        city_chicken_distance = 0    # 현재 도시의 치킨 거리
        for home_r, home_c in home_location_list:       # 각 거리의 치킨 거리를 구할 수 있다.
            min_home_chicken_distance = sys.maxsize
            for chicken_location in chicken_location_m_combinations:
                min_home_chicken_distance = min(min_home_chicken_distance,
                                                abs(home_r - chicken_location[0]) + abs(home_c - chicken_location[1]))
            city_chicken_distance += min_home_chicken_distance
        min_distance_of_m_combinations = min(min_distance_of_m_combinations, city_chicken_distance)
    return min_distance_of_m_combinations


# 출력
print(get_min_city_chicken_distance(n, m, city_map))  # 5 가 반환되어야 합니다!
print("hihi")

⠀ github 사용 방법에 대해서도 공부하였다!!

알고리즘 공부 5주차를 마무리 하였는데, 알고리즘이라는 것이 경험해 보지 않았을 때는 엄청 어렵겠구나 했다가 직접 경험해 보니 정말 어려운 것이라는 것을 느끼게 되었다. 그만큼 노력이 필요한 분야고 공부를 많이 해야 겠다는 생각을 하게 되었다. ⠀ ⠀ ⠀

알고리즘 무료 문제 사이트

1. 프로그래머스(https://programmers.co.kr/)

2. 코드시그널(https://app.codesignal.com/interview-practice)

3. 해커랭크(https://www.hackerrank.com/dashboard)

1. 트리, 힙의 개념과 활용법에 대해 배운다.
2. 그래프, BFS, DFS 에 대해 배워보자.
3. Dynamic Programming 의 개념과 그 필요성을 배워보자.

트리

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

지난 주에 작성했던 큐와 스택의 자료구조는 선형 구조라고 하는데, 선형구조는 자료를 구성하고 있는 데이터들이 순차적으로 나열된 형태의 구조를 말하는 것이다.

그러나 트리는 비선형 구조이다. 비선형 구조는 데이터가 계층적 혹은 망으로 구성되어 있는 구조 이다.

선형구조와 비선형 구조의 차이점은 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

트리 구조의 가장 대표적인 구조로는 컴퓨터 폴더 구조가 있다.

트리 용어

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

트리의 종류

• 이진 트리 : (Binary Tree) 각 노드가 최대 두 개의 자식을 가진다. 하위 노드가 무조건 0~2개만 있어야 한다.

• 완전 이진 트리(Complete Binary Tree) : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것이다.

완전 이진트리를 배열로 저장할 수 있다. ⠀⠀⠀ 8 ⠀⠀6⠀⠀ 3 ⠀4⠀⠀2⠀⠀5 [8] Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고, [6] [3]Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고 [4] [2] [5] Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다.

완전 이진 트리의 배열의 첫번째 인덱스에는 데이터를 저장하지 않는다. (헷갈리지 않게 하기 위해서) 그래서 None을 넣는다.

• 현재 인덱스 * 2 = 왼쪽 자식의 인덱스이다.

• 현재 인덱스 * 2 + 1 = 오른쪽 자식의 인덱스이다.

• 현재 인덱스// 2 = 부모의 인덱스이다.

완전 이진 트리의 높이

트리의 높이 : 루트 노드부터 가장 아래 리프(Leaf) 노드까지의 길이를 말한다. ⠀ ⠀ 만약, 각 레벨에 노드가 꽉 차있다면 각 레벨에는 몇개의 노드가 있는 것일까?

완전 이진 트리이기 때문에 각 노드는 2개의 자식 노드만 가질 수 있다.

⠀⠀⠀⠀⠀⠀1⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀level 0 -> 1개 ⠀⠀⠀2⠀⠀⠀⠀3⠀⠀⠀⠀⠀⠀⠀⠀⠀level 1 -> 2개 ⠀⠀4⠀5⠀⠀6⠀7⠀⠀⠀⠀⠀⠀⠀⠀level 2 -> 4개 ⠀8⠀⠀9....14⠀15⠀⠀⠀⠀⠀⠀⠀level 3 -> 8개

레벨을 k라고 하면 각 레벨에는 $$2^k$$개의 노드가 들어가 수 있다.

전체 완전 이진 트리의 노드의 개수는 시그마를 이용해 풀어보면

$$1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h$$ =⠀ $$2^(h+1) -1$$

그러면 최대 노드의 개수가 N이라면, 높이(h)는 어떻게 될까? => $$2^(h+1) -1 = N$$ ⠀⠀⠀ => $$h = log2(N+1) -1$$ 이진 트리의 높이는 최대 $$O(log(N))$$ 이라고 생각하면 된다.

힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전 이진 트리이다.

힙은 항상 큰 값이 위에 있거나 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 그래서 부모 노드의 값이 자식 노드의 값보다 항상 커야 하는 것이다.

⠀⠀⠀⠀8 ⠀⠀⠀⠀⠀Level 0 ⠀⠀6⠀⠀⠀3 ⠀⠀⠀Level 1
⠀4 2 ⠀1 ⠀⠀⠀⠀⠀# 자식 노드보다 부모 노드가 크니까 힙이 맞다

++ 힙은 최대값을 맨 윌 올리 수도 있고, 최솟값을 맨 위에 올릴 수도 있다.

Min Heap <=> Max Heap

맥스 힙에 원소 추가

힙의 규칙 : 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨이 있어야 한다. 이 규칙을 지키면서 원소를 추가하거나 삭제해야 한다

방법

• 원소를 맨 마지막에 넣는다. (맨 왼쪽부터 차례대로)
• 부모 노드와 비교한다. 만약 추가한 노드가 부모 노드보다 크다면 자리를 바꾼다
• 부모 노드보다 크지 않을 때까지 이 과정을 반복한다.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value) # 배열의 마지막에 새 노드를 삽입힌다.
        cur_index = len(self.items) - 1 # 배열의 자리를 변경하기 위해서 각 노드의 index를 알아야 한다.
        while cur_index > 1:     # 현재 index가 1보다 클 동안 반복한다. 즉, 1이면 가장 최상의 부모 노드이면 반복을 멈춘다.
            parent_index = cur_index // 2     # 부모 노드는 현재 노드의 index의 2를 나누면 알 수 있다. 
            if self.items[cur_index] > self.items[parent_index]:    # 현재 노드가 부모 노드보다 크다면, 
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]    # 그 자리를 변경한다.
                cur_index = parent_index    # 변경하고 현재의 index를 부모의 index번호로 변경한다. 
            else:
                break     # 만약 크지 않다면 반복문을 빠져나간다.


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items) 

# 결과 : [None, 9, 4, 2, 3]

맥스 힙의 원소를 추가하는 동작의 시간 복잡도는 가장 큰 값을 넣었을 때 완전 이진 트리의 꼭대기까지 올라간다고 보았을 때 이진 트리의 높이만큼의 시간 복잡도가 걸린다고 생각하면 됨으로 $$O(log(N))$$ 만큼의 시작 복잡도가 걸린다고 생각하면 된다.

맥스 힙의 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것이다. 즉, 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 없다!!

힙이라는 자료 구조가 원래 최댓값, 최솟값만 찾아내는 구조이기 때문에 가장 최상의 노드만 제거할 수 있게 된다.

그래서, 루트 노드를 삭제할 수 있다!

방법

• 루트 노드와 맨 끝에 있는 원소를 교체한다.
• 맨 뒤에 있는 노드를 삭제한다.
• 변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
• 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 과정을 반복한다.
• 원래의 루트 노드를 반환한다.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:  # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
            parent_index = cur_index // 2
            if self.items[parent_index] < self.items[cur_index]:
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
                cur_index = parent_index
            else:
                break

    def delete(self):
        self.items[1], self.items[-1] = self.items[-1], self.items[1] # -1 => 마지막 노드를 의미
        prev_max = self.items.pop()     # 루트 노드를 pop()을 이용해 배열에서 삭제 후 변수에 저장해 둔다.
        cur_index = 1   # 비교해야 할 노드의 index 를 저장해둔다.

        while cur_index <= len(self.items) - 1:     # 비교할 인덱스가 배열의 길이의 끝까지 갈 때까지 반복한다
            left_child_index = cur_index * 2    # 왼쪽 노드의 인덱스 구하기
            right_child_index = cur_index * 2 + 1   # 오른쪽 노드의 인덱스 구하기
            max_index = cur_index       # 현재 인덱스를 맥스 인덱스라 여기고 비교

            # 왼쪽 노드의 인덱스가 배열의 마지막 인덱스보다 작고, 왼쪽 노드의 값이 현재 노드의 값보다 클 때
            if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
                max_index = left_child_index    # 왼쪽 노드의 인덱스를 max 인덱스에 넣는다. 
            # 오른쪽 노드와도 왼쪽 노드의 인덱스와 비교한 것처럼 동일하게 비교한다.
            if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
                max_index = right_child_index
            if max_index == cur_index:  # 왼쪽, 오른쪽 노드와 다 비교했음에도 max 인덱스가 현재 인덱스와 동일하다면
                break                   # 반복문을 빠져나간다
            # 반복문을 빠져나가지 않았다면 현재 인덱스의 위치와 max 인덱스의 위치를 변경한다.
            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index   # 현재 인덱스에 max 인덱스를 넣어 반복한다.
        return prev_max  # 8 을 반환해야 합니다.


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

맥스 힙의 원소 제거의 시간 복잡도는 맨 위에 있던 노드가 맨 아래 레벨 까지 내려온다고 가정해서 분석해보면 이진 트리의 높이 만큼의 시간 복잡도가 걸리는 것으로 이진 트리의 높이의 시간 복잡도와 동일하게 $$O(log(N))$$ 만큼의 시간복잡도가 걸린다는 것을 알 수 있다.

그래프

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조이다. -> 그래프는 노드와 노드 사이의 연결 관계에 초점이 맞춰져 있다.

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

그래프는 유방향 그래프와 무방향 그래프가 있다.

• 유방향 그래프 : 방향이 있어서 방향 쪽으로만 가는 단방향 관계를 나타낸다.
• 무방향 그래프 : 방향이 없어서 쌍방 관계가 가능한 그래프이다.

컴퓨터에서 그래프 표현하기

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

          2 - 3
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 나타내보면
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현하면
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]
2. 이번에는 인접 리스트로 표현해보면
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장한다.

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

1과 2의 차이점은? 시간과 공간의 차이이다.

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

인접 리스트를 사용하면 즉각적으로 연결된 노드들을 확인할 수는 없고, 각 리스트를 다 돌아보아야 한다. 그래서 어떤 노드들이 연결되었는지 파악하기 위해 최대 O(간선)만큼의 시간을 사용해야 한다. 하지만 모든 조합의 여부를 저장할 필요가 없어서 O(노드 + 간선) 만큼의 공간만 사용하면 된다.

DFS & BFS

• DFS : 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]
• BFS : 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. [컴퓨터인터넷IT용어대사전]

모든 데이터를 탐색해야 하는 경우에 사용되는 방법이다.

DFS : 끝까지 파고드는 것 BFS : 갈라진 모든 경우의 수를 탐색해보고 오는 것

DFS는 끝까지 파고드는 것이라 그래프의 최대 갚이 만큼의 공간을 요구한다. 그래서 공간을 적게 쓴다. 그렇지만, 최단 경로를 탐색하는 것은 쉽지 않다. 하지만, BFS는 최단 경로를 쉽게 찾을 수 있다. 모든 분기되는 수를 다 볼 수 있기 때문이다. 하지만, 모든 경우의 수를 저장해야 하다 보니 공간을 많이 써야 하고 시간이 오래 걸릴 수 있다.

DFS(Depth First Search) 구현

갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
• 또 그 노드를 방문해서** 깊이 우선으로 인접한** 노드를 방문한다.
• 만약 끝에 도달했다면 리턴한다.

각 트리의 구조에서 어떤 루트에 방문했었는지 알기 위해서는 표시를 해 놓아야 한다. (visited)

1. 루트 노드부터 시작한다.
2. 현재 방문한 노드를 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 2부터 반복한다.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

[1]-> [2,5,9] visited = [1]⠀ [2] -> [1,3] 1은 방문했으니 [3]으로 이동 [3] -> [2,4]⠀ 2는 방문했으니 [4]로 이동 [4]에는 방문할 곳이 없으니 다시 최상위 루트 노드로 올라옴

[1] -> [2,5,9] [2]는 방문했으니 [5]로 방문 ..... 이렇게 끝까지 내려갔다가 더이상 방문할 곳이 없을 때 최상위 노드로 다시 올라오면서 모든 노드를 탐색하는 방법이다.

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


                                 # 시작하는 노드
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:
        if adjacent_node not in visited_array:    # 탈출조건
            dfs_recursion(adjacent_graph,adjacent_node, visited_array)

    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

무한정으로 깊어지는 노드가 있을 경우 RecursionError 에러가 발생할 수 있다. 그렇기에 재귀함수 말고 다른 방식으로 DFS를 구현해 보자.

DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드들만 꺼내서 탐색하면 된다는 뜻이다. 즉, 스택을 이용하면 된다.

방법

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

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]    # 시작하는 노드를 stack 에 저장해준다.
    visited = []
    while stack:    # stack 이 비지 않을 때까지 반복한다.
        cur_node = stack.pop()
        visited.append(cur_node)
        for adjacent_node in adjacent_graph[cur_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

BFS(Breadth-First)

BFS는 현재 인접한 노드 먼저 방문해야 한다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. => 큐를 이용하면 BFS 를 구현할 수 있다!

방법

1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = [start_node]    # 먼저 들어온 얘가 먼저 나감
    visited = []
    while queue:
        cur_node = queue.pop(0)
        visited.append(cur_node)
        for adj_node in adj_graph[cur_node]:
            if adj_node not in visited:
                queue.append(adj_node)
    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

Dynamic Programming (동적 계획법)

피보나치 수열 - 재귀함수

피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다.

n번째 피보나치 수를 Fibo(n)라고 표현하면,Fibo(1) 은 1이고, Fibo(2) 도 1이다. 즉, Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 = 2이 된다. Fibo(n) = Fibo(n - 1) + Fibo(n-2) 라고 표현할 수 있다.

Q. 피보나치 수열의 20번째 수를 구하시오.

input = 20

# fibo(N) = fibo(n-1) + fibo(n-2)
def fibo_recursion(n):
    # 1 + 1 = 2
    # 1 + 2 = 3
    # 2 + 3 = 5
    # 3 + 5 = 8
    if n == 1 or n == 2:    # 탈출조건
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

이 코드의 단점은 input의 수가 커지면 (ex.100) 연산이 너무 오래 걸리게 된다는 단점이 있다.

했던 작업을 또하고, 또 반복하면서 계속 삽질을 하고 있게 된다. 이미 했던 일을 기록했으면 이런 반복적인 일은 하지 않아도 될 것이다.

동적 계획법이란?

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

여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다. 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다!

• 메모이제이션(Memoization) : 결과를 기록하는 것
• 겹치는 부분 문제(Overlapping Subproblem) : 문제를 쪼갤 수 있는 구조

피보나치 수열을 메모이제이션 방법을 사용해 다시 풀어본다.

방법

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

fibo(5) 을 찾아와라!

1. memo[5]이 있는지 본다.
2. 없으니까 fibo(4) + fibo(3) 을 구해야 한다.
3. 그러면 memo[4] 와 memo[3] 이 있는지 찾아본다. ⠀⠀4. memo[4]가 없으니까 fibo(3) + fibo(2) 을 구해야 한다. ⠀⠀5. 그러면 memo[3] 와 memo[2] 이 있는지 찾아본다. ⠀⠀⠀⠀6. memo[3] 이 없으니까 fibo(2) + fibo(1) 을 구해야 한다. ⠀⠀⠀⠀7. 그러면 memo[2] 와 memo[1] 이 있는지 찾아본다. ⠀⠀⠀⠀8. 있으니까 그 값을 가져온 뒤 더해서 fibo(3) 을 만든다. ⠀⠀⠀⠀9. memo[3] 에 fibo(3) 을 기록한다.⠀⠀ ⠀⠀10. memo[3] memo[2] 를 더해 fibo(4) 를 만들고 memo[4] 에 기록한다.

11. memo[3] 이 있으니까 그 값을 가져온다. (9에서 기록해놨다!!!!) 12. memo[4] 와 memo[3]을 더해 fibo(5) 를 만들고 memo[5] 에 기록한다.

이렇게 기록을 한 부분을 통해 반복되는 작업을 하지 않아도 되어 더 효율적인 코드를 작성할 수 있게 된다.

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))

숙제

Q1.

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. ⠀ 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. ⠀ 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오. ⠀ dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다. ⠀ stock = 4 dates = [4, 10, 15] supplies = [20, 5, 10] k = 30

heapq라는 라이브러리가 이미 존재함으로 import heapq해서 heap 자료 구조를 사용할 수 있다.

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4)     # .heappush로 원소를 넣을 수 있고
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 7)
>>> heapq.heappush(heap, 3)
>>> print(heap)
[1, 3, 7, 4]    # 자동으로 heap 구조로 원소들을 배열해 준다.
>>> print(heapq.heappop(heap))
# 최솟값을 빼는 방법

위 코드는 최솟값으로 구하는 min_heap 방법이었다면, max_heap으로 구하고 싶다면, 음수를 사용한다.

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4 * -1)
>>> heapq.heappush(heap, 1 * -1)
>>> heapq.heappush(heap, 7 * -1)
>>> heapq.heappush(heap, 3 * -1)
>>> print(heap)
[-7, -3, -4, -1] # 힙의 형태를 유지한채로 원소가 넣어지기 때문에 heap[0]이 최솟값입니다!

>>> print(heapq.heappop(heap) * - 1) # 최댓값을 빼는 방법입니다.
7
>>> print(heap)
[-4, -3, -1] # 마찬가지로 힙의 형태가 유지됩니다.

데이터를 넣을 때마다 최대값을 동적으로 변경시키며 최솟/최댓값을 바로 꺼낼 수 있는 heap 구조를 사용하면 된다.

코드에 주석으로 설명 달아 놓았음

import heapq

ramen_stock = 4
supply_dates = [4, 10, 15]  # dates
supply_supplies = [20, 5, 10]   # supplies
supply_recover_k = 30       # k


def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
    heap = []
    answer = 0          # 최소한 해외 공장으로부터 몇번 공급 받아야 하는지
    last_added_data_index = 0   # 공장이 멈추지 않는 한 가장 마지막에 넣은 날짜의 인덱스 값
    while stock <= k:       # 남은 물량이 원래 공장에서 공급받을 수 있을 때까지 반복
        # last_added_data_index 가 dates 배열의 길이를 넘어가면서 조회하지 않도록 탈출 조건 작성
        # 날짜 배열의 값이 stock 의 값보다 작거나 같아야 공장을 돌리 수 있기 때문에 조건을 담
        while last_added_data_index < len(dates) and dates[last_added_data_index] <= stock:
            heapq.heappush(heap, -supplies[last_added_data_index])      
            # 현재 stock 보다 적거나 같은 날짜에 공급 받을 수 있는 supplies 의 값을 heap 에 push 한다.
            last_added_data_index += 1  # 최소한으로 공급을 받아야 하니 날짜를 올려 dates 배열에 가능한 날짜가 있는지 확인해본다.

        answer += 1     # 위에 while 문을 돌고 나왔으면 일단 공급을 받았단 이야기이기 때문에 answer에 1을 더해준다. 
        heappop = heapq.heappop(heap)   
        stock += -heappop   # 공급을 받았기 때문에 stock에 heap의 최상위에 있는 supplies의 값을 더해준다. 
    return answer


print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))
print("정답 = 2 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15], [20, 5, 10], 30))
print("정답 = 4 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15, 20], [20, 5, 10, 5], 40))
print("정답 = 1 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(2, [1, 10], [10, 100], 11))

Q2.

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. ⠀ 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. ⠀ 로봇 청소기는 다음과 같이 작동한다. ⠀

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다. ⠀

입력 조건 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. 이 때 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다. ⠀ 또한 청소하고자 하는 방의 지도를 2차원 배열로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다. ⠀ 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이라고 했을 때, 로봇 청소기가 청소하는 칸의 개수를 반환하시오.

r, c, d = 7, 4, 0
room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

⠀

이 문제는 로봇 청소기가 청소하는 칸의 개수를 알고 싶어 한다. 그래서 갈 수 있는 모든 칸을 전부 탐색해야 한다. 즉, BFS를 사용한다.

방법

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. ⠀⠀⠀왼쪽 방향으로 회전한다는 개념 구현 ⠀⠀⠀a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. ⠀⠀⠀b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. ⠀⠀⠀c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. ⠀⠀⠀d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

# 주석으로 설명 작성하였음
current_r, current_c, current_d = 7, 4, 0
current_room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# 0 은 청소하지 않은 장소,
# 1은 청소하지 못하는 장소,
# 2는 청소한 장소


# 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]


# 방향 전환
def get_d_index_when_rotate_to_left(d):
    return (d + 3) % 4
# 북 (왼쪽으로 회전) -> 서 : 0 -> 3    =>  (0 + 3) % 4 = 3
# 동 (왼쪽으로 회전) -> 북 : 1 -> 0    =>  (1 + 3) % 4 = 0
# 남 (왼쪽으로 회전) -> 동 : 2 -> 1    =>  (2 + 3) % 4 = 1
# 서 (왼쪽으로 회전) -> 님 : 3 -> 2    =>  (3 + 3) % 4 = 2
# ==> rotate -> index 가 (+ 3 % 4)


# 후진
def get_d_index_when_go_back(d):
    return (d + 2) % 4
# 북 (후진) -> 남 : 0 -> 2    =>  (0 + 2) % 4 = 2
# 동 (후진) -> 서 : 1 -> 3    =>  (1 + 2) % 4 = 3
# 남 (후진) -> 븍 : 2 -> 0    =>  (2 + 2) % 4 = 0
# 서 (후진) -> 동 : 3 -> 1    =>  (3 + 2) % 4 = 1


def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    count = 1               # 청소하는 칸의 개수
    n = len(room_map)       # row
    m = len(room_map[0])    # column
    room_map[r][c] = 2      # 청소가 된 칸은 2로 업데이트 시킨다
    queue = list([[r, c, d]])   #

    while queue:        # queue 가 끝날 때 까지 반복한다
        r, c, d = queue.pop(0)      # queue에 들어 있는 첫번째 칸을 꺼낸다
        temp_d = d      # 방향이 계속 돌아가기 때문에 임시 방향을 변수로 설정해준다
        for i in range(4):      # 모든 방향에 대해서 갈 수 있는 방향을 구한다
            temp_d = get_d_index_when_rotate_to_left(temp_d)    # 왼쪽으로 회전
            new_r, new_c = r + dr[temp_d], c + dc[temp_d]       # 왼쪽으로 회전시 새로운 row 와 column 의 위치 변동

            # 새로운 row와 새로운 column의 칸이 len() 을 넘어가지 않고, 또 0으로 청소되지 않았다면
            if 0 <= new_r < n and 0 <= new_c < m and room_map[new_r][new_c] == 0:
                count += 1      # 그 칸을 청소를 하는 칸이기 때문에 청소한 칸의 변수에 1을 더하고
                room_map[new_r][new_c] = 2      # 이 칸은 청소 되었다는 의미로 2를 2차원 배열에 작성해 준다.
                # 새로운 칸을 queue 에 추가해 주는데, 이동한 칸에서 다시 한 번 탐색을 해 주어야 하기 때문이다.
                queue.append([new_r, new_c, temp_d])
                break   # 탐색해서 올바른 방향이 나왔다면 break 로 for 문을 빠져나간다.
            elif i == 3:    # 네 방향이 모두 청소가 되어 있거나, 벽일 경우, 후진한다.
                # get_d_index_when_go_back -> 뒤로 가는 함수를 사용해 row 와 column 을 변경한다.
                new_r, new_c = r + dr[get_d_index_when_go_back(temp_d)], c + dc[get_d_index_when_go_back(temp_d)]
                queue.append([new_r, new_c, temp_d])
                # 후진하여 새로운 장소로 옮겼는데 1 = 벽인 경우,
                if room_map[new_r][new_c] == 1:
                    return count    # 다 청소 했다고 생각하고 청소한 칸의 값을 반환해준다.


# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))
current_room_map2 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 29 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(6,3,1,current_room_map2))
current_room_map3 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 33 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(7,4,1,current_room_map3))
current_room_map4 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 25 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(6,2,0,current_room_map4))

Q3.

극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. ⠀ 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. ⠀ 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다. ⠀ 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다. ⠀ 예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다. ⠀ 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. 총 좌석의 개수와 VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 반환하시오.

피보나치 공식을 사용하면 된다.

변경 가능한 좌석들의 규칙 좌석 [1, 2] 를 옮겨본다. 가능한 경우는 [1, 2] [2, 1] 총 2개다.

좌석 [1, 2, 3] 를 옮겨보면 가능한 경우는 [1, 2, 3] [2, 1, 3] [1, 3, 2] 총 3개다.

좌석 [1, 2, 3, 4] 를 옮겨보면 가능한 경우는 [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [2, 1, 3, 4] [2, 1, 4, 3] 총 5개다.

2, 3, 5, 8 ... 피보나치 공식을 사용하면 된다.

원래 피보나치 공식은 F(1) = 1 이었는데, 여기서는 F(1) = 1, F(2) = 2, F(3) = 3(2)개의 좌석을 옮기는 방법) 으로 생각하고 공식을 사용하면 된다.

# 주석으로 설명 작성
seat_count = 9
vip_seat_array = [4, 7]     # 고정되어 있는 좌석
# 최대 한 좌석만 이동할 수 있다

memo = {
    1: 1,
    2: 2
}


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


def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
    all_ways = 1        # 곱의 연산을 사용할 것이기에 1로 두기도 하고, 아무 자리도 옮기지 않았을 경우의 수도 1이기 때문에 1로 시작한다.
    current_index = 0
    for fixed_seat in fixed_seat_array:  # fixed_seat_array = [4, 7] -> index 가 아니라 번호이다.
        fixed_seat_index = fixed_seat - 1   # 그래서 1을 빼줌으로써 배열의 index 값을 구할 수 있다.
        count_of_ways = fibo_dynamic_programming(fixed_seat_index - current_index, memo)
        # fixed_seat_index - current_index = 사이 사이에 있는 변경할 수 있는 좌석들의 개수가 나온다. [(123) 4 (56) 7 (89)
        # count_of_ways = 고정된 좌석 사이 사이마다 있는 좌석들에서 나올 수 있는 경우의 수
        all_ways *= count_of_ways   # 곱 연산
        current_index = fixed_seat_index + 1    # 0 1 2 3 을 해 주었기 때문에 4 부터 진행하라고
    # 위 for 문은 7까지 진행되고 끝난다. 그래서 7 뒤에 있는 좌석들도 경우의 수를 구해야 하기 떄문에
    # total_count 에서 current_index 를 뺀 수를 다시 피보나치 함수에 돌려 경우의 수를 구한다.
    count_of_ways = fibo_dynamic_programming(total_count - current_index, memo)
    all_ways *= count_of_ways
    return all_ways


# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))
print("정답 = 4 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(9,[2,4,7]))
print("정답 = 26 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(11,[2,5]))
print("정답 = 6 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(10,[2,6,9]))

실전 문제에 다가갈 수록 점점 더 어려워지는 것 같다. 하루종일 붙잡고 강의를 보고 문제를 풀어서 그런지 힘이 너무 빠진다.....

내가 복습을 제대로 안해설까 아직도 알고리즘이 너무 어렵다 ㅠㅠㅠ

1. 정렬의 다양한 방법과 구현 방법에 대해 배운다.
2. 스택, 큐의 개념과 활용법에 대해 배운다.
3. 해쉬 개념과 활용법에 대해 배운다.

• 정렬 : 데이터를 순서대로 나열하는 방법
• 스택, 큐 : 들어가고 나오는 곳이 정해져 있는 자료구조
  • 스택 : last in, first out
  • 큐 : first in, first out
• 해쉬 : 해쉬알고리즘을 통해 문자열을 고정된 길이의 데이터로 만들 수 있다. ⠀

버블 정렬

가장 기본 적인 정렬 방법으로 첫 번째 자료와 두 번째 자료를 비교해서 바꾸고, 두 번째, 세 번재 자료를 비교해서 바꾸는 식으로 교환하면서 자료를 정렬하는 방식이다.

버블 정렬 이미지

파이썬에서는 Swap 함수가 잘 구현되어 있다. a,b = b,a라고 작성하면 된다.

>>> a = 3
>>> b = 4
>>> a, b = b, a
>>> print(a)
4
>>> print(b)
3

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오. input = [4, 6, 2, 9, 1]

코드 ↓

input = [4, 6, 2, 9, 1]

def bubble_sort(array):
    n = len(array)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return


bubble_sort(input)
print(input)

버블 정렬의 시간 복잡도는 $$O(N^2)$$이다. ⠀

선택 정렬

선택 해서 정렬하는 방법 선택 정렬도 각 배열을 계속해서 탐색하는 방식이라서 2중 반복문을 사용하게 된다.

버블 정렬과 선택 정렬이 다른 점은 "최솟값"을 찾아 변경하는 것이다. min_index라는 변수를 통해 각각의 인덱스들과 비교하고, 내부의 반복문이 끝나면, 최소 값의 인덱스와 i의 값들을 교체해준다.

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)

    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i+j] < array[min_index]:
                min_index = i + j
        array[i], array[min_index] = array[min_index], array[i]
    return array

selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

손으로 하나씩 단계를 그려보면 이해하기 쉽다! ⠀

삽입 정렬

삽입 정렬은 전체에서 하나씩 올바른 위체에 "삽입"하는 방식이다. 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.

삽입 정렬을 항상 정렬된 상태를 유지하면서 정렬하는 방식이기 때문에 새로운 원소가 들어오면 자기 자리를 찾아서 이동하는 식으로 정렬이 된다.

1번째 : [4, 6, 2, 9, 1] ⠀⠀⠀⠀⠀⠀← 비교! 2번째 : [4, 6, 2, 9, 1] ⠀⠀⠀⠀⠀⠀← ← 비교! 3번째 : [2, 4, 6, 9, 1] ⠀⠀⠀⠀⠀⠀← ← ← 비교! 4번째 : [2, 4, 6, 9, 1] ⠀⠀⠀⠀⠀⠀← ← ← ← 비교! 1만큼 비교했다가, 1개씩 늘어나면서 반복하게 된다.

for i in range(1, 5):
    for j in range(i): 
        print(i - j)

이 for문 구조를 사용하면 된다. 2번째 for문에서 i(=1)을 사용하는 이유는 배열의 첫번째 원소는 정렬되었다고 생각하고 정렬을 시작하기 때문이다. 그래서 두번째 원소를 첫번째 원소와 비교하여 더 큰 수를 뒤로 보내는 작업을 한다.

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):      # print(i-j)
            if array[i-j-1] > array[i-j]:
                array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
            else:
                break   # 비교할 필요가 없을 때 break 를 한다. 즉, 더 효율적임
    return


insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

삽입 정렬의 시간 복잡도는 $$O(N^2)$$ 만큼 걸린다. 하지만, 최선의 경우에는 $$O(N)$$ 만큼의 시간 복잡도가 걸릴 수 있다. 거의 정렬된 배열이 들어온다면 break 문에 의해 2번재 for 문이 반복되지 않을 수 있기 때문이다. ⠀

병합 - merge

병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

A 라고 하는 배열이 1, 2, 3, 5 로 정렬되어 있고, B 라고 하는 배열이 4, 6, 7, 8 로 정렬되어 있다면 이 두 집합을 합쳐가면서 정렬하는 방법이다.

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    array_c = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1
    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1
    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1
    return array_c


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

이 코드는 내 힘으로 직접 풀어보려고 했는데, 풀다보니 각 배열의 인덱스가 필요하다는 것을 끝에가서 알게 되었고, 다시 생각해 보다 강의를 보았는데, for 문이 아닌 while 문을 사용하여 문제를 풀면 더 쉽게 풀 수 있다는 것을 알게 되었다.

그래서 while문을 이용하여 첫번째, 두번째 배열을 컨트롤 할 수 있다는 것을 알게 되었다. 첫번째, 두번째 배열의 인덱스를 각각 정해두고, 각 인덱스 별로 비교하여 더 작은 것을 array_c에 저장하고, index를 한개 올리고 하는 방식으로 배열을 병합시킬 수 있다. ⠀

병합 정렬 - mergeSort

위에 내용들을 단지 병합만 했을 뿐이다. 그럼 병합 정렬을 무엇인가? 분할 정복의 개념을 적용해야 한다.

• 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하느 전략이다.

예를 들어서 [5, 4] 라는 배열이 있다면 이 배열을 [5] 와 [4] 를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것입니다. 그러면 이 둘을 합치면서 정렬한다면? 결국 전체의 정렬된 리스트가 될 수 있습니다. ⠀ 이 개념을 조금 더 확대해서 생각해보겠습니다. ⠀ [5, 3, 2, 1, 6, 8, 7, 4] 이라는 배열이 있다고 하겠습니다. 이 배열을 반으로 쪼개면 [5, 3, 2, 1] [6, 8, 7, 4] 이 됩니다. 또 반으로 쪼개면 [5, 3] [2, 1] [6, 8] [7, 4] 이 됩니다. 또 반으로 쪼개면 [5] [3] [2] [1] [6] [8] [7] [4] 이 됩니다. ⠀ 이 배열들을 두개씩 병합을 하면 어떻게 될까요? [5] [3] 을 병합하면 [3, 5] 로 [2] [1] 을 병합하면 [1, 2] 로 [6] [8] 을 병합하면 [6, 8] 로 [7] [4] 을 병합하면 [4, 7] 로 그러면 다시! [3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로 [6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로 그러면 다시! [1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다. ⠀ 어떤가요? 문제를 쪼개서 일부분들을 해결하다보니, 어느새 전체가 해결되었습니다! 이를 분할 정복, Divide and Conquer 라고 합니다.

==> 재귀 함수 형식!

# [5, 3, 2, 1, 6, 8, 7, 4]     맨 처음 array 이고,
# left_arary [5, 3, 2, 1]      이를 반으로 자른 left_array
# right_arary [6, 8, 7, 4]     반으로 자른 나머지가 right_array 입니다!

# [5, 3, 2, 1]                 그 다음 merge_sort 함수에는 left_array 가 array 가 되었습니다!
# left_arary [5, 3]            그리고 그 array를 반으로 자르고,
# right_arary [2, 1]           나머지를 또 right_array 에 넣은 뒤 반복합니다.

# [5, 3]
# left_arary [5]
# right_arary [3]

# [2, 1]
# left_arary [2]
# right_arary [1]

# [6, 8, 7, 4]
# left_arary [6, 8]
# right_arary [7, 4]

# [6, 8]
# left_arary [6]
# right_arary [8]

# [7, 4]
# left_arary [7]
# right_arary [4]

이렇게 배열을 반으로 쪼개고, 재귀함수를 이용해서 또 쪼개서 배열의 길이가 1이 될때까지 쪼개고, 그 다음 2개씩 쪼개진 배열들끼리 병합 정렬하여 최종적으로 병합하며 정렬하는 방식으로 문제를 풀 수 있다.

array = [5, 3, 2, 1, 6, 8, 7, 4]


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[0:mid])
    right_array = merge_sort(array[mid:])
    return merge(left_array, right_array)


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

⠀

스택

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조이다. Last in, First Out = LIFO 자료구조라 말하기도 한다. 가장 마지막에 넣은 것이 가장 빨리 나온다.

• push(data) : 맨 앞에 데이터 넣기
• pop() : 리스트의 마지막 항목을 삭제하고 돌려줌
• peek() : 맨 앞의 데이터 보기
• isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기

=> 스택은 데이터를 넣고 뽑는 걸 자주하는 자료구조다. 링크드 리스트와 유사하게 구현할 수 있다!

stack = [] ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀# 빈 스택 초기화 stack.append(4)⠀⠀⠀⠀⠀⠀# 스택 push(4) stack.append(3)⠀⠀⠀⠀⠀⠀# 스택 push(3) top = stack.pop()⠀⠀⠀⠀⠀# 스택 pop print(top) ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀# 3!

range() 함수 : range(시작하는 점, 끝나는 점, 증감)

Q. 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. ⠀ 예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고 받습니다. ⠀ 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. ⠀ 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. ⠀ 이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.

레이저를 왼쪽으로 쏘고 있기 때문에, 자신보다 높은 왼쪽 탑들과 위치를 비교하며 레이저를 맞은 탑의 위치를 배열로 설정해주면 된다.

탑의 높이가 담긴 배열들을 stack이라 하면, 맨 마지막의 값부터 하나하나 pop해서 앞의 원소들과 크기를 비교한다.

answer 배열을 0으로 초기화를 미리 해주는 것이 좋다! => answer = [0] * len(heights)

top_heights = [6, 9, 5, 7, 4]
# 총 O(N^2) 의 시간 복잡도

def get_receiver_top_orders(heights):
    answer = [0] * len(heights)
    while heights: # O(N)
        height = heights.pop()
        # [6, 9, 5, 7]
        for idx in range(len(heights)-1, 0, -1):    # O(N)
            if heights[idx] > height:
                answer[len(heights)] = idx + 1
                break
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

⠀

큐

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 First In First Out = FIFO

=> 순서대로 처리해야 하는 일이 있을 때 큐를 사용한다.

• enqueue(data) : 맨 뒤에 데이터 추가하기
• dequeue() : 맨 앞의 데이터 뽑기
• peek() : 맨 앞의 데이터 보기
• isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기

큐는 데이터 넣고 뽑는 걸 자주하는 자료 구조이다. 그래서 링크드 리스트를 사용한다. 그러나 스택과 다르게 큐는 시작과 끝의 노드르 전부 가지고 있어야 한다. self.head와 self.tail의 노드를 전부 가지고 있어야 한다.

enqueue

queue = [4] -> [2] 큐에 [3]을 enqueue 하면 [4] -> [2] -> [3] 이 된다. 여기서 [4] 는 self.head, [3]은 self.tail로 정해주어야 한다. 하지만 현재 queue의 head는 [4], tail은 [2] 이기 때문에 먼저 tail.next = new_node 현재 tail([2])에 새로운 노드를 포인터로 달아주고, tail을 새로운 노드로 저장시켜 주면 된다. -> tail = new_node

*** 그러나 이렇게만 하면 에러가 발생한다. 초기 상태는 head와 tail 모두가 None 이기 때문에 에러가 발생할 수 있다. 그래서 isEmpty() 함수로 큐에 노드가 있는지 미리 점검하는 코드를 작성해 주어야 한다.

dequeue

head ⠀⠀⠀⠀⠀tail [3] -> [4] -> [5] 에서 제일 앞에 있는 [3]을 빼는 함수이다. head ⠀ tail [4] -> [5] 가 되게 하면 되므로 head에 [4]를 저장하면 되고, 미리 저장해둔 self.head(=[3])을 반환해주면 된다. 큐가 없을 때의 상황도 미리 작성해준다.

peek

제일 위에 있는 (head) 노드를 반환해 주면된다. return self.head.data 해주면 된다. 큐가 없을 때의 상황도 미리 작성해준다.

isEmpty

링크드 리스트의 가장 위에 있는 노드를 반환해주면 된다. return self.head is None

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"
        delete_node = self.head
        self.head = self.head.next
        return delete_node.data

    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data

    def is_empty(self):
        return self.head is None


queue = Queue()
queue.enqueue(3)
print(queue.peek())
queue.enqueue(4)
print(queue.peek())
queue.enqueue(5)
print(queue.peek())
print(queue.dequeue())
print(queue.peek())
print(queue.is_empty())

해쉬

⠀ 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.해시 테이블은 해시 함수를 사용하여 인덱스를 버킷이나 슬록의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

파이썬의 딕셔너리를 해쉬 테이블이라 부르기도 한다!

dict = {"fast" : "빠른", "slow": "느린"} 

찾는 데이터가 있는지 배열을 다 둘러보지 않아도 key 값으로 검색하여 조회할 수 있기 때문에 매우 유용한 자료구조이다.

여기, "fast"라는 key 값이 있는데, 이 key 값을 어떤 index에 넣어야 할지, 어디에서 찾아야 할지 어떻게 알 수 있을까? => 바로 해쉬 함수를 사용한다. hash(object) 를 사용하여 배열에 들어갈 위치를 잡아준다. >>> hash("fast") -146084012848775433 이렇게 hash 함수를 사용하면 엄청나게 큰 수가 나오게 되는데, 이를 배열의 길이로 나눈 나머지 값(%) 을 사용하여 index를 사용한다.

만약 배열의 길이가 8이면,

index = hash("fast") % 8 

으로 계산하여 0~7 사이의 index 수로 배열의 index를 정할 수 있다.

⠀ 딕셔너리에는 put과 get 함수가 필요하다 ⠀ put(key, value) : key에 value를 저장하는 함수 ⠀

def put(self, key, value):
    index = hash(key) % len(self.items)
        self.items[index] = value

get(key) : key에 해당하는 value 가져오는 함수

해당 index를 가진 배열의 원소를 반환해주면 된다.

def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]

그런데 만약에 해쉬의 값이 같으면 어떻게 해야 할까?? 해쉬 값을 배열의 길이로 나누었더니 똑같은 나머지 수가 나오면 어떻게 될까? --> 충돌이 생길 것이다.

충돌을 해결하는 첫번째 방법

체이닝(Chaining)

링크드 리스트를 사용하는 방식이다. 같은 index 값이 나온 key 끼리 링크드 리스트 처럼 연결시켜 주는 것이다. [None, None, (fast, "빠른") -> (slow, "느린"), ...]

class LinkedTuple:
    def __init__(self):
        self.items = []

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v

items라는 배열을 생성하고, add() 함수가 호출 될 때, items 배열의 뒤에 (key, value) 구조로 내용을 붙인다. get() 함수가 호출되면, items 배열에 있는 k, v (key, value) 값을 하나씩 꺼내면서, k와 items에 있는 key 값이 같은지 비교하여 같으면 value 값을 꺼내는 방식으로 함수를 구현한다.

체이닝 방식으로 충돌을 막았으면, 이 방식으로 다시 딕셔너리를 구현해보자

class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def put(self, key, value):        
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)

# 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
# 현재 self.items[2] 가 [("slow", "느린")] 이었다!
# 그렇다면 새로 넣는 key, value 값을 뒤에 붙여주자!
# self.items[2] == [("slow", "느린") -> ("fast", "빠른")] 이렇게! 

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

# 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
# 현재 self.items[2] 가 [("slow", "느린") -> ("fast", "빠른")] 이었다!
# 그렇다면 그 리스트를 돌면서 key 가 일치하는 튜플을 찾아준다.
# ("fast", "빠른") 이 일치하므로 "빠른" 이란 값을 돌려주자!

⠀

충돌을 해결하는 두번째 방법

개방 주소법(Open Addressing)

배열의 다음 남는 공간에 충돌된 (key, value)를 넣는 것이다.

fast 의 해쉬 값이 3이 나와서 items[3] 에 들어갔다고 하는데, slow 의 해쉬 값이 동일하게 3이 나왔다. 그러면, items[4] 를 본다. items[4]도 이미 차 있다. 그러면 그 다음 칸인 items[5] 를 봅니다. 비어 있으니까 items[5] 에 slow의 value 값을 넣는다.

정리

해쉬 테이블은 "키"와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조이다. ⠀ 해쉬 함수는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다. ⠀ 해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤, 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장한다. ⠀ 만약, 해쉬 값, 인덱스가 중복되어 충돌이 일어나면 -> 체이닝과 개방 주소법 방법으로 해결할 수 있다. ⠀ 해쉬 테이블은 시간은 빠르되 공간을 대신 사용하는 자료구조라고 생각하시면 됩니다.

문제

Q. 오늘 수업에 많은 학생들이 참여했습니다. 단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다. ⠀ 모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때, 출석하지 않은 학생의 이름을 반환하시오.⠀

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]

student 딕셔너리에 모든 학생의 이름이 되는 key 값을 hash()를 통해 저장하고, present_student를 돌면서 student에 저장되어 있는 출석한 학생의 키 값들을 삭제한다. 그러면 student 딕셔너리에는 결석한 학생의 이름만 남아 있게 된다.

del 예약어 예약어는 뒤에 한 칸을 띄고 사용한다. 파이썬에서 사용하는 예약어로 if, for, or, and 등이 있다고 한다.

del array[index] 형태로 사용한다. 즉, 요소의 위치를 지정해서 삭제할 수 있다. 범위 연산자 (:) 슬라이싱을 이용하면 범위에 한에서도 삭제할 수 있다.

++ remove() 함수로 array의 요소를 삭제한다. -> array.remove() 로 사용된다. 한 번에 하나의 요소만 삭제가 가능하다.

dict.keys() : 딕셔너리의 key만을 모아서 key 값을 돌려준다. 주로 for 문을 이용하여 딕셔너리의 key 값을 확인한다.

for key in dict.keys():
    print(key)

정답

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]


def get_absent_student(all_array, present_array):
    student_dict = {}
    for key in all_array:
        student_dict[key] = True

    for key in present_array:
        del student_dict[key]

    for key in student_dict.keys():
        return key
    return


print(get_absent_student(all_students, present_students))

숙제

Q1.

다음과 같이 숫자로 이루어진 배열이 두 개가 있다. 하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다. 쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다. 이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가? 단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다.

=> 제일 할인을 많이 받으려면 가장 비싼 금액에서 가장 큰 할인율을 받으면 된다. .sort(revers=True) 함수를 사용하여 내림차순(큰 순서)으로 정렬을 한다. 그렇게 되면, 가장 큰 금액의 상품을 가장 큰 할인율로 바로 할인할 수 있게 된다.

각 배열의 index를 정하고, max_price에 가장 많이 할인된 금액들을 차곡차곡 더해 나가면, 가장 할인을 많이 받을 수 있는 금액이 나오게 된다.

⠀

shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]
# 제일 할인을 많이 받으려면 어떻게 해야 하는지


def get_max_discounted_price(prices, coupons):
    prices.sort(reverse=True)   # [1500000, 30000, 2000]
    coupons.sort(reverse=True)  # [40, 20]
    prices_index = 0
    coupons_index = 0
    max_price = 0

    while prices_index < len(prices) and coupons_index < len(coupons):
        max_price += prices[prices_index] * (100 - coupons[coupons_index]) // 100
        prices_index += 1
        coupons_index += 1
    while prices_index < len(prices):
        max_price += prices[prices_index]
        prices_index += 1

    return max_price


print(get_max_discounted_price(shop_prices, user_coupons))

⠀

Q2.

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 예를 들어 ⠀ ()() 또는 (())() 는 올바르다. )()( 또는 (()( 는 올바르지 않다. ⠀ 이 때, '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 True 를 반환하고 아니라면 False 를 반환하시오.⠀

"(())()" # True
"(((("   # False

문제를 분석하던 중 '('와 ')'는 짝이 이루어져야 한다는 것을 알게 되었다. 그래서 그 짝이 맞지 않으면 False를 반환해 주고, 짝이 맞으면 True를 반환해주면 된다고 생각했다.

하.지.만.

이 수업은 알고리즘 수업이기 때문에 알고리즘 적 사고를 해야 한다는 것이었다!!

그래서 알고리즘적으로 사고를 해서 이 문제를 다시 보면, stack 구조를 사용하면 된다! '(' 가 있었다면, stack에 쌓아 놓다가, ')'가 나오면 stack에 가장 마지막에 쌓아 놓은 '('를 pop으로 꺼내서 마지막에 stack이 비어있으면 True, 비어 있지 않으면, False를 반환해 주면 된다.

++ 여기서 주의해야 할 점은, ')'가 '('보다 먼저 더 많이 나올 수 있기 때문에 미리 stack에 들어 있는 '('를 체크해서 '('게 없다면 바로 False를 반환해 줄 수 있어야 한다.

s = "((())))"


def is_correct_parenthesis(string):
    stack = []
    for i in range(len(string)):
        if string[i] == "(":
            stack.append(i)
        elif string[i] == ")":
            if len(stack) == 0:
                return False
            stack.pop()
    if len(stack) != 0:
        return False
    else:
        return True

    # 이건 그냥 짝 맞춰서 푼 방법 (알고리즘xx)
    # first_small_letter_exist = 0
    # last_small_letter_exist = 0
    # for letter in string:
    #     if letter == '(':
    #         first_small_letter_exist += 1
    #     elif letter == ')':
    #         last_small_letter_exist += 1
    # if first_small_letter_exist == last_small_letter_exist:
    #     return True
    # else:
    #     return False


print(is_correct_parenthesis(s))  # True 를 반환해야 합니다!
print("정답 = True / 현재 풀이 값 = ", is_correct_parenthesis("(())"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis(")"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())))"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("())()"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())"))

⠀

Q3.

멜론에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다. ⠀ 노래는 인덱스 구분하며, 노래를 수록하는 기준은 다음과 같다. ⠀

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. (단, 각 장르에 속한 노래의재생 수 총합은 모두 다르다.) ⠀
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다. ⠀
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다. ⠀ 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, ⠀ 베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오.

   # 1
   genres = ["classic", "pop", "classic", "classic", "pop"]
   plays = [500, 600, 150, 800, 2500]
   # 정답 = [4, 1, 3, 0]
   ⠀
   # 2
   genres = ["hiphop", "classic", "pop", "classic", "classic", "pop", "hiphop"]
   plays = [2000, 500, 600, 150, 800, 2500, 2000]
   # 정답 = [0, 6, 5, 2, 4, 1]

{ } : 딕셔너리를 선언, 초기화 할 때 사용하는 기호

먼저, 어느 장르가 가장 많이 재생 되었는지 확이해야 하기 때문에 장르와 play 수를 확인할 수 있는 딕셔너리를 만들어서 확인해야 한다.

genre_play_dict = {} 장르 배열에서 장르를 빼오고, 그 장르에 맞는 play 수를 합산해서 어느 장르가 총 play 수가 더 많은지 확인해 보자.

n = len(genre_array)
genre_play_dict = {}
for i in range(n):
    genre = genre_array[i]
    play = play_array[i]
    if genre not in genre_play_dict:
        genre_play_dict[genre] = play
    else:
        genre_play_dict[genre] += play

list에 genre가 없다면, play 수를 입력하고, play가 이미 있다면 play 수를 더해 최종적으로 play 수가 얼마인지 나오게 한다.

각 장르의 총 play 수를 구했으니, 장르 내에서도 정렬을 해야 한다. 장르별 key에 재생 수와 인덱스를 배열로 묶어 배열에 저장하면 된다.

genre_index_play_dict = {}
    ...
for i in range(n):
    if genre not in genre_play_dict:
        genre_index_play_dict[genre] = [[i, play]]
    else:
        genre_index_play_dict[genre].append([i, play])

장르의 각 곡의 index와 play 수를 배열로 저장하였다. {'classic': [[0, 500], [2, 150], [3, 800]], 'pop': [[1, 600], [4, 2500]]}

이제 어느 장르가 더 많이 play 되었고, 그 장르 안에서 어떤 index의 곡이 더 많이 재생되었는지 확인하여 배열에 저장해야 한다.

classic, pop 장르 사이에 어떤 곡이 더 많이 play 되었는지 컴퓨터가 확인하려면, genre_play_dict를 정렬해보면 된다. genre_play_dict.items() 를 통해 확인해 보면, dict_items([('classic', 1450), ('pop', 3100)])로 딕셔너리의 key - value 값을 배열 형태로 출력해준다. 'classic' : 1450, 'pop' : '3100' 이라는 딕셔너리를 value 값에 따라 정렬하려면 sorted라는 함수를 사용해준다.

• sorted : 정렬할 배열을 기준에 따라 정렬해주는 함수, key 라는 인자에 람다값을 전달해준다.
  • 람다값 : 어떤 것을 정렬할지에 대해 정해주는 기준

sorted(genre_play_dict.items(), key=lambda item: item[0]) 이렇게 item[0]으로 기준을 잡으면, 'classic'이 기준이 된다. item[1]로 잡으면, 1450이 기준이 되어 배열을 정렬할 수 있게 된다. sorted(genre_play_dict.items(), key=lambda item: item[1]) ⠀ ⠀ 이 정렬대로면, 오름차순으로 정렬 되는데, 내가 구해야 하는 값은 가장 많이 재생된 수이기 때문에 역순으로 정렬되게 설정해 주어야 한다. sorted(genre_play_dict.items(), key=lambda item: item[1], reverse=True) ⠀

sorted_genre_play_array = sorted(genre_play_dict.items(), key=lambda item: item[1], reverse=True)
# [('pop', 3100), ('classic', 1450)]

'pop'이 더 많이 재생된 장르라는 것을 알게 되었으니, 이 장르를 가지고, 그 장르에 해당하는 곡들 중 어느 곡이 더 많이 재생되었는지 확인하고 배열에 넣는 작업만 마무리하면 된다.

result = []
for genre, value in sorted_genre_play_array:
    index_play_array = genre_index_play_dict[genre]
    sorted_index_genre_play_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
    for i in range(len(sorted_index_genre_play_array)):
    if i > 1:
        break
    else:
        result.append(sorted_index_genre_play_array[i][0])
return result

sorted_genre_play_array에서 구분한 genre를 genre_index_play_dict에서 찾는다. genre가 'pop'이라고 하면, index_play_array에는 'pop': [[1, 600], [4, 2500]]이 들어오게 된다. index_play_array를 sorted( ) 시키면 [[4, 2500], [1, 600]]으로 정렬된다. for 문에 의해서 result 배열에 삽입될 곡을 지정할 수 있게 된다. 문제에서 '노래를 두 개씩 모아' 베스트 앨범에 수록한다고 했으니까 if 문으로 조건을 주고 2개가 넘으면 break으로 for 문을 빠져나가게 했고, result 배열에 들어갈 데이터는 각 곡의 index이기 때문에 sorted_index_genre_play_array[i][0] 으로 곡의 index만 저장할 수 있게 한다.

# 변수 이름이 다를 수 있음
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]


def get_melon_best_album(genre_array, play_array):
    n = len(genre_array)
    genre_play_dict = {}
    genre_index_play_array_dict = {}
    for i in range(n):
        genre = genre_array[i]
        play = play_array[i]
        if genre not in genre_play_dict:
            genre_play_dict[genre] = play
            genre_index_play_array_dict[genre] = [[i, play]]
        else:
            genre_play_dict[genre] += play
            genre_index_play_array_dict[genre].append([i, play])
    # print(genre_play_dict.items())
    # print(genre_index_play_array_dict)

    sorted_genre_play_array = sorted(genre_play_dict.items(), key=lambda item: item[1], reverse=True)
    # print(sorted_genre_play_array)

    result = []
    for genre, _value in sorted_genre_play_array:
        index_play_array = genre_index_play_array_dict[genre]
        sorted_by_play_and_index_play_index_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
        print(sorted_by_play_and_index_play_index_array)
        for i in range(len(sorted_by_play_and_index_play_index_array)):
            if i > 1:
                break
            result.append(sorted_by_play_and_index_play_index_array[i][0])
    return result


print(get_melon_best_album(genres, plays))  # 결과로 [4, 1, 3, 0] 가 와야 합니다!
print("정답 = [0, 6, 5, 2, 4, 1] / 현재 풀이 값 = ", get_melon_best_album(["hiphop", "classic", "pop", "classic", "classic", "pop", "hiphop"], [2000, 500, 600, 150, 800, 2500, 2000]))

⠀ ⠀

오우 이번주도 역시나 빡센 공부였다. 하지만, 알고리즘 문제를 어떤 식으로 풀어나가야 하는지 조금씩 알게 되는 수업이었다. 문제들을 혼자 힘으로 풀어보거나, 어떤 식으로 방향을 잡아 나가야 하는지 알 수 있었던 것 같다. 아직 혼자 힘으로 문제를 풀라고 하면 어떤 개념을 적용해서 풀어야 할지는 모르겠지만, 여러 문제를 풀어가면서 그 유형을 익혀야겠다고 생각했다.

혼자 힘으로 생각한 문제풀이는 알고리즘적인 방식이 아니라 그냥 문제 해결 방식이었다. 알고리즘 개념들을 더 익혀서 내것으로 만들어 문제에 적용시켜 보는 연습이 필요할 것으로 보인다.!!!

1. 어레이와 링크드리스트에 대해 배우고 차이점을 익힌다.
2. 이진 탐색의 효율성과 전제 조건에 대해 배운다.
3. 재귀함수의 방법과 전제 조건에 대해 배운다.

어레이와 링크드 리스트

• 어레이 : 크기가 정해진 저장 공간 배열은 각 방에 접근할 수 있다. rooms[0]
  • 데이터 추가 시 모든 공간이 다 차면 새로운 메모리 공간을 만들어야 함.
  • 데이터에 접근하는 경우가 빈번하다면 어레이 사용하는게 좋음
• 링크드 리스트 : 크기가 정해져 있지 않은 저장 공간
  • 리스트는 특정 원소에 접근하려면 연결 고리를 탐색 해야 한다. 그래서 O(N)이라는 시간 복잡도를 가진다.
    • 모든 공간이 다 차도 뒤에 노드를 연결해서 추가할 수 있다.
  • 삽입과 삭제 시 더 유리하다

클래스

클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 말하는 것이다.

class Person:
    pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미입니다!


person_1 = Person()
print(person_1)  # <__main__.Person object at 0x1090c76d0> => 공간의 주소
person_2 = Person()
print(person_2)  # <__main__.Person object at 0x1034354f0>

생성자 : 객체를 만들 때 쓰는 함수

def __init__(self):
    print("hihihi", self)

위 함수는 클래스가 처음 생성될 때 작동하는 함수이다. 생성자가 처음 생성될 때 __init__ 안에 있는 내용이 실행된다. 여기서 self는 자기 자신을 넘겨준다는 의미이다. (항상 self는 존재해야 한다.)

Person 클래스 코드를 보면, 밑에서 Person() 이렇게 생성자를 실행하는 코드를 볼 수 있는데, 이 코드는 __init__() 함수와 동일한 모습을 취해야 한다. 그래서 __init__()에 self이외의 인자를 받겠다면, 생성자의 인자 자리에도 클래스 생성시 넘겨주어야 하는 인자가 생겨야 한다.

class Person:
    def __init__(self, param_name):
        print("hihihi", self)
        self.name = param_name

person_1 = Person("유재석")  
print(person_1.name)
# hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!

연관성 있는 데이터들을 클래스 내에서 관리할 수 있고, 다양한 객체들을 쉽게 생성할 수 있다.

링크드 리스트 구현

링크드 리스트의 자료구조 모습

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

노드에는 칸에 있는 데이터와 다음 칸이 뭔지 알아야 하는 두 가지 정보가 필요하다. 그래서 클래스로 묶는 것이 효율적이다.

링크드 리스트는 self.head에 시작하는 노드를 저장한다. 다음 노드를 보기 위해서 각 노드의 next를 조회한다.

여기서 꿀팁 코드 전체를 한 줄 내리거나 올리는 방법 control + shift + 방향키

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head
        while cur.next is not None:
            cur = cur.next
            print("cur is ", cur.data)
        cur.next = Node(data)

    def print_all(self):
        print("hihihi")
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next


Linked_list = LinkedList(3)
Linked_list.append(4)
Linked_list.append(5)
Linked_list.print_all()
# node = Node(3)
# first_node = Node(4)
# node.next = first_node

LinkedList 라는 클래스에 인자로 첫번째 node를 인자로 넘겨준다. -> 인자로 넘겨진 data는 Node 클래스의 생성자를 LinkedList 클래스의 head로 생성한다. -> (appedn 함수는 현재 존재하는 node의 next의 포인터로 가서 새로운 node를 append 해주는 함수이다.) 새로운 node를 append 함수를 이용해 연결해준다. -> print_all 함수를 통해 cur 변수에 cur.next로 다음 node를 가리키게 하면서 현재의 모든 노드들을 출력하게 한다.

특정한 index의 node 값을 알기 위해서 할 수 있는 코드는?

def get_node(self, index)라는 함수를 만들어 index 별로 링크드 리스트에 들어 있는 node를 반환해 준다.

함수에 알고 싶은 index의 번호를 넘겨주면, count 변수로 1씩 키우면서 index보다 작을 때까지 node.next로 node를 옮긴다.

 def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

*함수 내에서 다른 함수를 호출하고 싶을 때에는 self.함수이름() 으로 함수를 호출하면 된다. *

링크드 리스트에 원소 추가하기

index의 다음 노드로 연결되어 있는 화살표를 새로 생성한 노드에 연결해주고, 화살표가 닿아 있었던 index의 다음 노드는 새로 생긴 노드의 화살표를 다시 받기 위해서 다른 변수에 저장되어 있어야 한다.

새로운 노드 (index.next): new_node new_node.next = next_node(새로운 노드의 화살표가 닿는 노드)

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node    # head -> [6] -> [5]
            return

        node = self.get_node(index-1)  # index -> [5] -> [12] -> [6] -> [8]
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

index-1을 해주어서 인자가 1 이상이면 정상적으로 작동하지만, 0일 때는 -1이 되므로 예외처리를 해주어야 한다. => 이때는 index == 0 인 조건을 만들어 새롭게 생긴 노드에 next 자리에 현재 head 노드가 되는 노드를 집어 넣고, head 자리에 새로 만든 노드를 집어 넣어주면 된다.

링크드 리스트에 원소 삭제하기

[0] -> [1] -> [2] 이 리스트 중에서 1을 빼고 싶다면(삭제하고 싶다면) [0]이 가리키는 화살표를 [2]로 옮기면 된다. 그래서 옮기고 싶은 index번호에 1을 빼서 빼고 싶은 노드의 앞 노드를 가져오고, 앞 노드의 .next.next로 [2]의 노드로 화살표가 가게 한다. => node.next = node.next.next

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index-1)
        node.next = node.next.next

링크드 리스트 문제

문제 1

Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. ⠀ 예를 들어 아래와 같은 링크드 리스트를 입력받았다면, 각각 678, 354 이므로 두개의 총합 678 + 354 = 1032 를 반환해야 한다. ⠀ 단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다. ⠀ [6] -> [7] -> [8]⠀⠀⠀⠀⠀ [3] -> [5] -> [4]

각 list의 head를 가지고 있으니, head.next로 다음 노드를 찾아 더할 수 있다. 그러나, 6 + 7 + 8 = 21이므로 각 원소의 data로만 가지고는 문제를 풀 수 없다. => 6 * 10 + 7 = 67 => 67 * 10 + 8 = 678 로 각 단계마다 10을 곱해주면 된다는 것을 생가하면 된다!!! (이거 생각한 사람 개천재 ㄷㄷ)

linked_list가 2개 이기 때문에 중복된 코드를 함수로 구현해준다.

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = _get_linked_list_sum(linked_list_1)
    sum_2 = _get_linked_list_sum(linked_list_2)
    return sum_1 + sum_2

def _get_linked_list_sum(linked_list):
    linked_list_sum = 0
    head = linked_list.head
    while head is not None:
        linked_list_sum = linked_list_sum * 10 + head.data
        head = head.next
    return linked_list_sum

_get_linked_list_sum 함수로 중복된 내용을 잡아준다.

이진 탐색

배열에서 중간부터 탐색하여 효율적으로 배열을 탐색하는 탐색 방법이다.

숫자를 내림하는 방법 : // // 연산자를 이용하면 소수점 이하으 ㅣ수를 모두 버리고 몫만 나타낼 수 있다.

Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다. 이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오.

이진 탐색으로 시도해 본다.

<이진탐색의 핵심이 되는 코드만 작성>

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:   # up
            current_min = current_guess + 1
        else:                                 # down
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2
    return False

⠀ ⠀ ⠀ 일정한 규칙으로 정렬되어 있는 데이터일때만 이진 탐색이 가능하다

재귀함수

자신을 계속해서 반복적으로 호출하는 함수이다.

재귀함수를 사용하는 이유는 ??

• 재귀 함수를 이용해서 간결하고 효율성 있는 코드를 작성할 수 있기 때문

재귀함수를 돌 때는 언제 탈출할지 조건을 꼭 정해 주어야 한다. ⠀

가장 대표적인 재귀 함수 예시 코드

def count_down(number):
    if number < 0:
        return
    print(number)
    count_down(number - 1)
    ⠀
count_down(60)

팩토리얼

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다. 3! 은 3 * 2 * 1 = 6, 4! 는 4 * 3 * 2 * 1 = 4 * 3! = 24

Factorial(n) = n * Factorial(n - 1) Factorial(n - 1) = (n - 1) * Factorial(n - 2) .... Factorial(1) = 1

예시 코드

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
⠀
⠀
print(factorial(5))

회문 검사

회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미한다.

회문검사 문제

Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오. ⠀ "abcba" # True

코드

input = "abcba"
# 회문 검사

def is_palindrome(string):
    length = len(string)
    for i in range(length):
        print(string[length - 1 - i])
        if string[i] is not string[length - 1 - i]:
            return False
    return True

print(is_palindrome(input))

문자열 슬라이싱

• '가나다라마바사'[0:5] => '가나다라마' => 0번째 인덱스부터 5번 인덱스(6번째) 앞에 까지 짤라서 반환해준다.

• 뒤에서 2번째까지 문자열을 자르고 싶다면? '가나다라마바사'[0:-2] '가나다라마'

위에 회문검사 코드를 재귀함수로 다시 작성해보자

def is_palindrome(string):
    if len(string) <= 1:
        return True

    if string[0] != string[-1]:
        return False

    return is_palindrome(string[1:-1])


print(is_palindrome(input))

재귀함수로 작성하기 위해서는 문제가 축소되는 특징이 보여야만 한다. 특정 구조가 반복되는 것 같으면, 재귀함수로 축소시켜볼 수도 있다. -> 재귀함수 사용시 반드시 탈출 조건 작성하기!!

숙제

Q1. 링크드 리스트의 끝에서 K번째 값을 반환하시오. ⠀ [6] -> [7] -> [8] ⠀ ⠀# 이런 링크드 리스트가 입력되었을 때, 끝에서 2번째 값은 7을 반환해야 합니다!

시작점을 2개를 잡고 간다. 첫번째보다 k번째 떨어진 두번째 변수가 끝에 가게 되면, 첫번째 변수가 두번째 변수보다 k만큼 떨어져 있으니까 첫번째 변수의 node 값이 링크드 리스트의 끝에서 k번째 값이 된다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def get_kth_node_from_last(self, k):
        start = self.head
        end = self.head
        for i in range(k):
            end = end.next
        while end is not None:
            start = start.next
            end = end.next
        return start


linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)

print(linked_list.get_kth_node_from_last(2).data)  

⠀ ⠀

Q2. 배달의 민족 서버 개발자로 입사했다. 상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다. ⠀ 그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오. ⠀

menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"]
orders = ["오뎅", "콜라", "만두"]

이진 탐색 보다는 set() 함수인 집합 자료형을 사용하는 것이 좋다. 집합 자료형은 중복을 허용하지 않는 자료형이다.

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
# 현재 주문 가능한 상태인가?


def is_available_to_order(menus, orders):
    menus_set = set(menus)
    for order in orders:
        if order not in menus_set:
            return False
    return True


result = is_available_to_order(shop_menus, shop_orders)
print(result)

⠀ ⠀

Q3. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. ⠀ -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 ⠀ 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오. ⠀

numbers = [1, 1, 1, 1, 1]
target_number = 3

재귀함수를 이용하여 문제를 풀어야 했는데, 너무 너무 너무 어려웠다...

1로만 풀기는 너무 어렵기 때문에 [2, 3, 1]로 두고 보기 쉽게 풀어보았다.

1. +2 +3 → +1 = +2 +3 +1

           → -1 = +2 +3 -1

2. +2 -3 → +1 = +2 -3 +1

           → -1 = +2 -3 -1

3. -2 +3 → +1 = -2 +3 +1

           → -1 = -2 +3 -1

4. -2 -3 → +1 = -2 -3 +1

           → -1 = -2 -3 -1

이 방법을 생각하면서, +2 +3 +1 / -1 을 사용할 수 있는 재귀 함수를 이용하는 것이었다. 문제를 이해하며 풀긴 하였지만, 정확히 설명할 수가 없어서 제대로 이해했는지 장담할 수가 없다...

index 번호가 1개씩 올라가면서 array[0]=2 -> array[1]=3 -> array[2]=1 -> index = 3일때 값들을 다 더한 값을 배열에 append 시켜 최종적으로 6, 4, 0, -2, 2, 0, 4, 6 의 합들이 append되게 하여, 그 값을 출력시키는 코드를 먼저 작성하였다.

numbers = [2, 3, 1]
target_number = 0
result = []  # 모든 경우의 수를 담기 위한 배열


def get_all_ways_to_by_doing_plus_or_minus(array, current_index, current_sum, all_ways):
    if current_index == len(array):  # 탈출조건!
        all_ways.append(current_sum)  # 마지막 인덱스에 다다랐을 때 합계를 추가해주면 됩니다.
        return
    get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index], all_ways)
    get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index], all_ways)


get_all_ways_to_by_doing_plus_or_minus(numbers, 0, 0, result)
print(result)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
# 모든 경우의 수가 출력됩니다!
# [6, 4, 0, -2, 2, 0, -4, -6]

하지만 이 문제는 target의 수가 나오는 경우의 수를 묻는 문제이기 때문에 마지막 index = 3일 때 all_ways 배열에 append 시키는 대신 target과 current_sum의 값을 비교해 그 값이 맞다면 global 변수인 target_count에 저장하게 하여 최종적으로 주어진 배열에서 정해진 target의 결과값이 나올 수 있는 방법의 수를 구할 수 있게 된다.

numbers = [1, 1, 1, 1, 1]
target_number = 3
target_count = 0


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(array):
        if current_sum == target_number:
            global target_count
            target_count += 1
        return
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - array[current_index])


get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)  # 5를 반환해야 합니다! target_number
print(target_count)

알고리즘이라는 것이 필요하다고는 느끼지만, 아직 내가 자유롭게 알고리즘에 대해 생각하고, 프로그램의 효율성을 생각하며 프로그래밍을 하는 단계에 가기에는 부족하다는 생각이 많이 든다. 복잡한건 사실이지만, 조금만 더 깊게 생각하면 이해할 수 있다고 생각하며 수업을 듣고 싶다. 엄청나게 더운 2021년 여름에 머리가 답답하게 막혀오는 알고리즘을 수업을 듣고 과제를 하니 좀 힘든 부분도 많지만 그래도 결국에는 이해해 내고, 코드를 작성해나가는 나에게 더 잘할 수 있다고 말해주고 싶다.

학습목표

1. 개발자들에게 알고리즘 공부가 필요한 이유를 이해한다.
2. 알고리즘을 학습하기 위한 기본 코드 구현력을 높인다.
3. 시간 복잡도, 공간 복잡도에 대해 배운다.

알고리즘이란?

어떤 문제의 해결을 위하여, 입력된 자료르 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합 -> 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임이다.

좋은 개발자가 되려면 알고리즘을 공부해야 한다. 좋은 프로그램이란? 작은 공간을 이요해 빠른 속도로 수행되는 프로그램이다. 이런 프로그램을 만들기 위해서는 특정 자료구조나 접근방법을 사용해야 한다. 또한, 좋은 회사에 취업하고 싶다면 알고리즘을 공부해야 한다!

컴퓨터 언어를 배우면서 가장 기본적인 알고리즘으로 최대값, 최빈값 찾기를 해보았다. 기본적인 언어인 C나 JAVA 같은 컴파일러 언어들만 알고 있던 나에게 인터프리터 언어인 python은 조금 생소했다. 그래서 첫번째 연습 문제였던 최대값을 구하는 코드에서부터 막히기 시작했다. 프로젝트를 하면서 파이썬을 살짝 다룬적이 있어서 최대값 문제를 금방 풀 수 있을 줄 알았다. 그런데,,, for문 안에서 tab 키를 누르지 않아 코드가 이상하게 작동되었다. 최대값을 찾아야 하는데, 가장 처음 수만 출력 되는 것이었다.

def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num

if문과 같은 열로 else를 작성하였는데, if에서 당연히 3보다 3이 작을 테니 3이 return 되는 것이었다. 그런데, else를 2번째 for문 열로 맞춰주니, 2번째 for문 안에서 최대값을 찾고 나온 값을 얻을 수가 있었다. tab키의 사용의 중요성을 알 수 있었다.

파이썬의 내장 함수 str.isalpha() : 해당 문자열이 알파벳인지 알 수 있다.

파이썬의 배열 초기화 : array = [0] * 26 --> 배열을 0으로 26개를 초기화시킨다는 의미 파이썬에서 문자를 아스키코드로 변환시켜주는 함수 : print(ord('a')) # 97 반대로, 아스키코드를 문자로 변환하는 코드 : chr()

Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오 A. 정답은 ~ -> 내가 직접 작성한 코드(강사님의 코드x)

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    array = [0] * 26
    for char in string:
        if not char.isalpha():
            continue
        num = ord(char) - 97
        array[num] += 1
    max_index = 0
    for index in range(len(array)):
        max_num = array[0]
        if max_num < array[index]:
            max_num = array[index]
            max_index = index
    return chr(max_index + ord("a"))
result = find_max_occurred_alphabet(input)
print(result)

시간복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계이다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다. 입력값이 늘어도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘일 것이다!

각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산한다. 배열의 계산은 배열의 길이 만큼의 연산된다고 생각하여, N 만큼의 시간이 걸린다고 표현한다.

N과 $$N^2$$은 N이 커질수록 그 차이가 심하게 난다. 그래서 N의 지수를 비교하면서 시간복잡도를 분석할 수 있다.

상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.

공간복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다. 입력값이 늘어나도 공간은 덜 차지하는 알고리즘이 좋은 알고리즘일 것이다!

저장하는 데이터의 양이 1개의 공간을 사용한다고 계산한다. 공간복잡도로 계산되는 수들은 상수이기 때문에 (변하지 않기 때문에) 적은 차이의 공간 사용량은 크게 상관이 없다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다.

시간복잡도 계산하는 방법

         for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행 

        if occurrence > max_occurrence: # 비교 연산 1번 실행
            max_alphabet = alphabet     # 대입 연산 1번 실행
            max_occurrence = number     # 대입 연산 1번 실행

이 코드의 시간 복잡도는

1. alphabet_array 의 길이 X 대입 연산 1번
2. alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번) 즉, 52N + 104라는 시간이 걸린다.

$$26(1 + 2N + 3) = 52N + 104$$

    for char in string:        # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha(): # 비교 연산 1번 실행
            continue
        arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
        alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

    max_occurrence = 0        # 대입 연산 1번 실행 
    max_alphabet_index = 0    # 대입 연산 1번 실행 
    for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
        if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
            max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
            max_alphabet_index = index           # 대입 연산 1번 실행

이 코드의 시간 복잡도는

1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)
2. 대입 연산 2번
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번) 으로 3N + 106의 시간이 걸린다.

$$N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106$$

점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법이다.

• 표기법의 종류
  • 빅오(Big-O) : 최악의 성능이 나올 때 오느 정도의 연산량이 걸릴 것인지
  • 빅 오메가(Big-Ω) : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지

=> 알고리즘은 입력값에 따라서 성능이 달라질 수 있다. 입력값의 분포에 따라서 성능이 변화할 수 있다.

input = [3, 5, 6, 1, 2, 4]


def is_number_exist(number, array):
    for num in array:   # array 의 길이만큼 아래 연산이 실행
        if num == number:   # 비교 연산 1번 실행
            return True     # N *1 = N 만큼
    return False


result = is_number_exist(8, input)
print(result)

위 코드의 시간복잡도는 $$N * 1 = N$$ 만큼 이다. 그런데 만약 input 배열에 3이 가장 마지막에 들어가 있으면, for문이 배열 끝까지 돌아야 하기 때문에, 3이 배열의 첫번째에 있을 때보다 효율이 떨어질 수 밖에 없다. 그래서 앞에서 말했듯이 입력값의 분포에 따라 알고리즘의 성능에는 변화가 있다.

• 빅오 표기법으로 표시하면 O(N)(최악)
• 빅 오메가 표기법(최상)으로 표시하면 Ω(1)의 시간 복잡도를 가진 알고리즘이다.

✅ 알고리즘에서는 거의 모든 알고리즘을 빅오(최악) 표기법으로 분석한다. -> 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적기도 하고, 최악의 경우를 항상 대비해야 하기 때문이다!!

1차 반복문이 나오고, array의 길이만큼 그 반복문이 돈다면, 다른 상수 상관 없이 N만큼의 시간복잡도가 걸린다고 생각하면 된다.

Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오. 주어진 문자열 : "abadabac"

• 힌트 : 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 된다.

Q1. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

이 문제를 작성할 때 수학적인 지식이 부족해서 조금 애를 먹었다. 주어진 수에서 소수를 구분해 내는 것이 어려웠다.

처음에는 for문을 2차로 구성해서 문제를 푸는 방법밖에 생각이 안나서 앞에서 2차원이 되면 알고리즘 효율성에서 비효율적이라는 것은 알고 있었지만, 이 방법 밖에는 생각이 안났었다..

prime_list = []
    for n in range(2, number + 1):
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            prime_list.append(n)

위 방법으로 for문을 2개 사용해서 작성하였지만, 이건 효율적인 방법이 아님을 알기에 다른 방법이 있는지 공부해보기 위해 찾아보았다.

일단, 수가 2~ n-1까지의 수로 나눠지면 그 수는 소수가 아니기에 for문의 range를 수정하였다. 그런데, 2 ~ n-1까지의 소수로 나누어 떨어지지 않는다면 더 빠르게 소수를 찾을 수 있을 것이다. 또한, 주어진 자연수 n이 소수이기 위해서 필요한 조건은 n이 n의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다는 것이다. 수가 수를 나누면 몫이 발생하게 되는데, 몫과 나누는 수, 둘 중 하나는 반드시 n의 제곱근 이하이기 때문이다. *=> 그래서 i * i <= n 일때까지 비교하면 된다. *

prime_array = []
    if number < 2:
        return 0 #소수는 없다.
    for num in range(2, number+1):
        for n in prime_array:
            if num % n == 0 and n * n <= num:
                break
        else:
            prime_array.append(num)

나는 2보다 작은 수가 들어왔을 때를 다루기 위해 if문을 추가했고, 2차 for문에서 지금까지 구해진 소수들의 배열의 내용들로 수를 나누고, 그 수가 n의 제곱근 이하인지 확인하는 if문을 두어 소수를 구하는 배열을 만들어 내었다. 이 문제는 구현하는데 좀 많이 힘이 들었었다. 어떻게 접근해야 할지 몰라서 많이 헤맸던 문제였다. 이런 문제들이 코딩 시험에 나온다니 나는 못할 것 같다는 생각도 들었다...

Q2. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

0을 1로, 1을 영으로 몇 번 바꾸는게 최소한으로 바꾸는 것인지 구하는 알고리즘 문제였다. 전 문제와는 다르게 이 문제는 빠르게 풀 수 있었다.

input = "011110"

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_0_to_1 = 0
    count_1_to_0 = 0
    for index in string:
        if index == '0':
            count_0_to_1 += 1
        else:
            count_1_to_0 += 1
    if len(string) > 0 and (count_1_to_0 == 0 or count_0_to_1 == 0):
        return len(string)
    return min(count_1_to_0, count_0_to_1)

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

강사님의 해설과는 흐름은 같지만 약간 다른 접근을 해보았다. 현재 주어진 string에서 0과 1이 몇 개인지 각각 세고, 그 수가 적은 숫자를 바꾸는 것이 최소한으로 바꾸는 것이기에 그 수를 반환해 주면 되는 것이었다.

그런데, 내 코드의 문제점은 만약 전체가 다 0이거나, 1이면 한 쪽은 무조건 0이 되기 때문에 string의 길이만큼 변하는 것이 아닌 0으로 반환되는 것이다. 그래서 전체가 0이거나 1일때를 처리해주는 if문 코드를 넣어주었다. 그랬더니 어떤 string을 넣어도 최소 변환 횟수를 잘 출력해주었다. ⠀⠀⠀⠀

⠀ ⠀

⠀ 이번주 학습 소감 알고리즘은 어렵다....

마켓에 어떻게 배포하는지 배운다!

수익성을 낼 수 있는 방법

• 앱 마켓에 유료앱 베포 수익 모델
• 앱 내 배너 광고 수익 모델
• 앱 콘텐츠 판매 수익 모델 : 인 앱 결제
• 구독 수익 모델
• 앱 개발 용역 수익 모델
• 외부 브랜드 광고 수익 모델

우리는 <앱 내 배너 광고 수익 모델>을 공부해 본다!

구글 애드몹(AdMob)

expo 에 있는 광고 admob 모듈을 설치해준다

expo install expo-ads-admob

구글 애드몹에 가입하고, 앱에 광고를 달기 위해 앱을 등록한다 등록하면, 내가 올리고 싶은 앱의 ID 키가 발행된다. 그 키를 가지고 app.json 파일에 가서 adroid : { value } 에 가서 자신의 앱의 키 값을 넣는다.

"googleMobileAdsAppId": "키 값 넣기"

여기서 tip! 추가한 앱의 ID가 보이지 않는다면, 구글 애드몹 화면의 가장 왼쪽의 메뉴들에서 앱 버튼을 누르고, 모든 앱 보기 버튼을 눌러준다! 그러면 이렇게 등록한 앱들의 ID가 나온다!

가로 배너 설정

애드몹을 설정하는 코드들! 우선 설치한 expo admob에서 필요한 코드들을 import 시킨다.

import {
  setTestDeviceIDAsync,
  AdMobBanner,  //요거 사용함
  AdMobInterstitial,
  PublisherBanner,
  AdMobRewarded
} from 'expo-ads-admob';

그리고 카드들이 보이는 곳 바로 아래에 ad를 보이게 만들어준다. 이때, 3항 연산자로 Platform이 IOS인지, Adroid인지 확인하여 분리된 광고 를 보여지게 한다.

<View style={styles.cardContainer}>
            {/* 하나의 카드 영역을 나타내는 View */}
            {
            cateState.map((content,i)=>{
                return (<Card content={content} key={i} navigation={navigation}/>)
            })
            }
            {Platform.OS === 'ios' ? (
                <AdMobBanner
                  bannerSize="fullBanner"
                  servePersonalizedAds={true}
                  adUnitID="ca-app-pub-3233048070306066/8476925399"
                  style={styles.banner}
                />
            ) : (
                <AdMobBanner
                  bannerSize="fullBanner"
                  servePersonalizedAds={true}
                  adUnitID="ca-app-pub-3233048070306066/3033027021"
                  style={styles.banner}
                />
            )}
        </View>

배너의 사이즈와 위치 등은 개발자 마음대로 설정할 수 있다!

전면배너 설정

전면 배너는 AdMobInterstitial 를 활용한다.

전면 배너를 설정하기 위해서는 사전 설정이 조금 필요하다.

useEffect(()=>{
        // Card.js에 들어오자마자 전면 광고 준비하느라 useEffect에 설정
        //애드몹도 외부 API 이므로 실행 순서를 지키기위해 async/await 사용!
        //안드로이드와 IOS 각각 광고 준비 키가 다르기 때문에 디바이스 성격에 따라 다르게 초기화 시켜줘야 합니다.
        Platform.OS === 'ios' ? AdMobInterstitial.setAdUnitID("ca-app-pub-3233048070306066/4844161513") : AdMobInterstitial.setAdUnitID("ca-app-pub-3233048070306066/5948880695")
 AdMobInterstitial.addEventListener("interstitialDidLoad", () =>
            console.log("interstitialDidLoad")
        );
AdMobInterstitial.addEventListener("interstitialDidFailToLoad", () =>
            console.log("interstitialDidFailToLoad")
        );
AdMobInterstitial.addEventListener("interstitialDidOpen", () =>
            console.log("interstitialDidOpen")
        );
AdMobInterstitial.addEventListener("interstitialDidClose", () => {
              //광고가 끝나면 다음 코드 줄이 실행!
            console.log("interstitialDidClose")
            navigation.navigate('DetailPage',{idx:content.idx})
        });
    },[])

• interstitialDidLoad : 광고가 로드될 때 사용할 로직, 이벤트 작성하는 함수
• interstitialDidFailToLoad : 광고 로드에 실패했을 때 어떻게 할 건지 이벤트를 작성하는 함수
• interstitialDidOpen : 광고가 오픈되고 나서 뭘 할건지 설정하는 함수
• interstitialDidClose : 광고가 끝난 후 어떻게 할 것인지 설정하는 함수

지금 하고 있는 앱에서는 AdMobInterstitial.addEventListener("interstitialDidClose", () => { } 이 코드를 사용할 건데, avigation.navigate('DetailPage',{idx:content.idx}) 이렇게 광고 후에 DetailPage로 이동하게 한다.

그럼 이렇게 광고에 관련한 함수들은 작성했는데, 어떻게 광고가 보이게 할 것인가? 위에 코드들은 광고 자체에 관련한 함수였다. 이제는 광고를 보여주는 코드를 작성해야 한다.

const goDetail = async () =>{
      await AdMobInterstitial.requestAdAsync({ servePersonalizedAds: true});
      await AdMobInterstitial.showAdAsync();
    }

async () => { await } 함수로 세팅한 차례대로 함수가 실행될 수 있게 해준다.

실제 앱 배포해보기!

⠀ 앱을 배포하려면 필요한 것들이 있다

1) 앱 로고 2) 스플래시 스크린(앱 시작 초기 화면) 3) 앱 마켓에 올릴 설명 이미지 4) Expo의 도움을 빌려 쉽게 준비 가능한 앱 버전 관리, 안드로이드, iOS 인증서 관리 등

스플래시 스크린

스플래시 스크린은

온라인 포토샵 -->

앱 폴더의 asset 파일 안에 있는 splash.png 파일을 설정하고 싶은 스플래시 사진으로 변경한다. (꼭 png 파일로 저장하기!!)

내가 설정한 이미지 ↓

로고 설정하기

스플래시 스크린과 사진 만들기와 동일하게 이미지를 만드는데, icon.png 로 저장해 주면 된다.

내가 설정한 아이콘 이미지 ↓

icon이 적용된 모습

app.json 알기

"expo": {
    "name": "sparta-myhoneytip-rim",
    "slug": "sparta-myhoneytip-rim",
    "version": "1.0.0",
    "orientation": "portrait",
    "icon": "./assets/icon.png",
    "splash": {
      "image": "./assets/splash.png",
      "resizeMode": "contain",
      "backgroundColor": "#ffffff"
    },
    "updates": {
      "fallbackToCacheTimeout": 0
    },
    "assetBundlePatterns": [
      "**/*"
    ],
    "web": {
      "favicon": "./assets/favicon.png"
    },
    "ios": {
      "supportsTablet": true,
      "buildNumber": "1.0.0",
      "bundleIdentifier": "com.myhoneytip.rim",
      "config": {
        "googleMobileAdsAppId": "ca-app-pub-3233048070306066~8707384905"
      }
    },
    "android": {
      "adaptiveIcon": {
        "foregroundImage": "./assets/adaptive-icon.png",
        "backgroundColor": "#FFFFFF"
      },
          "package": "com.myhoneytip.rim",
          "versionCode": 1,
          "config": {
            "googleMobileAdsAppId": "ca-app-pub-3233048070306066~2706278875"
          }
  }
  }

• name : 앱의 이름을 뜻한다.
• slug : 앱 설명
• version : 앱 버전 (재배포 시 버전을 꼭 변경해야 한다!)
  • IOS와 Android 앱 서버 코드도 업데이트 하거나 변경되었을 시 꼭 버전 변경을 해주어야 한다.
• icon : 앱의 아이콘 이미지 경로
• splash : 스플래시 이미지 경로
• bundleIdentifier : 이 앱에 대한 고유한 주소를 앱 마켓에 알려 주는 것이다. 이 부분 뒤에는 주소가 들어온다.
  • 앱 마켓에 이름이 동일하더라도 고유한 주소 값이 다르기 때문에, 앱 마켓이 구분할 수 있게 된다. ⠀ ⠀ ⠀

최종 파일 생성하기

안드로이드 - 구글 플레이 스토어와 ios - 앱 스토어에 앱을 올리는 방법이 다르다는 것을 알게 되었다. 또한, 그 방법이 매우 복잡하다는 사실도 알게 되었다.. :(

라이센스도 구매해야 해서 나는 아직 연습하는 학생 신분이라 조금 더 앱 개발에 확신이 생기고, 정말 배포하고 싶은 앱을 개발했을 때 구매하여 배포하고 싶어 직접 배포하지는 않았다.

하.지.만. 내가 만든 앱을 블로글에 남겨보려 한다. (ㅎㅎ)

최종 프로젝트 작품

1. 녹화 영상 !youtube[4YJ1CUP82hk]

2. 취지&설명

   • 이 앱은 일상생활에서 적용해 볼 수 있는 꿀팁들을 담고 있는 앱입니다!
   • 나만의 꿀팁들을 저장할 수 있고, 또 다른 사람들에게 공유할 수도 있습니다.

   (앱개발 종합반에서 함께 만들었습니다. :-) )

3. 기술 설명

   • expo를 사용하여 앱개발에 도움을 받았습니다.
   • 메인 페이지와 메인 페이지에서 보여지는 카드들의 내용을 보여지는 디테일한 페이지와 계속해서 보고 싶은 꿀팁들은 저장하여 꿀팁 페이지에서 볼 수 있게 하였습니다.
   • firebase 서버를 연결하여 서버에서 사용자의 기기의 번호를 기준으로 각각 저장할 수 있게 하여 사용자들마다 자신들의 꿀팁들을 저장할 수 있습니다!

4. 어려웠던 점 & 극복 방법

   • 앱을 개발하면서 어려웠던 점은 매주 작성한 블로그 글에 자세히 적혀 있습니다!!
   • 수업 내용과 함께 따라가면서 어려웠던 내용들과 그 내용들을 어떤 방식으로 풀어나갔는지 자세히 작성하였습니다. :-)

5. 5주간 앱개발 수업 후기 앱 개발은 정말 코딩 지식이 많은 사람들만 개발할 수 있고, 나는 하기 어려운 개발이라고 생각했었는데, 알려주시는 방법대로 해보니 (물론 내용이 쉬운 건 아니었지만 ㅎㅎ) 생각보다 쉽게 앱을 만들어 볼 수 있었고, 다양한 기능들과 expo, yarn, firebase 등을 배우고 다뤄볼 수 있어서 소중한 경험이 된 것 같습니다. 정말 상세하게 하나하나 다 알려주시고, 코드들도 다 알려주셔서 실습해보는데 정말 도움이 많이 되었던 것 같습니다. 상세하게 알려주셔서 따라가고 이해하기 정말 도움이 많이 되었던 것 같았던 수업이었습니다 :)

   (안드로이드 스튜디오를 처음에 설치하라고 하셔서 깔았는데,, 언제 사용하는 거죠..?)

앱과 서버: 데이터가 담겨있는 곳, 즉 서버와 앱과의 관계를 살펴본다. 서버리스: 서브를 직접 구축하지 않고 서버를 사용하는 방법을 알아본다. (필요한 기능들만 가져와서 사용할 수 있다.) 파이어베이스: 서버리스의 한 종류인 파이어베이스 사용방법을 익힌다.

앱과 서버의 동작 방식

API API의 응답 방식: JSON (키와 밸류)

데이터를 요청하는 시점? 앱 화면이 그려지면 가장 먼저 실행되는 함수? useEffect 그렇기에, 항상 useEffect 함수 안에서 API를 요청한다.

• 데이터를 서버에 저장할 때: 서버에 요청을 해야하는데, 데이터도 함께 서버에 보내야 한다.

외부 API를 도메인 형태로 요청하는 방식

외부 날씨 API를 가져와서 앱 화면에 출력해주기 날씨를 API를 사용하기 위해서는 현재 위치의 좌표가 필요하다.

• 현재 위치를 가지고 오는 방법 expo의 모듈을 가지고 와서 현재 위치의 좌표를 알 수 있다.

expo install expo-location
import * as Location from "expo-location";  // mainPage 상단에 작성하는 코드

> ```
const getLocation = async () => {
    //수많은 로직중에 에러가 발생하면
    //해당 에러를 포착하여 로직을 멈추고,에러를 해결하기 위한 catch 영역 로직이 실행
    try {
      //자바스크립트 함수의 실행순서를 고정하기 위해 쓰는 async,await
      await Location.requestPermissionsAsync();
      const locationData= await Location.getCurrentPositionAsync();
      console.log(locationData)
    } catch (error) {
      //혹시나 위치를 못가져올 경우를 대비해서, 안내를 준비합니다
      Alert.alert("위치를 찾을 수가 없습니다.", "앱을 껏다 켜볼까요?");
    }
  }

try-catch문을 사용하여 에러 발생 상황을 잡는다.

location 정보를 가져가도 되는지 허락을 구하는 명령어

await location.requestPermissionsAsync()

현재 위치를 받는 명령어 getCurrentPositionAsync

자바스크립트는 실행결과가 나오는대로 결과값을 먼저 던져주기 때문에 순서가 뒤죽박죽이 될 수 있다. 코드에 작성된 순서대로 함수가 실행되게 하려면, 함수 앞에 async 를 붙이고, 함수 내부에 await를 두어 순차적으로 함수가 실행되게 한다.

const func = async function(){
    await func01()
  await func02()
}

> ```
const func = async () => {
   await func01()
   await func02()
}

화살표 함수로도 async를 사용할 수 있다.

날씨API를 앱에 적용해보자!!

JSON 방식으로 response가 오기 때문에 key값을기준으로 원하는 value를 찾아나간다.

const temp = result.data.main.temp; 

result 밑에 있는 data라는 키 값 밑에 main 밑에 temp라는 밸류 값을 찾아 가서 temp라는 변수에 넣어 앱 화면에 출력 시킨다.

_API 응답 값에서 필요한 정보를 찾아 나가는 방법은 이미 해봐서 알고 있어서 이해하는데 쉬웠다!! 하지만,, 앱 화면에서 위치를 요구하는 permission이 뜨지 않아서 앱 자체에서 API가 불러와지지 않았다.. 왜 그런지 몰라서 google에 찾아보고 여러가지 방법을 시도해본 결과 "새로고침"이 정답이었다... ㅋㅋㅋㅋㅋㅋㅋ 이 방법을 알게 된 계기가 expo에서는 앱 화면을 웹(web)에서도 띄워 볼 수 있게 하는 서비스를 제공하는데, 핸드폰에서 작동하지 않으니 웹에서라도 확인해 봐야겠다 하고 웹으로 띄웠는데 API가 너무 작동이 잘되어서, 그럼 핸드폰에 문제가 있다!하고 생각하여 expo 앱을 새로고침 해보니 permission 창도 뜨고, 너무 잘 작동되는 것을 볼 수 있었다. 역시 등잔밑이 어둡다는 말이 정말이었다... 왜 새로고침해볼 생각을 안했을까.. _ ⠀ ⠀

날씨라는 상태를 또 만들어주어 데이터를 관리해준다!

const [weather, setWeather] = useState({
    temp : 0,
    condition : ''
  })

setweather(상태 변경함수)를 통하여 API로 받아온 날씨를 weather 상태에 넣어 상태변수를 변경한다.그래서 새로운 데이터가 들어오면 새로운 데이터로 상태가 변경되어 변경된 데이터로 화면을 다시 그려준다.

⠀

서버리스(serverless)

서버를 직접 만들 필요가 없다!! 서버를 직접 구성할 필요 없이 필요한 서버 기능만을 가져다 서비를 제공하는 서비스이다.

파이어베이스(firebase)

구글에서 만든 서버리스 서비스이다. 한 서비스를 만드는데 충분하고 많은 서버적 기능들을 제공해준다. (로그인, 이미지, 푸시 알람 등등) 데이터를 자율적으로 저장하고 구현할 수 있다!!

사용방법

1) 파이어베이스에 가입한다. 2) 파이어베이스 프로젝트 생성 3) 사용 할 파이어베이스 서비스 활성화

파이어베이스를 앱과 연결시켜주기 주소를 연결해주는 방법 파이어베이스에서 프로젝트를 웹앱으로 설정하면, firebaseConfig라는 딕셔너리를 제공해준다.

expo에서 firebase를 사용할 수 있는 모듈이 있다.

expo install firebase

를 입력하여 모듈을 설치해준다.

파이어베이스에서 만들어야 하는 것들을 순차적으로 프로젝트를 만든다.

• 버킷: 저장소

storage라는 곳에서 프로젝트를 하나 생성하면, 올리는 파일을 주소로 관리할 수 있게 된다. 폴더로도 관리할 수 있어서 폴더 생성 후 이미지를 업로드 하면, 이미지 고유의 주소가 생겨 어디에서든지 접근할 수 있게 되어 접근성이 높아지게 된다!

리얼타임 데이터베이스

파이어베이스 안에 있는 서비스로, JSON 형태로 데티터가 저장/관리되는 데이터베이스 서비스이다.

이 서비스를 사용할 때, 파이어베이스에서 제공하는 함수를 이용하기만 하면 데이터 저장, 수정, 삭제가 가능하다고 한다!!

useEffect에서 setTimeout 함수를 사용하는 것보다 사용자들마다 네트워크 상태가 다르기 때문에 무조건 몇초 뒤에 실행시키는 setTimeout 함수보다 파이어베이스 API의 실행 완료 시간에 맡겨두는 것이 더 좋다.

useEffect(()=>{
      //헤더의 타이틀 변경
        navigation.setOptions({
            title:'나만의 꿀팁'
        })
        firebase_db.ref('/tip').once('value').then((snapshot) => {
          console.log("파이어베이스에서 데이터 가져왔습니다!!")
          let tip = snapshot.val();
          setState(tip)
          setCateState(tip)
          getLocation()
          setReady(false)
        });

=> 즉, 원격으로 데이터를 요청하고 요청한 데이터를 앱 화면에 보여주는 것이다! ⠀

리얼타임 데이터베이스에서 특정 데이터 읽기

_여기서 꿀팁! 만들어 놓은 데이터들을 잘 관리하고 잘 불러오려면 각 데이터별로 고유의 index 번호가 존재하는 것이 좋다!(사실 거의 필수) _

인덱스 번호를 서버에 넘겨주는 이유는 실시간 데이터(RealTime Database)를 보여주기 위함이다. 실시간으로 변경되는 데이터를 보여주려면, 변경된 데이터를 서버로부터 바로 가져와야 하기 때문에 인덱스로 데이터를 가져오는 것이다.

firebase_db.ref('/tip').once('value').then((snapshot) => {})

firebase_db: firebase파일에서 압축해서 export시킨 변수이름, firebase API에 접속하는 마스터키 역할을 한다. firebase_db.ref(''): reference = ' ' 안에 들어간 데이터 조회 snapshot: 조회한 데이터가 담기는 곳, { } 내부에서 조회한 데이터를 사용할 수 있고, 필요한 데이터는 snapshot.val()로 가져와 변수에 담아서 사용할 수 있다. ( ex. let tip = snapshot.val(); )

리얼타임 데이터베이스에서 쓰기

파이어베이스로 데이터를 보내 저장하는 상황에서 쓰이는 명령어들! 어떤 구조로 데이터를 보내 저장해야 할지 알아보자

사용자가 원하는 정보를 저장하고 싶다면, 각각의 사용자의 정보도 따로 고유한 번호가 지정되어야 할 것이다. 사용자들을 관리하는 것도 expo에서 모듈로 제공한다.

expo install expo-constants

import Constants from 'expo-constants';
console.log(Constants.installationId)

installationId: 사용자 디바이스의 고유한 아이디를 의미한다.

firebase_db.ref('/like/'+user_id+'/'+ tip.idx).set(tip,function(error){
    console.log(error)
        Alert.alert("찜 완료!")
});

ref로 저장될 장소를 지정하고, set 함수를 이용한다. set 함수의 첫번째 인자는 상태 데이터를 보내준다.(현재 클릭된 tip) ++ 원래 firebase database에는 like 폴더가 없었는데, 위에 코드를 작성함으로써 폴더를 생성하고, tip까지 저장하게 되는 것이다. like 폴더 / 사용자 id / tip의 인덱스 라는 주소에 set 함수로 저장해준 tip이 저장되게 되는 것이다.

• 데이터 베이스에 파일을 저장하는 함수 => firebase 마스터키.ref(저장될 장소 주소).set(저장할 데이터,함수())

과제를 제출하였다! 4주차 강의를 듣고 일주일만에 과제를 하는 것이어서 내용을 좀 많이 까먹었었다. 그래서 복습도 하면서 과제를 하여 시간이 조금 오래 걸리게 되었지만, 내 힘으로 왠만한 부분들을 구현해 낼 수 있어서 다행이었다!! (많이 안까먹은 것 같다.. ㅋㅋㅋ) 꿀팁 찜 페이지를 만들고, 찜한 카드들을 가지고 와서 보여주고, 삭제까지 하는 기능을 구현했는데, 다른 부분들보다 삭제 후 로딩하는 기능이 가장 어려웠었다. 공식문서를 찾아서 삭제까지 가능했는데, 삭제를 하고는 다시 likePage로 돌아오는 것이 안되어서 이 문제를 가지고 한참을 씨름했던 것 같다.

결국,

 let tip = snapshot.val();
                let tip_list = Object.values(tip)
                setTip(tip_list)

이 방법으로 서버에서 넘어오는 데이터를 다시 다른 변수로 파싱하여 상태를 설정하니 잘 작동되었다.

추가적으로, 메인 화면에서 카드들을 클릭하면, 데이터가 없어서 오류가 날 수 있는 상황을 방지하기 위해 설정해 놓은 기본 카드 화면이 먼저 보이고, 방금 클릭한 카드가 그 위로 보이게 되어, 카드 화면이 2번 열리는 것처럼 보이는 상황이었다. 강의에서 강사님의 상황도 동일해 보였는데, 나는 이게 너무 거슬려서 어떻게하면 기본 데이터는 살려 놓지만, 다른 카드를 눌렀을 때 카드가 2번 뜨는 것처럼 보이지 않게 할 수 있을까 생각해 보았다.

생각을 좀 해본 결과로, 페이지가 뜰 때, 이미지가 링크로 연결되어 있어서 이미지를 불러오고 화면에 띄워주는 시간 때문에 default 카드가 확실하게 보이고, 다른 카드가 엎쳐지는 것처럼 보인다는 것을 알게 되었다. 이미지 때문인 것을 알게 되어, default 카드의 이미지 링크를 지워보았다. 지우니, 아주 빠른 속도로 로딩되었다가 사라지면서 어어어엄청 예민하지 않으면 변경되는 화면을 눈치채지 못할 정도가 되었다. 그래서 만족스럽게 과제를 마무리할 수 있었다!!

• 리액트 필수 지식 활용
• Expo 기능 사용
• 페이지 적용
• 앱다운 앱을 만들기 위해 사용할 리액트 네이티브와 Expo 기능들
• 앱에 페이지 기능 넣기

flex를 쓸 때, 자식 태그들의 고유한 영역을 지정해주고 싶을 때 사용한다.

flex를 쓰지 않을 때, 부모 태그가 영역이 지정되어 있을 때에는, justifyContent와 alignItems를 사용해 아이템들을 가운데 정렬 시킬 수 있다.

내 핸드폰은 안드로이드인데, 안드로이드에서는 상단바에 내용이 출력되는 문제가 있었다. 배경화면을 #000(검정색)으로 설정하면 상단바가 아예 보이지 않는 문제가 발생하여 상단바에 공간을 비워두고 앱 화면을 만드는 것을 어떻게 할 수 있을지 찾아보았다. 스파르타코딩클럽에서 하는 슬랙스에서 다른 어떤 분도 동일한 문제를 갖고 계셔서 쉽게 해답을 찾을 수 있었다.

expo에 SafeAreaContext 모듈을 설치하는 방법이었다.

expo install react-native-safe-area-context

터미널에 코드를 작성하고, 전체 코드를 로 감싸주면 상단바를 따로 분리하는 화면이 출력된다.

(상단바가 분리되지 않을 때)

(상단바가 분리되었을 때)

상단바가 분리되면서 화면 하단도 조금 더 많이 공간이 생기게 되었지만, 점차 해결해 나가기로 하였다.

나중에 할 수 있다면 앱 화면을 켰을 때 배경화면과 상단바가 색은 동일하지만, 상단바의 글씨 색은 다르게 하여 눈에 띌 수 있게 만들어 보고 싶다. ⠀ ⠀

리액트 기초지식

• 컴포넌트: 정해진 엘리먼트들을 사용하여 만든 화면의 일부분
• 상태: 컴포넌트에서 데이터를 유지하고 관리하기 위한 유일한 방법 == 그냥 사용할 데이터
• 속성: 상위 컴포넌트에서 하위 컴포넌트로 데이터를 전달하느 방식 == 그냥 데이터 전달
• useEffect: 화면에 컴포넌트가 그려지면 처음 실행해야 하는 함수들을 모아두는 곳

1) 컴포넌트는 앱 화면에 나타나는 모든 UI들을 쪼개서 운영하는 기법이기 때문에 유지보수가 편리하다는 장점이 있다. 즉, 화면의 모든 부분을 뜻한다. (직접 태그를 만들 수 있다.)

2) 속성(Props) 속성은 컴포넌트에 데이터를전달한다는 것이다. JSON처럼 key와 value의 형태이다.

비구조 할당 방식: props의 구조

props:{
      content: {
      },
      key: {
      }
  }

비구조 방식으로 넘어오는 데이터들을 
  export default function Card({content}) {} 처럼 content에서 쉽게 꺼내 쓸 수 있게 해준다.

3) 상태
  컴포넌트 안에서 데이터를 관리하는 방법인 상태:
  **상태(State,useState)**
  데이터에 따라서 화면이 바뀔려면 항상 상태(state)로 데이터가 관리되어야 한다. 즉, 상태로 관리하던 데이터가 변경이 되면, 화면이 바뀐다.

  ex) 주식 앱 - 상태로 관리하던 데이터가 바뀌면, 화면을 다시 그려준다.

UI = User Interface
UI = component(state)

  useEffect(() => {
      화면이 그려진 다음 가장 먼저 실행되어야 할 코드 작성 공간
  }, {})


**useState 사용법**
[state,setState] 에서 state는 이 컴포넌트에서 관리될 상태 데이터를 담고 있는 변수
setState는 state를 변경시킬때 사용해야하는 함수
useState()안에 전달되는 값은 state 초기값
> ```
const [state,setState] = useState([])

UseState가 컴포넌트 안에서 상태관리를 할 수 있게 변수(state)와 상태를 변경시킬 수 있는 함수(setState)를 준다. 이 변수와 함수를 통해 컴포넌트 안의 데이터들을 관리하는데, useEffect 함수 안에서 하게 된다.

useEffect(()=>{
    setState(data)
},[])

useEffect를 사용하는 것은 - return 문이 실행되어 화면이 그려진다음 실행되는 함수이다. 
그런데, 화면이 다 그려지기도 전에 (return이 실행되기도 전에) 상태(state)에 있는 데이터를 가져오려 하면, state 변수에는 아무 데이터도 존재하지 않기 때문에 오류가 발생한다. 
=> 이 해결책으로 로딩화면을 보여주면서 페이지의 데이터들이 로드될 때까지 기다려주고, useEffect 함수를 실행시킨다면, 오류가 해결될 수 있을 것이다.

> ```
 const [state,setState] = useState([])
 useEffect(()=>{
    setState(data)
  },[])
let tip = state.tip;
    let todayWeather = 10 + 17;
  let todayCondition = "흐림"
  return ( .... )

상태로 컴포넌트를 관리하지만, 상태의 데이터가 없어서 오류가 나는 것은 앱 개발 상에서 빈번하니, 개발 중 오류가 발생하면, 상태에 데이터가 없어서 발생하는 오류인지 체크하면 좋을 듯 하다!!

상태를 컴포넌트 안에 무수히 많을 수 있다! 관리할 상태이름과 함수는 자유롭게 정할 수 있고, 초기 상태값으로 리스트, 참거짓형, 딕셔너리, 숫자, 문자 등등 다양하게 들어갈 수 있다.

  const [ready,setReady] = useState(true)

  지연함수 : setTimeout() 주어진 시간후 함수 안에 있는 코드를 실행하라는 의미

>```
 setTimeout(()=>{
        setState(data)
        setReady(false)
    },1000)

return ready ? < Loading /> : (...) ready의 상태에 따라서 ready 중이면(true) < Loading />를 출력하고, ready가 false면 ( mainPage ) 안에 있는 데이터를 출력시킨다. (삼항연산자)

카테고리라는 함수를 만들어서 카테고리별로 팁들을 볼 수 있게 한다.

const category = (cate) => {
        if(cate == "전체보기"){
            //전체보기면 원래 꿀팁 데이터를 담고 있는 상태값으로 다시 초기화
            setCateState(state)
        }else{
            setCateState(state.filter((d)=>{
                return d.category == cate
            }))
        }
    }

  cate라는 변수가 category 함수에 넘어가게 된다. 
state 안에는 전체 꿀팁이 들어가 있다. 그래서 '전체보기'라는 단어가 cate에 들어오면 setCateState로 모든 tip들을 다시 불러와 뿌려주게 되고, 다른 것들(else)가 들어오면, fliter를 통해 걸러진 카테고리가 들어오면 그것을 뿌려주게 된다. fliter에는 조건문이 들어간다. (return 옆에 있는 코드)
들어온 카테고리(cate)가 state에 들어온 얘들 중에서 동일한 얘들을 골라 새롭게 리스트를 만들어서, setCateState 함수에다 넘겨주게 된다.

==> 그래서 매번 들어오는 데이터에 따라서 처리하는 코드가 달라지기 때문에 달라지는 데이터 따라 화면이 달라지게 된다.

전체 팁들을 불러오는 상태 하나, 카테고리별로 내용을 다룰 수 있는 상태 하나, 준비된 상태인지 확인하는 상태 하나로 구분한다.


(앞에서 혼자 상태바에 대해서 공부하며 찾아보았는데, 수업에서도 다루다니...)

  ⠀
## 앱 상태 바(State Bar) 관리하기
 cmd 창에 
> ```
import { StatusBar } from 'expo-status-bar';

Status Bar 관련 모듈 설치해주고,

import { StatusBar } from 'expo-status-bar';

  이 코드와 
  상위 코드 바로 아래에 

### 스택 네비게이션 ⠀⠀⠀⠀
앱은 페이지가 쌓이는 구조이다. 그렇기 때문에 stack이라 불린다. 
  - Stack.Screen: 페이지
  - Stack.Navigator: 책갈피

스택 네비게이터를 설치하는 코드
> ```
yarn add @react-navigation/stack

  <Stack.Navigator>로 감싸는 태그가 있어야 한다.

스크린 옵션: 컴포넌트들을 페이지처럼 여기게 해주는 기능을 하는 네비게이터 태그를 선언하고, 태그 내부에 페이지 화면을 스타일링 할 수 있는 다양한 옵션들이 있다.

> ```
<Stack.Navigator
            screenOptions={{
                headerStyle: {
                    backgroundColor: "black",
                    borderBottomColor: "black",
                    shadowColor: "black",
                    height:100
                },
                headerTintColor: "#FFFFFF",
                headerBackTitleVisible: false
            }}  >

컴포넌트를 페이지화 하고, 페이지를 이동할 수있는 네비게이션(새 페이지)도 준비가 되었다면 최상단 컴포넌트인 App.js에 네비게이션 기능을 달아야 한다. 
  ==> 그래야 앱 어디서든 원하는 페이지로 이동이 가능하기 때문이다.

<Stack.screen>에 있는 속성 중에 name은 페이지 상단에 뜨는 이름을 뜻한다.
  ![](https://images.velog.io/images/likeablue_bee/post/11620921-a821-4205-b8a2-6fb3b84b702e/image.png)

![](https://images.velog.io/images/likeablue_bee/post/55b1fcc3-75d6-4483-8c82-cc87181a39fc/image.png)

- navigatin.etOptions: 페이지의 제목을 변경하거나, 특정 페이지의 헤더의 스타일을 바꾸는 도구
- navigation.navigate(" "): 페이지 이동 시키는 도구
- navigation.navigate(" ", { }) : 데이터를 함께 건내주는 도구
- route:전달받은 데이터를 받는 route 딕셔너리이다. 비구조 할당 방식으로 route에 params 객체 키로 연결되어 전달되는 데이터를 꺼내 사용할 수 있다. 

⠀
⠀

Card.js에 각 카드의 영역을 TouchableOpacity로 부여하고, onPress(눌렸을 때)될 때, navigation으로 DetailPage로 넘어갈 수 있게 한다.
***데이터 없이 페이지 이동하기 --> 페이지 이동시 다 똑같은 DetailPage로 이동한다...
> ```
<TouchableOpacity style={styles.card} onPress={()=>{navigation.navigate('DetailPage')}}>

onPress={()=>share()}     

  ![](https://images.velog.io/images/likeablue_bee/post/0f06ceeb-099c-4b74-94dc-e72ed23ef3aa/image.png)

  ⠀
### 외부 링크 클릭 이벤트
외부 링크로 넘어가게 하려면 모듈을 추가해야 한다.

> ```
expo install expo-linking

node와 npm 자바스크립트에서 사용하는 도구를 사용하기 위한 도구를 가져오는 역할을 한다. (도구를 가져오기 위해 도구를 사용한다!)

Yarn npm 도구로 사용하는 도구이다. 더 효율적인 속도를 내기 위해 설치하는 도구이다. ↓ cmd 창에서 이 코드를 입력해 yarn을 설치한다.

npm install -g yarn

Expo cmd에 expo 공구함을 설치하여 어디서든 expo를 사용할 수 있게 설치해준다.

npm install -g expo-cli

expo를 설치하여 우리는 프로젝트 생성 프로젝트 실행 프로젝트 빌드 등의 여러 기능들을 사용 할 수 있다.

expo를 사용하기 위해서 Expo 서비스에 회원가입을 해야 한다.

회원가입을 하고, 개인 컴퓨터 cmd에서 expo login --username "____" 을 치면

expo 서비스와 내 컴퓨터가 연결된다.

expo를 설치하는 방법들

asset 폴더 앱에서 사용되는 사진을 넣는 폴더

node_modules 폴더 앱을 개발할 때 사용할 도구들이 있는 폴더

app.json 앱을 설명해주는 설명서라고 할 수 있다.

expo가 큐알코드를 보여줘서 핸드폰으로 코드를 찍으면 expo 클라이언트 앱이 깔려 있다면 바로 앱화면을 스마트폰에서 볼 수 있다.

앱을 실행시키고 싶다면? 터미널 창에서

expo start

코드를 쳐야 한다.

※ 이때 주의할 점, windows에서는 프롬프트 창이 꼭 cmd 창으로 되어 있어야 오류가 생기지 않으니

이곳을 cmd로 변환하여 expo start 명령을 입력해야 한다.

JSX 문법 앱 화면을 그릴 때 JSX 문법을 사용하는데, < > 안에 코드가 들어 있다.

<View style={styles.container}>
      <Text>Open up App.js to start working on your app!</Text>
      <StatusBar style="auto" />
</View>

태그로 화면을 그린다.

App() 이라는 함수가 앱의 화면을 return(반환)하는데, 이것을 랜더링(rendering)한다고 표현한다.
앞으로 사용할 태그(앨리먼트)들은 'react-native'에서 가져온다고 생각해야 한다.
App.js에서 보면, 
> ```
import { StyleSheet, Text, View } from 'react-native';

라는 코드를 볼 수 있다. 리엑트 네이티브에서 가져온다고 명시해야 한다. (라이브러리)

*여는 태그, 닫는 태그 주의!! * 꼭 한 쌍으로 사용한다.

모든 태그들은 모든 태그를 감싸는 최상위 태그가 존재해야 한다. 또한, 모든 태그를 감싸고 있는 최상위 태그를 감싸는 () 소괄호가 있어야 한다. ( < > </> )

주석 다는 방법 JSX 밖에서 주석을 달기 위해서는

//주석 내용

// -> /를 두번 사용하여 주석을 처리한다.

하지만, JSX 안 < > 태그 안에서는

{/* 주석 내용 */}

좀 더 복잡한 모습으로 주석을 작성해야 한다.

* 여기서 Tip! 주석을 그냥 작성하고, 드래그하여 ctrl + /를 누르면 자동으로 주석을 만들어 준다!! 귀찮게 {/ */} 작성하지 말고, ctrl + / 사용하자!

View 태그

<view> </view>

화면에 영역을 잡아주는 태그이다.

view 태그는 StyleSheet를 사용하여 스타일을 지정할 수 있다.

text 태그

문자를 쓰기 위해서는 꼭!! 태그 안에 작성해야 한다. 태그 안에 쓰면 에러 발생!

ScrollView 태그

화면보다 넘치는 정보를 담고 있는 경우, 스크롤 해서 정보들이 보일 수 있게 해주는 태그이다.

이 태그를 사용하려면 무엇이 먼저 되어야 할까? 바로 reat-native에서 꺼내서 써야 한다.!!

import { StyleSheet, Text, View, ScrollView } from 'react-native';

#### button 태그

![](https://images.velog.io/images/likeablue_bee/post/f19cb447-1056-4a42-9998-c18ea1a10fee/Screenshot_20210620-011128_Expo%20Go.jpg)

> ```
<Button 
          style={styles.buttonStyle} 
          title="버튼입니다 "
          color="#f194ff" 
          onPress={function(){
            Alert.alert('팝업 알람입니다!!')
          }}
/>

버튼 태그는 스스로 닫는 태그이다. title이라는 속성은 버튼의 내용을 담는 것이고, color는 버튼의 색 onPress는 버튼이 눌러졌을 때 어떤 기능이 실행될지 구현해주는 것이다. 함수에 연결하여 사용한다.

Alert

import { StyleSheet, Text, View, Button, Alert } from 'react-native';
Alert.alert('팝업 알람입니다!!')

  리액트 네이티브에서 Alert 기능을 가져와 페이지에 추가한 다음, 연결 연산자(.)로 연결하여 Alert 명령어를 사용한다.
  예제에서는 버튼을 누르면 alert이 뜨도록 해놨다.

  Alert 기능을 외부에 함수로 만들어서 작성할 수 있다.
> ```
const customAlert = () => {
    Alert.alert("JSX 밖에서 함수 구현 가능!")
}
<Button 
          style={styles.buttonStyle} 
          title="버튼입니다 "
          color="#f194ff" 
          onPress={customAlert}
/>  

onPress={customAlert}처럼 바로 함수 이름을 작성하여 실행시킬 수 있고,

<Button 
            style={styles.buttonStyle} 
            title="버튼입니다 "
            color="#FF0000" 
            onPress={() => {customAlert()}}
/>

  화살표 함수를 사용하여 함수 이름 옆에 ()를 붙여 사용할 수도 있다.

####   <TouchableOpacity />

  영역을 생성하는 명령어이다. 역역을 누를 수 있는 기능이고, TouchableOpacity로 감싸 onPress 함수로 연결하면 버튼 역할을 할 수 있게 된다.
>   ```
<TouchableOpacity style={styles.textContainer} onPress={customAlert}>
        <Text style={styles.textStyle}>영역을 충분히 갖는 텍스트 입니다!</Text>
</TouchableOpacity>

Image

assets 폴더에 있는 이미지를 가져와 사용하는 (import)와 외부 이미지 링크를 넣어서 사용하는 방식 (uri) 2가지가 있다.

import favicon from "./assets/favicon.png"
  <Image 
        source={favicon}
                // 사용설명서에 나와 있는 resizeMode 속성 값을 그대로 넣어 적용합니다
        resizeMode={"repeat"}
        style={styles.imageStyle}
/>

  ![](https://images.velog.io/images/likeablue_bee/post/bcc2c69c-f1d2-4ecb-b235-a3d1606c1237/Screenshot_20210620-012922_Expo%20Go.jpg)
  resizeMode에는 다양한 방법으로 이미지를 변화시킬 수 있는 속성이다. 

> ```
resizeMode={"cover"}

resizeMode에 cover를 넣으면

이렇게 화면을 꽉 채우는 모습으로 이미지가 보여진다.

외부 이미지를 사용하려면 uri 를 사용한다.

source={{uri:'https://images.unsplash.com/photo-1424819827928-55f0c8497861?fit=crop&w=600&h=600%27'}}
        resizeMode={"cover"}
        style={styles.imageStyle}

  외부 무료 이미지 링크를 source 속성에 입력하여 앱 이미지로 사용할 수 있다.



###   이제는 앱 화면 꾸미기!!

####   Styles
>   ```
const styles = StyleSheet.create();

뼈대에 옷을 입혀주는 스타일 코드 함수다! 함수라는 것을 기억하여 ( ) 빼먹지 않을 수 있도록 해야함

<View style={styles.container}>

 ↑ 이 코드를 보면 view 태그에 style={styles.conatiner}라는 카거 연결된 것을 볼 수 있다.
  영역에 옷을 입혀주는 것이라 생각하면 된다!!

>   ```
<View style={styles.container}>
  container: {
    //영역을 잡는 속성입니다. 따로 자세히 다룹니다.
    //flex: 1은 전체 화면을 가져간다는 뜻입니다
    flex: 1,
    //영역의 배경 색을 결정합니다
    backgroundColor: '#fff',
    //아래 두 속성은 영역 안의 컨텐츠들의 배치를 결정합니다. 
    //flex를 자세히 다룰때 같이 자세히 다룹니다
    justifyContent:"center",
    alignContent:"center"
  }

앱 화면의 스타일을 구성할 때 보여지는 곳을 꾸밀 때 사용하는 속성 margin: 컨텐츠 밖에서의 여백 padding: 컨텐츠 안에서의 여백 borderRadius: 테두리의 가장자리 borderWidth: 테두리의 두께 borderColor: 테두리의 색깔 borderStyle: 테두리의 속성 (ex. dotted: 점선) color: 글자 색 설정 fontSize: 글자 크기 결정 fontWeight: 글자 두께 (100 단위로 커짐) textAlign: 글자의 위치를 결정

컨텐츠의 위치: Flex

flex: 1 ==> 전체 화면을 다 가져간다.

export default function App() {
  return (
    <View style={styles.container}>
      <View style={styles.containerOne}>
      </View>
      <View style={styles.containerTwo}>
      </View>
    </View>
  );
}
const styles = StyleSheet.create({
  container: {
    flex:1
  },
  containerOne: {
    flex:1,
    backgroundColor:"red"
  },
  containerTwo:{
    flex:2,
    backgroundColor:"yellow"
  }
});

  ![](https://images.velog.io/images/likeablue_bee/post/399efb00-8d4d-4121-9e0d-374ae812e614/Screenshot_20210620-021732_Expo%20Go.jpg)

  안에 2개의 컨테이너들이 한 화면을 나눠 갖게 되는데, 그 때 containerOne은 1을 가지고, containerTwo는 2를 가지게 된다.
  1+2 = 3 이니 화면을 3등분 하여 1/3은 빨강이, 2/3은 노랑이 차지하게 된다.


>   ```
import React from 'react';
import { StyleSheet, Text, View } from 'react-native';
export default function App() {
  return (
    <View style={styles.container}>
      <View style={styles.containerOne}>
      </View>
      <View style={styles.containerTwo}>
        <View style={styles.innerOne}>
        </View>
        <View style={styles.innerTwo}>
        </View>
      </View>
    </View>
  );
}
const styles = StyleSheet.create({
  container: {
    flex:1
  },
  containerOne: {
    flex:1,
    backgroundColor:"red"
  },
  containerTwo:{
    flex:2,
    backgroundColor:"yellow"
  },
  innerOne: {
    flex:1,
    backgroundColor:"blue"
  },
  innerTwo: {
    flex:4,
    backgroundColor:"orange"
  }
});

blue는 1/5 orange는 4/5 영역을 전체 화면의 2/3를 차지하는 containerTwo 에서 나눠 갖게 된다.

즉, flex는 상대적이다. 안에 있는 영역이 바깥의 영역의 비율로 따져서 몇분의 몇을 가져가는지를 flex로 정하게 된다. flex는 위치한 곳의 영역을 같은 레벨의 flex 합 비율대로 가져가게 된다!!

flexDirection

import React from 'react';
import { StyleSheet, Text, View } from 'react-native';
export default function App() {
  return (
    <View style={styles.container}>
      <View style={styles.containerOne}>
      </View>
      <View style={styles.containerTwo}>
        <View style={styles.innerOne}>
        </View>
        <View style={styles.innerTwo}>
        </View>
      </View>
    </View>
  );
}
const styles = StyleSheet.create({
  container: {
    flex:1
  },
  containerOne: {
    flex:1,
    backgroundColor:"red"
  },
  containerTwo:{
    flex:2,
    flexDirection:"row",
    backgroundColor:"yellow"
  },
  innerOne: {
    flex:1,
    backgroundColor:"blue"
  },
  innerTwo: {
    flex:4,
    backgroundColor:"orange"
  }
});

  ![](https://images.velog.io/images/likeablue_bee/post/9f4193f7-59b7-41e5-b98d-172635b0dd31/Screenshot_20210620-022657_Expo%20Go.jpg)

  flexDirection:"row"의 의미는 좌우를 의미한다.
  flexDirection:"column"은 상하를 의미한다.
  flexDirection의 default 값은 기본 cloumn이다. 그래서 flexDirectiond을 따로 지정하지 않으면 화면이 정렬된다.
>   ```
innerOne: {
    flex:2,
    backgroundColor:"blue"
  },
  innerTwo: {
    flex:2,
    backgroundColor:"orange"
  }

inner의 비율을 2:2로 바꾸었을 때,

justifyContent

justifyContent는 flexDirection과 동일한 방향으로 정렬하는 속성이다.

const styles = StyleSheet.create({
  container: {
    flex:1
  },
  containerOne: {
    flex:1,
    backgroundColor:"red"
  },
  containerTwo:{
    flex:2,
    flexDirection:"row",
    backgroundColor:"yellow"
  },
  innerOne: {
    flex:1,
    backgroundColor:"blue"
  },
  innerTwo: {
    flex:4,
    justifyContent:"flex-start",
    backgroundColor:"orange"
  }
});

  justifyContent가 flext-start로 지정되면, orange 영역의 가장 왼쪽 위로 가서 text가 붙게 된다.
  ![](https://images.velog.io/images/likeablue_bee/post/60ae28a8-4671-407e-b6c3-21800ba3514f/image.png)

  justifyContent가 flext-end 로 지정되면,
  ![](https://images.velog.io/images/likeablue_bee/post/d0d9210d-8bf0-4880-b459-e5a485b60c3c/image.png)
  이렇게 왼쪽 아래로 지정된다.
  현재 코드에서는 flexDirection이 default 값인 column으로 지정되어 있어서 content가 상하로 움직이는데, 만약 flexDirection이 row로 지정되면, 
>   ```
innerTwo: {
    flex:4,
    flexDirection:"row",
    justifyContent:"flex-start",
    backgroundColor:"orange"
  }

justifyContent:"flex-start"는 왼쪽 위에 붙는 것이 동일하지만, justifyContent:"flex-end"는 오른쪽을 붙는 것을 알 수 있다. left, right 대신에 flex-start, flex-end가 있다고 생각하면 된다!

justifyContent:"center"도 가능하다.

alignItems

flexDirection과 반대 방향이라고 생각하면 된다.

innerTwo: {
    flex:4,
    flexDirection:"row",
    alignItems:"center",
    backgroundColor:"orange"
  }

  현재 flexDirection이 row 이고, alignItems가 center 이다. row라는 것은 좌우 정렬이기 때문에, 원래 같아서 center를 잡으면 orange 영역의 위쪽의 가운데에 text가 위치해야 한다.
  하지만, alignItems는 flexDirection과 반대 방향으로 content를 두기 때문에 cloumn으로 설정한 것 처럼 상하를 기준으로 text를 배칫한다.
  ![](https://images.velog.io/images/likeablue_bee/post/a9ef7d81-226e-444e-9f89-be9da813b390/image.png)



##   리액트 네이티브의 기본 구조
  이 코드가 가장 리액트 네이티브의 가장 기초가 되기 때문에 잘 알고 있을 것!
>   ```
import React from 'react';
import main from './assets/main.png'; 
import { StyleSheet, Text, View, Image, TouchableOpacity, ScrollView } from 'react-native';
  export default function App() {
      console.disableYellowBox = true;
      //return 구문 밖에서는 슬래시 두개 방식으로 주석
      return ()
}
const styles = StyleSheet.create({}

앱 만들기

앱 만들기에 대해선 과정을 상세하게 작성하려 하면 너무 복잡해질 것 같아 코드를 짜면서 다시 공부해보야야 할 것들에 대해서만 기록해보려 한다.

alignSelf: 전체를 flex로 잡지 않아도 content 스스로 위치를 잡을 수 있게 해줌 width:"90%" : 문자열로 content의 %를 잡을 수 있다.

ScrollView를 수평으로 스크롤 하기 위해서는

<ScrollView horizontal={true}>

  코드를 넣어 좌우로 (수평으로) 스크롤 할 수 있다.
  ![](https://images.velog.io/images/likeablue_bee/post/1a12b8b8-1ac1-476e-a852-459ac3c4a523/image.png)

  이미지는 고유한 영역을 지정해 주어야지만, 화면에 출력된다.
  width나 height, flex 같은 속성들로 위치를 지정해 주어야 한다.

####   ※ 코드 작성 중 에러에서 발견한 react-native 팁!!

  상위 태그를 < Text >로 작성한 경우
>   ```
<Text style={styles.cardText}>
            <Text style={styles.cardTitle}>먹다 남은 피자를 촉촉하게!</Text>
            <Text style={styles.cardDesc} numberOfLines={3}>먹다 남은 피자는 수분이 날라가기 때문에 처음처럼 맛있게 먹을 수 없는데요. 이럴 경우 그릇에 물을 받아 전자레인지 안에서 1분 30초에서 2분 정도 함께 돌려주면 촉촉하게 먹을 수 있습니다. 물이 전자레인지 안에서 수증기를 일으키고, 피자에 촉촉함을 더해줍니다.</Text>
            <Text style={styles.cardDate}>2020.09.09</Text>
</Text>

앱 화면에서 줄바꿈이나 numberOfLines가 실행되지 않는 다는 것을 볼 수 있다.

하지만,

상위 태그를 < View >로 변경하면,

 <View style={styles.cardText}>
            <Text style={styles.cardTitle}>먹다 남은 피자를 촉촉하게!</Text>
            <Text style={styles.cardDesc} numberOfLines={3}>먹다 남은 피자는 수분이 날라가기 때문에 처음처럼 맛있게 먹을 수 없는데요. 이럴 경우 그릇에 물을 받아 전자레인지 안에서 1분 30초에서 2분 정도 함께 돌려주면 촉촉하게 먹을 수 있습니다. 물이 전자레인지 안에서 수증기를 일으키고, 피자에 촉촉함을 더해줍니다.</Text>
            <Text style={styles.cardDate}>2020.09.09</Text>
</View>

![](https://images.velog.io/images/likeablue_bee/post/9ce55ae8-fad4-48c2-bc5c-ab1d0ddc25d7/image.png)

  줄바꿈과 numberOfLines가 잘 동작되는 것을 볼 수 있다!!
  즉, 상위 태그가 어떤 것인가에 따라서 보여지는 화면이 다르기 때문에 주의해서 작성해야 한다!

  expo를 정상적으로 멈추는 방법: **Ctrl + C **를 누르기 (까먹었음..)


  모듈 시스템으로 map 함수를 이용해 data.json 을 불러온다. 

  JSX 문법 안에서 자바스크립트 변수를 쓰려면 **{ }** 로 감싸야 한다. 
>   ```
<Text style={styles.weather}>오늘의 날씨: {todayWeather + '°C ' + todayCondition} </Text>

또한, 문법을 사용할 때도, 중괄호 { }를 사용한다.

반복문을 돌릴 때는 가상 상위의 태그에는 반문으로 사용될 키(key)값이 주어지고 각 content가 유니크(index) 해야 한다.

** 다시 복습하는 map 함수 map 함수는 리스트의 길이를 몰라도 된다.

map ((value, i) => {
}

  value는 리스트의 내용을 의미하고, i는 리스트의 index 번호를 의미한다.

####   삼항 연산자
>   ```
let result = 10 > 2 ? "참" : "거짓"
let result = 조건 ? 참일 때 : 거짓 일때

앱 만들기 예제에서는 홀수 카드에서 배경에 색을 넣는 방법으로 삼항 연산자를 사용했다.

tip.map((content,i)=>{
            return i % 2 == 0 ? (<View style={styles.cardEven} key={i}>
              <Image style={styles.cardImage} source={{uri:content.image}}/>
              <View style={styles.cardText}>
                <Text style={styles.cardTitle} numberOfLines={1}>{content.title}</Text>
                <Text style={styles.cardDesc} numberOfLines={3}>{content.desc}</Text>
                <Text style={styles.cardDate}>{content.date}</Text>
              </View>
            </View>) : (<View style={styles.cardOdd} key={i}>
                <Image style={styles.cardImage} source={{uri:content.image}}/>
                <View style={styles.cardText}>
                  <Text style={styles.cardTitle} numberOfLines={1}>{content.title}</Text>
                  <Text style={styles.cardDesc} numberOfLines={3}>{content.desc}</Text>
                  <Text style={styles.cardDate}>{content.date}</Text>
                </View>
              </View>)
})

  간략하게 작성하면 , 
      tip.map((content, i) => {
        return i % 2 == ? ( ) : ( )
      })
  으로 쓸 수 있다.


  파일 이름과 함수의 이름은 같아야 한다.![](https://images.velog.io/images/likeablue_bee/post/238df0c1-78c4-4e3a-8877-84a678071357/image.png)![](https://images.velog.io/images/likeablue_bee/post/1364f7b9-02eb-4c12-97d3-e238a6a1b9e6/image.png)


  상하좌우 가운데 (=정가운데)로 맞추는 방법

> ```
justifyContent:"center",
alignItems:"center",

content의 기본 flex 방향은 column으로 상하 기준으로 되어 있기 때문에, justifyContent:"center"하면 상하의 중심을 뜻하고, alignItems:"center"면 상하의 반대인 좌우 정렬이 되어 정가운데에 아이템이 놓이게 된다.

2주차 숙제

새로운 앱화면 만들기!

해설영상을 보지 않고 최대한 만들려고 하였고, 가운데 정렬하는 부분이 정말 까다로워서 정렬부분만 해설 영상을 참고했다! 그래도 내힘으로 앱화면을 만들어 보니 나도 내가 만들어보고 싶은 앱 화면을 만들 수 있겠다는 자신감이 들어서 좋다!!

화면을 만들면서 들었던 생각이 CSS로 웹 화면 꾸미는 것과 비슷하다는 느낌을 정말 많이 받았다. 기말고사로 웹 페이지를 꾸면서 하나의 서비스를 제공하는 기말과제가 있었는데, 그 과제를 하며 CSS를 정말 열심히 공부했었다. 그런데 다행이 앱 화면도 CSS와 느낌이 비슷하게 가서 미리 감각을 세워나 맨땅에 헤딩하는 것보다는 자신감을 가지고 숙제를 할 수 있어서 좋았다!

다음 주차에서 어떤 새로운 기능들을 배울지 기대가 된다.

수업을 들으며 연습했던 코딩들을 정리해본다!

비주얼 스튜디오 코드를 사용하지 않고 크롬에서 F12 키를 누르면 콘솔 창이 튀어 나온다. 그 곳에서 코드를 작성하면 자바스크립트를 이용할 수 있다!! 여러 라인을 사용하려면 Shift + Enter를 사용하면 한 번에 여러 라인으로 코드들을 작성할 수 있다.

이제부터 코드 시작!!

문자열을 대문자로 바꾸는 방법!

문자열 나누기!

함수 만들기!

function funcName() {
    console.log("함수")
}
funcName()

조건문

반복문 예시

1~100 까지 더하기 연습!

function get_sum(n) {
    let sum = 0
    for (let i = 0; i < n; i++) {
        sum += i;        
    }
    return sum
}

let result = get_sum(10); 
console.log(result) 

반복문과 조건문을 사용하여 원하는 문자열 찾기!

let fruit_list = ['사과','감','감','배','포도','포도','딸기','포도','감','수박','딸기']

let count = 0;
for(let i=0; i<fruit_list.length;i++){    
    let fruit = fruit_list[i];
    if(fruit == "딸기"){
        count +=1;    
    }
> }
console.log(count)

JSON 데이터 분석하기 (리스트와 딕셔너리 복합 구조 예제)

화살표 함수(arrow funtion)

let a = () => {

}

() => 문자가 function과 같은 의미!!

<새로 배운 것>

비구조 할당 방식!

let blogFunction = ({owner,url,getPost}) => {
    console.log(owner)
    console.log(url)
    console.log(getPost())
}
blogFunction(blog)

비구조 할당 방식으로 변수들을 넘긴다면 함수 안에서 각 변수들을 따로 선언해주지 않아도 되기 때문에 훨씬 코드가 짧아진다.

문자열을 상용할 때 자유롭게 줄바꿈을 할 수 있는 방법! `(백틱)을 사용한다.

let name = "yerim"
let str = `나는 ${name} 입니다.`
console.log(str)

=> 문자열 안에 변수가 들어야야 할 때 가독성 좋게 만들 수 있다!

딕셔너리 구조를 짧게 작성할 수도 있다.

변수와 키 값이 동일하다면, 딕셔너리를 짧게 선언할 수 있게 된다.

반복문을 줄여서 사용할 수 있다아! map() 함수 사용하기

map((value,index) => { })

map이라는 도구가 리스트의 . (연결 연산자)로 붙어 있으면, 함수에 리스트의 값(value)과 순서(index)를 던져주게 된다.

2주차 예습 module system export, import

export는 외부에서 함수를 사용할 수 있게 꺼낼 수 있게 하는 키워드이고, import는 외부에서 사용할 수 있는 함수를 가지고 와서 파일에 적용시키는 키워드이다.

작성 방법

export function times(x) {
  return x * x;
}
export function plusTwo(number) {
  return number + 2;
}
import { times, plusTwo } from './util.js';
console.log(times(2));
console.log(plusTwo(3));

길게 작성할 수도 있고, 짧게 특정 파일에 있는 export된 함수를 가져올 수도 있다.

export default function times(x) {
  return x * x;
}
import k from './util.js';
console.log(k(4));

시험기간인데 머리 식힐 겸 수업을 들었다가 생각보다 많은 수업 내용에 당황하였다. 그래도 javascript 언어는 익숙한 언어여서 크게 부담감으로 느껴지지는 않았다.
그럼에도 새로 배우는 함수들과 도구들이 있어서 시험이 끝나고 따로 공부해야 할 것 같다. 

생각보다 수업이 딱딱하지 않고 너무 재미있어서 즐겁게 수업을 들을 수 있었던 것 같다!!


**이번 주 숙제!**
> 1. map 함수를 사용하여 list에서 딸기가 몇개 있는지 알아보기

let fruit_list = ['사과','감','감','배','포도','포도','딸기', '포도','감','수박','딸기'] let count = 0; fruit_list.map((value,i) => { if(value == "딸기") { count += 1; } }) console.log(count);

> 2. 이메일 검사 함수 만들기
2-1. indexOf()로 풀기

function checkEmail(email){ if(email.indexOf('@')<0){ console.log("이메일이 아닙니다.") }else{ console.log("이메일이 맞습니다.") } } checkEmail("yerim2021@gamil.com"); checkEmail("yerim2021%gamil.com");

2-2. 정규 표현식으로 풀기

function checkEmail(email){
    var emailRule = /^[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*.[a-zA-Z]{2,3}$/i;
    if(!emailRule.test(email)){
        console.log("이메일이 아닙니다.")
    }else{
        console.log("이메일이 맞습니다.")
    }
}
checkEmail("yerim2021@gamil.com");
checkEmail("yerim2021%gamil.com");

2-3. .com이 없는 경우 판별

function email_check( email ) {    
    var regex=/([\w-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([\w-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)$/;
    return (email != '' && email != 'undefined' && regex.test(email));
}
console.log(email_check('yerim2021@gmail'));        //false
console.log(email_check('yerim2021@gmail.com'));    //true
console.log(email_check('yerim2021$$gmail.com'));    //false