https://www.acmicpc.net/problem/1515

문제 설명

N까지 숫자를 세웠을 때 입력값에 있는 모든 숫자가 존재해야한다. 두개의 예제를 확인해 보면 이해하기가 쉽다! 예제처럼 숫자를 하나의 문자열처럼 나열하여 1,2,3,4를 모두 가질 수 있는 최솟값은 '4'이다.

예제2는 234092 입력받게 되는데 모든 숫자를 지우려면 1부터 20까지는 줄세워야 한다. 여기서 주의점은 입력값의 순서대로 찾아야 한다는 것이다! 29403이라면 2를 찾고 그다음 9을 찾고 4를 찾는... 순서를 가져가야 한다.

📌 풀이

풀이 - (성공)

n = input()
ans = 0 #최솟값변수 
while True:
    ans += 1
    num = str(ans) #각숫자별로 비교하기 때문에 문자로 변환
    while len(num) > 0 and len(n) > 0:
        if num[0] == n[0]:
            n = n[1:]
        num = num[1:]
    if n == '':
        print(ans)
        break

https://www.acmicpc.net/problem/3986

문제 설명

문제를 이해하면 쉬운데 문제를 이해하는 것이 어려웠다... 아래의 이미지를 처럼 가까이 위치한 문자를 아치형으로 이어본다. 이때 아치들끼리 교차된다면 "안좋은 단어"에 속하게 되면 어떠한 교차점도 없다면 "좋은 단어"이다.!!

자료구조 문제 중 대표적인 올바른 괄호 인지를 맞추는 문제와 동일하다. 단지 괄호를 알파벳으로 바꾼거라고 생각하면 된다😬

📌 풀이

풀이 - (성공)

n = int(input())
ans = 0

for _ in range(n):
    stack = []
    _list = list(input())
    for i in _list:
        if not len(stack):
            stack.append(i)
        elif stack[-1] == i:
            stack.pop(-1)
        else:
            stack.append(i)

    if not len(stack):
        ans += 1 

print(ans)

https://www.acmicpc.net/problem/10026

📌 풀이

적록색약을 가지고 있지 않는 사람은 case_1, 적록색약을 가진 사람은 case_2라고 칭한다.

1. (case_1) 각 색깔별 구역 갯수를 저장하기 위해 딕셔너리(color_1)를 생성한다.
2. 인풋으로 받은 그림을 이중리스트(maps)로 만든다.
3. 한번 지나간 컬러를 다시 지나가지 않기 위해 방문여부(chk)를 담는 이중리스트를 만든다.
4. 딕셔너리의 키를 하나씩 가져와 dfs함수를 호출한다.
5. dfs함수로 구한 구역 갯수를 딕셔너리의 밸류 값으로 저장한다.

case_2도 같은 방식으로 거의 같다. 하지만 case_1에 사용한 maps에 변형을 주어야 한다. 적록색약은 빨강과 초록을 구분못하기에 기존의 maps에서 'R'을 'G'로 바꾸거나 'G'을 'R'로 바꾸어야 한다. 이로 인해 빨강과 초록을 하나의 색으로 취급하는 것이다.

풀이 - (성공)

import sys

# 원하는 재귀 깊이로 설정
sys.setrecursionlimit(10000)

n = int(input())
color_1 = {'R':0,'B':0, 'G':0}
color_2 = {'R':0, 'B':0}

maps = [list(input()) for _ in range(n)]
chk = [[False]*n for _ in range(n)]

maps_2 = [[char.replace('G', 'R') for char in row] for row in maps]
chk_2 = [[False]*n for _ in range(n)]


dy=[1,0,-1,0]
dx=[0,1,0,-1]
def dfs(y,x,c,cnt,board,visited):
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<=ny<n and 0<=nx<n:
            if board[ny][nx] == c and visited[ny][nx] == False:
                visited[ny][nx] = True
                dfs(ny,nx,c,cnt,board,visited)

#case_1       
for c in color_1:
    cnt = 0
    for i in range(n):
        for j in range(n):
            if maps[i][j] == c and chk[i][j] == False:
                chk[i][j] = True
                dfs(i,j,c,cnt, maps,chk)
                color_1[c] += 1


#case_2       
for cc in color_2:
    cnt_2 = 0
    for i in range(n):
        for j in range(n):
            if maps_2[i][j] == cc and chk_2[i][j] == False:
                chk_2[i][j] = True
                dfs(i,j,cc,cnt_2,maps_2,chk_2)
                color_2[cc] += 1


print(sum(color_1.values()), sum(color_2.values()))

여기서 잠깐.. 🤚 (알아 두면 좋은 개념)

1️⃣ 런타임 에러 (RecursionError) 방지 DFS로 구현하려면, 재귀를 사용하되, 재귀 깊이를 초과하지 않도록 주의해야 합니다. 재귀 깊이를 제한하는 방법 중 하나는 sys.setrecursionlimit()함수를 사용하는 것이지만, 이 방법은 주의해서 사용해야 합니다. 좀 더 안전한 방법은 반복문을 사용하여 DFS를 구현하는 것입니다.

2️⃣ deepcopy를 사용한 이유 chk를 chk_2에 복사할 때 chk_2 = chk.copy()를 사용하면 안됩니다. (이거 몰라서..한참동안 코드문제를 찾았네요.. ㅠㅠ 만약 사용하게 된다면 case_1의 값은 잘 구해지지만 case_2가 안될거에요..)
copy() 문제가 되는 이유는 해당 메서드가 얕은 복사(shallow copy)를 수행하기 때문입니다!! 얕은 복사는 객체 내부의 내부 객체를 새로 생성하지 않고 원래 객체의 참조를 그대로 사용합니다. 쉽게 말하면 chk_2와 chk는 동일한 내부 리스트를 참조하게 되어 두 리스트가 같은 메모리 공간을 공유하게 되어chk_2를 변경할 때 chk도 변경되므로 원치 않는 결과가 발생합니다. 이런 문제를 해결하려면 깊은 복사(deep copy)를 사용해야 합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/178871

📌 풀이

풀이 1 - (9~13번 시간초과)

1. 호명되는 이름의 인덱스 값을 저장해둔다.
2. 호명된 이름을 players에서 삭제한다.
3. 저장해둔 이름의 인덱스에 1를 뺀 값이 새로운 인덱스 자리이다. 새로운 인덱스에 호명이름 넣는다.

def solution(players, callings):
    answer = []
    for c in callings:
        idx = players.index(c)
        players.remove(c)
        players.insert(idx-1,c)

    return players

풀이 2 - (성공)

거저 먹으려고 했지만, 시간초과가 난다..🥲 다른 방법을 시도해야 한다. 아마 "해시"문제로 풀어야 하는 것 같다.

def solution(players, callings):

    # 초기 순위를 인덱스로 딕셔너리 생성 --> 이름: 순위
    players_ranking = {player: int(idx) for idx, player in enumerate(players)}

    for c in callings:
        current_rank = players_ranking[c]  # 호명한 선수의 현재 순위

        # 호명된 선수 순위 올리기
        players_ranking[c] -= 1
        # 밀린선수 순위 낮추기 
        players_ranking[players[current_rank - 1]] += 1

        # players 배열에서 선수들의 순위 바꿔주기
        players[current_rank - 1], players[current_rank] = c, players[current_rank - 1]

    return players

https://school.programmers.co.kr/learn/courses/30/lessons/161989

📌 풀이

풀이 1 - (1,6,7,9,13,23~25번 테스트 케이스 실패)

