avatar

풀스택 웹🌐 개발자 지망생 🧑🏽‍💻
➕ 인공지능 관심 🤖

Categories

Recent views

  • 1
  • 2
  • 3
  • 4
  • 5

알고리즘-상

  1. 파이썬 SW문제해결 기본

알고리즘 정리

파이썬 SW문제해결 기본

List1

01_알고리즘

알고리즘 개요
  • 알고리즘이란 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
    1) 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
    2) 어떠한 문제를 해결하기 위한 절차
  1. 알고리즘 표현법
    슈도 코드(의사 코드): 특정 프로그래밍 언어의 문법을 따라 쓰여진 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓은 코드
# 코드 예시 (1~100까지 더하는 코드의 2가지 방법)
{: #코드-예시-1~100까지-더하는-코드의-2가지-방법}
def calcSum(n) :
	sum = 0
	for i in range(1, n+1):
	    sum = sum + i
	return sum
    
def calcSum2(n):
	return n*(n+1)//2
	
print(calcSum(100))
print(calcSum2(100))
  • 의사 코드로 흉내만 냈으며, 컴퓨터에서 실행 불가능
  • 알고리즘을 대략적으로 모델링하는데 쓰임

순서도: 프로그램, 작업의 진행 흐름을 순서에 따라 여러 가지 기호나 문자로 나타낸 도표
흐름도: 프로그램의 논리적인 흐름, 데이터의 처리과정을 표현하느데 사용,

  • 프로그램을 작성하기 전에 프로그램의 전체적인 흐름과 과정 파악을 위해 거쳐야하는 작업
  1. 알고리즘의 성능 분석
    1) 정확성 : 얼마나 정확하게 동작하는가?
    2) 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가?
    3) 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
    4) 단순성 : 얼마나 단순한가?
    5) 최적성 : 더 이상 개선할 여지 없이 최적화되었는가?
    • 많은 문제에서 알고리즘의 성능 분석 기준으로 알고리즘의 작업량을 비교
    • 실제 걸리는 시간을 측정, 또는 실행되는 명령문의 개수(주로 쓰임)를 계산
      - 예를 들어 위의 예시 코드 첫번째는 99번의 연산 (덧셈 99번)
      - 2번째 코드를 사용하면 3번의 연산 ( 덧셈 1번, 곱셈 1번, 나눗셈 1번) 더 효율적임
      * 시간복잡도
      - 실행되는 명령문의 개수를 계산

      알고리즘 1
      ```python
      def calcSum(n) :
      sum = 0# 1번
      for i in range(1, n+1):# n 갯수마다 1번
      sum = sum + i# n 갯수마다 1번
      return sum

      시간 복잡도 : 1 + n * 2= 2n+1

      {: #시간-복잡도-1-n-2-2n-1}
      print(calcSum(100))

> 알고리즘 2

```python
def calcSum(n):
    return n*(n+1)//2#3번
# 시간 복잡도 : 3
{: #시간-복잡도-3}
print(calcSum(100))

  • 시간 복잡도의 표기법으로 __빅-오 표기법__이 있다.

    • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

    • 계수(Coefficient)는 생략하여 표시

    • ex) 위의 O(2n+1)은 O(2n) (최고차항만 선택) = O(n) (계수 제거) 과 같음

    • 요소 수가 증가함에 따라 각기 다른 시간복잡도의 알고리즘은 아래와 같은 연산 수를 보임

    • 시간복잡도

    • 0.1초에 1억개의 연산을 처리할 수 있는 기계를 가정했을 때임

    • 시간복잡도에 따라 몇 초에서 몇 년까지 걸리기도 함

02 List

Python 소개

  • 파이썬 : 1991년 귀도 반 로섬이 개발한 프로그래밍 언어

    1) 인터프리터 언어로 독립적인 플랫폼 (실행시 마다 기계어를 해석함, 플랫폼에 관계 없음)

    2) 객체지향 언어 : 파이썬에서는 모든 자료가 객체, 변수의 선언 따로 없음, 초기화시 생성

    • 하나의 변수에 다른 타입의 값을 변수에 저장할 수 있음

    3) 업그레이드 중, 파이썬 3버전은 2버전과 호환성 없음

    4) 라즈베리파이, 빅데이터 자료분석 등에서 관심이 높아짐

    5) 프로그램의 실행속도가 크게 차이 났었음, 실행속도가 느렷었음

    6) 하지만 개발 속도와 생산성이 파이썬이 좋으며, 컴퓨터 하드웨어의 발달로 실행속도 차이가 줌

  • 이하 파이썬의 특징은 PythonTIL jupyter notebook 참조

Exhaustive Search(완전 검색)

  • 문제의 해법으로 생각할 수 있는 모든 경위의 수를 나열해보고 확인하는 기법

  • Brute-force 혹은 Generate-and-Test 기법이라고도 불림

  • 모든 경우의 수를 테스트한 후, 최종 해법을 도출함

  • 일반적으로 경우의 수가 상대적으로 작을 때 유용함

  • 모든 경우의 수를 생성하고 테스트하기 때문에 수행속도는 느리지만, 해답을 찾아내지 못할 확률이 작음

  • 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직함

  • 예시 : Baby-gin game : AlgorithmTIL 참조

    • 고려할 수 있는 모든 경우의 수 생성하기, 6개의 숫자로 만들 수 있는 모든 숫자 나열(중복 포함), 이후 해답 테스트하여 판단해서 찾음
순열(Permutation)

  • 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

  • 서로 다른 n개 중 r개를 택하는 순열은 다음과 같이 표현 (nPr)

  • nPr은 다음과 같은 식이 성립, n(n-1)(n-2)…(n-r+1)

  • nPn은 n!이라고 표기하며 Factorial이라 부름

    • n! = n(n-1)(n-2)…2*1

Greedy Algorithm(탐욕 알고리즘)

  • 최적 해를 구하는데 사용되는 근시안적인 방법

  • 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달함

  • 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없음

  • 일반적으로 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됨

탐욕 알고리즘의 수행과정

1) 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가함

2) 실행 가능성 검사: 새로운 부분 해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지를 검사

3) 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지를 확인, 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작함

  • ex) AlgorithmTIL Baby-gin, Algorithm PPT 참고

  • 일부 해를 구하고 나머지 해를 구하는 방식?

  • 탐욕 알고리즘 접근이 해답을 찾아내지 못하는 경우도 있음 주의

Sort(정렬)

  • 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰값(ascending) 또는 그 반대의 순서대로(descending) 재배열 하는 것

  • 키란 자료를 정렬하는 기준이 되는 특정 값

