[프로그래머스 인공지능 스쿨]Day01:어서와! 자료구조와 알고리즘은 처음이지?(1)

21 minute read

1. 자료구조와 알고리즘

파이썬의 기본적인 데이터 타입

문자열(str) : “This is a string”
리스트(list) : [5,8,2,7]
사전(dict) : {‘a’:6, ‘bc’:4} 키와 값의 쌍
순서쌍(tuple)
집합(set)
…

웬만한 것들은 파이썬에서 이미 제공하는 데이터 타입으로 다 해결할 수 있을 것 같은데, 자료구조라는 것은 도대체 왜 알아야 하는 걸까?

import time

n = int(input("Number of elements: "))
haystack = [k for k in range(n)]

print("Searching for the maximum value...")

ts=time.time()
maximum = max(haystack)
elapsed = time.time() - ts

print("Maximum element = %d, Elapsed time = %.2f" % (maximum, elapsed))

max라는 함수의 실행 시간을 측정하는 파이썬 코드이다.
0부터 n-1까지의 수를 나열한 리스트에서, 맥시멈 값을 max함수로 찾는데 걸리는 시간을 측정한다.
수들이 나열되어 있을 때, 이미 오름차순으로 나열되어있으므로 맥시멈은 리스트의 마지막 숫자가 된다.
일반적으로 n개의 수가 늘어선 리스트에서 최대값을 찾기 위해 가장 빠르게 할 수 있는 방법은 무엇일까?
1만 개, 10만 개, 100만 개, 1000만 개, 1억 개… 리스트의 길이가 커질 수록 확연히 탐색 속도가 늘어난다.
리스트에 있는 원소값을 전부 다 보지 않고서는 최대값을 알아낼 수 없기 때문이다.
따라서 파이썬의 내장함수인 max는 리스트의 모든 값을 확인하기 때문에 개수에 비례하는 만큼의 시간이 걸린다.
일반적으로 수가 정렬되지 않고 마구 섞여 있을 때, 우리가 어떤 자료구조를 사용해야 시간을 단축할 수 있을까?
자료구조라 함은, 어떤 데이터가 있고, 그 데이터에 대해서 행할 수 있는 연산들이 있는 무엇인가의 구조로 생각할 수 있다. 연산이라 함은 최대값을 찾는다던가, 특정 위치의 새로운 원소를 집어넣거나, 특정 원소를 삭제하는 것 등이 있다.

알고리즘(algorithm)이란?

사전적 정의 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
프로그래밍 : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대해 선택
해결하고자 하는 문제에 따라 (응용 종류와 범위에 따라)최적의 해법은 서로 다르다! -> 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다.

실습

입력으로 주어지는 리스트 x 의 첫 원소와 마지막 원소의 합을 리턴하는 함수 solution() 을 완성하세요.

def solution(x):
    answer = x[0]+x[len(x)-1]
    return answer

2. 선형 배열(Linear Arrays)

파이썬에서는 배열을 구현하는 데 리스트를 활용할 수 있다.
배열이라 함은, 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻한다. 파이썬에서는 배열이라는 것이 따로 데이터타입으로 존재하지 않고, 리스트를 이용하게 된다. 파이썬의 리스트는 다른 프로그래밍 언어의 배열보다는 조금 더 융통성이 있는 자료구조를 제공한다.

배열 : 원소들을 순서대로 늘어놓은 것

배열의 인덱스는 0부터 시작한다.

Python에서의 리스트(list) :

파이썬에서의 리스트는 다른 언어에서 동일한 종류의 원소들만이 줄을 설 수 있는 어레이와는 달리, 아무런 타입의 데이터라도 배열의, 리스트의 원소로 채택할 수 있다.

L = ['Bob', 'Cat', 'Spam', 'Programmers']

리스트에서 이 문자열들의 길이는 다 같지 않아도 되고, 각 리스트의 원소가 서로 다른 데이터타입을 가지고 있어도 된다.
여기서 L[1]은 ‘Cat’으로, 리스트에 접근할 수 있다.

리스트(배열) 연산

원소 덧붙이기

L = ['Bob', 'Cat', 'Spam', 'Programmers']
L.append('New')

L = ['Bob', 'Cat', 'Spam', 'Programmers', 'New']

끝에서 꺼내기
```
L = ['Bob', 'Cat', 'Spam', 'Programmers', 'New']
L.pop() #끝에서 하나의 원소를 꺼냄(리스트도 변화)
```
‘New’라는 문자열이 반환됨과 동시에 리스트에서도 그 원소가 없어지게 된다.
따라서 L.pop()의 return은 ‘New’이고, 리스트에서 사라진다.