1. 각 stage에 머무는 사람의 수를 세린다. (Counter 함수 사용)
2. 1~N번와 임의의 숫자를 넣어 이중리스트를 만든다 (ex. [[1,0],[2,0],[3,0] ..] 0이라는 임의의 숫자는 실패율을 넣을 예정이다.
3. 처음 시작하는 인원의 수는 stage의 길이 수와 동일하다
4. for문을 돌려 각 stage별(1단계,2단계, ... N) 실패율을 계산한다. (여기서 굳이 N의 실패율을 구하지 않아도 된다. N에 있다는 것은 이미 모든 판을 깨고 성공사람을 의미하기 때문이다.
5. 계산한 실패율로 0의 자리에 넣어 업데이트한다.
6. 실패율이 높은거로 정렬하되 만약 실패율이 같다면 단계가 낮은 순서로 정렬시킨다.

from collections import Counter
def solution(N, stages):
    answer = []
    _dict = Counter(stages)    
    _list = [[i,-1] for i in range(1, N+1)]

    persons = len(stages)
    for i in range(N):        
        temp = _dict[i+1]
        _list[i][1]= temp/persons
        persons -= temp

    _list.sort(key = lambda x:(x[1],-x[0]),reverse = True)
    for l in _list:
        a,b= l
        answer.append(a)

    return answer

풀이 2 - (성공)

코드를 돌릴때 딱히 문제가 없어서 간과하고 있었던 부분이 있다. 실패율을 구할때 0으로 나눈 경우가 있을 수 있다. ZeroDivisionError: division by zero 이부분을 조건문으로 달아야 예외처리 해야한다.

from collections import Counter
def solution(N, stages):
    answer = []
    _dict = Counter(stages)    
    _list = [[i,-1] for i in range(1, N+1)]

    persons = len(stages)
    for i in range(N):        
        temp = _dict[i+1]
        if temp != 0 and persons != 0:
            _list[i][1]= temp/persons
            persons -= temp

    _list.sort(key = lambda x:(x[1],-x[0]),reverse = True)
    for l in _list:
        a,b= l
        answer.append(a)

reference

• Counter함수 정리글
• sort,sorted함수 정리글
• 람다(lambda)함수 정리글

https://school.programmers.co.kr/learn/courses/30/lessons/161989

📌 풀이

풀이 1 - (11,20,24,26번 테스트 케이스 실패)

1. n갯수 만큼 1를 만든다.

2. section에 있는 숫자에서 -1을 뺀 인덱스의 값을 0으로 바꾼다.

3. while문을 돌려 0이 없을때까지 반복한다. 3-1.가장 앞에 있는 0의 인덱스 값을 찾는다. 그리고 인덱스 값을 idx에 저장한다. 3-2. idx:idx+m까지 1로 바꾼다 (덧칠했다는 뜻이다) 3-3. 덧칠한 횟수를 담은 변수 answer에 1을 더한다.

   def solution(n, m, section):
    answer = 0
    _list= [1 for _ in range(n)]
    for i in section:
        _list[i-1] = 0
   
    while True:
        if 0 not in _list:
            break
        idx=_list.index(0)
        _list[idx:idx+m] = [1] * m
        answer +=1
    return answer

풀이 2 - (성공)

(시간초과 오류는 항상 답답해요.. 이래서 효율성 어느정도 계산할 줄 알아야 하나바요... ) 위의 코드에서 시간초과 난것은 제한사항을 보면 대략 가늠이 된다. n이 10만이고 section도 10이다. m이 1이면 _list를 10만번 재설정한다는 것이다. 이러한 재설정 방법을 사용하지 않고 코드를 짤 필요가 있다.

1. start를 -100001로 저장한다. (무조건 section의 첫번째 값을 덧칠하기 위해서)
2. section을 돌며 아래 과정을 반복한다. 2-1. start+m 보다 section원소(s)가 더 큰지 비교한다. 2-2. 더 크다면 s를 start에 저장하고 answer에도 +1을 한다.

def solution(n, m, section):
    answer = 0
    start = -100001

    for s in section:
        if s>=start+m:
            start = s
            answer += 1
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/169199

문제 내 예시는 아래 이미지와 같이 움직이게 되며 규칙은 아래와 같다.

• 시작점 R에서 시작한다.
• 범위 안에서 돌아다닐 수 있다.
• D를 만날때까지 특정 방향으로 계속 움직이다.
• G를 지나갈수 있다. 아래 이미지의 2번 움직임을 봤을때 G에서 서는 것이 아니라 G를 지나쳐 D앞에서 멈추게 된다. (처음에 2번만에 끝날수 있는거 아닌가.. 했슴돠 😭)
• 정확하게 G에 서야한다.

만약 이해가 안된다면 아래 동영상을 꼭 보면 좋습니다!!! 동작원리를 쉽게 이해할수 있어요 https://www.youtube.com/watch?v=QqSREKrNSIg

📌 풀이

풀이 1 - (11,20,24,26번 테스트 케이스 실패)

1. 입력으로 주어진 보드를 이차원 리스트 graph에 저장한다.
2. chk는 최소 이동 횟수를 기록하는 이차원 리스트로, 모든 값을 무한대(float('inf'))로 초기화한다.
3. 이중 반복문을 사용하여 출발과 도착 위치를 찾아 start_y, start_x, end_y, end_x 변수에 저장한다.
4. BFS 함수 호출한다.

• bfs 함수는 시작점부터 도착점까지의 최소 이동 횟수를 계산하는 함수이다.
• 네 방향 (상, 하, 좌, 우)으로 이동할 수 있는지 확인하고, 이동할 수 있다면 이동한 후의 위치를 계산한다.
• 만약 이동한 위치의 최소 이동 횟수가 현재 위치의 최소 이동 횟수보다 크다면, 최소 이동 횟수를 업데이트하고 해당 위치를 큐에 추가한다.

5. 결과가 None이라면 도착점에 도달할 수 없는 경우이므로 -1을 반환한다.

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    graph = [list(board[i]) for i in range(n)]
    chk = [[float('inf')] * m for _ in range(n)]

    # 시작점, 도착점 찾기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                start_y, start_x = i, j
            elif graph[i][j] == 'G':
                end_y, end_x = i, j
    chk[start_y][start_x] = 0

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]

    def move_there(dir_y, dir_x, c_y, c_x):
        while True:
            c_y = c_y + dir_y
            c_x = c_x + dir_x

            if 0 > c_y or c_y >= n or 0 > c_x or c_x >= m or (graph[c_y][c_x] == 'D'):
                return [c_y - dir_y, c_x - dir_x]

    def bfs(s_y, s_x, e_y, e_x):
        q = deque()
        q.append((s_y, s_x))

        while q:
            y, x = q.popleft()
            if y == e_y and x == e_x:
                return chk[e_y][e_x]
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                if 0 <= ny < n and 0 <= nx < m:
                    if graph[ny][nx] == '.':
                        ny, nx = move_there(dy[k], dx[k], y, x)
                        if chk[ny][nx] > chk[y][x] + 1:
                            chk[ny][nx] = chk[y][x] + 1
                            q.append((ny, nx))

    result = bfs(start_y, start_x, end_y, end_x)

    if result is None:
        return -1
    else:
        return result

풀이 2 - (성공)

'.' 뿐만 아니라 'R', 'G'도 지나칠 수 있다. 이전 코드에선 if graph[ny][nx] == '.'로 되어있어 테케 통과가 되지 않음을 알 수 있다. 'D'가 아닌곳이라면 지나갈 수 있도록 수정했다!

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    graph = [list(board[i]) for i in range(n)]
    chk = [[float('inf')] * m for _ in range(n)]

    # 시작점, 도착점 찾기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                start_y, start_x = i, j
            elif graph[i][j] == 'G':
                end_y, end_x = i, j
    chk[start_y][start_x] = 0

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]

    def move_there(dir_y, dir_x, c_y, c_x):
        while True:
            c_y = c_y + dir_y
            c_x = c_x + dir_x

            if 0 > c_y or c_y >= n or 0 > c_x or c_x >= m or (graph[c_y][c_x] == 'D'):
                return [c_y - dir_y, c_x - dir_x]

    def bfs(s_y, s_x, e_y, e_x):
        q = deque()
        q.append((s_y, s_x))

        while q:
            y, x = q.popleft()
            if y == e_y and x == e_x:
                return chk[e_y][e_x]
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                if 0 <= ny < n and 0 <= nx < m:
                    if graph[ny][nx] != 'D': #수정한곳 
                        ny, nx = move_there(dy[k], dx[k], y, x)
                        if chk[ny][nx] > chk[y][x] + 1:
                            chk[ny][nx] = chk[y][x] + 1
                            q.append((ny, nx))

    result = bfs(start_y, start_x, end_y, end_x)

    if result is None:
        return -1
    else:
        return result