대표적인 정렬 방식의 종류
버블 정렬(Bubble Sort)

  • 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

  • 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

  • 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨

  • 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블이라고 지음

  • 시간 복잡도 O(n^2)

  • 버블정렬의 예시는 Algorithm PPT 참고

  • 비교와 교환 방식, 코딩이 가장 손쉬움, 평균과 최악 전부 O(n^2)

    리스트를 활용한 버블정렬 슈도코드

    ```python
    def BubbleSort(a):# 정렬할 List
    for i in range(len(a)-1,0,-1):# 범위의 끝 위치
    for j in range(0,i):
    if a[j] > a[j+1]:
    a[j], a[j+1] = a[j+1], a[j]

##### 카운팅 정렬 (Counting Sort)

- 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘. 

- 정렬과정: 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능

- 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함

- 시간 복잡도 O(n + k): n은 리스트의 개수, k는 정수의 최대값

- __비교환 방식, n이 비교적 작을 때만 가능. 최악, 평균 경우 모두 :O(n + k)__

- 정렬 과정 예시 Algorithm PPT 참고
  
  > 리스트를 활용한 카운팅 정렬 슈도코드
  
```python
def CountingSort(A, B, k):
# A[1 .. n] -- 입력 리스트 사용된 숫자(1 ~ k)
{: #a-1-n-입력-리스트-사용된-숫자-1-~-k}
# B[1 .. n] -- 정렬된 리스트.
{: #b-1-n-정렬된-리스트}
# C[1 .. k] -- 카운트 리스트.
{: #c-1-k-카운트-리스트}
	C = [0]*k
  
    for i in range(0, len(B)):
	    C[A[i]] += 1
  
    for i in range(1, len(C)):
	    C[i] += C[i-1]
  
    for i in range(len(B)-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
a = [0,4,1,3,1,2,4,1]
b = [0]*len(a)
ContingSort(a, b, 5)
print(b)

List 2

2차원 List 구조

  • 1차원 List를 묶어놓은 List

  • 2차원 이상의 다차원 List는 차원에 따라 Index를 선언

  • 2차원 List의 선언: 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함

  • 파이썬에서는 데이터 초기화를 통해 변수 선언과 초기화가 가능함

List 초기화

  • 리스트 원소 나열, 리스트 축약형 등을 사용하여 초기화 가능

  • PythonTIL jupyter notebook 참조

2차원 List 입력 받기

  • for문, 원소 등 여러가지 방법이 있다.

2차원 List의 순회

  • n X m List의 n*m 개의 모든 원소를 빠짐없이 조사하는 방법
    1. 행 우선 순회

  • List의 행을 우선으로 List의 원소를 조사하는 방법

    행 우선 순회 예시

    ```python
    arr = [[0,1,2,3],[4,5,6,7],[8,9,10,11]]

    i : 행의 좌표, n = len(arr)

    {: #i-행의-좌표-n-len-arr}

    j : 열의 좌표, m = len(arr[0])

    {: #j-열의-좌표-m-len-arr-0}
    for i in range(len(arr)):
    for j in range(len(arr[i])):
    arr[i][j]# 필요한 연산 수행

2. 열 우선 순회
- List의 열부터 먼저 조사하는 방법
  
  ```python
  arr = [[0,1,2,3],[4,5,6,7],[8,9,10,11]]
# i : 행의 좌표, n = len(arr)
{: #i-행의-좌표-n-len-arr}
# j : 열의 좌표, m = len(arr[0])
{: #j-열의-좌표-m-len-arr-0}
  for j in range(len(arr)):# 행과 열 요소를 반대로
    for i in range(len(arr[i])):
        arr[i][j]# 필요한 연산 수행
  1. 지그재그 순회
    • List의 행을 좌우로 조사하는 방법
  arr = [[0,1,2,3],[4,5,6,7],[8,9,10,11]]
# i : 행의 좌표, n = len(arr)
{: #i-행의-좌표-n-len-arr}
# j : 열의 좌표, m = len(arr[0])
{: #j-열의-좌표-m-len-arr-0}
  for i in range(len(arr)):
    for j in range(len(arr[0])):
        arr[i][j + (m-1-2*j)*(i%2)]# 필요한 연산 수행

델타를 이용한 2차 List 탐색

  • 2차 List의 한 좌표에서 네 방향의 인접 List 요소를 탐색할 때 사용하는 방법

  • 델타 값은 한 좌표에서 네 방향의 좌표와 x, y의 차이를 저장한 List로 구현

  • 델타 값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근 가능

  • 이차원 List의 가장자리 원소들은 상하좌우 네 방향에 원소가 존재하지 않을 경우가 있으므로, Index를 체크하거나 Index의 범위를 제한해야 합니다.

    델타를 이용한 2차 List 탐색 예시

    ```python

    arr[0…n-1][0…n-1] : 2차원 List

    {: #arr-0-n-1-0-n-1-2차원-list}
    dx = [0, 0, -1, 1]# 상하좌우
    dy = [-1, 1, 0, 0]

    for x in range(len(arr)) :
    for y in range(len(arr[x])):
    for i in range(4) :
    testX = x + dx[i]
    testY = y + dy[i]
    print(arr[testX][testY])

#### 전치 행렬

- 행과 열의 값이 반대인 행렬을 의미

- 모든 좌표에 대하여 행과 열의 값을 바꾸게 되면 본래의 모습으로 되돌아오기 때문에 이를 주의해야 함
  
  > 전치 행렬 예시
  
```python
# i : 행의 좌표, len(arr)
{: #i-행의-좌표-len-arr}
# j : 열의 좌표, len(arr[0])
{: #j-열의-좌표-len-arr-0}
arr = [[1,2,3], [4,5,6], [7,8,9]]# 3*3 행렬 

for i in range(3):
    for j in range(3):
        if i<j:
            arr[i][j], arr[j][i] = arr[j][i], arr[i][j ]

zip 함수 활용

zip 함수는 주어진 배열들의 각각 위치의 서브 배열을 tuple로 묶은 1차원 리스트로 만들 수 있다.

이를 이용해 배열을 조작할 수 있음.

zip 함수를 활용한 배열 회전

lists = []
#  정사 배열 생성
{: #정사-배열-생성}
for i in range(1,10):        
    temp = [[j+k*i for j in range(i)] for k in range(i)]
    lists.append(temp)

# 배열 90도 회전
{: #배열-90도-회전}
def spin(arr):
    return list(zip(*arr[::-1]))
# 배열 -90도 회전
{: #배열-90도-회전}
def spin_rev(arr):
    return list(reversed(list(zip(*arr))))

# 배열 전용 출력
{: #배열-전용-출력}
def print_arr(rev_arr,origin, arr, arr2):
    print("*"*20)
    for i in range(len(arr)):
        print(rev_arr[i], end="   ")
        print(origin[i], end="   ")
        print(arr[i], end="   ")
   x     print(arr2[i])
    print("arr: ", len(arr), "X", len(arr))
    print("*"*20)

# after spin
{: #after-spin}
for arr in lists:
    print_arr(spin_rev(arr), arr, spin(arr), spin(spin(arr)))

print(*[[1,2],[3,4]])# *은 내부 element를 각각의 부분 배열로 만들어준다.

부분 집합

부분 집합 문제

예시) 유한개의 정수로 이루어진 집합이 있을 때 이 집합의 부분 집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는가?

  • 완전 검색 기법으로 문제를 풀기 위해서는 모든 부분집합을 생성후 각 부분 집합의 합을 계산함

  • 부분집합의 총 개수는 집합의 원소의 개수가 n 개일때 공집합을 포함해서 2^n개

  • 각 원소를 부분집합에 포함시키거나 포함시키지 않는 경우를 1과 0으로 표현해서 알고리즘으로 표현 가능

Loop를 이용하여 확인하고, 부분 집합을 생성하는 방법

bit = [0, 0, 0, 0]# 비트 리스트: 각 원소를 포함할지 말지 결정하는 List
for i in range(2):
    bit[0] = i# 0번째 원소
	for j in range(2):
	    bit[1] = j# 1번째 원소
		    for k in range(2):
				bit[2] = k# 2번째 원소
			    for l in range(2):
			        bit[3] = l# 3번째 원소
print(bit)# 생성된 부분집합 출력

부분 집합 문제 알고리즘 2

  • 비트 연산자 : 0과 1로 이루어진 이진수에 대한 연산을 수행하는 연산자

  • 비트연산자 종류 : C나 C++ 정리 참조

  • ex) 1« n:2n^n == 원소가 n개일 경우의 모든 부분 집합의 수를 의미함

  • ex) i & (i«j): 1 == i의 j번 비트가 1인가? (비트번호는 0번부터 시작)

  • 만약 0이면 and 연산자에 의해 0, 1이면 둘다 1이므로 1이 나온다.(특정비트 검사)

비트 연산을 이용한 간결한 부분집합 생성

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)# n:원소의 개수

for i in range(1<<n) :# 1<<n: 부분 집합의 개수
    for j in range(n) :# 원소의 수만큼 비트를 비교함
        if i&(1<<j) :# i의 j번째 비트가 1이면 j번째 원소 출력
	        print(arr[j], end=",")
    print()

검색

검색 개요

  • 저장되어 있는 자료 중에서 원하는 항목(목적하는 탐색키(Search key : 자료를 구별하여 인식할 수 있는 키)를 가진 항목)을 찾는 작업

  • 순차검색, 이진검색, 인덱싱 등의 방법이 있음

순차 검색

  • 일렬로 되어 있는 자료를 순서대로 검색하는 방법

  • List나 연결 List 등 순차구조로 구현된 자료구조에서 유용함

  • 구현이 쉽지만 검색대상이 많은 경우 수행시간 증가로 비효율적

  • 정렬 되지 않은 경우 :
    1) 첫번째 원소부터 순서대로 검색대상과 키 값이 같은 원소가 있는지를 비교하여 찾음
    2) 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
    3) 자료구조의 마지막에 갈 때까지 검색 대상을 찾지 못하면 검색 실패

  • 찾고자 하는 원소의 순서따라 비교횟수 결정, 평균 비교 횟수는 n+1/2 복잡도 O(n)

  • 정렬 된 경우:
    1) 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
    2) 자료를 순차적으로 검색하면서 키값을 비교함
    3) 원소의 키 값이 검색 대상의 카 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료함
  • 정렬되어 있으므로 검색 실패를 반환하는 경우 평균 비교횟수가 반으로 줄어듦
  • 시간 복잡도 O(n)
이진 검색

  • 효율적인 검색 방법, 자료의 가운데 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속하는 방법

  • 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 빠르게 검색을 수행함

  • 이진 검색을 하기 위해서는 __자료가 정렬된 상태__여야함

  • 정렬된 데이터 n개가 있는 경우의 시간 복잡도 : O(logN)
    1) 자료의 중앙에 있는 원소를 선택

2) 중앙 원소의 값과 찾고자 하는 목표 값을 비교

3) 목표값 < 중앙 원소 값 : 자료의 왼쪽 반에 대해서 새로 검색을 수행
목표값 > 중앙 원소 값 : 자료의 오른쪽 반에 대해서 새로 검색을 수행

4) 찾고자 하는 값을 찾을 때까지 [ 1 ~ 3 ]의 과정을 반복

  • 시작점과 종료점을 이용해 검색을 반복 수행

  • 자료에 삽입이나 삭제 발생시, List의 상태를 항상 정렬 상태로 유지 작업 필요

인덱스

  • 데이터베이스에서 유래 테이블에 대한 동작 속도를 높임, 룩업 테이블 등으로도 불림

  • 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블 저장에 필요한 디스크 공간보다 작음 (인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목은 없음)

  • List를 사용한 인덱스 (대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없음, 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 List 인덱스를 사용할 수 있음)

  • 원본 데이터에 데이터가 삽입될 경우, 상대적으로 크기가 작은 인덱스 List를 정렬하기 때문에 속도가 빠름

정렬

셀렉션 알고리즘

  • 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
  • 최소값, 최대값, 혹은 중간값을 찾는 알고리즘을 의미하기도 함
    셀렉션 선택 과정
    1) 정렬 알고리즘을 이용하여 자료를 정렬

2) 원하는 순서에 있는 원소 가져오기

k번째로 작은 원소를 찾는 알고리즘

   def select(list, k):
    for i in range(0,k):
        minIndex = i
        for j in range(i+1, len(list)):
            if list[minIndex] &#38;#62; list[j]:
                minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]
    return list[k-1]

  • 1번부터 k번째까지 작은 원소들을 찾아 List의 앞쪽으로 이동시키고, List의 k번째를 반환

  • k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 함

