2주차 월요일

정화·2024년 3월 25일

today what i learned

TIL

목록 보기

1/11

자료구조를 배우는 이유 : 각각의 문제마다 최적의 해법을 찾기 위해

선형배열

배열 (array) 이라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻하는데

Python 에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 리스트 (list) 라는 데이터형이 있다.

append 삽입

pop 끝에서 꺼내기

리스트의 길이와 무관하게 순식간에 할 수 있는 일.

이는 상수시간이 걸린다고 한다.

빅오 노테이션으로 나타내면 O(1)로 나타내면 상수시간이 걸린다고 생각하면 된다

대신 리스트가 길어질 수록 오랜 시간이 걸리는 것도 있다.

insert(몇번째 자리에, 무슨 값을 삽입할지) 삽입하면 그위치에 있는게 하나 뒤칸으로 다 이동

del(리스트[위치]) 리스트의 위치에 있는 값을 삭제하고 뒤에 있는 값을 다 앞으로 땡겨옴

리스트의 길이가 길면 오래 걸리는 일.

이는 선형시간이 걸린다고 한다.

빅오노테이션 : O(n)으로 나타낸다

배열 연산

원소 검색(탐색)
index('문자열')

당연히 선형시간일 것이다.

리스트 슬라이싱[ a:b ]

index를 했는데 리스트 안에 찾는값이 없다면 ValueError가 뜬다.

이를 해결하기 위해서는 try/except 매커니즘이 있다.

## try/except, pass문을 적절히 활용해보자
# pass : 파이썬에서의 빈(empty, null)문장으로서, 아무런 처리도 하지 않는다
# 인덱스 에러가 발생하는 경우에 대해서 테스트 해보자!

a = [1,2,3,4,5,6,7,8,9]
for i in range(20):
   try:#에러로부터 보호되는 코드부분
       print(a[i])
   except: #에러가 발생하면 실행되는 부분
       pass #그냥 지나가고 싶다면, pass문을 사용하면 된다.

# 만약 예외 처리 코드가 특정한 에러만을 고려하여 처리하도록 하고 싶다
# 그러기 위해선, except문에 에러 종류를 지정해주면 된다!

# 에러 종류를 지정하게 되면, 예외 처리 코드가 범용에서 특정형으로 바뀌기 때문이다

a = [1,2,3,4,5]
for i in range(10): 
    try:
        print(a[i])
    except IndexError: ##인덱스 벗어나는 에러를 잡았을 경우에 대해서만!
        print("list index out of range")
# 이번엔 ValueError에 대해서도 해보자.

a = [1,2,3,4,5]
a.index(10) #리스트 a에서 10이라는 item의 인덱스 위치를 반환한다.
            #하지만, 리스트a에는 10이 없기 때문에 에러가 발생!
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-7-dd96be22e3e8> in <module>
      2 
      3 a = [1,2,3,4,5]
----> 4 a.index(10) #리스트 a에서 10이라는 item의 인덱스 위치를 반환한다.
      5             #하지만, 리스트a에는 10이 없기 때문에 에러가 발생!

ValueError: 10 is not in list
# 위 경우에 대해서 try/except문을 활용해보자

a = [1,2,3,4,5]
try:
    print(a.index(10))
except ValueError:
    print("10 is not in list")
--------------------------------------------------------------------------------
10 is not in list

sort= 정렬 = 재배열

sorted() : 정렬된 새로운 리스트를 얻어냄

sort() : 기존 리스트를 정렬해줌

정렬의 순서를 반대로 하고싶으면 reverse = True를 추가하자

L2 = sorted(L,reverse=True)

L.sort(reverse=True)

이렇게!

근데 문자열로 이루어져있으면 문자열 길이 순이 아니라 알페벳 순으로 정렬이 된다.

문자열 길이 순서로 정렬하기 위해선 key를 지정해야한다.

sorted(L, key = lambda x: len(x))

key = 함수

이렇게 쓰이고 여기선 람다 함수를 썼다.

key = 함수, reverse = True 이렇게 둘 다 쓸 수 있다.