https://school.programmers.co.kr/learn/courses/30/lessons/159993

📌 풀이

풀이 1 - (실패)

1. 미로를 2차원 배열로 표현하고, 시작 지점(S), 출구(E), 레버(L)의 위치를 찾는다.
2. BFS (너비 우선 탐색) 알고리즘을 사용하여 시작 지점(S)에서 레버(L)까지의 최단 거리를 계산한다.
3. BFS (너비 우선 탐색) 알고리즘을 사용하여 시작 지점(L)에서 레버(E)까지의 최단 거리를 계산한다.
4. 두 단계에서 계산한 거리를 합산하여 출발 지점(S)에서 출구(E)까지 이동하는 최단 거리를 구한다.
5. 만약 어떤 단계에서도 출구(E)에 도달할 수 없는 경우에는 -1을 반환합니다.

from collections import deque

def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])

    graph = [list(maps[i]) for i in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'S':
                start_y, start_x = i, j 
            elif graph[i][j] == 'E':
                end_y, end_x = i, j 
            elif graph[i][j] == 'L':
                lever_y, lever_x = i, j 


    dy= [1,0,-1,0]
    dx= [0,-1,0,1]
    def bfs(start_y, start_x, end_y, end_x):
        chk[start_y][start_x] = 0
        q= deque()
        q.append((start_y, start_x))

        while q:
            y,x = q.popleft()
            if y == end_y and x == end_x:
                return chk[y][x]

            for k in range(4):
                ny = y+ dy[k]
                nx = x+ dx[k]
                if 0<=ny<n and 0<=nx<m:
                    if graph[ny][nx] != 'X' and chk[ny][nx] =='inf':
                        chk[ny][nx] = chk[y][x] + 1
                        q.append((ny,nx))
        return None 


    chk = [['inf'] * m for _ in range(n)]
   # 출발지에서 lever까지 거리 구하기 
    distance1 = bfs(start_y, start_x, lever_y, lever_x)

   # lever에서 도착지까지 거리 구하기
    distance2 = bfs(lever_y, lever_x, end_y,end_x)

    if distance1 is None or distance2 is None:
        return -1
    else:
        return distance1+distance2

풀이 2 - (성공)

문제를 다시 읽어보니, 우선적으로 레버를 찍은다음, 레버에서 다시 도착지로 가야 한다. 이때 갔던곳을 또 갈 수 있다는 것이 기본 미로탈출 문제와는 다른점이다.

1. 출발지에서 레버까지의 거리 계산

• chk 배열 초기화
• chk 배열 업데이트

2. 레버에서 도착지까지의 거리 계산

• chk 배열 초기화
• chk 배열 업데이트

*(중요!!!) 각 스텝을 시작할때 거리를 저장할 chk는 새롭게 시작해야 한다. *

from collections import deque

def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])

    graph = [list(maps[i]) for i in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'S':
                start_y, start_x = i, j 
            elif graph[i][j] == 'E':
                end_y, end_x = i, j 
            elif graph[i][j] == 'L':
                lever_y, lever_x = i, j 


    dy= [1,0,-1,0]
    dx= [0,-1,0,1]
    def bfs(start_y, start_x, end_y, end_x):
        chk[start_y][start_x] = 0
        q= deque()
        q.append((start_y, start_x))

        while q:
            y,x = q.popleft()
            if y == end_y and x == end_x:
                return chk[y][x]

            for k in range(4):
                ny = y+ dy[k]
                nx = x+ dx[k]
                if 0<=ny<n and 0<=nx<m:
                    if graph[ny][nx] != 'X' and chk[ny][nx] =='inf':
                        chk[ny][nx] = chk[y][x] + 1
                        q.append((ny,nx))
        return None 



   # 출발지에서 lever까지 거리 구하기 
    chk = [['inf'] * m for _ in range(n)]
    distance1 = bfs(start_y, start_x, lever_y, lever_x)

   # lever에서 도착지까지 거리 구하기
    chk = [['inf'] * m for _ in range(n)]
    distance2 = bfs(lever_y, lever_x, end_y,end_x)

    if distance1 is None or distance2 is None:
        return -1
    else:
        return distance1+distance2

https://school.programmers.co.kr/learn/courses/30/lessons/68645

📌 풀이

풀이 1 - (성공)

문제의 규칙은 아래 이미지와 같다: 채우는 방향이 3가지로 나뉘어져 있으며 n만큼 실행하였을때 삼각형이 모두 채워진다. (규칙을 찾을때는 n이 다른 경우에도 잘맞는지를 꼭 더블체크하자!)

1. n*n의 매트릭스를 생성한다.
2. 숫자가 1부터 시작하기때문에 cnt에 1을 저장한다.
3. y,x = -1,0을 저장한다. 이는 매트릭스의 위치를 표현하는 좌표이다. y를 0이 아닌 -1로 한 이유는 for문 첫번째 실행이 무조건 아래로 숫자를 채우는 형식이여야 하기 때문이다.
4. for문을 n만큼 돈다. 2-1. i/3의 나머지가 1인경우, 세로방향으로 한칸씩 채운다. cnt에 1을 더한다. 2-2. i/3의 나머지가 2인경우, 가로방향으로 한칸씩 채운다.cnt에 1을 더한다. 2-3. i/3의 나머지가 3인경우, 윗 대각선방향으로 한칸씩 채운다.cnt에 1을 더한다.

def solution(n):
    answer = []
    _list = [[0]*i for i in range(1, n+1)]
    y,x = -1,0 
    cnt = 1
    for i in range(n):
        for _ in range(i,n):
        # for j in range(n):
            if i % 3 == 0: #아래로 한칸씩 채우기
                y += 1 
            elif i% 3 == 1: #오른쪽으로 한칸씩 채우기
                x += 1 
            elif i% 3 == 2: #위대각선으로 한칸씩 채우기
                x -= 1
                y -= 1
            _list[y][x] = cnt
            cnt+=1 

    for i in _list:
        for j in i:
            answer.append(j)

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/77885

📌 풀이

풀이 1 - (성공)

문제에서 원하는 것은 주어진 숫자x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 찾는 것이다. 이문제는 짝수와 홀수로 나누어 이 문제를 풀 수 있다.

- 짝수일때 짝수를 이진법으로 변환했을때 마지막 숫자는 무조건 0이 될것이다. 2 --> 10 4 --> 100 6 --> 110 마지막 숫자를 0을 1로 바꿔주면 x보다 크지만 다른 비트 갯수가 1개인 숫자를 찾을 수 있다. 이 숫자는 주어진 짝수에서 +1가 된다.

- 홀수일때 홀수를 이진법으로 변환했을때 가장 오른쪽에 있는 '0'을 찾는 것이 중요하다. 가장 오른쪽에 위치한 0의 인덱스가 n이라고 가정한다. 그렇다면 n인덱스에 위치한 0을 1로 바꿔주고, n+1에 위치한 0으로 바꿔준다. 예를 들자면 아래와 같습니다. 3 --> 011 --> 101(5) 5 --> 101 --> 110(6) 7 --> 0111 --> 1011(11) 9 --> 1001 --> 1010(10)

1. for문을 돌려 numbers 리스트에 있는 원소를 하나씩 꺼낸다. 꺼낸 원소를 n이라고 부르겠다.
2. 만약 n이 짝수라면 n+1을 한 값을 answer에 집어넣는다.
3. 만약 n이 홀수라면 가장 오른쪽에 있는 0을 찾고 그 인덱스값을 right_idx에 저장한다. right_idx값을 1로 바꾸고 right_idx+1 값을 0으로 바꾼다. 3-1. 3단계를 거친 string 리스트를 하나로 합치고 이를 숫자형(int)로 바꾼다. 3-2. 이진 숫자를 다시 십진법 숫자로 변환하여 answer에 집어 넣는다.

def solution(numbers):
    answer = []

    for n in numbers:
        if n % 2 == 0:  # 짝수일 경우
            answer.append(n + 1)
        else:  # 홀수 인 경우
            temp = '0' + bin(n)[2:]
            right_idx = temp.rfind('0')
            temp_list = list(temp)

            temp_list[right_idx] = '1'
            temp_list[right_idx+1] = '0'

            temp_str = "".join(temp_list)

            answer.append(int(temp_str, 2))

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42885

📌 풀이

풀이 1 - (product 함수 사용 성공)

1. numbers에 들어 있는 수의 음수 형태를 만든다
2. (양수, 음수)와 같이 튜플형태를 nums라는 리스트에 넣는다.
3. nums 리스트로 만들 수 있는 모든 조합을 만든다.
4. 조합의 합을 구하여 target과 같으면 answer에서 1을 더한다.

from itertools import product

def solution(numbers, target):
    answer = 0
    nums = [(i, -1 * i) for i in numbers]  # 각 숫자에 대해 양수와 음수 조합 생성

    # 가능한 모든 조합을 생성하여 합을 계산
    for combination in product(*nums):
        if sum(combination) == target:
            answer += 1

    return answer

Tip! 예를 들어, nums 리스트가 다음과 같이 구성되어 있다고 가정해 봅시다:

nums = [(1, -1), (2, -2), (3, -3)]

만약 product 함수에 nums를 그대로 전달하면, 이 리스트 하나가 하나의 인수로 처리됩니다. 즉, product는 이 리스트 하나를 하나의 요소로 간주합니다.

for item in product(nums):
    print(item)

#결과: ((1, -1), (2, -2), (3, -3))

하지만 (*nums)를 사용하면, nums 리스트 내부의 각 튜플을 개별적인 인수로 전달하게 됩니다. 이렇게 하면 product 함수는 nums 리스트 안에 있는 각 튜플의 요소들을 개별적으로 조합합니다.

for item in product(*nums):
    print(item)
##결과
(1, 2, 3)
(1, 2, -3)
(1, -2, 3)
(1, -2, -3)
(-1, 2, 3)
(-1, 2, -3)
(-1, -2, 3)
(-1, -2, -3)

참고

• itertools.product 정리 글

https://school.programmers.co.kr/learn/courses/30/lessons/42885

풀이

풀이 1 - (성공)

1. 구명보트에 태울 수 있는 사람은 최대 2명입니다.

2. 따라서, 사람들의 몸무게를 오름차순 정렬한 뒤,

3. 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나

4. 한 명(몸무게가 가장 많은 사람)을 태웁니다.

   def solution(people, limit):
    answer =0
    people.sort() #작은수에서 큰수
    left = 0
    right = len(people)-1
   
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1 
        else:
            right -= 1
   
        answer +=1 
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12936

📌 풀이

풀이 1 - (성공)

1. 1부터 n까지의 수로 리스트("_list")를 생성한다.
2. 리스트의 원소로 만들수있는 모든 순열 조합을 리스트("list")로 생성한다. (순열 조합으로 만들었을 때 이미 사전순으로 정렬되어 나옴)
3. 순열 조합에서 k-1번째 값을 반환한다. (k-1을 사용하는 이유는 파이썬의 리스트 인덱스가 0부터 시작하기 때문이다)

from itertools import permutations
def solution(n, k):
    answer = []
    _list = [i for i in range(1,n+1)]
    ways = list(permutations(_list, len(_list)))
    return list(ways[k-1])

풀이 2 - (12,13번 테스트케이스 시간 초과)

주어진 코드는 itertools의 permutations 함수를 사용하여 n개의 숫자로 이루어진 순열을 모두 생성한 다음, 그 중에서 k번째 순열을 반환하려고 한다. 그러나 이 코드는 순열의 개수가 매우 커질 때(특히 n이 큰 경우) 성능 문제가 발생할 수 있다.

이러한 성능 문제를 해결하려면 다른 방식으로 접근해야 한다. 순열을 구하는 대신, 팩토리얼 개념을 통해 k번째 순열을 직접 계산하는 방법을 사용할 수 있다.

def solution(n, k):
    answer = []
    _list = [i for i in range(1, n + 1)]

    k -= 1  # k를 0-based 인덱스로 변환

    factorial = 1
    for i in range(1, n):
        factorial *= i

    for i in range(n - 1, -1, -1):
        index = k // factorial
        answer.append(_list.pop(index))
        k %= factorial
        if i > 0:
            factorial //= i

    return answer

• data
• loss
• model
• algorithms

1️⃣ Data (데이터)

데이터는 모델이 학습하고 예측하는 데 사용되는 정보입니다. 예를 들어, 이미지 분류 모델을 만들려면 이미지와 해당 이미지에 레이블(예: 고양이, 개)이 필요합니다. 데이터는 모델이 세상을 이해하고 일반화하는 데 사용되는 훌륭한 표본 집합이며, 좋은 데이터는 모델의 성능을 크게 향상시킬 수 있습니다.

그러면 어떤 관점에서 "데이터"를 이해해야 하나요?🧐

• 우선 어떤 종류의 데이터를 사용하는지 파악하세요! 이미지, 텍스트, 오디오, 비디오 등 다양한 형태의 데이터가 있을 수 있습니다. 논문에서 사용한 데이터의 특성과 종류에 대한 이해는 모델과 실험 결과를 이해하는 데 중요합니다.
• 논문에서 어떤 데이터 전처리 기술을 사용했는지 확인하세요! 데이터의 정규화, 크기 조정, 잡음 제거, 불균형 클래스 처리 등의 전처리 기술은 모델 학습에 중요한 영향을 미칩니다.
• *데이터의 양과 품질의 정도를 파악해보세요! * 데이터의 양과 품질, 정확도를 확인해 모델의 성능에 영향을 미칠만한 부분이 있는지를 확인해야 합니다. 너무 적거나 많은 데이터 양은 성능에 영향을 줄수 있으며,잘못된 레이블, 이상치, 노이즈가 모델 학습에 부정적인 영향을 미칠 수 있습니다.

2️⃣ Loss (손실)

손실은 모델의 예측과 실제 값 간의 차이를 측정하는 지표입니다. 모델의 목표는 손실을 최소화하는 것입니다. 이를 통해 모델이 더 나은 예측을 할 수 있도록 가중치를 조정하게 됩니다. 손실 함수의 선택은 문제 유형에 따라 다양합니다.

회귀 문제(실수값 예측)에서 주로 사용되는 "평균 제곱 오차", 분류 문제에서 주로 사용되는 "크로스 엔트로피", SVM과 같이 정확한 분류를 필요하는 문제에 사용되는 "힌지"등이 있습니다! (하나도 들어보지 못했다해도 괜찮습니다! 나중에 하나씩 자세하게 다루어볼께요 😀)

3️⃣ Model (모델)

모델은 데이터에서 패턴을 학습하고 예측을 수행하는 데 사용되는 수학적인 구조입니다. 딥러닝 모델은 신경망(neural network)이라고도 불립니다. 이 모델은 여러 계층으로 구성되며 각 계층은 데이터로부터 특징을 추출하고 정보를 처리합니다. 모델은 가중치와 활성화 함수를 사용하여 입력을 출력으로 변환합니다.

대표적으로 모델은 아래와 같이 분류될 수 있어요!

• 인공 신경망 (Artificial Neural Networks, ANN): 가장 일반적으로 사용되는 딥러닝 모델 중 하나로, 뉴런과 연결된 가중치로 구성된 여러 계층으로 이루어집니다. 다양한 종류의 ANN이 있으며, feedforward, recurrent, convolutional 등 다양한 구조가 있습니다.

• 순환 신경망 (Recurrent Neural Networks, RNN): 순차적 데이터 (예: 텍스트 또는 시계열 데이터)를 처리하기에 적합한 모델입니다. RNN은 순환적인 구조로 이전 시간 단계의 정보를 현재 시간 단계에 전달합니다.

• 합성곱 신경망 (Convolutional Neural Networks, CNN): 주로 이미지 처리에 사용되며, 합성곱 계층과 풀링 계층으로 구성됩니다. 이미지에서 특징을 추출하는 데 효과적이기에 컴퓨터비전에서 많이 사용되는 모델입니다.

  • 트랜스포머 (Transformer): 주로 자연어 처리에 사용되는 모델로, 어텐션 메커니즘을 기반으로합니다. 시퀀스 데이터 처리에 뛰어난 성능을 보입니다. (저희가 많이 사용하는 Chat GPT도 트랜스포머 모델을 사용합니다 😲)

모델은 다양한 종류와 구조를 가지고 있습니다. 모델을 이해하기 위해서는 데이터 처리, 계층 구성, 가중치 업데이트, 활성화 함수의 역할 등을 고려하여 살펴보는 것이 중요합니다!! 또한 모델의 선택과 구성은 주어진 작업에 따라 다르므로 문제에 맞게 적절한 모델을 선택하고 이해하는 것이 중요합니다.

4️⃣ Algorithms (알고리즘)

알고리즘은 모델이 데이터로부터 패턴을 학습하고 손실을 최소화하기 위한 과정을 정의합니다. 주요 딥러닝 알고리즘은 경사 하강법(gradient descent)입니다. 이 알고리즘은 손실을 최소화하기 위해 모델의 가중치를 조정합니다. 경사 하강법은 모델이 데이터를 효과적으로 학습하고 최적화하는 핵심 도구 중 하나입니다.

경사하강법 이외에도 경사하강법, Adam, RMSptop, Adagrad등이 있습니다. 알고리즘은 풀고자 하는 문제에 따라 다를 수 있으며 어떤 알고리즘을 택하냐에 따라 모델의 수렴 속도, 안정성, 최종 성능에 영향을 미칩니다. 적절한 알고리즘 선택은 모델 학습의 효율성과 성능 향상에 기여합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/154539

📌 풀이

풀이 1 - (20~23번 테스트케이스 실패)

1. numbers길이와 동일한 리스트를 생성하는데 원소를 -1로 통일한다.
2. 이중 for문을 돌려 뒤에 있는 큰수를 찾는다. 2-1. numbers[i]는 현재 숫자이며 numbers[j]는 뒤에 있는 숫자이다. 2-2. number[j]가 numbers[i]보다 크면 answer[i]의 값을 number[j]로 바꾸면 for문을 중지한다.

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]

    for i in range(len(numbers)-1):  
        for j in range(i+1,len(numbers)):
            if numbers[i] < numbers[j]:
                answer[i] = numbers[j]
                break

    return answer