선택 정렬

  • 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식

  • 셀렉션 알고리즘을 전체 자료에 적용한 것
    정렬 과정
    1) 주어진 List 중에서 최소값을 찾음
    2) 그 값을 List의 맨 앞에 위치한 값과 교환
    3) 맨 처음 위치를 제외한 나머지 List를 대상으로 위의 과정을 반복

  • 시간 복잡도 ,평균, 최악 전부 O(n^2), 비교와 교환 방식, 버블 삽입정렬보다 나음

    선택 정렬 알고리즘

    ```python
    def selectionSort(a) :
    for i in range(0, len(a)-1):
    min = i
    for j in range(i+1, len(a)):
    if a[min] &#62; a[j]:
    min = j
    a[i], a[min] = a[min], a[i]

### String 1

#### 문자 표현

#### 컴퓨터에서의 문자표현

- 메모리는 숫자만을 저장할 수 있기 때문에 A라는 글자의 모양 그대로 비트맵으로 저장하는 방법을 사용하지 않는 한 (메모리 낭비 심각) 각 문자에 대해서 대응되는 숫자를 정해놓고 이것을 메모리에 저장하는 방법이 사용됨

- 코드 체계
  
  - 영어가 대소문자 합쳐서 52이므로 6(64가지) 비트면 모두 표현 가능
  - 네트워크 발전 이후 표준화를 위해 ASCII 인코딩 표준 제정
  1) ASCII(아스키) 

- 문자 인코딩 표준, 7bit 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어 문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 이루어짐
2) 확장 아스키
- 표준 문자 이외의 악센트 문자, 도형문자, 특수문자, 특수 기호 등  128개를 추가

- 1Byte 내의 8bit를 모두 사용하여 추가적인 문자 표현 가능

- 컴퓨터 생산자와 소프트웨어 개발제에게 할당된 확장 부호는 표준 아스키와 다르게 서로 다른 프로그램이나 컴퓨터 사이에 교환 불가능

- 프로그램이나 컴퓨터/프린터가 그것을 해독할 수 있도록 설계되어 있어야만 올바로 해독 가능
3) 유니 코드
- 다국어 처리를 위한 표준, 각 국가들은 자국의 문자를 표현하기 위해 코드체계 제작

- 각국의 코드체계가 다른 국가에서 잘못 해석되는 문제 발생

- 다국어 처리를 위해 표준을 마련한것이 유니코드, 

- CharacterSet: 유니코드를 저장하는 변수의 크기를 정의, UCS-2, UCS-4 등

- 유니코드 인코딩 (UTF:Unicode Transformation Format)
  
  - UTF-8(in web), MIN: 8bit, MAX: 32bit(1 Byte * 4)
  - UTF-16(in windows, Java), MIN: 16bit, MAX: 32bit(2 Byte * 2)
  - UTF-32(in unix), MIN: 32bit, MAX: 32bit(4 Byte * 1)

- 파이썬은 2.x 버전 때는 ASCII, 3.x버전은 유니코드 UTF-8로 인코딩

- 2.X 버전은#-*- coding:utf-8 -*- 로 변환해야했다.

- 3.x 버전은 생략해도 되고 바꾸고 싶을때 기입하여 인코딩 방식 전환 가능

#### 문자열의 분류

- 문자열(String)
- Fixed length : 고정길이 문자열, Variable length: 가변길이 문자열
- Length controlled : java 언어에서의 문자열, 맨앞에 문자열길이 저장
- Delimited : C언어에서의 문자열, 문자열 끝을 알리는 부호를 맨 끝에 저장(\0)
- C : 아스키 코드로 저장, java: 유니코드 UTF-16으로 저장, python : UTF_8
- 파이썬은 문자 하나와 문자열을 동일하게 취급함, 시퀀스 자료형
- 인덱싱, 슬라이싱 연산들을 사용할 수 있음
- 문자열을 뒤집기, 비교, 숫자로 변환 등을 할줄 알아야함

### 02 패턴 매칭

#### 패턴 매칭 알고리즘

- 패턴매칭: 본문에서 특정한 문자열 찾는 것
  
#### 고지식한 알고리즘(Brute Force)

- 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식, M = 문자열 패턴의 길이, n = 총 문자열 길이

- 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴 비교하여 O(MN)이 됨
  
> 고지식한 알고리즘 예시
  
```python
p = &#34;is&#34;# 찾을 패턴
t = &#34;This is a book~!&#34;# 전체 텍스트
M = len(p)# 찾을 패턴의 길이
N = len(t)# 전체 텍스트의 길이

def BruteForce(p, t):
    i = 0# t의 인덱스
    j = 0# p의 인덱스
    while j &#38;#60; M and i &#38;#60; N :
        if t[i] != p[j]:
            i = i - j
            j = -1
        i = i + 1
        j = j + 1
	    if j == M : return i - M# 검색 성공
	    else: return -1# 검색 실패

KMP 알고리즘

  • 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행

  • 패턴을 전처리하여 배열 nextM을 구해서 잘못된 시작을 최소화함

  • 시간 복잡도 O(M+N)

보이어-무어 알고리즘

  • 오른쪽에서 왼쪽으로 비교, 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘

  • 앞부분 보단 끝부분에서 불일치가 일어날 확률이 높다는 성질 이용

  • 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 패턴의 길이 만큼이 됨

  • 시간복잡도 최악의 경우 O(MN)이지만, 일반적으로 O(n)보다 적음

01 Stack 자료구조의 개념

Stack의 특성

  • 프로그램에서 중요성과 활용도가 매우 높은 자료구조

    1) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조임
    2) 스택에 저장된 자료는 선형구조(자료 간의 관계가 1대 1의 관계)를 가짐

    • 비선형 구조 : 자료 간의 관계가 1대 N의 관계를 가짐(예: 트리)
      3) 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음
      4) 마지막에 삽입한 자료를 가장 먼저 꺼냄(후입선출, LIFO)
    • 1, 2, 3 순으로 자료를 삽입한 후 꺼내면 역순으로 3, 2, 1 순으로 꺼내짐

Stack의 구현

  • 자료를 선형으로 저장할 저장소로, C에서는 배열, Python에서는 리스트를 사용하며

  • 스택에서 마지막 삽입된 원소의 위치를 top이라고 부름

  • 연산에 관련하여

    • 삽입 : 저장소에 자료를 저장하고 보통 push라고 부름

    • 삭제 : 저장소에서 자료를 꺼냄, 꺼낸 자료는 삽입한 자료의 역순으로 꺼냄, pop이라고 부름

    • isEmpty : 스택이 공백인지 아닌지를 확인하는 연산

    • peek : 스택에 top에 있는 item의 값을 반환

Stack의 연산

  • 빈스택에 원소를 집어넣으면 나중에 넣은 것이 맨위 (Push 연산)

push 알고리즘

def push(item):
    s.append(item)

  • python의 리스트는 크기의 제한이 없으므로, overflow 문제 고려안해도 됨,

  • top 변수 또한 필요 없음, 자동으로 append를 통해 맨 마지막에 삽입 가능

pop 알고리즘

def pop():
    if len(s) == 0:
  # underflow
        return
    else:
        return s.pop(-1)

  • 리스트를 사용하면 구현이 용이하지만, 리스트 크기 변경 작업이 큰 overhead 발생 작업으로 많은 시간이 소요

  • 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해놓거나, 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하면 된다.

  • 그러면 구현이 어려운 대신 리스트 크기 변경작업이 잦을 때 성능이 좋다.

Stack 1

Stack의 운용

괄호검사
  • 알고리즘 TIL의 bracketExamination 참조
함수 호출 관리(Function call)

  • 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리

  • 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조의 스택을 이용하여 수행순서 관리

  • 함수 호출 발생시 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입

  • 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)을 삭제(pop)하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀

  • 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 됨

재귀호출

  • 자기 자신을 호출하여 순환 수행되는 것 ex) factorial, fibonacci

  • 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음

  • 디버깅이 어렵고 잘못작성하게 되면 수행시간이 많이 소요됨

extra) 재귀호출의 기본

  • 특징

    • 자기 자신을 호출하지만 사용하는 메모리 영역이 구분되므로 다른 함수를 호출 하는 것과 같음

    • 정해진 횟수만큼, 혹은 조건을 만족할 때 까지 호출을 반복함

      • 호출 횟수에 대한 정보는 인자로 전달, 정해진 회수에 다다르면 호출 중단

Memoization

피보나치 수열

  • 피보나치 수열을 재귀함수로 작성 가능하다
def fibo(n):
    if n &#38;#60; 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)
  • 이러한 방식은 중복 호출이 상당히 많아서 비효율적이다. 예를 들어 fib(6)은 같은 값을 가지는 fib(1) = 1을 8번 구한다.

Memoization(메모이제이션)

  • 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술

  • DP(동적 계획법)의 핵심이 되는 기술

    memoization 방법을 적용한 알고리즘

# memo를 위한 리스트를 생성하고,
&#123;: #memo를-위한-리스트를-생성하고&#125;
# memo[0]을 0으로 memo[1]는 1로 초기화 한다
&#123;: #memo-0-을-0으로-memo-1-는-1로-초기화-한다&#125;
def fibo1(n):
    global memo
    if n &#38;#62; = 2 and len(memo) &#38;#60;= n:
         memo.append(fibo1(n-1)+fibo1(n-2))
    return memo[n]
  
memo = [0, 1]

DP(동적계획법) 알고리즘

DP(동적계획법)

  • Dynamic Programming의 약자, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘

  • 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결, 최종적으로 원래 주어진 입력의 문제를 해결

DP 피보나치 수 함수

1) 문제를 부분 문제로 분할

2) 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구함

3) 결과를 테이블에 저장 후, 테이블에 저장된 부분 문제 해로 상위 문제 해 구함

4) 부분 문제의 답으로 본 문제의 답을 얻을 수 있는 최적 부분구조로 이뤄져야 가능

DP 적용 피보나치 수 함수

def fibo2(n):
    f = [0, 1]
   
    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])
   
    return f[n]

DP 구현방식

1) recursive (재귀함수) 방식 : fibo1()

  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있음
    2) iterative (반복문) 방식 : fibo2()
  • Memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현하는 것이 성능 면에서 보다 효율적

DFS(깊이 우선 탐색)이란?

DFS(깊이 우선 탐색)

  • 비선형 구조인 그래프 구조는 표현된 모든 자료를 빠짐없이 검색하는 것이 중요

    • 그러한 알고리즘으로는 아래가 있다.
      1) 깊이 우선 탐색 (Depth First Search, DFS)
      2) 너비 우선 탐색 (Breadth First Search, BFS)

  • 깊이 우선 탐색은 stack을 이용하여 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색 후, 더이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴, 그후 다른 방향으로 정점을 탐색하고 결국 모든 정점을 방문

  • 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복하므로, 후입선출 구조의 스택을 사용

    DFS 알고리즘의 슈도코드

