영어권에서 queue는 대기(줄)을 뜻하기도 한다. "나 한 시간 째 줄 서있어"를 영어로 I've been in the queue for an hour라고 한다. 실제로 영국에 갔을 때 웨이팅 리스트를 queue라고 부르기도 했다. 그러면 자료구조에서 큐는 무엇을 뜻할까?

Queue 정의

• queue는 데이터를 저장하는 자료구조 중 하나로, 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 관리한다.

• 앞서 얘기한 웨이팅 줄을 떠올리면 먼저 줄 선 사람이 먼저 나가게 된다. queue라는 자료구조에서 데이터도 먼저 들어온 데이터가 먼저 나가는 것이다.

• queue의 rear(뒤쪽)에 데이터를 추가하는 것을 enqueue라고 한다.

• queue의 front(앞쪽)에서 데이터를 꺼내는 것을 dequeue라고 한다.

Queue의 구현

• 파이썬에서는 deque라는 queue 모듈이 이미 정의되어 있어서 모듈을 불러와서 사용 가능하다.

• 파이썬에는 deque외에도 queue 라는 모듈이 있지만 약간의 차이가 존재한다. 차이는 다음의 하이퍼링크를 클릭해서 확인해보자 ---> 파이썬 모듈 deque와 queue 차이

• queue는 시간복잡도 문제때문에 Array list가 아닌 Linked list를 기반으로 구현한다.

• Array List로 구현할 경우 pop(0)으로 deque를 구현할 수 있지만, 매번 데이터를 앞으로 옮겨줘야 하므로 시간 복잡도가 증가하기 때문이다.

• 파이썬의 deque(Doubly Ended Queue)은 Linked list로 구현되어 있다.

from collections import deque
queue = deque()

#데이터 삽입하기
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

#데이터 출력하기
queue.popleft()
queue.popleft()
queue.popleft()

Deque의 Method

• append(item) : item을 테크 오른쪽 끝에 삽입
• appendleft(item) : item을 데크의 왼쪽 끝에 삽입
• pop() : 데크의 오른쪽 끝 element를 가져오는 동시에 데크에서 삭제
• popleft() : 데크의 왼쪽 끝 element를 가져오는 동시에 삭제
• extend(array) : 주어진 배열을 순환하면서 데크의 오른쪽에 추가
• extendleft(array) : 주어진 배열을 순환하면서 데크의 왼쪽에 추가
• remove(item) : item을 데크에서 찾아 삭제
• rotate(num) : 데크를 num만큼 회전한다 = shift

Stack

컵 쌓기는 cup stacking이라고 부른다. 흔히 쌓여져 있는 구조를 stack이라고 생각하면 된다.

Stack 정의

• stack은 자료구조의 하나로, 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장한다.
• 위의 이미지처럼 쌓인 컵을 생각해보자. 맨 아래의 컵은 가장 먼저 쌓였지만 우리는 컵의 더미 중 가장 늦게 들어온 컵인 가장 위의 컵을 먼저 사용하게 될 것이다.
• Stack의 가장 위인 top에 데이터를 추가하는 것을 push라고 하고 top에서 데이터를 추출 하는 것을 pop이라고 한다.

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)

stack.pop()
stack.pop()
stack.pop()

List 와 Set의 차이

• List는 순서가 중요한 자료구조이다.
  • [1,2,3] ≠ [3,2,1]
• Set은 순서가 중요하지 않은 자료구조이다
  • (1,2,3) = (3,2,1)

파이썬의 List

• 자료구조 List ≠ 파이썬의 List
• 파이썬의 LIst = Array List임.
• 파이썬의 Array List는Dynamic Array로 구현되어 있는데, Dynamic Array는 Array로 구현되어 있음

Array List vs Linked List

• Array list는 메모리 구조상 변수가 순차적으로 할당
• Linked list는 각 노드가 메모리 상 따로 저장되어 있고, 이를 Link로 잇는 형태

배열 (Array)

배열의 특성

1. 고정된 저장 공간(fixed-size)
2. 순차적인 데이터 저장(order)