원소 덧붙이기와 끝에서 꺼내기 연산은 순식간에 할 수 있는 일이다. 리스트의 길이와 무관하게 상수 시간 O(1) 안에 끝나는 작업이다.

원소 삽입하기
```
L = [20, 37, 58, 72, 91]
L.insert(3,65)  #index 3의 위치에 원소 65를 삽입
```
```
L = [20, 37, 58, 65, 72, 91]
```
이것을 단계별로 살펴보자.
- 3번 인덱스의 앞을 찾아낸다.
- 리스트의 맨 뒤의 숫자를 오른쪽으로 한칸 옮기고,
- 그 앞의 숫자를 또 오른쪽으로 한칸 옮기고,
- 그 앞에 65를 삽입한다.
원소 삭제하기
```
L = [20, 37, 58, 65, 72, 91]
del(L[2])#리스트 L의 index 2위치(세번째) 원소를 삭제
```
```
L = [20, 37, 65, 72, 91]
```
- 인덱스 2의 뒤의 숫자를 한칸 왼쪽으로
- 리스트의 끝에 도달할때까지 계속 한칸 왼쪽으로
- 마지막 리스트의 값 제거 L.pop(2)와의 차이점? : del은 반환값이 없지만, pop은 반환값이 있다!
  원소 삽입, 삭제는 리스트의 길이가 길면 오래 걸리는 일이다. 리스트의 길이에 비례한다.(선형 시간, O(n))
원소 탐색하기
```
L = ['Bob', 'Cat', 'Spam', 'Programmers']
L.index('Spam')
```
세번째, 즉 인덱스 2에서 발견되므로 결과값은 2가 나온다.

실습

리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요. 인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.

def solution(L, x):
    answer = []
    answer = L
    # print(answer)
    for i in range(len(answer)):
        if L[i]>x:
            break
        i+=1
    answer.insert(i, x)
    return answer

인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요. 리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다. 이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고, 만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.

def solution(L, x):
    answer = []
    for i in range(len(L)):
        if x == L[i]:
            answer.append(i)
    if x not in L:
        answer.append(-1)
        return answer
    else:
        return answer

index를 사용하는 방법이 있었지만 그러지 않았다..ㅎㅎ

3. 배열 - 정렬과 탐색(Sorting & Searching)

정렬(sort)이란?
복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업

Python 리스트의 정렬

sorted()
- 내장 함수(built-in function)
- 정렬된 새로운 리스트를 얻어냄
sort()
- 리스트의 메서드(method)
- 해당 리스트를 정렬함

정렬의 순서를 반대로

reverse = True<br>
L2 = sorted(L, reerse=True)
L.sort(reverse=True)

정렬 - 문자열로 이루어진 리스트의 경우 정렬 순서는 사전 순서(알파벳 순서)를 따름. 문자열 길이가 긴 것이 더 큰 것이 아님. Python 문자열은 대문자가 소문자에 비해서 무조건 우선한다.

문자열 길이 순서대로 정렬하려면?

정렬에 이용하는 키(key)를 지정한다.

L = ['abcd', 'xyz', 'spam']
sort4ed(L, key=lambda x: len(x))

x의 길이를 key로 사용해서 원소들을 정렬한다.

['xyz', 'abcd', 'spam']

정렬 - 키를 지정하는 또 다른 예

L = [{'name':'John', 'score':83, 'name':'Paul','score':92}]
L.sort(key=lambda x: x['name'])#레코드들을 이름 순서대로 정렬
L.sort(key=lambda x:x['score'], reverse=True)#레코드들을 점수 높은 순으로 정렬

탐색 알고리즘(1) - 선형 탐색(Linear Search)

순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아낸다.
배열의 길이에 비례하는 시간이 소요된다. -> O(n)
최악의 경우에는 배열에 있는 모든 원소를 다 검사해야 할 수 있다. 리스트의 맨 끝에 있거나 없는 원소를 찾을 경우!

def linear_search(L, x):
    i = 0
    while i < len(x) and L[i] != x:
        i += 1
    if i < len(L):
        return i
    else:
        return -1

파이썬의 index 함수가 하는 일과 동일하다.

탐색 알고리즘(2) - 이진 탐색(Binary Search)

탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
크기 순으로 정렬되어 있다는 성질 이용!
한 번 비교가 일어날 때마다 리스트가 반씩 줄어든다.(divide & conquer)
O(log n) 배열의 가운데 원소와 찾으려 하는 값을 비교해서 (크기 순으로 정렬되어 있다고 가정) 왼쪽에 있을지 오른쪽에 있을지를 알 수 있다 (만약 있긴 있다면). 그러면, 적어도 반대쪽에 없는 것은 확실하므로, 배열의 반을 탐색하지 않고 버릴 수 있다. 이 과정을 반복하면 원하는 값을 찾아낼 수 있다.

lower = 0
upper = len(L)-1
idx = -1
while lower <= upper:
    middle = (lower + upper)//2
    if L[middle] == target:
        ...
    elif L[middle] < target:
        lower = ...
    else:
        upper = ...

실습

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

def solution(L, x):
    answer = -1
    lower = 0
    upper = len(L)-1
    while lower <= upper and upper <= len(L)-1:
        middle = (lower + upper)//2
        if L[middle] == x:
            answer = middle
            break
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    return answer

4, 재귀 알고리즘 기초

재귀함수(recursive functions)란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것. 생각보다 많은 종류의 문제가 재구적으로 해결 가능

예제 : 자연수의 합 구하기

문제 : 1부터 n까지 모든 자연수의 합을 구하시오.

def sum(n):
    return n + sum(n-1)

이렇게 점화식으로 쓸 수 있다!

1 부터 n 까지 모든 자연수의 합을 구하는 문제 (sum(n))는, 1 부터 n - 1 까지의 모든 자연수의 합을 구하는 문제 (sum(n - 1))를 풀고, 여기에 n 을 더해서 그 답을 찾을 수 있다. 즉,

sum(n) = sum(n - 1) + n

위의 코드를 쓸 경우, 마이너스로 무한 재귀에 빠지게 된다. 따라서 종결 조건을 걸어줘야 한다.

def sum(n):
    print(n)
    if n <= 1:
        return n
    else:
        return n + sum(n-1)
a = int(input("Number : "))
print(sum(a))

재귀 알고리즘을 작성할 때는 종결 조건에 특히! 주의해야 한다.

Recursive version O(n)

def sum(n):
  if n <= 1:
      return n
  else:
      return n + sum(n-1)

Iterative version O(n)

def sum(n):
  s = 0
  while n>=0:
      s+=n
      n-=1
  return s

그리고 극단적인 방법으로…
O(1)

def sum(n):
  return n*(n+1)//2

재귀 알고리즘 추가 예제

def what(n):
  if n<=1:
      return 1
  else:
      return n*what(n-1)

팩토리얼(n!)을 구하는 재귀함수이다.

실습

인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

def solution(x):
    if x==0 : return 0
    elif x==1 or x==2 : return 1
    else:
        return solution(x-1)+solution(x-2)

5. 재귀 알고리즘 응용

조합의 수 계산

문제 : n개의 서로 다른 원소에서 m개를 택하는 경우의 수
nCm = n!/(m!(n-m)!)

from math import factorial as f
def combi(n, m):
    return f(n)/(f(m)*f(n-m))

이렇게 파이썬 라이브러리를 이용해 구현할 수 있지만, 재귀로 구현할 수 있다.

조합의 수 계산 - 재귀적 방법으로

nCm = n-1Cm + n-1Cm-1

def combi(n,m):
    return combi(n-1, m)+combi(n-1, m-1)

-> Trivial case를 고려하지 않은 실수!
Trivial case를 고려하면 다음과 같이 된다.

def combi(n,m):
    if n==m:return 1
    elif m==0: return 1
    else:return combi(n-1, m)+combi(n-1, m-1)

효율성 측면에서는 리턴문에서 함수를 두번 호출하기 때문에 상당히 비효율적이다. 차라리 루프를 이용하는게 효율이 좋다.
그런데 왜 재귀를 쓸까? 사람이 생각하는 방식을 그대로 옮기기 좋기 때문이다. ex. 하노이의 탑

실습

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다. 인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

def solution(L, x, l, u):
    if l>u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid-1)
    else:
        return solution(L, x, mid+1, u)

6. 알고리즘 복잡도(Complexity of Algorithm)

시간 복잡도(Time Complexity) : 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
공간 복잡도(Space Complexity) : 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

우린 시간 복잡도를 더 집중적으로 볼 것이다! 시간 복잡도는 다음과 같이 나뉜다.

평균 시간 복잡도(Average Time Complexity) : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
최악 시간 복잡도(Worst-case Time Complexity) : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-O Notation