visited[],stack[] 초기화
DFS(v)
    v방문;
    visited[v]&#38;#60;-true;
    do &#123;
        if (v의 인접 정점 중 방문 안 한 w 찾기)
            push(v);
        while(w)&#123;
            w 방문;
            visited[w] &#38;#60;- true;
            push(w);
            v&#38;#60;-w;
            v의 인접 정점 중 방문 안 한 w 찾기
        &#125;
        v &#38;#60;- pop(stack);
    &#125; while(v)
end DFS()

stack2

계산기

  • 문자열 계산식을 스택을 이용하여 결과값 계산하는 방법으로 중위 표기법 수식을 후위표기법으로 변경하는 방법이 있다.

  • 중위 표기법(infix notation): 연산자를 피연산자의 가운데 표기하는 방법 (일반적으로 우리가 사용하는 방법 ex)A+B)

  • 후위 표기법(postfix notation): 연산자를 피연산자 뒤에 표기하는 방법 (컴퓨터가 연산할때 자주 사용하는 방법 ex)A B + )

중위표기식을 후위표기식으로 변환

  1. 중위표기식의 후위표기식으로 변환 방법 1

    1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현
    -((A*B)-(C/D))

    2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동

    • ((A B) * (C D)/)-

    3) 괄호 제거

    • AB*CD/-

  2. 중위표기식 후위표기식 알고리즘 (스택이용)

    1) 입력 받은 중위표기식에서 토큰을 읽음
    2) 토큰이 피연산자이면 토큰을 출력 (stack 거쳐가지 않음)
    3) 토큰이 연산자(괄호포함)일 경우 (stack 거쳐감)

    • 우선선위가 높으면 -> 스택에 push
    • 우선순위가 안 높으면 -> 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push ( ‘(‘ 는 ‘)’를 만날 때까지 pop 되면안되므로 우선순위가 가장 작다. 나머지는 동)
    • 만약에 top에 연산자가 없으면 -> push
      4) 토큰이 오른쪽 괄호 ‘)’일 경우
    • 스택 top에 왼쪽 괄호 ‘(‘가 올 때까지 스택에 pop 연산을 수행
    • pop한 연산자를 출력
    • 왼쪽 괄호를 만나면 pop만 하고 출력하지는 않음( (, ) 둘다 안쓰고 버려짐)
      5) 중위 표기식에 더 읽을 것이 없다면 중지, 더 읽을 것이 있다면 1부터 반복
      6) 스택에 남아있는 연산자를 모두 pop하여 출력
    • 스택 밖의 왼쪽 괄호는 우선 순위가 가장 높으며,
    • 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮음

    • 토큰 : 수식에서 의미 있는 최소 단위

    • icp(in-coming priority)

    • isp(in-stack priority)

      if (icp > isp) push()
      else pop()

      토큰 우선순위

      토큰 (낮을 수록 우선순위가 낮다) ISP(스택 안에서) ICP(외부에서)
      ) - -
      *, / 2 2
      +, - 1 1
      ( 0 3
           
    • 자세한 예시는 APS 기본 참조

후위표기법 알고리즘
1) 피연산자를 만나면 스택에 push함
2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push함
3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력
계산시 주의사항 : 후위 표기식을 계산 시, 피연산자를 스택에 쌓아 계산

  • 파이썬 내장함수인 eval() 함수로 처리할 수도 있음

백트래킹

백트래킹 기법의 정의

  • 백트래킹(Backtracking): 해를 찾는 도중에 막히면, 즉 해가 아니면 되돌아가서 다시 해를 찾아가는 기법

  • 어떤 노드의 유망성을 점검 후, 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감

  • 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 함, 반대로 해답 가능성이 있으면 유망하다고 함

  • 가지치기(Pruning): 유망하지 않은 노드가 포함되는 경로는 더 이상 고려 안함

  • 최적화(Optimization) 문제 해결 가능

  • 결정(Decision) 문제 해결 가능

  • 문제의 조건을 만족하는 해가 존재하는지의 여부를 ‘yes’ 또는 ‘no’로 답하는 문제

  • 미로 찾기, n-Queen 문제, Map coloring, 부분 집합의 합(Subset Sum ) 문제 등

백트래킹 기법의 특징

  • 어떤 노드에서 출발하는 경로가 해결책으로 이어질것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임(가지치기, Prunning)

  • 불필요한 경로의 조기 차단, 깊이 우선탐색은 모든 경로와 후보를 추적함

  • 백트래킹을 가하면 경우의 수가 줄어들지만 최악의 경우는 깊이 우선탐색과 동일함

1) 상태 공간 Tree의 깊이 우선 탐색을 실시

2) 각 노드가 유망한지를 점검

3) 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가 검색을 계속

