[Week2 자료구조/알고리즘] TIL 1일차 - 리스트

자료구조의 필요성

상황에 알맞은 자료구조를 선택하면, 시간 단축의 이점을 얻을 수 있음

알고리즘

자료구조와 연산을 알맞게 선택하는 것

 

0) 알고리즘 복잡도

시간, 공간 자원을 얼마나 필요로 하는지에 대해 표현하는 것

 

- 선형 시간 복잡도 O(${n}$)

- 로그 시간 복잡도 O(${log n}$)

ex) 정렬된 수목록에서 특정값을 찾기 위해 이진트리 알고리즘을 사용

- 이차 시간 복잡도 O(${n^2}$)

ex) 삽입정렬

 

cf) 가장 적은 시간복잡도를 갖는 정렬 알고리즘 : 병합정렬 (divide and conquer)

나눌 때 O(${log_n}$) * 합칠 때 O(${n}$)

ex) 배낭문제

 

1) 선형배열 (List)

연산

- 원소 추가

L.append(value)

- 원소 삭제

del(L[index])

L.pop(index)

- 원소 삽입

L.insert(index, value)

- 정렬

sorted(L) : 정렬된 새로운 리스트를 반환

L.sort() : 해당 리스트를 정렬

cf) 함수의 매개변수

• reverse=True :  역순으로 정렬할 수 있게 하는 옵션
• key=조건 : 조건식을 기준으로 해당 리스트를 정렬

cf) 조건에는 주로 lambda 함수를 이용한다.

ex1) 원소의 길이를 기준으로 정렬 lambda x:len(x)

ex2) 딕셔너리의 key 값을 기준으로 정렬 lambda x:x["index0"] : key가 index0인 딕셔너리 값을 기준으로 정렬

주어진 리스트

[{”index0” : 3, “index1” : 2}, {”index0” : 0, “index1”: 4}]

결과 리스트

[{”index0” : 0, “index1”: 4}, {”index0” : 3, “index1” : 2}]

 

탐색 알고리즘

- 선형 탐색 O(${n}$)

리스트 앞에서부터 순차적으로 탐색하는 알고리즘

- 이진 탐색 O(${log n}$) 

탐색하려는 리스트가 정렬되어 있다는 전제를 가지고 값을 탐색하는 알고리즘

한 번 연산이 이뤄질 때마다 탐색해야 하는 리스트의 범위가 반으로 줄어들게 됨

 

메인 로직

lower : 맨 앞의 인덱스(제일 작은 값의 인덱스)

upper : 맨 뒤의 인덱스(제일 큰 값의 인덱스)

middle : (lower+upper)//2

• • middle 인덱스의 값이 탐색하려는 값보다 작으면 lower=middle+1
  • 탐색하려는 값보다 크면 upper=middle-1
  • 탐색하려는 값과 같으면 middle 반환

 

1) 재귀 알고리즘을 이용한 풀이

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)

2) 반복문을 사용한 풀이

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

    return answer

 

2) 재귀 알고리즘

하나의 함수에서 자기 자신을 호출하여 작업을 수행하는 알고리즘.

대부분 반복문을 수행하는 연산보다 효율성이 낮으나, 사람의 사고방식 그대로 구현할 수 있기 때문에 사용

종결조건이 필요함에 주의하자!

대표적인 문제

🎄이진트리

• 오른쪽 서브트리는 항상 root보다 클 것
• 왼쪽 서브트리는 항상 root보다 작을 것

 

🔅 자연수의 합

• 자연수의 합 구하는 문제

 

🦆 조합의 수(Combination)

N개의 서로 다른 원소에서 M개를 뽑는 것

조합의 수 ${\frac{N!}{M!(N-M)!}}$ 는 다음과 같은 두가지 경우로 쪼개어 생각할 수 있다.

• 특정 원소를 포함하는 경우
• 특정 원소를 포함하지 않는 경우

이를 이용하여 조합을 재귀적으로 계산할 수 있다.

combi(n, m) = combi(n-1, m-1)+combi(n-1, m)

${\frac{N!}{M!(N-M)!}}$ = ${\frac{(N-1)!}{(M-1)!(N-M)!}}$ + ${\frac{(N-1)!}{M!(N-1-M)!}}$

 

🏗️ 하노이의 탑

세 개의 기둥에 원판을 꽂을 때, 큰 원판이 작은 원판 위에 얹히지 않고 최소로 원판을 옮기는 경우의 수

 

1) 재귀 알고리즘을 이용한 풀이

def Hanoi(n, start, end):
    temp=6-start-end
    if n==1:
        return [[start, end]]
    else:
        return Hanoi(n-1, start, temp)+[[start, end]]+Hanoi(n-1, temp, end)

def solution(n):
    return Hanoi(n, 1, 3)

프로그래머스

 

🧑‍🦰 피보나치수열

F(0) = 0, F(1)=1 일 때, F(n)=F(n-1)+F(n-2)인 수열

 

1) 재귀 알고리즘을 이용한 풀이

def fibonacci(x):
    if x==0:
        return 0
    if x==1:
        return 1
    return fibonacci(x-1)+fibonacci(x-2)
def solution(x):
    return fibonacci(x)

2) 반복문을 사용한 풀이

def solution(x):
    last_2=0
    last_1=1
    if x==0:
        return 0
    answer=0
    for i in range(2, x+1):
        answer=last_2+last_1
        last_2, last_1=last_1,answer 
    return answer

관련 문제

프로그래머스