풀이 2 - (성공)

이전 코드는 두 개의 중첩된 반복문을 사용하기 때문에 입력이 커지면 시간 복잡도가 크게 증가할 수 있다. 특히 입력 리스트의 길이가 매우 큰 경우에는 시간 초과가 발생한다.

입력 리스트의 길이를 N이라고 하면, 첫 번째 반복문은 (N-1)번을 순회하며 두 번째 반복문은 최대 (N-1) + (N-2) + ... + 1 = N*(N-1)/2 번을 순회한다. 이로 인해 최악의 경우 시간 복잡도는 O(N^2)가 된다.

이제껏 리스트의 길이가 길어지는 경우 시간 초과가 나면 stack 구조를 이용하여 풀면 성공하는 경우가 매우 많았다.

def solution(numbers):
    answer = [-1] * len(numbers)  # 결과를 저장할 리스트
    stack = []  # 더 큰 값을 찾기 위한 스택

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:  # 스택이 비어있지 않고 현재 값이 스택의 맨 위 값보다 큰 경우
            last_index = stack.pop()  # 스택의 맨 위 값을 빼내고
            answer[last_index] = numbers[i]  # 해당 인덱스에 현재 값을 저장

        stack.append(i)  # 현재 값을 스택에 추가

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42746

📌 풀이