점근 표기법(asymptotic notation)의 하나
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
O(logn), O(n), O(n^2)등으로 표기 수학적인 정의는 일단 차치하고
입력의 크기가 n일 때,
O(log n) - 입력의 크기의 로그에 비례하는 시간 소요
O(n) - 입력의 크기에 비례하는 시간 소요
계수는 그다지 중요하지 않음! 2n이던 100n이던 상관없다. 입력의 크기가 아주 커지면 계수는 거의 무의미해지기 때문이다.

선형 시간 알고리즘 - O(n)

예 : n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용
Average case : O(n)
Worst case : O(n)

로그 시간 알고리즘 - O(log n)

예 : n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용

이차 시간 알고리즘 - O(n^2)

예 : 삽입 정렬 (insertion sort)
하나의 원소를 삽입할 때마다 입력, 즉 n만큼 걸리기 때문에 총 n^2만큼의 시간복잡도를 갖는다.
Best case : O(n), 모든 수가 이미 정렬이 되어있는 상태일 때. 삽입을 한번도 하지 않고 n개의 수만 확인하고 끝난다.
Worst case : O(n^2), 모든 수가 역순으로 이루어져 있을 때

보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘

예 : 병합 정렬(merge sort) - O(nlogn)
참고 : 입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있음.
예 : 병합 정렬(merge sort)

정렬할 데이터를 반씩 나누어 각각을 정렬시킨다. -> O(log n)
정렬된 데이터를 두 묶음씩 한데 합친다. -> O(n) => O(nlogn)

꽤나 복잡한 문제

유명한 예 : 배낭 문제(Knapsack Problem)
배낭에는 15kg만 담을 수 있는데, 서로 다른 가치와 무게를 가지는 아이템들이 있다. 그럼 어떤것들을 골라 담아야 최대의 가치를 얻을 수 있는가?

7. 연결 리스트(Linked Lists) (1)

추상적 자료구조(Abstract Data Structures)

Data
- 예 : 정수, 문자열, 레코드, …
A set of operations
- 삽입, 삭제, 순회, …
- 정렬, 탐색, …

기본적 연결 리스트

칸 하나, 데이터 아이템이 들어있는 칸 하나를 Node라고 한다.

Node
- Data
- Link(next) Node 내의 데이터는 다른 구조로 이루어질 수 있음.
  (예) 문자열, 레코드, 또 다른 연결 리스트 등
리스트의 맨 처음 노드 : Head
리스트의 맨 끝 노드 : Tail

자료 구조 정의

Node

Data

Link(next) 이를 클래스로 나타내면 다음과 같다.

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

class LinkedList:
  def __init__(self):
  self.nodeCount = 0
  self.head = None
  self.tail = None

이것은 # of nodes: 0이고, Head와 Tail이 아무것도 가리키고 있지 않은 비어 있는 연결 리스트이다.

연산 정의

특정 원소 참조(k번째)
리스트 순회
길이 얻어내기
원소 삽입
원소 삭제
두 리스트 합치기

노드 시작 번호가 0이 아니라 1부터 시작하는 것에 주의한다!

특정 원소 참조

def getAt(self, pos):#pos번째에 있는 노드 자체를 반환
    if pos<=0 or pos>self.nodeCount:
        return None
    i = 1
    curr = self.head#연결리스트의 첫번째 노드가 커런트
    while i<pos:
        curr = curr.next#pos-1만큼 전진
        i+=1
    return curr

배열과 비교한 연결 리스트

	배열	연결리스트
저장 공간	연속한 위치	임의의 위치
특정 원소 지칭	매우 간편	선형탐색과 유사
	O(1)	O(n)

연습문제 - 리스트 순회

def traverse(self):
    answer = []
    i=1
    while i<=self.nodeCount:
        answer.append(self.getAt(i))
    return answer

이렇게 하면 안된다! 두번째를 찾을때 첫번째 두번째, 세번째를 찾을때 첫번째 두번째 세번째 이렇게 하도록 짜면 안된다.

실습

제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.

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

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        if not self.head:#is empty
            return []
        answer = []
        curr = self.head
        while curr is not None:
            answer.append(curr.data)
            curr = curr.next
        return answer


# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
    return 0

8. 연결 리스트(Linked Lists) (2)

연결 리스트의 연산 - 원소의 삽입

def insertAt(self, pos, newNode):
    pos가 가리키는 위치에 (1<=pos<=nodeCount+1)
    newNode를 삽입하고
    성공/실패에 따라 True/False를 리턴

