[AI class day 1] 파이썬 자료구조와 알고리즘 TIL

del(lst[2])
print(lst)

* 국가에서 지원하는 K-digital training 인공지능 코스를 수강하게 되었다.

여러 기관에서 이 코스를 진행하는 것으로 알고 있고, 상세한 커리큘럼과 난이도는 조금씩 다르다고 한다.

내가 수강하는 기관은 매일 매일 공부한 내용을 정리하여 포스팅할 것을 권장한다.

그날 공부한 내용을 정리하고 잘 몰랐다가 알게 된 것들에 대한 기록을 남기려고 한다.

 

*감상

: 솔직히 7~9강의 연결리스트는 너무 어려웠다.

파이썬 클래스에 대해서 배운 적이 있기는 하지만, (작년 11월에 파이썬 입문 수업 때)

지난, 1~3월에 들었던 빅데이터 분석 수업에서는 거의 활용하지 않았었기 때문에 가물가물하다.

솔직히 여기서 너무 헤매서 커리큘럼에서 하루 동안 제시한 진도를 모두 마무리하지 못했다.

<번외> 문자열 내에서 변수 출력하는 여러 방법 중 %

%s 문자열(string)

%d 정수(integer)(앞에 0붙일 수 있음 %03d 는 d 까지 합쳐서 총 3자리가 되도록 앞에 0을 붙이라는 뜻)

%f 실수(float) (실수는 소수점자리 지정가능 %.2f 는 소수점 둘 째자리까지 표시)

 

a = "Jane"
print("Hello! I'm %s." % (a))

결과 > Hello! I'm Jane.

num = 11
print("The room number is %03d." %(num))

결과 > The room number is 011.

 

ts1 = time.time()
stack = [k for k in range(1000000)]
ts2 = time.time()
elapsed = ts2-ts1
print("elapsed time = %.2fs." % (elapsed))

결과 > elapsed time = 0.09s.

 

본 강의는  프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지? 와 동일한 것 같다.

커리큘럼이 동일하다.

1. 자료구조와 알고리즘

 

• 웬만한 것들을 Python에서 이미 제공하는 데이터 타입으로 다 해결할 수 있는데 왜 자료구조를 알아야 하는건지
  • 효과적으로 해결하고자 하는 문제가 무엇이냐에 따라서 적합하게 이용하려는 자료구조가 달라짐
  • 기본적으로 제공되는 데이터 타입만으로는 해결할 수 없는 문제가 있다
• 알고리즘이란?
  • 사전적 정의
    • 어떤 문제를 해결하기 위한 절차, 방법, 명령어 들의 집합
  • 프로그래밍
    • 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
• 해결하고자 하는 문제에 따라 (응용 종류와 범위에 따라) 최적의 해법은 서로 다르다 -> 선택을 위해 자료구조를 이해해야 함

2. 선형 배열 (linear array)

• 배열 array : 데이터를 순서대로 늘어놓은 형태
• 리스트 list : 파이썬의 데이터형
• 파이썬 리스트에서 사용할 수 있는 연산
  • 리스트 길이와 실행시간 관계없는 연산 (상수 시간, O(1)) : .append() (끝에 원소 하나 붙이기), .pop() (끝에 원소 하나 빼기)
  • 리스트 길이와 실행시간 비례하는 연산 (선형 시간, O(n)) : .insert() (원소 삽입), del() (원소 삭제)
  • 그외 : .index() (원소 탐색)

lst = [5,60,20,14, 98,88]
lst.insert(2, 25)
print(lst)

결과 > [5, 60, 25, 20, 14, 98, 88]

del(lst[2])
print(lst)

결과 > [5, 60, 20, 14, 98, 88]

 

*.pop() 과 del()의 차이점

lst = [5,60,20,14, 98,88] 
print(lst.pop(2))
print(lst)

결과> 20

          [5, 60, 14, 98, 88]

 

lst.pop(2) del(lst[2])와는 달리 빼는 값을 반환한다.

lst = [5,60,20,14, 98,88] 
del(lst[2])
print(del(lst[2]))
print(lst)

결과 > print(del(lst[2]))

                        ^      

          SyntaxError: invalid syntax

 

3. 정렬과 탐색 (sort and search)

1) 정렬