풀이 1 - (시간 초과)

1. numbers에 주어진 숫자를 가지고 가능한 순열을 모두 만든다.
2. 순열의 조합을 붙여 숫자로 만들어 새로운 리스트에 저장한다.
3. 리스트를 정렬하여 가장 마지막숫자 반환한다.

from itertools import permutations
def solution(numbers):
    answer = ''
    _list= [str(i) for i in numbers]
    nums = [int("".join(i)) for i in (list(permutations(_list, len(_list))))]

    nums.sort()

    return str(nums[-1])

풀이 2 - (11번 테스트케이스 실패)

itertools.permutations 함수는 입력으로 주어진 리스트의 모든 순열을 생성하는 데 사용된다. 하지만 이 함수는 입력 리스트의 길이에 따라 순열의 개수가 급격하게 증가하기 때문에, 입력 리스트의 크기가 큰 경우에는 연산량이 매우 많아질 수 있다. 따라서 입력 리스트의 길이가 큰 경우에는 시간 초과가 발생할 수 있다. (거저 먹기는 안되네요...🥲)

그래서 정렬을 이용해서 해야한다. 예를 들어 3,30,34가 있을 경우 가장 최대값을 만들기위해서 34, 3, 30으로 정렬되어야 합니다. 문자로 정렬해야 하며 문자로 정렬하면 '34', '30', '3'된다. *여기서 제한 조건을 잘 읽어야한다!! 제한 조건에 숫자는 1000이하라고 했으니 문자를 3번 반복한 문자로 정렬을 해야한다. *

def solution(numbers):
    nums =[ str(_) for _ in numbers]
    nums.sort(key= lambda x: x*3, reverse=True)

    return "".join(nums)

아깝게도 11번 케이스 실패했다..... 😭

풀이 3 - (성공)

풀이2 코드에서 모든 numbers가 0인 경우에 대해 고려하지 않았다. 예를들어 [0,0,0,0]가 매개변수로 주어졌을때 "0000"이 만들어지고 이를 그대로 반환하게 된다. 이 경우에는 "0"을 반환해야 하기에 추가 조건문으로 예외처리 했다.

def solution(numbers):
    _list = list(map(str, numbers))

    _list.sort(key=lambda x: x*3, reverse=True)

    # '0'만 여러 번 있는 경우는 예외 처리
    if  _list[0] == '0':
        return '0'

    return ''.join(_list)

reference

• permutations함수 정리글
• sort,sorted함수 정리글
• 람다(lambda)함수 정리글