L.insertAt(pos, newNode) node의 pos-1번째를 prev라고 했을 때,
pos-1(prev) —> newNode —> pos 가 되려면!(newNode가 삽입된 것)
1. newNode의 nextlink가 pos를 가리키게 한다.
2. prev노드의 nextlink가 newNode를 가리키게 한다.
3. nodeCount += 1 이렇게 하면 연결 리스트의 노드 삽입 완성!
```
def insertAt(self, pos, newNode):
  prev = self.getAt(pos -1)
  newNode.next = prev.next
  prev.next = newNode
  self.nodeCount += 1
```
  이렇게 1,2,3번의 과정을 그대로 코드로 옮겨주면 될 것만 같지만… 코너 케이스들이 있다!

코드 구현 주의사항

삽입하려는 위치가 리스트 맨 앞일 때 -> prev 없음
-> Head 조정 필요
삽입하려는 위치가 리스트 맨 끝일 때 -> Tail 조정 필요
- 빈 리스트에 삽입할 때? 이 두 조건에 의해 처리됨!

def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:#삽입하려는 위치가 리스트 맨 앞일 때
            newNode.next = self.head
            self.head = newNode

        else:#삽입하려는 위치가 리스트 맨 앞이 아닐 때
            prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:#삽입하려는 위치가 리스트 맨 끝일 때
            self.tail = newNode

        self.nodeCount += 1
        return True

이렇게하면 빈 리스트에 첫 원소를 삽입하는 경우도 잘 처리된다!

그런데 잠깐

삽입하려는 위치가 리스트 맨 끝일 때, 즉 pos == nodeCount+1인 경우?
prev==tail이니까 tail의 넥스트링크를 뉴노드로 하고, 뉴노드는 none을 가리키게 해서,
맨 앞에서부터 찾아갈 필요가 없다!

def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:#삽입하려는 위치가 리스트 맨 앞일 때
            newNode.next = self.head
            self.head = newNode

        else:#삽입하려는 위치가 리스트 맨 앞이 아닐 때
            if pos == self.nodeCount + 1:#삽입하려는 위치가 리스트 맨 끝일 때
                prev = self.tail#앞에서부터 하나하나씩 찾지 말고 바로 tail로
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:#삽입하려는 위치가 리스트 맨 끝일 때
            self.tail = newNode

        self.nodeCount += 1
        return True

연결 리스트 원소 삽입의 복잡도

맨 앞에 삽입하는 경우 : O(1)
중간에 삽입하는 경우 : O(n)
맨 끝에 삽입하는 경우 : O(1)

연결 리스트 연산 - 원소의 삭제

def popAt(self, pos):
    pos가 가리키는 위치의(1<=pos<=nodeCount)
    node를 삭제하고
    그 node의 데이터를 리턴

r = L.popAt(pos) pos-1 –> pos –> pos+1
여기에서 pos를 삭제한 후 그 값을 반환할 것이다.
1. pos-1을 prev라는 변수로 둔다.
2. pos, 즉 삭제해야 할 것을 curr라는 변수로 둔다.
3. prev.next링크를 curr.next링크가 가리키도록 한다.
4. 데이터를 꺼내서 리턴한다.
5. nodeCount -= 1

코드 구현 주의사항

삭제하려는 node가 맨 앞의 것일 때 -> prev 없음
-> Head 조정 필요. Head를 삭제되는 노드의 다음 것으로 정해야 한다.
리스트의 맨 끝의 node를 삭제할 때 -> Tail 조정 필요. prev로 해야한다.
- 유일한 노드를 삭제할 때? 이 두 조건에 의해 처리되는가?

그런데 잠깐

삭제하려는 node가 마지막 node일 때, 즉 pos==nodeCount인 경우, 삽입할때와 마찬가지로 앞에서부터 찾아오지 않고 curr==tail로 한번에 처리할 수 있을까?
tail로 현재의 prev를 얻을 수 없다. 한번에 처리할 방법이 없다(prev를 찾을 방법이 없으므로) -> 앞에서부터 찾아와야 함!

연결 리스트 원소 삭제의 복잡도

맨 앞에서 삭제하는 경우 : O(1)
중간에서 삭제하는 경우 : O(n)
맨 끝에서 삭제하는 경우 : O(n)

연결 리스트 연산 - 두 리스트의 연결

def concat(self, L):
    연결 리스트 self의 뒤에 
    또다른 연결 리스트인 L을 이어 붙임

L1.concat(L2)

self.tail.next=L2.head
self.tail = L2.tail