만약 리스트가 이중 리스트고 key=lambda x : x[0] 으로 쓴다면

이중리스트 안의 첫번째 값을 기준으로 정렬이 된다.

그리고 리스트 안에 집합이 들어있다면 그 집합에서 키를 기준으로 정렬할 수 있다.

key = lambda x : x['score']

라고 쓰면 score가 낮은 순으로 정렬이 된다.

탐색 알고리즘

선형탐색 = 순차탐색

앞에서부터 값이 나올 때까지 순차적으로 진행하는 것.

-> 리스트의 길이에 비례하는 시간 소요됨 : O(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

i가 0부터 시자개서 하나씩 커지고, 이게 리스트의 길이보다 커지거나 리스트의 i위치에 들어있는 값이 x와 같다면

와일문이 꺼진다.

그때까지 i는 계속 커진다.

와일문이 꺼졌을 때 i값을 리턴하면 x가 들어있는 인덱스값이 i라는 것을 알 수 있다.

만약 i가 리스트의 길이보다 커져서 꺼졌다면 그 값은 리스트 안에 없는 것이므로 -1을 리턴한다.

인덱스 메서드랑 같은 원리.

이진탐색 - 크기순으로 정렬되어있다는 가정을 갖고 실행

lower, upper, middle을 이용.

미들의 좌 우를 버린다..

미들이 그 값이 될때까지 진행.

한 번의 비교가 일어날때마다 리스트가 반 씩 준다 = divide & conquer

-> log n 에 비례하는 복잡도를 가지는 알고리즘이다.

이진탐색코드의 구현

lower = 0
upper = len(L) -1
idx = -1

while lower <= upper :
    middle= (lower+upper)//2

    if L[middle] == target : break -> 그리고 타겟이 middle 인덱스에 있다고 표시
    elif L[middle] < target : lower = middle+1
    else : upper = middle-1

idx = middle

이진탐색 구현해보기를 할 때 자꾸 효율성에서 오류가 떴는데,

if x in L 을 써서 그런거였다.

while문에서 lower<=upper 이 아닌 경우에 middle을 answer에 넣지 않게 하고,

기본 answer값을 =-1 로 했더니 해결되는문제였다..

if 같은 구문을 많이 쓰면 효율성이 떨어지는 것 같다.

최대한 중복되는 게 없도록 코드를 짜야할 것같다.

재귀

1부터 n까지의 합

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

이 코드는 에러가 난다.

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

이렇듯 재귀 호출의 종결 조건은 매우 중요하다.

알고리즘의 종결 조건에 특별히 주의를 기울여야 한다.

모든 재귀 알고리즘은 while문을 통해 코드를 작성하고 있다. 이때 카운터마운트를 항상 갖고 있게 되어있다.

재귀는 n이 커지면 함수를 여러번 돌려야 함. O(n)

while문도 여러번 반복해야함 O(n)

하지만 효율적인 측면에서 본다면 재귀함수가 훨씬 낫다.

재귀 알고리즘 추가 예제

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

위 코드는 팩토리얼을 구하는 예제

피보나치 순열은 앞선 두개의 항의 합으로 이뤄진다.

매우 재귀적!!! 급증한다.

이 코드를 recursive ver, iterativ ver 두가지 버전으로 써보는것이 실습예제

def solution(x):
    if x==0 or x== 1 : return x
    else:
        return solution(x-1)+solution(x-2)
def solution(x):
    i=0
    c=0
    a=0
    b=1
    if x <=1 : return x
    while i+2 <=x:
        c = b + a
        a = b
        b = c
        i +=1
        
    return c

이 내용을 참고했더니 잘 이해되었다.

문제 설명

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

인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

예를 들어,
L = [2, 3, 5, 6, 9, 11, 15]
x = 6
l = 0
u = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

또 다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
l = 0
u = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

2021년 9월 5일, 아래 질문에 의하여 테스트 케이스의 미비점이 드러났고, 보완하기 위하여 테스트 케이스 하나 (정확성 테스트 케이스 5번) 가 추가되었습니다.