https://school.programmers.co.kr/learn/courses/30/lessons/42583

📌 풀이

풀이 1 - (5번 테스트케이스 실패)

1. truck_weights 왼쪽에서 빼기 때문에 deque 자료구조로 바꾸어 준다.
2. bridge_length만큼 원소가 들어갈수 있도록 새로운 deque 자료구조를 생성한다. (이는 현재 bridge위에 있는 차와 무게를 나타낸다.)
3. truck_weights에서 대기하는 자동차가 없을때까지 반복문을 반복한다. 3-1. truck_weights에서 가장 앞에 있는 자동차의 무게와 bridge의 무게를 합하여 weight(다리 제한무게)를 넘지 않는다면 truck_weights의 첫번째 자동차를 빼서 bridge에 넣어준다. 그리고 초를 세기위해 answer +1을 해준다. 3-2. truck_weights에서 가장 앞에 있는 자동차의 무게와 bridge의 무게를 합하여 weight(다리 제한무게)를 넘는다면 bridge에 0을 넣어준다. 그리고 초를 세기위해 answer +1을 해준다.

(주의!) bridge위의 자동차무게를 구할때 sum(bridge)가 아닌 sum(bridge) - bridge[0]으로 해야한다. 0초: [0,0] 1초: [0,7] 2초: [7,0] 3초: [0,0] [0,4] 위의 예시와 같이 "7"이 나가는 동시에 "4"가 들어오는데 이것은 1초 내에 함께 이루어진다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0 for _ in range(bridge_length)],maxlen=bridge_length)

    while len(truck_weights):
        estimated = truck_weights[0] + sum(bridge) - bridge[0]
        if estimated <= weight:
            temp = truck_weights.popleft()
            bridge.append(temp)
            answer += 1
        else:
            bridge.append(0)
            answer += 1

    return answer + bridge_length

풀이 2 - (성공)

이전 코드에서 시간 초과가 발생하는 이유는 estimated = truck_weights[0] + sum(bridge) - bridge[0] 부분이다. 이 부분은 매 반복마다 다리 위의 트럭들의 무게를 모두 더하는 작업을 수행하고 있습니다. 이 작업은 sum(bridge)를 통해 다리 위의 트럭 무게를 더하는 것인데, 이러한 작업은 시간복잡도가 O(다리의 길이)가 되며, 다리 위에 있는 트럭의 수가 다리의 길이에 가까워질수록 계산 시간이 길어지게 된다.

*따라서 테스트 케이스 시간초과 문제를 해결할 수 있는 핵심은, "다리 위의 트럭들의 무게 합을 매번 다시 계산하지 않고도 관리할 수 있는 방법"을 찾는 것이다. *

'current_weight' 변수를 통해 현재 다리 위의 트럭 무게의 합을 유지하면서, sum(bridge) 계산을 피하고자 한다. 이렇게 함으로써 불필요한 계산을 줄이고 시간복잡도를 개선할 수 있다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length, maxlen=bridge_length)
    current_weight = 0

    while len(truck_weights):
        if len(bridge) == bridge_length:
            current_weight -= bridge.popleft()

        if current_weight + truck_weights[0] <= weight:
            current_truck = truck_weights.popleft()
            bridge.append(current_truck)
            current_weight += current_truck
        else:
            bridge.append(0)

        answer += 1

    return answer + bridge_length

reference

• stack 정리글

변수는 말그대로 "변하는 수"를 말하죠. 그렇다면 확률변수는 무엇을 일까요? 확률변수란 영어로 random variable로 무작위로 시험했을 때 각 경우의 결과를 수치적으로 나타낸 변수를 의미합니다.

사전적 정의로 이해하기 어려우니 예시를 들어 설명해보도록 할께요!

동전을 두번 던졌을 때 발생되는 경우는 HH,HT,TH,TT로 4가지 입니다. "앞면이 몇번 나올 것인가"에 대해 실수값을 대응시키는 작업을 "확률 변수"만드는 과정이라고 합니다.

• 확률변수 (즉, 앞면의 갯수)가 2인경우: HH (1개)
• 확률변수 (즉, 앞면의 갯수)가 1인경우: TH, HT (2개)
• 확률변수 (즉, 앞면의 갯수)가 0인경우: TT (1개)

• 확률변수가 2가 될 확률: 1/4
• 확률변수가 2가 될 확률: 2/4
• 확률변수가 2가 될 확률: 1/4

📌 확률변수 종류

확률변수는 이산 확률변수(discrete random variable)과 연속 확률변수(continuous random variable)로 구분할 수 있습니다. 확률 변수를 이산 확률 변수와 연속 확률 변수로 구분하는 기준은 그 값이 가능한 결과의 집합이나 범위의 특성에 따라 결정됩니다.

간단히 말하면 결과값을 셀수 있으면 이산확률변수 셀수 없는 경우를 연속확률변수라고 할 수 있습니다.

1️⃣ 이산확률변수 (discrete random variable)

• 이산확률변수의 특징
  • 이산 확률 변수는 유한한 또는 세기 가능한 값을 가집니다. 즉, 값의 개수가 셀 수 있거나 유한합니다.
  • 표, 함수, 그래프로 나타낼 수 있습니다.
  • 이산 확률 변수는 각각의 값에 대한 확률을 정의할 수 있습니다. 따라서 이산 확률 변수의 확률 분포는 확률 질량 함수를 사용하여 나타낼 수 있습니다. (🤭 질량 함수에 대해 밑에서 자세히 설명할께요!)

• 이산확률변수의 예시
  • 어느 날 동물원의 입장갯수
  • 2개의 동전을 던졌을 때 나올 수 있는 앞면 갯수
  • 스트라이크를 성공할 때 가지 볼링공을 굴린 횟수

2️⃣ 연속확률변수 (continuous random variable)

• 이산확률변수의 특징
  • 연속 확률 변수는 실수 범위 내에서 무한한 가능한 값을 가집니다. 즉, 값의 개수가 무한히 많을 수 있습니다.
  • 연속 확률 변수는 각각의 특정 값에 대한 확률을 정의할 수 없으며, 대신 구간(interval) 내의 확률을 정의합니다. 이를 위해 확률 밀도 함수를 사용합니다.(🤭 밀도 함수에 대해 밑에서 자세히 설명할께요!)
  • 표로는 나타낼 수 없지만, 함수와 그래프로 나타낼 수 있습니다.
  • 시간,온도,길이,무게 등은 무한개의 연속적 값을 가지므로 연속확률변수에 속할 수 있습니다.

• 연속확률변수의 특징
  • 어느 지역에 일년 동안 내리는 강수량
  • 어느 공장에서 생산된 전구의 수명
  • 한 버스가 오기까지의 시간

📌 확률분포

이산확률변수는 질량 함수으로 나타내고 연속확률변수는 밀도함수로 나타낼수 있다고 앞서 말씀드렸는데요.이에 대해 더 자세히 설명하려고 합니다. 이를 위해 확률 분포가 뭔지 먼저 짚고 넘어가도록 하겠습니다. 확률 분포는 어떤 사건의 가능한 결과들과 그 결과들이 일어날 확률을 보여주는 것입니다.

예를 들어 주사위를 던져서 어떤 숫자가 나올지 생각해봅시다. 각 숫자가 나올 확률은 같아서 1/6이 될 것입니다. 이렇게 가능한 결과와 그 결과들이 일어날 확률을 모아놓은 것이 확률 분포입니다. 이 또한 확률변수와 같이 "이산확률분포"과 "연속확률분포"로 나뉩니다.

1️⃣ 이산확률분포

