파이썬자료구조(1-4)_안녕,자료구조&알고리즘!

1강. 자료구조 & 알고리즘

1강 자료구조 알고리즘 소개
선형 배열
정렬과 탐색
재귀 알고리즘 기초

Q) 자료구조는 왜 알아야 하는가?

n = int(input("Number of elements : "))
haystack = [k for k in range(n)]
print("Searching for the maxinum value...")
ts = time.time()
maxinum = max(haystack)
elapsed = time.time() - ts
print("Maxinum element = %d, Elapsed time = %.2f" % (maximum, elapsed))

입력값이 늘어날수록, 시간이 확연이 걸린다.

내가 이용하는 자료 구조가 어떤 성질을 가져야 하는가에 대해서 알아야 한다.

알고리즘은 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합 프로그래밍 에서는 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택을 의미한다.

Q) 100개의 수 중에 549를 찾는다면 ? 사람이 눈으로 보는 것처럼, 규칙없이 늘어서 있으면, 가로세로로 뒤져보면서 봤던 걸 또 보지 않는 방법으로 찾아야 한다.

하지만 수가 정렬되어있다는 조건이 있다면 ? 쉽게 549를 발견할 수 있다.

해결하고자 하는 문제에 따라 최적의 해법은 서로 다르고 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다.

과제 : 프로그래머스 테스트에 익숙해지기

-> 그냥 슬라이스 해서 더해준 뒤 리턴하면 끝

2강. 선형배열 (Linear Arrays)

파이썬

배열이 따로 데이터 타입으로 존재 x 파이썬의 리스트는 배열보다 더 융통성 있는 자료구조 제공

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

2,7,-2,5,10 0,1,2,3,4 (index)

파이썬에서도 배열은 0부터 시작한다.

리스트 배열 연산
리스트 끝에 덧붙이기 -> L.append()
리스트 끝에서 꺼내기 -> L.pop() => 상수시간
리스트 연산 (리스트의 크기가 커지면 커질수록 시간이 오래걸림)
리스트 삽입 -> L.inert(3,65)
리스트 삭제 -> del(L[2]) => 리스트의 길이에 비례(선형 시간)
[del과 pop의 차이]https://stackoverflow.com/questions/11520492/difference-between-del-remove-and-pop-on-lists
remove(리스트 요소의 값)
del a[1] 리스트 요소의 인덱스
pop은 리스트의 인덱스로 삭제하고 반환까지 해준다.

실습 답안

def solution(L, x):
    if(L[-1] < x):
        L.append(x)
        return L
    for idx, i in enumerate(L):
        if(x < i):
            L.insert(idx, x)
            return L

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


print(solution([64, 72, 83, 72, 54], 49))

3강 정렬과 탐색

정렬

sorted()

내장함수
정렬된 새로운 리스트를 얻어냄

sort()

리스트의 method
해당 리스트를 정렬함

정렬의 순서를 반대로

reverse = True
L2 = sorted(L,reverse=True)
L.sort(reverse=True)

파이썬의 리스특 문자열로 이루어진 경우라면 ?

정렬 순서가 사전에 나타난 순서(알파벳 순서를 따름)
문자열 길이 순서로 정렬하려면 ? -> 정렬에 이용하는 key지정
ex) sorted(L, key = lambda x: len(x)) : 길이 순서대로 정렬 (같으면 앞에있는 것 부터)
키를 지정하는 또 다른 예
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)
레코드들을 점수 높은 순으로 정렬

탐색

선형탐색 (Linear Search)

리스트의 길이에 비례하는 시간 소요

이진탐색 (Bianry Search)

탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용이 가능
O(log n) (divde & conquer)
정렬되어야만 가능하기 떄문에 이진탐색이 항상 답이라곤 볼 수 없다.

def solution(L, x):
    start = 0
    end = len(L)-1
    while(start <= end):
        middle = (start + end)//2
        if(x == L[middle]):
            return middle
        elif(L[middle] > x):
            end = middle - 1
        else:
            start = middle+1
    return -1

4강 재귀 알고리즘 기초.

드디어 재귀 알고리즘이네

재귀함수란 ? : 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
생각보다 많은 종류의 문제가 재귀적으로 해결 가능하다.
ex) 이진트리 - 왼쪽 서브트리의 원소들은 모두 작거나 같을 것, 오른쪽 서브트리의 원소들은 모드 틀 것.
재귀 함수를 이용하면 트리를 만들기 편하다.
트리를 보고 10을 찾으라고 한다면 ? -> 이것도 재귀적으로 찾을 수 있다. 이진 탐색의 경우와 비슷하게 이루어진다.
루트노드인 12에서 찾으려고 시작한다. 10을 찾으려면 12보다 작으니 왼쪽으로, 10은 9보다 크니 오른쪽으로 이런 식이다.
보다 간단한 예 자연수의 합 구하기: 1부터 n까지의 모든 자연수의 합을 구하시오
def sum(n) return n+sum(n-1) -> maximum recursion depth exceeded
재귀를 멈출 조건을 넣어준다. if n<=1 일때, return n 해주고, else:로 연결해주기

재귀 함수의 종결 조건

def sum(n):
    if n ...:
        # 매우 중요
    else :
        sum()

재귀 알고리즘의 효율

모든 재귀 알고리즘은 반복문으로 대체가 가능하다.
recursive version vs Iterative version
둘다 복잡도는 O(n). 하지만 효율적 측면에서 recursive는 함수 호출에 관한 부가적인 작업량이 많다.
재귀 알고리즘 추가 예제

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

팩토리얼 정의 자체가 재귀적이기에, 직관적으로 보기 좋다

실습 피보나치 수열

재귀적 방법 사용

def solution(a):
    if(a <= 1):
        return a
    else:
        return solution(a-1) + solution(a-2)


print(solution(10))

반복적 방법 사용

def solution(a):
    A, B = 0, 1
    for i in range(a):
        if(i % 2 == 0):
            A = A+B
        else:
            B = A+B
    if A > B:
        return B
    else:
        return A
    return a

참고사항

맨날 까먹는다. 파이썬 삼항 연산자
참인경우 값 if 조건 else 거짓인경우 값

참고자료 [파이썬_자료구조_알고리즘]https://programmers.co.kr/learn/courses/57