def concat(self, L):
    self.tail.next = L.head
    if L.tail:#인자 L에 주어진 리스트가 빈 리스트이면! 안되므로! 빈 리스트를 붙이지 않는 경우에만 수행하게끔 한다!
        self.tail = L.tail
    self.nodeCount += L.nodeCount

실습

제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, def popAt(self, pos): 의 메서드 몸체만 구현하세요.

만약, 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.

def popAt(self, pos):
        # prev = self.getAt(pos-1)
        curr = self.getAt(pos)
        if pos < 1 or pos > self.nodeCount:
            raise IndexError

        if pos == 1:#삭제하려는 위치가 리스트 맨 앞일 때
            if self.nodeCount == 1:
                self.head=None
                self.tail=None
                self.nodeCount = 0
            else:
                self.head = self.head.next
                self.nodeCount -= 1
            return curr.data
        else:#삭제하려는 위치가 리스트 맨 앞이 아닐 때
            prev = self.getAt(pos-1)
            prev.next = curr.next
            if pos == self.nodeCount:#맨 뒤에서 삭제할때
                prev.next = None
                self.tail = prev
        self.nodeCount -= 1
        return curr.data

9. 연결 리스트(Linked Lists) (3)

연결 리스트가 힘을 발휘할 때

스마트폰에서 여러 프로세스 중 하나를 위로 밀어서 삭제하기
중간에 무언가를 끼워넣거나 빼는 동작.
삽입과 삭제가 유연하다는 것이 가장 큰 장점!
이 장점을 살리기 위한 새로운 메서드들을 만들자:

insertAfter(prev, newNode)#어떤 노드의 뒤에 삽입해라
popAfter(prev)#어떤 노드의 뒤의 것을 삭제해라

맨 앞에서는 어떻게?

조금 변형된 연결 리스트

맨 앞에 dummy node를 추가한 형태로! (아무 데이터도 담고 있지 않은 노드) dummy node에 0번을 붙임으로써 사용 가능하다.
```
class LinkedList:
  def __init__(self):
      self.nodeCount = 0
      self.head = Node(None)
      self.tail = None
      self.head.next = self.tail
```
연결리스트의 초기화는 이런식으로 구성되게 된다.

연산 정의

길이 얻어내기
리스트 순회
특정 원소 참조(k번째)
원소 삽입
원소 삭제
두 리스트 합치기

연결 리스트 연산 - 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next:
        curr = curr.next
        result.append(curr.data)
    return result

연결 리스트 연산 - k번째 원소 얻어내기

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    i=0
    curr = self.head
    while i < pos:
        curr = curr.next
        i+=1
    return curr

연결 리스트 연산 - 원소의 삽입

def insertAfter(self, prev, newNode):
    prev가 가리키는 node의 다음에
    newNode를 삽입하고
    성공/실패에 따라 True/False를 리턴

L.insertAfter(prev, newNode)

원소의 삽입 - 코드 구현

def insertAfter(self, prev, newNode):
    newNode.next = prev.next
    if prev.next is None :
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

메서드 insertAt()의 구현

def insertAt(self, pos, newNode):

이미 구현한 insertAfter()를 호출하여 이용하는 것으로

pos 범위 조건 확인
pos==1인 경우에는 head 뒤에 새 node 삽입
pos==nodeCount+1인 경우는 prev <- tail

그렇지 않은 경우에는 prev <- getAt(…)

def insertAt(self, pos, newNode):
 if pos < 1 or pos > self.nodeCount +1:
     return False
 if pos != 1 and pos == self.nodeCount+1:#tail뒤에 삽입하려는 경우 
     prev = self.tail
 else:
     prev = self.getAt(pos -1)
 return self.insertAfter(prev, newNode)

연결 리스트 연산 - 원소의 삭제

def popAfter(self, prev):
    prev의 다음 node를 삭제하고
    그 node의 data를 리턴

코드 구현 주의사항

prev가 마지막 node일 때(prev.next==None) -> 삭제할 node 없음
-> return None
리스트 맨 끝의 node를 삭제할 때(curr.next==None) ->Tail 조정 필요

연결 리스트 연산 - 두 리스트의 연결

L1.concat(L2)

def concat(self, L):
    self.tail.next = L.head.next
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

실습

제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다. 이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다. (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.)

def popAfter(self, prev):
        curr = prev.next
        if prev.next == None:
            return None
        elif curr.next == None:
            prev.next = None
            self.tail = prev
        else:
            prev.next = curr.next
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        answer = self.popAfter(prev)
        return answer