이산확률변수에서 말한 예시를 들자면 주사위를 던져 나온 숫자를 생각해봅시다. 이 주사위는 5면으로 이루어져 있으며 각 숫자의 면의 넓이 다릅니다. 이러한 주사위를 던졌을때 각 숫자가 나올 확률이 아래와 같다고 가정해봅시다!

• 1이 나올 확률: 2/15
• 2가 나올 확률: 3/15
• 3이 나올 확률: 5/15
• 4이 나올 확률: 3/15
• 5이 나올 확률: 2/15

각 숫자를 x에 두고 x일때 나올수 있는 확률을 y로 하여 그래프를 그린다면 아래 이미지의 왼쪽과 같을겁니다.

만약 숫자3이 나올 확률을 묻는다면 x가 3일때 y값을 구하면 됩니다. 이와 같이 이산 확률 분포에서 특정 값 x에 대한 확률을 나타내는 함수를 확률 질량 함수(probability mass function, PMF)라고 합니다. 확률 질량 함수로 이산 확률 분포를 나타낼 수 있습니다.

2️⃣ 이산확률분포

이산확률분포는 주사위 예시처럼 딱딱 나눠진 값이 아니라 어떤 범위 내에서 일어날 수 있는 경우입니다. 예를 들어, 온도나 시간과 같은 것들이 연속 확률 분포를 가집니다. 예를 들어 24시간동안 기온 변화를 나타내는 그래프가 있다고 생각해봅시다. (x축이 시간 y축이 온도입니다) 시간이란 무한한 가능한 값(1시 1분 1초, 1시 1.111111초 ...)들의 범위에서 값을 가지므로 선으로 된 그래프를 만들게 될겁니다.

시간개념은 연속적인 개념이기에 특정 값 하나에 대한 확률을 직접 계산하기 어렵습니다. 따라서 우리가 알고 싶은 사건이 발생하는 구간의 넓이를 계산함으로써 그 사건이 발생할 확률을 계산할 수 있습니다. 이를 확률 밀도 함수(probability density function, PDF))라고 합니다

참고

• https://dlearner.tistory.com/32

그래서 확률/통계 시리즈를 찬찬히 다시 수정하려고 합니다. 이번은 첫 챕터로 "모집단"과 "표본"에 대한 글을 써볼려고 합니다.

📌모집단(population)이란?

모집단이라는 말은 데이터, 통계등을 공부하셨다면 많이 듣는 단어 중 하나가 아닐까 생각합니다. 하지만 "모집단의 정의가 뭐해요?"라고 묻는다면 당황하는 사람이 꽤 있을 겁니다. (이것도 나... ;;)

쉽게 말해 모집단은 "(알고싶어하는) 전체 집단"이라고 생각하시면 좋습니다.예를 들어 학교 내에 있는 모든 학생들의 키를 조사하려고 한다고 상상해봅시다. 이때, 학교 내의 모든 학생들의 키를 포함하는 집합을 "모집단"으로 정의할 수 있습니다.

(Quiz) 조금 더 어려운 예시를 들어보겠습니다.🧐

한 연구팀은 코로나 백신 A와 백신 B를 개발했다. 두 백신의 효과를 비교하고 싶다. 이 경우 모집단은 무엇이 될까요?

. . . . .

정답은 백신 두개를 처방했을 때 모든 효과가 모집단이라고 할 수 있습니다. 조금 추상적인 답이죠?? 처음에 모집단을 "알고 싶은" 전체 집단이라고 말했습니다. 여기서 "알고 싶은" 매우 특정적일수 있지만 넓고 광범위 할 수도 있습니다. "효과"처럼 말이죠!! 즉, "모집단"은 때때로 추상적일 수 있다는 말입니다.

다시 정리하면 모집단은 "특정 사람이 알고 싶은 전체집단"이지만 경우에 따라 모집단 자체가 매우 추상적일 수 있다는 것입니다.

📌 표본(sample)이란?

표본도 많이 사용하는 단어입니다. 때때로 특정 단어의 개념을 이해할 때 영단어가 편할 때가 있습니다. 표본은 영어로 샘플(sample)입니다. 화장품 가게에서 뭘 사면 샘플 여러개 받는 경우가 있습니다. 샘플은 대게 본제품의 소량을 주어 고객이 본제품을 테스트 해보도록 하는 목적에서 만들어졌습니다.

통계에서도 샘플은 같은 역할은 합니다! 앞서 애기했던 예시처럼 국가 기간에서 우리나라의 남여성의 키의 평균을 알고 싶어 합니다. 이때 전국의 모든 국민을 "모집단"이라고 간주할 수 있겠지요? 그러나 현실적으로 모든 직원의 월급을 직접 조사하는 것은 시간과 노력이 많이 들어갈 수 있습니다. 그래서 모집단(=전국민)에서 남여 각각 1000명씩을 추출해 이를 표본으로 간주하게 됩니다.

이렇게 만들어진 표본을 가지고 저희는 전국민의 키의 평균, 성별 키의 평균 등등을 추정할 수 있게 되는 겁니다 😀!

CNN은 Convolution Neural Networks의 약자로 컴퓨터 비전 분야에서 이미지나 영상 데이터를 처리할 때 많이 이용됩니다. 모델을 이해할 때 해당 모델이 왜 생겨났는지에 대한 배경을 알아둔다면 모델을 이해하기 쉽습니다. 그렇다면 CNN을 왜 사용하게 된걸까요? 이건 MLP가 가진 한계점 때문입니다!

MLP(다층 퍼셉트론)은 이미지와 같은 2D 구조의 데이터를 평평하게 펼쳐서 처리할 수는 있지만, 이로 인해 이미지의 공간 구조와 지역적 정보가 손실될 수 있습니다. 이로 인해 이미지 내의 패턴, 텍스처, 공간적인 관계 등의 중요한 정보가 무시되며, 이로 인해 MLP를 사용한 학습은 이미지 처리 작업에 비효율적일 수 있습니다.

CNN은 이러한 문제를 극복하기 위해 등장한 모델입니다. CNN은 이미지를 input 그대로 받아서 공간적/지역적 정보를 보존하면서 특성의 계층을 구축하는데 중점을 둡니다. 이는 주로 두 가지 개념인 "합성곱 연산"과 "풀링"을 활용하여 이루어집니다.(뒤에서 상세하게 설명할께요 😀) CNN의 핵심 아이디어는 이미지를 작은 부분들로 나누어 보는 것이며, 이렇게 작은 부분을 통해 이미지의 지역적인 패턴과 특징을 감지하고 학습합니다. 이를 통해 이미지의 한 픽셀과 그 주변 픽셀들 간의 연관성을 살리고 이미지 내의 구조를 이해하는 데에 도움을 줍니다.

CNN 큰그림 이해하기

이해를 돕기 위해 간단한 예시로 다시 설명해보겠습니다!

이미지가 고양이인지 고양이가 아닌지를 감지하는 분류 모델을 구축한다고 가정해봅시다. 고양이와 다른동물(ex. 개, 곰, 사슴)/사물을 구분하기 위해서는 고양이라는 것을 특정할 수 있는 정보가 필요합니다. 이 경우에 눈,코,귀를 보면 고양이인지를 특정할 수 있다고 생각해봅시다.

하지만 세개의 정보는 전체 이미지에서 비교적 작은 부분을 차지 합니다. 따라서 전체 이미지를 다 보는 것보다 특정 부분을 잘라 중요 정보를 가지고 있는 지를 판별하는 것이 더 효율적일 것 입니다. 이를 해주는 것이 "CNN"입니다.

📌 CNN 작동원리

1️⃣ Convolution 이해하기

CNN은 Covolution Neutral Networks 약자이며 한국어로는 "합성곱 신경망"이라고 불립니다. 이때 Convolution/합성곱은 무슨 의미 일까요?