일반 백트래킹 알고리즘

  • 주로 nqueen 문제에 씀, n*n의 정사각형 안에 n개의 queen을 배치하는 문제로, 모든 queen은 자신의 일직선 상 및 대각선 상에 아무것도 놓이지 않아야 함

    일반 백트래킹 대략적인 슈도 코드
    ```python
    def checknode (v):# node
    if promissing(v):
    if there is a solution at v:
    write the solution
    else:
    for u in each child of v :
    checknode(u)

##### Power Set

- 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합

- 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n이 나옴
  
  > Power Set을 구하는 백트래킹 알고리즘
  
  ```python
  def backtrack(a, k, input):
    global MAXCANDIDATES
    c = [0]*MAXCANDIDATES
  
    if k == input:
        process_solution(a,k)# 답이면 원하는 작업을 한다
    else:
        k+=1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
            a[k] = c[i]
            backtrack(a, k, input)
  
  def construct_candidates(a, k, input, c):# 후보군 구하는 함수
      c[0] = True
      c[1] = False
      return 2
  
  def process_solution(a, k) :
      print(&#34;(&#34;, end=&#34;&#34;)
      for i in range(k+1):
          if a[i]:
              print(i, end=&#34; &#34;)
      print(&#34;)&#34;)
  
  MAXCANDIDATES = 100
  NMAX = 100
  a = [0]*NMAX
  backtrack(a, 0, 3)

순열을 구하는 백트래킹 알고리즘

  def backtrack(a, k, input):
    global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
  
    if k == input:
        for i in range(1, k+1):
            print(a[i], end=&#34; &#34;)
        print()
    else:
        k += 1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
            a[k] = c[i]
            backtrack(a, k, input)

def construct_candidates(a, k, input, c):
in_perm = [False] * NMAX

for i in range(1, k):
    in_perm[a[i]] = True

ncandidates = 0
for i in range(1, input+1):
    if in_perm[i] == False:
        c[ncandidates] = i
        ncandidates += 1
    return ncandidates

#### 분할 정복

##### 분할정복 알고리즘

1. 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눔

2. 정복(Conquer) : 나눈 작은 문제를 각각 해결

3. 통합(Combine) : (필요하다면) 해결된 해답을 모음

   &#38;#62; 보통의 거듭 제곱(Exponentiation) 알고리즘 : O(n)

   ```python
   def Power(Base, Exponent):
    if Base == 0 : return 1
    result = 1# Base^0은 1이므로
    for i in range(Exponent):
        result *= Base
    return result

분할 정복 기반의 알고리즘 : O(log2n)

def Power(Base, Exponent):
 if Exponent == 0 or Base == 0:
     return 1
 if Exponent &#37; 2 == 0:
     NewBase = Power(Base, Exponent/2)
     return NewBase * NewBase
 else :
     NewBase = Power(Base, (Exponent-1)/2)
     return (NewBase * NewBase) * Base
  • 거듭 제곱을 반으로 나눈 후 합치는 방식
퀵 정렬

퀵정결과 합병 정렬 비교

  합병 정렬 퀵 정렬
공통점 주어진 리스트를 두개로 분할하고, 각각을 정렬
차이점 분할할 때, 단순하게 두 부분으로 나눔 기준 아이템(Pivot Item)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킴
  각 부분 정렬이 끝난 후, 합병 이란 후처리 작업 필요 후처리 작업 필요 없음

퀵 정렬 알고리즘

def quickSort(a, begin, end):
if begin &#38;#60; end:
    p = partition(a, begin, end)
    quickSort(a, bdgin, p-1)
    quickSort(a, p+1, end)

주어진 리스트에서 피봇을 구하는 알고리즘

def partition(a, begin, end):
    pivot = (begin + end) // 2
    L = begin
    R = end
    while L &#38;#60; R:
        while(a[L]&#38;#60;a[pivot] and L&#38;#60;R):L+=1
        while(a[R]&#38;#62;=a[pivot] and L&#38;#60;R):R-=1
        if L &#38;#60; R:
            if L==pivot : pivot = R
            a[L], a[R] = a[R], a[L]
    a[pivot], a[R] = a[R], a[pivot]
    return R
  • 퀵정렬의 최악의 시간 복잡도는 O(n^2)로 합병정렬에 비해 좋지않지만
  • 평균 시간 복잡도는 nlogn으로 오히려 좋다

정렬 알고리즘의 특성 비교

알고리즘 평균 수행시간 최악 수행시간 알고리즘 기법 비고
버블 정렬 O(n^2) O(n^2) 비교와 교환 코딩이 가장 손쉬움
카운팅 정렬 O(n+K) O(n+K) 비교환 방식 n이 비교적 작을 때만 가능
선택 정렬 O(n^2) O(n^2) 비교와 교환 교환의 회수가 버블, 삽입정렬보다 작음
퀵 정렬 O(n logn) O(n^2) 분할 정복 최악의 경우 O(n^2)이지만 평균적으로 가장 빠름
삽입 정렬 O(n^2) O(n^2) 비교와 교환 n의 개수가 작을 때 효과적
병합 정렬 O(n logn) O(n logn) 분할 정복 연결 List의 경우 가장 효율적인 방식, 메모리 사용량 큼

Queue

01 Queue

Queue 자료 구조의 개념

1) 삽입, 삭제의 위치가 제한적인 자료구조

  • 뒤에서 삽입, 앞에서는 삭제만 이루어짐
  • 삽입 : enQueue, 삭제: deQueue
    2) 선입선출구조(FIFO: First In First Out)
  • 큐에 삽입한 순서대로 원소가 저장
  • 가장 먼저 삽입(First in)된 원소는 가장 먼저 삭제(First Out)됨
    3) 큐의 예: 서비스 대기 행렬 (줄서기)
Queue의 구조 및 기본 연산

큐의 주요 연산
| 연산 | 기능 |
| ————- | ————————————————– |
| enQueue(item) | 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 |
| deQueue() | 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 |
| createQueue() | 공백 상태의 큐를 생성하는 연산 |
| isEmpty() | 큐가 공백상태인지를 확인하는 연산 |
| isFull() | 큐가 포화상태인지를 확인하는 연산 |
| Qpeek() | 큐의 앞족(front)에서 원소를 삭제없이 반환하는 연산 |

Queue의 연산과정

1) 공백 큐 생성 : createQueute();

  • front = rear = -1
    -1: 없음(가상의 공간), 0: [], 1: [], 2: []
    front, rear = -1
    2) 원소 A 삽입: enQueue(A);
    -1: 없음(가상의 공간), 0: [A], 1: [], 2: []
  • front= -1 , rear + 1, rear = 0
    3) 원소 B 삽입: enQueue(B);
    -1: 없음(가상의 공간), 0: [A], 1: [B], 2: []
  • front= -1 , rear + 1, rear = 1
    4) 원소 반환/삭제: deQueue();
    -1: 없음(가상의 공간), 0: [], 1: [B], 2: []

  • front= 0 , front + 1, rear = 1

  • A가 반환됨
    5) 원소 C 삽입: enQueue(C);
    -1: 없음(가상의 공간), 0: [], 1: [B], 2: [C]
  • front= 0 , rear + 1, rear = 2
    6) 원소 반환/삭제: deQueue();
    -1: 없음(가상의 공간), 0: [], 1: [], 2: [C]

  • front= 1 , front + 1, rear = 2

  • B가 반환됨
    7) 원소 반환/삭제: deQueue();
    -1: 없음(가상의 공간), 0: [], 1: [], 2: []

  • front= 2 , front + 1, rear = 2

  • C가 반환됨

  • front값과 rear값이 같아짐 == 큐가 비어있다고 판단 가능
Queue의 종류

  • 선형큐: 간단하고 기본적인 형태 (리스트로 구현)

  • 원형큐: 선형에서 발전된 형태 (리스트로 구현)

  • 연결큐: 연결 리스트 형식을 이용

  • 우선순위 큐: 이들을 응용한 큐

02 Queue의 종류

선형 Queue
선형 큐의 특징
  1. 1차원 리스트를 이용한 큐
    • 큐의 크기 = 리스트의 크기

  • front: 저장된 첫 번째 원소의 인덱스

  • rear: 저장된 마지막 원소의 인덱스
    1. 상태 표현

  • 초기 상태 : front = rear = -1

  • 공백 상태 : front = rear

  • 포화 상태 : rear = n-1(n: 리스트의 크기, n-1: 리스트의 마지막 인덱스)
    1. 문제점

    1) 잘못된 포화 상태 인식:

    • 리스트의 크기를 고정, 사용할 큐의 크기만큼을 미리 확보, 메모리의 낭비 발생
    • 삽입, 삭제 반복시, 리스트 앞부분 공간이 있어도 rear=n-1이면 포화상태로 인식하여 더 이상의 삽입을 수행할 수 없음
    • ex) n = 5, front= 3, rear=4이면 포화상태, 실제로는 3메모리 더 남음

  1. 장점: 삽입, 삭제의 처리속도 빠름, 대신 메모리 낭비가 심함

    • 원형 큐 사용으로 메모리 절약 가능

    • 파이선 리스트는 동적이므로 메모리 절약 가능, 대신 연산 수행 시간 소모

    • 단순 연결 리스트로 구현한 큐 사용으로 메모리 동적 확보 가능

    • 큐 라이브러리를 사용하여 구현도 가능

선형큐의 구현

  • 크기 n인 1차원 리스트 생성, front, rear = -1로 초기화

  • 위 Queue의 연산과정 참조

    큐의 삽입(enQueue(item)) 코드

def enQueue(item):
    global rear
    if isFull() : print(&#34;Queue_Full&#34;)
    else :
        rear += 1
        Q[rear] = item

큐의 반환 및 삭제(deQueue()) 코드

def deQueue(item):
    glbal front
    if isEmpty():print(&#34;Queue_Empty&#34;)
    else:
        front += 1
        return Q[front]

공백상태 및 포화상태 검사: isEmpty(), isFull()

def isEmpty():
    return front == rear
  
def isFull():
      return rear == len(Q) - 1

  • front == rear일 경우 공백 상태

  • rear == n-1일 경우 포화 상태

    값 검색: Qpeek()

  • 가장 앞에 있는 원소를 검색하여 반환하는 연산

  • 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐에 첫 번째에 있는 원소를 반환

def Qpeek():
    if isEmpty(): print(&#34;Queue_Empty&#34;)
    else: return Q[front+1]

  • 가장 앞에 있는 원소를 검색하여 반환하는 연산

  • 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환

원형 Queue
  • 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용함, 즉, 인덱스 0과 인덱스 n-1이 연결됨
원형 Queue의 특징

1) 초기 공백 상태

  • front = rear = 0
    2) index의 순환
  • front와 rear의 위치가 리스트의 마지막 인덱스인 n-1을 가리킨 후, 논리적 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야함
  • 이를 위해 나머지 연산자 %를 사용
    3) front 변수

  • 공백 상태와 포화 생태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠

    원형 큐와 선형 큐의 삭제 위치 비교

테이블 인덱스 삽입 위치 삭제 위치
선형 큐 rear = rear + 1 front = front + 1
원형 큐 rear = (rear + 1) % n front = (front + 1) % n
원형 큐의 기본 연산과정

1) 큐 생성: front, rear 값이 0으로 초기화 (n = 4)

2) 원소 A 삽입: enQueue(A); : front = 0, rear = (rear+1) % len(cQ), rear = 1 Q[1] = A

3) 원소 B 삽입: enQueue(B); : front = 0, rear = (rear+1) % len(cQ), rear = 2 Q[2] = B

4) 큐 삭제: front = (front + 1) % len(cQ), front = 1, rear = 2 Q[1] = None,

5) 원소 C 삽입: enQueue(C); : front = 0, rear = (rear+1) % len(cQ), rear = 3 Q[3] = C

6) 원소 D 삽입: enQueue(D); : front = 0, if rear > 3: rear = 0,rear = (rear+1) % len(cQ) Q[4] = D

  • front가 있는 자리는 사용하지 않으므로 Q는 포화 상태
원형 큐의 구현

  • 초기 공백큐 생성은 선형 큐와 다르지 않되, front, rear = 0

    공백 상태 및 포화 상태 검사: isEmpty(),isFull()

    ```python
    def isEmpty():
    return front == rear

    def isFull():
    return (rear+1) % len(cQ) == front

- 공백 상태 : front = rear

- 포화 상태 : 삽입할 rear의 다음 위치 = 현재 front

- (rear + 1) % n = front
  
  > 삽입: enQueue(item)
  
  ```python
  def enQueue(item):
    global rear
    if isFull():
        print(&#34;Queue_Full&#34;)
    else:
        rear = (rear + 1) &#37; len(cQ)
        cQ[rear] = item

  • 마지막 원소 뒤에 새로운 원소를 삽입하기위해,

    1) rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련함

    • rear <- (rear +1) % n;

    2) 인덱스에 해당하는 리스트 원소 cQ[rear]에 item을 저장

    삭제: deQueue(), delete()

    ```python
    def deQueue():
    global front
    if isEmpty():
    print("Queue_Empty")
    else:
    front = (front + 1) % len(cQ)
    return cQ[front]

  def delete():
  
      global front
      if isEmpty() :
          print("Queue_Empty")
      else:
          front = (front + 1) % len(cQ)
  • 가장 앞에 있는 원소를 삭제하기 위해
    1) front 값을 조정하여 삭제할 자리를 준비함

2) 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능을 함

리스트의 특성을 사용한 Queue

3) 파이썬의 리스트 특성을 사용한 큐

  • 리스트는 크기를 동적으로 변경할 수 있음
  • 메모리 절약
  • 삽입, 삭제 시 복사, 데이터를 이동시키는 연산을 수행하는데 많은 시간 소모

4) 리스트의 메서드

  • append와 pop을 이용
    3) front는 리스트의 맨 앞: -1

4) rear는 리스트의 맨 뒤: len(queue) -1

&#62; 리스트 메서드 큐

def isEmpty():
return len(queue) == 0

def enQueue(item):
queue.append(item)

def deQueue():
if isEmpty():
print(“Queue_Empty”)
else:
return queue.pop(0)

def Qpeek():
if isEmpty():
print(“Queue_Empty”)
else:
return queue[0]

##### 연결 Queue

&#38;#62; 연결 큐의 특징

1. 단순 연결 리스트(Linked List)를 이용한 큐

   - 큐의 원소: 단순 연결 리스트의 노드
   - 큐의 원소 순서: 노드의 연결 순서, 링크로 연결되어 있음
   - front: 첫 번째 노드를 가리키는 링크
   - rear: 마지막 노드를 가리키는 링크

2. 상태 표현

   - 초기 상태: front = rear = None

   - 공백 상태: front = rear = None

###### 연결 큐의 연산 과정
1) 큐 생성 createLinkedQueue();

   - front와 rear의 값을 None으로 쵝화

2) 원소 A 삽입 : enQueue(A); front, rear 값 모두 A 위치 가리킴

3) 원소 B 삽입 : enQueue(B); front는 A를 가리킴, A의 링크, rear 값은 B를 가리킴

4) 원소 삭제: deQueue(); front와 rear가 B를 가리킴, A 삭제

5) 원소 C 삽입: enQueue(C); front는 B, B의 링크와 rear는 C를 가리킴