• 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업
• Python의 리스트는 내장된 정렬기능이 있다
  • 파이썬 내장 함수 : sorted()
    • 정렬된 새로운 리스트를 return
  • 리스트 메서드 : sort()
    • 해당 리스트를 정렬해서 리스트 자체가 바뀜
  • 정렬의 순서를 반대로 하고 싶을 때: reverse=True
• string 정렬
  • 알파벳순 정렬
  • 대문자가 소문자보다 우선
  • 문자열 길이 순서로 정렬하고 싶다면?  람다 활용해서 key 지정해서 정렬

2) 탐색

• 복수의 원소로 주어진 데이터에서 특정 원소를 찾아내는 작업
• 선형탐색 linear search, 순차탐색 sequential search
  • 순차적으로 모든 요소를 탐색
  • O(n)
•  
• 이진탐색 binary search
  • 배열이 이미 정렬되어 있을 때만
  • 한번 비교가 일어날 때마다 리스트의 길이를 반씩 줄임(divide & conquer)
  • O(log n)
• 이진탐색이 빠르지만, 정렬에 대한 복잡도를 생각해봐야 한다

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

def binary_search(L, x):
    min = 0
    max = len(L) - 1
    idx = -1

    while min <= max:
        middle = (min + max) //2
        if L[middle] == x:
            idx =middle
            break
        elif L[middle] < x:
            min = middle + 1
        else:
            max = middle - 1
    
    answer = idx
    return answer

 

4. ~5. 재귀 알고리즘

• 같은 알고리즘을 반복적으로 적용해서 풀어내는 방법
• 재귀함수(recursive function) : 하나의 함수에서 자기 자신을 다시 호출해서 작업하는 것
• 종결 조건 (수학에서는 점화식)이 필요

ex>

1. binary tree

2. 자연수의 합 구하기

3. n!

 

예제> 피보나치 순열을 1)재귀적 방법으로 2)반복적 방법으로 프로그래밍하기

 

• 재귀 버전recursive version 은 항상 counterpart 인 반복 버전iterative version이 있음 -> 무엇이 더 효율적일까? 복잡도가 더 낮은가? 고려해봐야 한다 ex> 재귀 함수 내에서 함수를 2번 이상 부르는데, n값이 매우 커지면 어떻게 되겠는가?

6. 알고리즘의 복잡도

1) 시간 복잡도 time complexity : 문제의 크기와 해결하는데 걸리는 시간 사이의 관계

2) 공간 복잡도 space complexity :  문제의 크기와 해결하는데 걸리는 메모리 공간 사이의 관계

 

알고리즘의 복잡도란 1), 2)로 컴퓨터의 자원을 얼마나 잡아먹느냐 라는 개념

 

시간 복잡도는 더 구체적으로

1) 평균 시간 복잡도 average time complexity : 임의의 입력 패턴을 가정했을 때 소요되는 시간 평균

2) 최악 시간 복잡도 worst-case time complexity: 가장 긴 시간을 소요하게 만드는 입력에서 소요되는 시간

 

특히 2)가 중요함

 

• Big O notation : 함수의 증가 양상을 대강 파악 가능
  • O(n) 복잡도를 가지는 알고리즘 = 원소의 개수가 n개면 이에 비례해 소요 시간 증가
  • O(logn) : 입력 크기의 로그에 비례하는 소요 시간 증가

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

ex> linear search : n개의 무작위로 나열된 수에서 최댓값을 찾기

• Average case: O(n)
• Worst case : O(n)
• 모든 수를 다 탐색 하기 때문에 같음

2) 로그 시간 알고리즘 - O(logn)

ex> binary search : n개의 정렬된 수에서 특정값 찾기

• O(logn)의 복잡도를 가지고 문제를 풀 수 있으면 효율적

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

ex>  insertion search : 삽입 정렬(정렬할 요소를 정렬된 요소 중 어느곳에 넣어서 정렬된 상태를 유지)

• Best case: O(n) : 이미 정렬이 된 상태
• Worst case: O(n^2) : 역순으로 늘어서 있을 때

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

• merge sort 병합정렬 - O(nlogn)
  • 입력 패턴에 따라 정렬 속도 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음
    1. 정렬할 데이터를 반씩 나누어 각각을 정렬시킴 : O(logn)
    2. 정렬된 데이터를 두 묶음씩 한데 합친다 : O(n)
    3. 전체적으로 O(nlogn)이 된다

* 복잡한 문제 ex> knapsack problem : 모든 경우의 수를 구해서 해결하면 O(n^2)

 

7~9. 연결 리스트 Linked Lists