"convolution(합성곱)"은 신호 및 이미지 처리 뿐만 아니라 다양한 분야에서 사용되는 개념입니다만 CNN에서의 "convolution(합성곱)"은 이미지 처리와 패턴 인식을 위해 사용되는 기본 연산 중 하나입니다.

Convolution은 filter(kernel, feature detector)를 이미지와 겹쳐서 계산하는 작업을 말합니다. 이 때 filter는 이미지의 작은 부분에 적용되며, 각 부분에서 필터의 가중치와 이미지의 해당 부분의 값을 곱한 후 모두 더하여 결과를 얻어냅니다.

input 이미지과 feature detector이 주어졌습니다.(컴퓨터는 저희가 보는 이미지는 픽셀별로 변환하여 봅니다!) feature dectector은 input 이미지의 모든 영역을 훓으면서 주요 정보를 뽑게 됩니다. 주요 정보를 뽑은 결과값은 feature map으로 만들어 지게 됩니다.

7x7 크기의 input 이미지에서 3x3 크기의 filter를 겹쳐서 움직이면서 연산을 수행하므로 (7-3+1) x (7-3+1) = 5x5 크기의 출력 이미지가 생성됩니다. 이때 출력 이미지의 크기가 입력 이미지보다 작아지는 현상이 발생합니다

이미지가 작아진다는 것은 비교를 하는데 걸리는 속도가 빨라진 반면 데이터의 크기를 줄이면서 일부 미세한 디테일은 무시될 수 있습니다. 여기서 질문! 그러면 정보가 날아가면 고양이인지 판별못하는거 아닌가요?

결론적으로 말하면 정보 손실이 있어도 판별할 수 있다 입니다. 저희는 input 이미지의 모든 픽셀이 고양이 사진의 픽셀과 같은지를 판단하는 것이 아닌 input 이미지가 고양이의 특징을 가지고 있는지를 비교해야 합니다. 따라서 feature map에서 고양이의 귀/눈/코와 같은 패턴을 가졌는지를 확인하면 됩니다!

2️⃣ Stride

위에 예시에서는 필터를 오른쪽으로 한칸씩 옮겼습니다. 하지만 무조건 한칸씩 옮겨야 하는 것은 아닙니다. 여기서 나오는 개념이 "stride"입니다. 쉽게 말하면 stride는 filter가 얼마나 움직이는 것인가 입니다. - Stride = 1 - Stride = 2

stride를 키우면 공간적인 feature 특성을 손실할 가능성이 높지만 불필요한 특성을 제거하는 효과와 Convolution 연산 속도를 향상시킵니다.

3️⃣ Padding

위에서 말했듯이 convolution을 반복하면 출력 사이즈가 줄어든다는 것을 확인했습니다. 이렇게 하다보면 가장자리 부분의 값은 합성곱을 하지 못하게 됩니다. 합성곱을 하지 못한다는 것은 가장자리의 정보를 잃어버린다는 것을 의미합니다.

이를 막기 위해서 "padding"이라는 개념이 들어오게 됩니다. 패딩 옷처럼 원래 몸보다 몸집을 키운다고 생각하시면 쉽습니다🧐 가장 많이 쓰는게 "zero padding"입니다. 0로 구성된 테두리를 이미지 가장자리에 감싸 준다고 생각하면 됩니다.

padding, stride 인해 output size가 달라지게 됩니다. output사이즈를 구하는 공식은 아래와 같으니 알아두시면 편할거에요 🙌 $(I - K + 2P)/S + 1)$ x $(I - K + 2P)/S + 1)$

• I x I = 입력 사이즈
• K x K = 필터 사이즈
• P = 패딩 크기
• S = strid 크기

📌 CNN 구조 알아보기

Convolution 작동원리에 대해 대략 감을 잡았다면 CNN 전체 구조에 대해 알아보도록 하겠습니다. 전체 구조는 아래의 그림과 같습니다!

1️⃣ Convolution Layer: Convolution + ReLU

앞서 설명한 convolution과 활성화 함수 함께 사용한 것은 "convolution layer"라고 합니다. 주로 ReLU(Rectified Linear Activation) 함수가 사용됩니다.

convolution은 이해했는데 활성화 함수는 왜 쓸까?가 궁금할 겁니다🧐 선형함수(linear function)인 convolution에 비선형성을 추가하기 위해 사용하는 것입니다. (활성화 함수엔 대해서 별도의 글을 쓰도록 할께요!)

2️⃣ Pooling Layer

이전 단계의 합성곱(Convolution) 과정을 통해 다양한 특징 맵(feature map)이 생성되는데, 이러한 많은 특징 맵들을 그대로 다음 계층으로 넘겨주게 되면 매우 많은 계산이 필요해질 뿐만 아니라 모델의 파라미터 수도 급증하게 됩니다.

이를 위해 "풀링 레이어"개념이 들어오게 됩니다. 간략히 말하면, 풀링 레이어는 이미지에서 중요한 정보를 유지하면서 이미지 크기를 줄이는 역할을 합니다. 이렇게 해서 계산량을 줄이고 모델이 더 빠르고 효율적으로 작동하게 도와줍니다. 특히 이미지가 약간 움직여도 중요한 부분을 잘 인식할 수 있게 도와줍니다. 이렇게 함으로써 모델은 이미지의 특징을 더 정확하게 학습하고 분류하게 됩니다.

Pooling에는 대표적으로 두가지 방법으로 Max pooling과 Average pooling이 있습니다.

"Convolution+Relu+Pooling"단계를 지나면서 input이미지는 점점 고차원으로 압축되어 계층적 특징을 잡아나가는 구조를 가지고 있습니다. 계층적 특징이란 아래의 그림처럼 점 -> 선 -> 물체 인식하는 것을 의미합니다.

3️⃣ Flatten

Flatten은 2차원 또는 다차원의 특징 맵(feature map)을 1차원 벡터로 변환하는 작업을 말합니다. 쉽게 말해 각 세로줄을 일렬로 줄 세우는 겁니다.

Flatten을 통해 1차원으로 변환된 데이터는 이미지의 공간적인 구조보다는 특징이나 패턴을 나타내는 데이터로써 활용됩니다. 특히 풀링 레이어에서 얻어낸 작은 크기의 특징 맵들은 이미지의 지역적인 정보보다는 주요 특징이나 패턴을 표현하는데 중점을 둡니다. 이러한 작은 특징 맵들을 1차원 벡터로 펼쳐서 완전 연결 레이어로 넘겨주는 것은 이러한 특징과 패턴을 모델이 더 잘 이해하고 활용할 수 있도록 도와주는 역할을 합니다.

정리하면, Flatten을 통해 얻어진 1차원 데이터는 이미지의 공간적인 구조보다는 주요 특징과 패턴을 표현하는 데이터로 변환된 것이며, 완전 연결 레이어에서 이러한 정보를 활용하여 모델이 패턴을 학습하고 판별하는 데 도움을 줍니다.

4️⃣ FC: Fully-Connected Layers(Dense Layers)

Fully-Connected Layers 또는 Dense Layers는 Convolutional Neural Network (CNN)의 마지막 부분에 있는 레이어입니다. 이 레이어는 이미지나 다른 입력 데이터의 추출된 특징을 기반으로 최종적인 결정을 내리는 역할을 합니다.

참고

• https://talkingaboutme.tistory.com/entry/DL-Convolution%EC%9D%98-%EC%A0%95%EC%9D%98
• https://junklee.tistory.com/111
• https://towardsdatascience.com/applied-deep-learning-part-4-convolutional-neural-networks-584bc134c1e2
• https://halfundecided.medium.com/%EB%94%A5%EB%9F%AC%EB%8B%9D-%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-cnn-convolutional-neural-networks-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-836869f88375