6) 원소 삭제: deQueue(); front와 rear가 C를 가리킴 B 삭제

7) 원소 삭제: deQueue(); front와 rear가 None을 가리킴 C 삭제

##### 연결 큐의 구현

8) createLinkedQueue(): 리스트 노드 없이 포인터 변수만 생성함

   - front = None, rear = None으로 초기화

9) isEmpty(): 공백상태: front = rear = None

   ```python
   def isEmpty():
    return front == None

10) enQueue(item):

1) 새로운 노드 생성 후 데이터필드에 item 저장

2) 연결 큐가 공백인 경우, 아닌 경우에 따라 front, rear 변수 지정
   
   > enQueue(item)
   
   ```python
   def enQueue(item):# 연결 큐의 삽입 연산
   global front, rear
   newNode = Node(item)# 새로운 노드 생성
   if isEmpty():# 큐가 비어있다면
    front = newNode
   else :
    rear.next = newNode
   rear = newNode

11) deQueue():
    
    1) old가 지울 노드를 가리키게 하고, front 재설정
    
    2) 삭제 후 공백 큐가 되는 경우, rear도 None로 설정
    
    3) old가 가리키는 노드를 삭제하고 메모리 반환
       
       > deQueue()
       
       ```python
       def deQueue():# 연결 큐의 삭제 연산
       global front, rear
       if isEmpty():
        print(&#34;Queue_Empty&#34;)
        return None
       
       item = front.item
       front = front.next
       if isEmpty():
        rear = None
       return item

파이썬으로 구현한 연결 큐

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

    def enQueue(item):# 연결 큐의 삽입 연산
        global front, rear
        newNode = Node(item)# 새로운 노드 생성
        if front == None:# 큐가 비어있다면
            front = newNode
        else:
            rear.next = newNode
        rear = newNode

    def isEmpty():
        return front == None

    def deQueue():# 연결 큐의 삭제 연산
        global front, rear
        if isEmpty():
            print(&#34;Queue_Empty&#34;)
            return None
        item = front.item
        front = front.next
        if front == None :
            rear = None
        return item
Queue 라이브러리
큐 모듈
  1. 큐 모듈에 정의된 클래스
클래스 내용
queue.Queue(maxsize) 선입선출(FIFO First-In, First-Out)큐 객체를 생성
queue.LifoQueue(maxsize) 스택(Stack)개념의 후입선출 큐 객체 생성
queue.PriorityQueue(maxsize) 우선순위 큐 객체를 생성, 입력되는 아이템의 형식은 (순위, 아이템)의 튜플로 입력되며, 우선순위는 숫자가 작을수록 높은 순위를 가짐

  1. maxsize는 최대 아이템수, 지정하지 않거나 음수이면 내용만큼 늘어남

  2. 제시된 3개의 클래스는 다음과 같은 메설드를 동일하게 가짐

메서드 내용
qsize() 큐 객체에 입력된 아이템의 개수를 반환
put(item[, block[, timeout]]) 큐 객체에 아이템을 입력
get([block[, timeout]]) 생성된 큐 객체 특성에 맞추어, 아이템 1개를 반환
empty() 큐 객체가 비어있으면 True 리턴
full() 큐 객체가 꽉차있으면 True 리턴

  1. 클래스의 정렬방식에 따라 get 계열의 메서드 결과가 달라짐

  2. import queue로 사용

03 Queue의 활용

우선순위 Queue

  • 우선순위를 가진 항목들을 저장하는 큐

  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됨

  • 우선순위가 같은 경우, 선입선출 방식을 사용

  • 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제의 테스크 스케줄링 등에 쓰임

  • 구현을 위해 리스트를 이용하거나 Queue 라이브러리 사용

  • 삽입시 우선순위에 맞는 위치에 삽입하고 삭제시 가장 앞에있는 원소 삭제

리스트를 이용한 우선순위 큐의 구현

1) 리스트를 이용하여 자료 저장

2) 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조

3) 가장 앞에 최고 우선순위의 원소가 위치하게 됨

4) 단점으로 삽입이나 삭제 연산시 원소 재배치로 인한 시간 소요가 걸림

5) 연결리스트로 할시 조금 나으나, PriorityQueue 클래스 또는 힙 자료구조가 직빵

버퍼

  • 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역을 의마하며 버퍼링 : 버퍼를 활용하는 방식 또는 채우는 동작을 의미

  • 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용, 순서대로 입출력,전달해야하므로 선입 선출 방식의 자료구조인 큐가 활용됨

04 BFS(너비 우선 탐색)

BFS(너비 우선 탐색) 특징

  • 그래프 탐색 방법으로는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)가 있다

  • DFS(Depth First Search, 깊이 우선 탐색)

    • Stack 활용

  • BFS(Breadth First Search, 너비 우선 탐색)

    • 큐 활용

    • 시작점의 인접한 정점들을 모두 차례로 방문후 방문했던 정점들을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

    • 인접한 정점들을 탐색한 후, 찰례로 너비 우선 탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐 활용

      너비 우선탐색 알고리즘

def BFS(G, v):# 그래프 G, 탐색 시작점 v
    visited = [0]*n# n: 정점의 개수
    queue = []# 큐 생성
    queue.append(V)# 시작점 V를 큐에 삽입
    while queue:# 큐가 비어있지 않은 경우
      t = queue.pop(0)# 큐의 첫번째 원소 반환
      if not visited[t]:# 방문되지 않은 곳이라면
          visited[t] = True# 방문한 것으로표시
          visit(t)
      for i in G[t]:# t와 연결된 모든 선에 대해
          if not visited[i]:# 방문되지 않은 곳이라면
              queue.append(i)# 큐에 넣기

LinkedList

01 Linked List

List(리스트)

  1. 순서를 가진 데이터의 묶음- 같은 데이터의 중복 저장 가능

  2. 시퀀스 자료형 - 인덱싱, 슬라이싱, 연산자, 메서드 사용 가능

  3. 크기 제한 없음, 타입 제한 없음, 배열과의 차이점임

    • 배열을 기반으로 구현된 것을 순차 리스트 (파이썬 리스트)
  • 메모리의 동적할당을 기반으로 구현된 것을 연결 리스트라고 함
순차 List

  • 변수에 값을 초기화하는 것으로 리스트 생성 가능

  • 시퀀스 자료형으로 인덱스를 이용해 원하는 위치의 데이터를 변경 및 참조 가능

  • 자료의 삽입, 삭제 연산시 원소의 이동작업이 필요 이때 성능이 떨어짐

  • 리스트 복사에는 여러가지 방법이 있으며 각각 수행시간과 의미가 달라짐

    리스트 복사

  코드 설명
1 new_list = old_list 주소의 복사, 얕은 복사
2 new_list = old_list[:] 슬라이싱, 깊은 복사
3 new_list = [] , new_list.extend(old_list) extend() : 리스트를 추가하는 함수 깊은 복사
4 new_list = list(old_list) list(), 깊은 복사
5 import copy, new_list = copy.copy(old_list) copy 활용, 깊은 복사
6 new_list = [i for i in old_list] 리스트 함축, 깊은 복사
7 import copy, new_list = copy.deepcopy(old_list) 리스트 원소까지도 깊은 복사, 가장 느림, 깊은 복사
연결 List
  • 리스트의 단점을 보완한 자료 구조
    1. 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룸

  1. 링크를 통해 원소에 접근하므로, 순차 리스트에서 물리적인 순서를 맞추기 위한 작업이 필요하지 않음

  2. 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능

  3. 탐색- 순차 탐색

    연결 리스트 사용을 위한 주요 함수

함수명 기능
addtoFirst() 연결 리스트의 앞쪽에 원소를 추가하는 연산
addtoLast() 연결 리스트의 뒤쪽에 원소를 추가하는 연산
add() 연결 리스트의 특정 위치에 원소를 추가하는 연산
delete() 연결 리스트의 특정 위치에 있는 원소를 삭제하는 연산
get() 연결 리스트의 특정 위치에 있는 원소를 리턴하는 연산

  • 노드란? : 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

    • 데이터 필드 : 원소의 값을 저장하는 자료구조
    • 링크 필드 : 다음 노드의 주소를 저장하는 자료구조

  • 헤드란? : 리스트의 처음 노드를 가리키는 레퍼런스

  • 단순 연결 리스트 : 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐

    • 헤드가 가장 앞의 노드를 가리키고, 각 노드의 링크 필드가 연속적으로 다음 노드를 가리킴

    • 최종적으로 None을 가리키는 노드가 리스트의 가장 마지막 노드임

      Node class 예시

      ```python
      class Node:
      def __init(self, data, link):
      self.data = data
      self.link = link

      def addtoLast(data):# 마지막에 데이터 삽입
      global Head
      if Head == None:# 빈 리스트이면
      Head = Node(data, None)
      else:
      p = Head
      while p.link != None :# 마지막 노드 찾을 때까지
      p = p.link
      p.link = Node(data, None)

      def add(pre, data):# pre 다음에 데이터 삽입
      if pre == None:
      print('error')
      else:
      pre.link = Node(data, pre.link)
      '''
      또는
      def add(data, idx):
      global pHead
      p = pHead
      n = 0
      while n&#60;idx-1:
      p = p.link
      n += 1
      t = p.link
      p.link = Node(data, t)
      return
      '''

      def get(idx):# idx의 데이터 리턴

###### 단순 연결 리스트의 삽입 연산

- A, C, D를 원소로 갖고 있는 리스트의 두 번째에 B 노드를 삽입할 때
1. 메모리를 할당하여 새로운 노드 new 생성임
2. 새로운 노드 new의 데이터 필드에 B 저장
3. 삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 new에 복사
4. new의 주소를 앞 노드의 링크 필드에 저장

> 첫번째 노드로 삽입하는 알고리즘