• 추상적 자료 구조

1) 데이터 : 정수, 문자열....

2) 연산  a set of operations : 삽입, 삭제, 정렬, 탐색...

 

linear array 와 linked list 의 차이

• 선형 배열 : 번호가 붙여진 칸에 원소를 채워넣은 것
• 연결 리스트: 원소들을 줄줄이 엮어서 관리

• 연결 리스트의 장점
  • 삭제, 삽입 등 처리를 선형 배열보다 빠르게 가능
• 연결 리스트의 단점
  • 메모리 소요가 더 큼 : 링크 또한 저장해야 하므로
  • n번째 원소를 찾는데 오래 걸림 : 선형 배열은 붙여진 번호를 이용할 수 있어 쉬운 반면, 연결 리스트는 앞에서 부터 하나씩 링크를 따라가면서 찾아야 함
• 연결 리스트의 기본 자료 구조
  • Node :Data, Link(next)
  • 맨 앞 노드는 head, 맨 뒤 노드는 tail
  • node의 갯수
• 연결 리스트에 가할 수 있는 연산 정의
  • 특정 원소 참조
  • 리스트 순회 (traversal)
  • 길이 얻어내기
  • 원소의 삽입(insertion)/ 삭제(deletion)
  • 두 리스트 합치기(concatenation)
• 더미노드 dummy node: 데이터 원소를 담고 있지 않은 자리만 차지하는 노드
  • 더미노드가 있는 연결 리스트로 위의 6개 연산 구현하기

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

• 링크가 앞뒤로 다 연결되어있는 리스트
• 더미 노드도 head와 tail에 다 있음
• 메모리를 더 많이 잡아먹고, 리스트의 모습은 복잡해 지지만 연산 코드는 깔끔해짐 (예외 처리해야할 경우가 줄어듦)
• 위치 참조, 삽입, 삭제 등에서 binary search 활용 가능 (head에서 순방향, tail에서 역방향으로)

11. 스택(Stacks)

1) 스택이란?

• 자료를 보관할 수 있는 선형구조
  • 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(push 연산), 꺼낼 때에는 넣었던 쪽에서 뽑아 꺼내야 하는 제약이 있다.(pop연산)
• 꺼낼 때 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조
• 마지막에 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 스택을 다른 말로는 후입선출(LIFO, Last In First Out) 자료구조

2) 스택의 동작

• 초기상태: 비어있는 스택(empty stack) S = stack()
• 데이터 원소 A를 스택에 추가 S.push(A)
• 데이터 원소 B를 스택에 추가 S.push(B)
• 데이터 원소 꺼내기 맨 위의 B가 r1에 담김 r1 = S.pop()
• 데이터 원소 한번 더 꺼내기 A가 r2에 담김 r2 = S.pop()

3) 스택에서 발생할 수 있는 오류

•  비어있는 스택에서 데이터 원소를 꺼내려 할 때 : 스택 언더플로우(stack underflow)

• 꽉 찬 스택에 데이터 원소를 넣으려 할 때: 스택 오버플로우(stack overflow)

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

• 배열 array : 파이썬의 리스트와 메서드 이용
• 연결리스트 linked list : 양방향 연결 리스트 이용
• 연산의 정의
  • size() : 현재 스택에 들어있는 데이터 원소의 수를 구함
  • isEmpty() : 현재 스택이 비어있는지를 판단
  • push(x) : 데이터 원소 x를 스택에 추가
  • pop() : 스택의 맨 위에 저장된 데이터 원소를 제거 또한, 반환)
  • peek() : 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)
• 라이브러리도 있다 (from pythonds.basic.stack import Stack)

5) 연습문제 = 수식의 괄호 유효성 검사

• 올바른 수식

(A+B)

{(A+B)*C}

[(A+B)*(C+D)]

• 올바르지 않은 수식

(A+B

{A+(B*C})

[(A+B)*(C+D)}

 

--> 정리하면

• 수식을 왼쪽부터 한 글자씩 읽어서 여는괄호를 만나면 스택에 푸시(마지막으로 여는 괄호를 기록)
  
• 닫는 괄호를 만나면 팝  -->이 때 비어있으면 x(열리지 않은 괄호를 닫았으므로), 팝했을 때 쌍을 이루는지 검사
• 끝까지 검사한 후, 스택이 비어 있어야 올바른 수식(아니면 연 괄호를 닫지 않은 것임)