배열의 정의

• 배열은 선언시 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속/순차적으로 저장하는 자료구조

int arr[5] = {3,7,4,2,6}

• 위의 예시에서는 배열의 사이즈를 5로 정했기 때문에 int형 데이터 4byte 5개를 저장할 메모리 공간인 20byte를 미리 할당받는다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 부른다.

  • int형 = 4byte

  • 1byte = 8bit

  • 1 GB = $1000^3$byte

    

• 또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장

Random access

• 메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다.
• 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킨다.
• 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능한다
• 이를 direct access 또는 random access라고 부른다.
• 첫 번째 데이터가 저장된 주소값이 0x4AF55라면 두번째 데이터는 0x4AF55 + 41에 저장이 되어있고, n번째 데이터는 0x4AF55 + 4(n-1)에 저장이 되어있다.
• 아무리 긴 배열이라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있어서 O(1)의 시간복잡도를 갖는다
• Linked list는 메모리상에서 연속적으로 저장되어 있지 않기 때문에 random accesss가 불가능하다. n번째 데이터에 접근하기 위해서 **array**의 시간복잡도는 **O(1)** 이지만 , **linked list**는 n번의 연산을 해야하므로 시간복잡도는 **O(n)**이 된다.

Static array의 한계

• 데이터의 개수가 정해져 있는 경우에는 staticc array를 사용하는 것이 효율적이다.
• 하지만 선언시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우, 공간이 남아있지 않아서 문제가 발생할 수 있다.
• 그렇다고 매번 크기가 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생한다.
• 이런 문제점을 해결할 수 있는 것이 Dynamic array이다.

Dynamic Array

Dynamic Array 정의

• 선언 이후에 size를 변경할 수 없는 정적배열(Static Array)과 다르게 동적배열(Dynamic Array)는 size를 변경(resizing)할 수 있다.
• fixed-size인 Static Array의 한계점을 보안하고자 고안되었다.

Dynamic Array의 변수할당과 Resizing 과정

• 사이즈가 10인 배열에 순차적으로 13개의 변수를 할당한다고 하자.
• 동적배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, Resizing을 하게 된다.
• 데이터를 추가할 때는 **O(1)** 의 시간복잡도이지만, 배열의 크기를 늘리는 Resizing은 **O(n)**의 시간복잡도가 소요된다.
• Resizing은 기존의 배열보다 두배 큰 배열을 만들고, 이전 배열에서 새로운 배열로 각 데이터를 옮기게 된다. 이후 기존의 배열은 삭제한다. 이 과정에서 **O(n)** 의 시간복잡도가 발생하는 것이다.
• Resizing을 두배로 하는 이유는, Resizing이 O(n)의 시간복잡도를 요구하기에 크기를 1만큼씩 늘리게 되면 많은 시간복잡도가 요구된다. 반면 큰 사이즈의 배열을 만들지 않는 이유는 메모리 낭비가 발생하기 때문이다.
• 이렇게 2배 큰 크기로 Resizing 하는 것을 더블링(Dubling)이라고 한다.

Dynamic Array의 사용법

• 선언시에 배열의 크기를 정하지 않아도 되기 때문에 코딩테스트에서 dynamic array를 자주 사용하게 된다.
• Python에서는 list 자료형을 통해 dynamic array를 이미 잘 구현해 두었기에 직접 dynamic array를 구현할 필요없이 list 자료형을 사용하면 된다.
• 즉 문제에서 배열을 사용해야 하는 경우에는 list 를 사용하면 된다.
• 우리가 익혀야 할 것은 list의 연산(operation) 들과 시간복잡도 이다.

List 연산

• append(x) : 리스트의 맨 마지막에 x 추가

• sort() : 리스트의 요소를 순서대로 정렬

• reverse() : 현재 리스트를 그대로 거꾸로 뒤집는다.

• index(x) : x값에 해당하는 인덱스 리턴. 인덱스를 구하기 위한 함수!

• insert(idx, x) : idx위치에 x값을 삽입