10. 양방향 연결 리스트(Doubly Linked Lists)

기존에 연결리스트는 한쪽 방향으로는 갈 수 있는데, 반대쪽 방향으로는 가지 못하는게 아쉬운 점이었다. 이를 보완하기 위한 것이 바로…

양방향 연결 리스트(Doubly Linked Lists)

한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
-> 앞으로도(다음 노드) 뒤로도(이전 노드)진행 가능

Node의 구조 확장

class Node:
  def __init__(self, item):
      self.data = item
      self.prev = None#prev링크를 따라갈 수 있도록 링크도 None으로 초기화!
      self.next = None

리스트 처음과 끝에 dummy node를 두자! -> 데이터를 담고 있는 node들은 모두 같은 모양이 된다.

class DoublyLinkedList:
  def __init__(self, item):
      self.nodeCount = 0
      self.head = Node(None)#더미노드
      self.tail = Node(None)#더미노드
      self.head.prev = None
      self.head.next = self.tail#헤드와 테일이 서로를 가리키고 있음
      self.tail.prev = self.head
      self.tail.next = None

리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result

리스트 역순회

def traverse(self):
    result = []
    curr = self.tail
    while curr.prev.prev:
        curr = curr.prev
        result.append(curr.data)
    return result

리스트 순회와 리스트 역순회는 대칭이다. 혹시 빈 리스트에 대해서도 유효할까? 유효하다! 신난다~

원소의 삽입

L.insertAfter(prev, newNode)

next = prev.next
newNode.prev <- prev
newNode.next <- next
prev.next <- newNode
nodeCount <- nodeCount+1

def insertAfter(self, prev, newNode):
    next = prev.next
    newNode.prev = prev
    newNode.next = next
    prev.next = newNode
    next.prev = newNode
    self.nodeCount += 1
    return True

코드로 구현해보면, self의 tail조정, head조정 이런 귀찮은 조정들이 사라지고 훨씬 간편해진다!

특정 원소 얻어내기

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    i=0
    curr = self.head
    while i < pos:
        curr = curr.next
        i+=1
    return curr

9강의 연결리스트에서의 getAt과 완전히 동일하다.

원소의 삽입

L.insertAt(pos, newNode)

그런데 잠깐, 리스트 마지막에 원소 삽입하면?

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    if pos > self.nodeCount//2:#pos이 노드카운트의 절반보다 뒤쪽이면 앞에서부터 찾지 말고, 뒤에서 하나씩 세도록 한다.
        i=0
        curr = self.tail
        while i < self.nodeCount - pos + 1:
            curr = curr.prev
            i+=1
    else:
        #원래 getAt의 앞에서부터 찾아가는 과정

그러냐 여전히, 선형 시간 알고리즘이고 리스트의 길이가 길어질수록 오래 걸린다!

실습1

제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.

이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서, 방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.

def reverse(self):
        answer = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            answer.append(curr.data)
        return answer

강의에서 다뤘던 리스트 역순회를 그대로 쓰면 된다.

실습 2

제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 의 메서드로 insertBefore() 를 구현하세요. 이 insertBefore() 메서드에는 두 개의 인자가 주어지는데, next 는 어느 node 의 앞에 새로운 node 를 삽입할지를 지정하고, newNode 는 삽입할 새로운 node 입니다.

def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.prev = prev
        newNode.next = prev.next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

insertAfter와 거의 비슷하다.

실습3

제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 node 의 삭제 연산에 관련한 아래와 같은 메서드들을 구현하세요. popAfter(prev) 는 인자 prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제하고, popBefore(next) 는 인자 next 에 의하여 주어진 node 의 이전에 있던 node 를 삭제합니다. 그리고 삭제되는 node 에 담겨 있던 data item 을 리턴합니다.

popAt(pos) 는 인자 pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴하는데, 위 popAfter() 또는 popBefore() 를 호출하여 이용하는 방식으로 구현하세요. 또한, 만약 인자 pos 가 올바른 범위 내에 있지 않은 경우에는 raise IndexError 를 이용하여 IndexError exception 을 일으키도록 구현하세요.

def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popBefore(self, next):
        curr = next.prev
        prev = curr.prev
        prev.next = next
        next.prev = prev
        self.nodeCount -=1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        answer = self.popAfter(prev)
        return answer

실습4

제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 두 개의 양방향 연결 리스트를 앞뒤로 이어 붙이는 메서드 concat() 을 구현하세요.

def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount

11. 스택