```python
def addtoFirst(data):# 첫 노드에 데이터 삽입
    global Head
    Head = Node(data, Head)# 새로운 노드 생성

가운데 노드로 삽입하는 알고리즘

def add(pre, data):# pre 다음에 데이터 삽입
    if pre == None:
        print(&#39;error&#39;)
    else:
        pre.link = Node(data, pre.link)

  • 노드 pre의 다음 위치에 노드 삽입

    마지막 노드로 삽입하는 알고리즘

    ```python
    def addtoLast(data):# 마지막에 데이터 삽입
    global Head
    if Head == None:# 빈 리스트이면
    Head = Node(data, None)
    else:
    p = Head
    while p.link != None :# 마지막 노드 찾을 때까지
    p = p.link
    p.link = Node(data, None)

###### 단순 연결 리스트의 삭제 연산 (A, B, C, D 리스트의 B 노드를 삭제 시)
1. 삭제할 노드의 앞 노드(선행노드) 탐색

2. 삭제할 노드의 링크 필드를 선행노드의 링크 필드에 복사
   
   > 첫 번째 노드를 삭제하는 알고리즘
   
   ```python
   def deletetoFirst():# 처음 노드 삭제
    global Head
    if Head == None:
        print(&#39;error&#39;)
    else:
        Head = Head.link

노드를 삭제하는 알고리즘

  • 노드 pre의 다음 위치에 있는 노드 삭제
  def delete(pre):# pre 다음 노드 삭제
    if pre==None or pre.link==None:
        print(&#39;error&#39;)
    else:
        pre.link = pre.link.link
이중 연결 리스트

  • 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

  • 두 개의 링크 필드와 한 개의 데이터 필드로 구성 (prev, data, next)

    이중연결 리스트 class

    ```python
    class Node:
    def init(self, data, pre, link):# 이중 연결 리스트
    self.data = data
    self.pre = pre
    self.link = link

1) cur이 가리키는 노드 다음에 D값을 가진 노드를 삽입하는 과정
   
   1. 메모리를 할당하여 새로운 노드 new를 생성하고 데이터 필드에 'D'를 저장
   2. cur의 next를 new의 next에 저장하여 cur의 다음 노드를 삽입할 노드의 다음 노드로 연결
   3. new의 값을 cur의 next에 저장하여 삽입할 노드를 cur의 다음 노드로 연결
   4. cur의 값을 new의 prev 필드에 저장하여 cur를 new의 이전 노드로 연결
   5. new의 값을 new가 가리키는 노드의 다음 노드의 prev 필드에 저장하여 삽입하려는 노드의 다음 노드와 삽입하려는 노드를 연결

2) 이중 연결 리스트의 삭제 연산 (cur이 가리키는 노드를 삭제하는 과정)
   
   1. 삭제할 노드의 다음 노드의 주소를 삭제할 노드의 이전 노드의 next 필드에 저장하여 링크를 연결
   
   2. 삭제할 노드의 다음 노드의 prev 필드에 삭제할 노드의 이전 노드의 주소를 저장하여 링크를 연결
   
   3. cur이 가리키는 노드에 할당된 메모리를 반환
      
#### 02 삽입 정렬
      
##### 삽입 정렬의 특징
- 자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교해 자신의 위치를 찾아냄으로써 정렬을 완성, 시간 복잡도 O(n^2)
  
###### 삽입 정렬의 정렬 과정
1. 정렬할 자료를 두 개의 부분집합 S와 U로 가정
   
   - 부분집합 S : 정렬된 앞부분의 원소들
   - 부분집합 U : 아직 정렬되지 않은 나머지 원소들

2. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 이를 반복

3. 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 함

4. 부분집합 U가 공집합이 되면 삽입정렬이 완성됨
   
#### 03 병합 정렬
   
##### 병합 정렬의 특징
- 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
1. 분할 정복 알고리즘 활용, 시간 복잡도 :O(n log n)
   
   - 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
   
   - Top-Down 방식
     
##### 병합 정렬의 과정

2. 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 계속함

3. 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합
   
##### 병합 정렬 알고리즘
   
###### 분할 과정의 알고리즘
   
> 분할 과정 알고리즘 파이썬 코드

```python
def merge_sort(m):
    if len(m) &#38;#60;= 1:# 사이즈가 0이거나 1인 경우, 바로 리턴
        return m
# 1. DIVIDE 부분
    mid = len(m) // 2
    left = m[:mid]
    right = m[mid:]

# 리스트의 크기가 1이 될 때까지 merge_sort 재귀 호출
    left = merge_sort(left)
    right = merge_sort(right)

# 2. CONQUER 부분 : 분할된 리스트들 병합
    return merge(left, right)
병합 과정의 알고리즘
def merge(left, right):
    result = []# 두 개의 분할된 리스트를 병합하여 result를 만듦

    while len(left) &#38;#62; 0 and len(right) &#38;#62; 0 :# 양쪽 리스트에 원소가 남아있는 경우 
# 두 서브 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가함
        if left[0] &#38;#60;= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    if len(left) &#38;#62; 0 :# 왼쪽 리스트에 원소가 남아있는 경우
        result.extend(left)
    if len(right) &#38;#62; 0 :# 오른쪽 리스트에 원소가 남아있는 경우
        result.extend(right)
    return result

  • 연결 리스트를 사용하면 리스트의 삽입, 삭제, 크기 변경에서 일어나는 성능 저하를 줄일 수 있음

    정렬 알고리즘의 특성 비교

알고리즘 평균 수행시간 최악 수행시간 알고리즘 기법 비고
버블 정렬 O(n^2) O(n^2) 비교와 교환 코딩이 가장 손쉬움
카운팅 정렬 O(n+K) O(n+K) 비교환 방식 n이 비교적 작을 때만 가능
선택 정렬 O(n^2) O(n^2) 비교와 교환 교환의 회수가 버블, 삽입정렬보다 작음
퀵 정렬 O(n logn) O(n^2) 분할 정복 최악의 경우 O(n^2)이지만 보통 가장 빠름, 데이터가 자주 추가 삽입시 비효율
삽입 정렬 O(n^2) O(n^2) 비교와 교환 n의 개수가 작을 때 효과적
병합 정렬 O(n logn) O(n logn) 분할 정복 연결 List의 경우 가장 효율적인 방식, 메모리 사용량 큼

04 Linked List의 활용

List를 이용한 Stack

  • 스택의 원소: 리스트의 노드

  • 스택 내의 순서는 리스트의 링크를 통해 연결됨

  • Push: 리스트의 마지막에 노드 삽입

  • Pop: 리스트의 마지막 노드 반환/삭제

  • 변수 Top : 리스트의 마지막 노드를 가리키는 변수, 초기상태는 None

List를 이용한 Stack의 연산
  • Push와 Pop 연산 구현
    1. None 값을 가지는 노드를 만들어 스택 초기화

  1. 원소 A 삽입: push(A)

  2. 원소 B 삽입: push(B)

  3. 원소 C 삽입: push(C)

  4. 원소 반환: pop

Push / Pop 연산의 알고리즘

def push(i):# 원소 i를 스택 top(맨앞) 위치에 push
    global top
    top = Node(i, top)# 새로운 노드 생성
   
def pop():# 스택의 top을 pop
    global top
   
    if top == None:# 빈 리스트이면
        print(&#34;error&#34;)
    else:
        data = top.data
        top = top.link# top이 가리키는 노드를 바꿈
    return data
우선순위 Queue
우선순위 큐의 구현과 기본 연산

  • 우선순위 큐의 구현 : 연결 리스트를 이용한 우선순위 큐

  • 기본 연산 : 삽입: enQueue, 삭제: deQueue

순차 리스트를 이용한 우선순위 큐 구현

  • 순차 리스트를 이용하여 자료 저장

  • 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조

  • 가장 앞에 최고 우선순위의 원소가 위치하게 됨

  • 문제점 : 배열을 사용하므로 삽입, 삭제 연산 시 원소 재배치로 인한 시간과 메모리 낭비가 큼

연결 리스트를 이용한 우선순위 Queue 구현

  • 연결 리스트를 이용하여 자료 저장

  • 원소를 삽입하는 과정에서 리스트 내 노드의 원소들과 비교하여 적절한 위치에 노드를 삽입하는 구조

  • 리스트의 가장 앞쪽에 최고 우선순위가 위치하게 됨

  • 배열 대비 장점: 삽입/삭제 연산 이후 원소의 재배치가 필요 없음, 메모리의 효율적인 사용이 가능함

Tree

01 Tree

Tree의 특성

  • 비선형 구조로 원소들 간에 1:n 관계를 가지는 자료구조

    1) 원소들 간에 계층관계를 가지는 계층형 자료구조
    2) 상위 원소에서 하위 원소로 내려가면서 확장되는 Tree(나무) 모양의 구조
    1. 한 개 이상의 노드로 이루어진 유한 지합

    • 루트(Root) : 노드 중 최상위 노드
    • 단말 노드 : 가장 마지막, 자식이 없는 끝 노드
    • 나머지 노드들: n(>= 0)개의 분리 집합 T1, …, TN으로 분리될 수 있음
  1. 이들 T1, …, TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 서브트리(SubTree)라고 함
Tree의 구성요소
노드(node)

  • 트리의 원소, 트리 내부에 속해있는 원소들

    1. 루트 노드(Root node) : 트리의 시작 노드 (문제 안에서 부모가 없는 노드)

    2. 형제 노드(Sibling node) : 같은 부모 노드의 자식 노드들

    3. 조상 노드(Ancestor node) : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

    4. 서브 트리(Sub Tree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

    5. 자손 노드(Descendent node) : 서브트리에 있는 하위 레벨의 노드들( 자식의 자식들 포함)

간선(edge)
  • 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
차수(degree)

  • 노드에 연결된 자식 노드의 수 (B의 차수 = 2, C의 차수 = 1)

  • 트리의 차수는 트리에 있는 노드의 차수 중에서 가장 큰 값

단말 노드 (리프 노드, 맆 노드?)
  • 차수가 0인 노드, 자식 노드가 없는 노드
높이

  1. 노드의 높이

    • 루트(Root) : 노드 중 최상위 노드
    • 노드의 높이(레벨)는 루트 노드로 부터의 거리

  2. 트리의 높이

    • 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

02 Binary Tree-

Binary Tree의 특징
이진 트리

  1. 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리

    • 즉 레벨 i에서의 노드의 최대 개수는 2^i개
    • 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1)-1)개가 됨

  2. 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리

    • 왼쪽 자식 노드 (Left child node)

    • 오른쪽 자식 노드 (Right child node)

Binary Tree의 종류
포화 이진 트리 (Full binary Tree)

  • 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리

    1. 최대의 노드 개수인 (2^(h+1)-1)의 노드를 가진 이진 트리

    2. 루트를 1번으로 하여 (2^(h+1)-1)까지 정해진 위치에 대한 노드 번호를 가짐

완전 이진 트리 (Comlete binary Tree)

  • 높이가 h이고 노드 수가 n개일 때 (단, 2^h <= n < (2^(h+1)-1)), Full 이진 트리의 노드 번호 1번부터 n번까지 빈자리가 없는 이진 트리

  • 즉 계속 그리다가 만 포화 이진 트리 같은 느낌

편향 이진 트리 (Skewed binary Tree)

  • 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리

  • 왼쪽 평향 이진 트리와 오른쪽 평향 이진트리가 있다, 일직선으로 뻗어나가는 느낌

  • 편향 이진 트리는 메모리 공간 낭비와 비효율을 만드므로, 완전이진트리로 변향하는 알고리즘을 쓴다(알아보자)

Binary Tree - 순회(traversal)

  • 순회란, 트리의 각 노드를 중복되지 않게 전부 방문(Visit) 하는 것을 말하는데, 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없음

  • Segment tree에 대해서도 알아보기

3가지의 기본적인 순회 방법

V: 루트 노드
L: 루트의 자손 노드 중 왼쪽 서브 트리
R: 루트의 자손 노드 중 오른쪽 서브 트리
이라고 하였을 때,

  1. 전위 순회 (Preorder traversal)

    • VLR 순

    • 자손 노드보다 루트 노드를 먼저 방문

      전위 순회 알고리즘

def preorder_traverse(T) :# 전위순회
	if T :# T is not None
	    visit(T)# print(T.item)
	    preorder_traverse(T.left)
	    preorder_traverse(T.right)

  1. 중위 순회 (Inorder traversal)

    • LVR 순

    • 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문

      중위 순회 알고리즘

def inorder_traverse(T) :# 중위 순회
	if T:# T is not None
		inorder_traverse(T.left)
	    visit(T)# print(T.item)
	    inorder_traverse(T.right)
  1. 후위 순회 (Postorder traversal)
    • LRV 순
    • 루트노드보다 자손을 먼저 방문

후위 순회 알고리즘

def postorder_traverse(T) :# 후위 순회
	if T:# T is not None
	    postorder_traverse(T.left)
	    postorder_traverse(T.right)
	    visit(T)# print(T.item)

03 Expression Tree

List를 이용한 Binary Tree의 표현
리스트를 이용한 이진 트리의 표현

  1. 이진 트리에 각 노드 번호를 다음과 같이 부여

  2. 루트의 번호를 1로 함

  3. 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2n 부터 2^(n+1) - 1 까지 번호를 차례로 부여

노드 번호의 성질

  1. 노드 번호가 i인 노드의 부모 노드 번호는 i//2

  2. 노드 번호가 i인 왼쪽 자식 노드 번호는 2*i

  3. 노드 번호가 i인 오른쪽 자식 노드 번호는 2*i+1

이진트리의 리스트 표현 인덱스

  1. 노드 번호를 리스트의 인덱스로 사용

  2. 높이가 h인 이진 트리를 위한 리스트의 크기는 2^(h+1), 마지막 인덱스는 2^(h+1) - 1

리스트를 이용한 이진 트리 표현의 단점

  • 편향 이진 트리의 경우에 사용하지 않는 리스트 원소에 대한 메모리 공간 낭비 발생

  • 이를 보완하기 위해 연결 리스트를 이용하여 트리를 표현 가능,

  • 또는 연결 자료구조를 이용하면 이진 트리는 최대 2개의 자식 노드를 가지므로 쉽게 구현 가능

    리스트(배열)을 이용한 이진트리 표현 예시

    ```python
    V = 13# 간선 수 = V - 1
    E = V - 1
    t = [1, 2, 1, 3, 2, 4, 3, 5, 6, 4, 7, 5, 8, 5, 9, 6, 10, 6, 11, 7, 12, 11, 13]