• remove(x) : 리스트에서 첫 번째로 나오는 x를 삭제 (값 기준)

• pop() : 맨 마지막 요소 리턴하고 리스트에서 삭제

• cound(x) : 리스트 안에 x가 몇 개 있는지 조사하여 개수 리턴

• extend(array) : 원래 리스트에 array를 추가

    a = [1,2,3]
    a.extend([4,5])
    >>> [1, 2, 3, 4, 5]
  
    b = [6, 7]
    a.extend(b)
    >>> [1, 2, 3, 4, 5, 6, 7]

Array List의 시간복잡도

• 파이썬에서는 Array List를 Static array와 Dynamic array로 구현했다.

• 선언과 초기화 : **O(n)**

• Dynamic array에서 원소를 뒤에 추가할 때 리사이징이 필요하다면 O(n)의 시간복잡도가 걸리지만, 보통은 O(1)이다. 그렇기에 이런경우 분활상환기법을 사용하여 O(1)이라고 표기한다.

• 중간에 데이터를 추가하게 될 경우, 그 인덱스 이후의 데이터들은 한칸씩 밀어야 하기 때문에 n만큼의 시간복잡도 요구

  

• *Amortized : 분할상환

인공 신경망에서 활성화 함수는 입력값을 변환하여 출력값을 생성하는 함수이다. 활성화 함수에는 선형 활성화 함수와 비선형 활성화 함수가 있다. 인공 신경망에서는 비선형 활성화 함수를 사용하는 것이 일반적이다. 왜냐하면 선형 활성화 함수를 사용할 경우, 여러 층을 쌓아도 결국 선형 변환이 되므로 복잡한 비선형 함수를 표현할 수 없기 때문이다.

선형 활성화 함수

선형 활성화 함수는 입력값에 대해 일정한 비율로 변환되는 함수이다. 즉, 입력값과 출력값 사이에 선형적인 관계가 존재하는 것이다. 예를들어 f(x) = 2x와 같은 함수가 선형 활성화 함수이다.

비선형 활성화 함수

비선형 활서오하 함수는 비선형적인 형태를 가지며, 신경망이 복잡한 비선형 함수를 근사할 수 있도록 도와준다. 대표적인 비선형 활성화 함수로는 ReLU, 시그모이드, 소프트맥수 등이 있다.

ReLU

ReLU는 Rectified Linear Unit의 약자로, 딥러닝에서 가장 많이 사용되는 활성화 함수 중 하나이다.

ReLU 함수는 입력값이 0보다 크면 입력값을 그대로 출력하고, 0보다 작으면 0을 출력하는 함수이다. 수식으로 나타내면 f(x) = max(0, x)로 표현할 수 있다.

ReLU 함수는 다른 활성화 함수들과 비교했을 때, 연산 속도가 빠르고 ㄱ현이 쉬우며, 신경망의 성능도 매우 우수하다. 특히 과적합을 방지하고, 희소성을 가진 입력 데이터의 경우 더욱 뛰어난 성능을 보인다.

하지만 입력값이 음수인 경우에는 출력값이 0이 되기 때문에, 뉴런이 활성화 되지 않아 학습이 멈추는 문제가 발생할 수 있다. 이러한 문제를 해결하기 위해 LeakyReLU, PReLU, ELU 등의 변형된 ReLU 함수들을 사용할 수 있다.

Sigmoid

Sigmoid 함수는 하나의 입력에 대해 0과 1사이의 연속된 값을 출력한다. 입력값이 크면(입력값이 다른 변수에 비해 더 큰 영향을 미치면) 출력값이 1에 가까워지고, 입력값이 작으면 출력값이 0에 가까워진다. 따라서 이 함수는 이진분류(Binary Classification)문제의 출력층으로 사용될 수 있다.

Sigmoid 함수는 출력값이 0또는 1에 수렴할 때, 기울기가 0에 가까워진다. 이러한 형상은 역전파 과정에서 기울기 소실(Vanishing gradient)이라는 문제를 발생시킬 수 있다.