스택(Stack) : 자료를 보관할 수 있는 선형 구조. 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(push 연산) 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음(pop 연산). 후입선출(LIFO-Last-In-First-Out)특징을 가지는 선형 자료구조
```
S = Stack()
S.push(A)
S.push(B)
r1 = S.pop()
r2 = S.pop()
r3 = S.pop()#비어있는 스택에서 데이터 원소를 꺼내려 할 때
```
비어있는 스택에서 데이터 원소를 꺼내려 할 때 : 스택 언더플로우(stack underflow)
꽉 찬 스택에 데이터 원소를 넣으려 할 때 : 스택 오버플로우(stack overflow)

스택의 추상적 자료구조 구현

배열을 이용하여 구현
- 파이썬 리스트와 메서드들을 이용
연결 리스트를 이용하여 구현
- 양방향 연결 리스트 이용

연산의 정의

size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() : 현재 스택이 비어 있는지를 판단
push(x) : 데이터 원소 x를 스택에 추가
pop() : 스택의 맨 위에 저장된 데이터 원소를 제거(또한, 반환)
peek() : 스택의 맨 위에 저장된 데이터 원소를 반환(제거하지 않음)

배열로 구현한 스택

class ArrayStack :
    def __init__(self):#빈 스택을 초기화
        self.data=[]
    
    def size(self):#스택의 크기를 리턴
        return len(self.data)
    
    def isEmpty(self):#스택이 비어 있는지 판단
        return self.size()==0

    def push(self, item):#데이터 원소를 추가
        self.data.append(item)
    
    def pop(self):#데이터 원소를 삭제(리턴)
        return self.data.pop()
    
    def peek(self): #스택의 꼭대기 원소 반환
        return self.data[-1]

Twitter Facebook LinkedIn

채린

1. 자료구조와 알고리즘

파이썬의 기본적인 데이터 타입

알고리즘(algorithm)이란?

실습

2. 선형 배열(Linear Arrays)

배열 : 원소들을 순서대로 늘어놓은 것

Python에서의 리스트(list) :

리스트(배열) 연산

실습

3. 배열 - 정렬과 탐색(Sorting & Searching)

Python 리스트의 정렬

정렬의 순서를 반대로

문자열 길이 순서대로 정렬하려면?

정렬 - 키를 지정하는 또 다른 예

탐색 알고리즘(1) - 선형 탐색(Linear Search)

탐색 알고리즘(2) - 이진 탐색(Binary Search)

실습

4, 재귀 알고리즘 기초

재귀함수(recursive functions)란?

예제 : 자연수의 합 구하기

실습

5. 재귀 알고리즘 응용

조합의 수 계산

조합의 수 계산 - 재귀적 방법으로

실습

6. 알고리즘 복잡도(Complexity of Algorithm)

Big-O Notation

선형 시간 알고리즘 - O(n)

로그 시간 알고리즘 - O(log n)

이차 시간 알고리즘 - O(n^2)

보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘

꽤나 복잡한 문제

7. 연결 리스트(Linked Lists) (1)

추상적 자료구조(Abstract Data Structures)

기본적 연결 리스트

자료 구조 정의

연산 정의

특정 원소 참조

배열과 비교한 연결 리스트

연습문제 - 리스트 순회

실습

8. 연결 리스트(Linked Lists) (2)

연결 리스트의 연산 - 원소의 삽입

코드 구현 주의사항

그런데 잠깐

연결 리스트 원소 삽입의 복잡도

연결 리스트 연산 - 원소의 삭제

코드 구현 주의사항

그런데 잠깐

연결 리스트 원소 삭제의 복잡도

연결 리스트 연산 - 두 리스트의 연결

실습

9. 연결 리스트(Linked Lists) (3)

연결 리스트가 힘을 발휘할 때

조금 변형된 연결 리스트

연산 정의

연결 리스트 연산 - 리스트 순회

연결 리스트 연산 - k번째 원소 얻어내기

연결 리스트 연산 - 원소의 삽입

원소의 삽입 - 코드 구현

메서드 insertAt()의 구현

연결 리스트 연산 - 원소의 삭제

코드 구현 주의사항

연결 리스트 연산 - 두 리스트의 연결

실습

10. 양방향 연결 리스트(Doubly Linked Lists)

양방향 연결 리스트(Doubly Linked Lists)

리스트 순회

리스트 역순회

원소의 삽입

특정 원소 얻어내기

원소의 삽입

실습1

실습 2

실습3

실습4

11. 스택

스택의 추상적 자료구조 구현

연산의 정의