배열의 모든 순회 알고리즘 예시

def preorder(n):
if n &#62; 0:
print(n, end=' ')
preorder(ch1[n])
preorder(ch2[n])

def inorder(n):
if n &#62; 0:
inorder(ch1[n])
print(n, end=' ')
inorder(ch2[n])

def postorder(n):
if n &#62; 0:
postorder(ch1[n])
postorder(ch2[n])
print(n, end=' ')

조상 찾기

def f(n):# n의 조상 출력하기
while(par[n] != 0):# n의 부모가 있으면
print(par[n], end=' ')
n = par[n]# 부모를 새로운 자식으로 해서 부모의 부모를 찾으러 감

1. 배열 방식

부모를 인덱스로 자식을 저장하는 방법

ch1 = [0] * (V+1)# 부모를 인덱스로 자식 저장
ch2 = [0] * (V+1)

for i in range(E) :
p = t[2 * i]
c = t[2 * i + 1]
if ch1[p] == 0:# 아직 ch1 자식이 없으면
ch1[p] = c
else:
ch2[p] = c

배열 방식 2번째

자식을 인덱스로 부모를 저장하는 방법

ch1 = [0] * (V+1)# 부모를 인덱스로 자식 저장
ch2 = [0] * (V+1)
par = [0] * (V+1)# 자식을 인덱스로 부모 저장

for i in range(E) :
p = t[2 * i]
c = t[2 * i + 1]
if ch1[p] == 0:# 아직 ch1 자식이 없으면
ch1[p] = c
else:
ch2[p] = c
par[c] = p

```

링크드 리스트를 이용한 이진 트리 표현
  • 배열을 이용한 이진트리 표현의 단점(편향 이진 트리 일시 메모리, 퍼포먼스 낭비, 트리 중간에 새로운 노드를 삽입 하거나 기존의 노드 삭제시 배열 크기 변경 어려움)을 보완하지만 대신 구현과 구조가 복잡해진다는 단점이 생김

04 Binary Search Tree

Binary search Tree의 특징

  1. 탐색작업을 효율적으로 하기 위한 자료구조

  2. 모든 원소는 서로 다른 유일한 키를 가짐

  3. 키 기준으로, key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)

  4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리임

  5. 중위 순회시, 오름차순으로 정렬된 값을 얻을 수 있음

Binary search Tree의 연산
탐색 연산

  1. 루트에서 시작

  2. 탐색할 키값 x를 루트 노드의 키값과 비교

    1) 키값 x == 루트 노드의 키값일 경우, 원하는 원소를 찾았으므로 성공
    2) 키값 x < 루트 노드의 키값일 경우, 왼쪽 서브트리에 대해서 탐색 연산 수행
    3) 키값 x > 루트 노드의 카값일 경우, 오른쪽 서브트리에 대해 탐색 연산 수행

  3. 서브트리에 대해서 순환적으로 탐색 연산을 반복

삽입 연산

  1. 먼저 탐색 연산을 수행

    • 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인
    • 탐색에서 탐색 실패가 결정되는 위치가 삽입위치가 됨

  2. 탐색 실패한 위치에 원소를 삽입

Binary search Tree의 성능

  1. 탐색(searching), 삽입(insertion), 삭제(deletion) 시간은 트리의 높이에 좌우 됨
    • 시간 복잡도는 O(h), h: BST의 깊이
  2. 평균의 경우
    • 이진 트리가 균형적으로 생성되어 있는 경우, O(log n)
  3. 최악의 경우
    • 한쪽으로 치우친 평향 이진 트리의 경우 O(n)
  • 순차탐색과 시간 복잡도가 같음
검색 알고리즘 성능 비교
  1. 리스트에서의 순차 검색: O(N)
  2. 정렬된 리스트에서의 순차 검색: O(N)
  3. 정렬된 리스트에서의 이진 검색: O(logN)
  4. 이진 탐색 트리에서의 평균: O(logN)
    • 최악의 경우: O(N)
    • 완전 이진 트리 또는 균형 트리로 바꿀 수 있다면 최악의 경우를 없앨 수 있음
      • 새로운 원소를 삽입할 때 삽입 시간을 줄임
      • 평균과 최악의 시간이 같음 O(logn)
  5. 해쉬 검색: O(1), 대신 메모리가 크게 듦

05 Heap

Heap의 특징

  • 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료 구조

    1. 최대 힙(Max heap)
      • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리

    • {부모 노드의 키값 > 자식 노드의 키값}

    • 루트 노드: 키값이 가장 큰 노드
      1. 최소 힙(Min heap)

    • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

    • {부모 노드의 키값 < 자식 노드의 키값}

    • 루트 노드: 키값이 가장 작은 노드
Heap의 연산
  • 노드의 값이 중복되어 있으면 힙의 정의에 맞지않는 이진트리이다.
Heap의 삽입 연산

  • 삽입 연산의 경우 새로 넣을 값을 노드의 맨 마지막에 새로 자리를 만들어 넣고 부모노드와 값을 비교해 유효한지 확인한다.

  • 유효할 경우 그대로 종료, 유효하지 않을 경우, 부모 노드와 위치를 바꾼다. 이를 유효할 때까지 반복

Heap의 삭제 연산
  1. 힙에서는 루트 노드의 원소만을 삭제할 수 있음
  2. 루트 노드의 원소만을 삭제하여 반환
  3. 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있음
    • 이를 이용하여 우선순위 큐를 힙으로 구현 가능
      - 루트 노드의 원소를 삭제하고, 마지막 노드를 루트 노드 위치로 이동, 이후 삽입 노드와 자식 노드를 비교하며 유효할 때까지 자리를 바꿔나가면 된다
      - 최소값 힙 구현 algorithm TIL 190924 확인