Softmax

Softmax 함수는 다중 클래스 분류(Multi-class Classfication) 문제의출력층에서 사용된다. 이 함수는 모든 출력값의 합이 1이 되도록 각 클래스에 대한 *정규화(Normalization)하는 역할을 한다. 즉, 입력값이 어떤 클래스에 속할 확률을 출력한다. 이 함수는 다중 클래스 분류에서 활성화 함수로 가장 많이 사용되는 함수 중 하나이다.

*정규화(Normalization) : 데이터의 스케일(scale)을 일정하게 맞추어 학습을 원활하게 하고, 모델의 성능을 향상시키기 위한 방법 중 하나

배치사이즈란, 한 번에 모델이 학습하는 데이터 샘플의 개수를 의미합니다. 학습 데이터셋이 매우 클 경우, 전체 데이터셋을 한 번에 모델에 넣어 학습하는 것은 메모리와 게산적인 측면에서 불가능할 수 있습니다. 이러한 경우, 데이터셋을 작은 단위로 나누어 모델에 입력하게 되는데, 이때 단위를 배치라고 합니다.

예를 들어, 1000개의 학습 데이터가 있다고 합시다. 배치 사이즈가 100이라면 전체 데이터셋을 10개의 배치로 나누어 모델에 입력하게 됩니다. 각 배치는 100개의 데이터 샘플을 포함하므로, 모델은 100개의 데이터 샘플을 처리한 후에 가중치를 업데이트 합니다.

• 인공지능 모델은 각 배치사이즈마다 가중치와 편향을 업데이트 합니다.

에폭(Epoch)

에폭(Epoch)란, 전체 학습 데이터셋을 모델이 한 번 학습하는 것을 의미합니다. 따라서 1 에폭은 전체 데이터셋을 한 번 사용하여 학습한 것입니다.

예를들어, 1000개의 학습 데이터가 있고 배치 사이즈가 100이라면, 1에폭은 10개의 배치를 처리한 후에 완료됩니다. 만약 10 에폭을 실행했다면, 전체 데이터셋을 10번 반복해서 학습한 것입니다!

가중치의 업데이트

인공지능 모델은 각 배치사이즈와 에폭마다 가중치를 업데이트 합니다. 초기 학습 시작시, 가중치와 편향은 초기값으로 설정되어 있고, 모델이 학습을 시작함에 따라 인공지능 모델은 각 배치마다 입력 데이터를 받아 출력을 계산하고, 이 출력과 정답 데이터 간의 차이를 계산하여 손실(loss)를 구합니다. 손실은 모델의 성능을 나타내는 지표이며, 이 손실을 최소화하는 방향으로 가중치와 편향을 업데이트 합니다.

따라서, 각 배치마다 모델은 손실을 계산하고, 이 손실을 최소화하기 위해 가중치와 편향을 업데이트합니다. 이 과정을 반복하면서 모델은 최적의 가중치와 편향을 찾아내고, 높은 정확도를 가진 예측 결과를 출력할 수 있게 됩니다.

추가로 모델은 전체 학습 데이터셋을 한 번 처리한 후(에폭마다) 모든 배치의 손실을 평균하여 전체 손실을 게산합니다. 이렇게 계산된 전체 손실을 최소화하기 위해 가중치를 업데이트합니다.

에폭마다 가중치를 업데이트하는 이유는 모델이 학습 데이터셋을 더 많이 보고 가중치를 더 많이 업데이트할 수 있기 때문입니다. 일반적으로 에폭을 늘릴수록 모델의 성능이 향상되지만, 너무 많은 에폭을 설정하면 과적합(Overfitting)이 될 가능성이 있으므로 적절한 에폭 값을 설정하는 중요합니다.

요약

배치사이즈 : 전체 데이터셋을 쪼갠, 모델이 한 번에 처리하는 데이터 샘플의 개수. 에폭 : 전체 학습 데이터셋을 모델이 한 번 학습한 것. 배치사이즈와 에폭마다 모델의 가중치와 편향이 업데이트 된다.