1주차 - 1 [자료구조/알고리즘]

두괄식 요약

 

1. 컴퓨터에게 일을 잘 시키기 위해 자료구조와 알고리즘을 배운다.

2. 자료구조마다 시간 복잡도가 다르므로 이를 잘 숙지한다.

3. 단순한 선형 배열과 기본함수는 특히 시간복잡도를 고려해 활용할 것

4. 이분탐색은 강력하지만 정렬이 보장된 경우에만 사용 가능

5. 재귀는 익숙해지기만하면 반복(Iteration)과정에 직관적으로 간섭할 수 있다.

   (하지만 보편적으로 재귀는 시간복잡도상으로 불리하다. 순열과 조합을 기준으로 n이 20이상만 넘어가도 대개 TLE)

 

 

 

 

자료구조와 알고리즘 학습의 궁극적인 목표?

 

우리가 컴퓨터와 개발을 배우는 이유는 사람이 할 일을 컴퓨터에게 대신 시키기 위함입니다.

 

문제는 과제를 처리하기 위해 사용할 수 있는 컴퓨터의 자원은 한정됐다는 점입니다.

 

자료구조에 따라 컴퓨터의 수행시간과 메모리 사용량은 극명하게 달라지며

그에 따라 문제해결을 위해 우리가 선택 및 구현해야 할 알고리즘 역시 달라지게 됩니다.

 

자료구조의 중요성을 깨닫기 위해 쉬운 알고리즘 문제를 하나 예시로 들겠습니다.

 

https://www.acmicpc.net/problem/1620

1620번: 나는야 포켓몬 마스터 이다솜

 

문제가 길지만 요약하자면

내가 임의의 숫자 n을 입력하면 n번째 입력했던 포켓몬의 이름을, 임의의 포켓몬 이름 s를 입력하면

s라는 포켓몬을 내가 몇번째 입력했는지 숫자를 출력하는 프로그램을 작성하라는 문제입니다.

 

포켓몬의 수와 문제의 수는 최대 10만개 입니다.

단순히 배열로 포켓몬의 이름들을 받아내고 index() 함수로 프로그램을 작성하게 되면

최악의 경우 시간 복잡도가 10만 x 10만 즉, 100억까지 치솟게 됩니다.

 

가장 빠른 언어인 C++로 풀어도 100초가 넘게 걸리므로 시간 제한 2초 안에 풀지 못하게 됩니다..

 

풀이 방법

해시 자료구조(파이썬에서는 딕셔너리)를 사용하는 것이 이 문제의 출제 의도입니다.

 

즉, 자료구조 선택과 이에 따른 알고리즘 선택은 문제해결과 프로그램 개발의 기본중의 기본이라고 할 수 있겠습니다.

 

 

 

 

 

 

 

문제 풀이와 설명

문제 1)

오름차순으로 정렬된 리스트 L 과 정수 x를 입력 받아 x를 추가하되 정렬을 준수한 리스트를 반환하는 함수 작성

def solution(L, x):
    # L=[20, 37, 58, 72, 91]
    # x=100
    
    if x<=L[0]:
        L=[x]+L
        return L
    elif x>=L[-1]:
        L.append(x)
        return L
    
    for i in range(len(L)):
        if L[i]>=x:
            L.insert(i, x)
            return L

 

입력 받은 정수가 리스트 L의 최소값보다 작거나 최대값보다 크다면 별다른 절차 없이 x를 앞이나 뒤에 붙여주면 끝

 

 

 

 

 

문제 2)

리스트 L에 요소 x가 존재시 x의 인덱스를 반환하고 그렇지 않다면 -1을 반환하는 함수를 작성

def solution(L, x):
    lt, rt=0, len(L)-1
    
    while lt<=rt:
        mid=(lt+rt)//2
        if L[mid]==x:
            return mid
        elif L[mid]<x:
            lt=mid+1
        else:
            rt=mid-1
    
    return -1

 

입력 받은 리스트 L이 정렬되어 있는 것이 보장된 경우에만 이분탐색이 가능하다는 것에 주의

 

 

 

 

 

문제 3)

숫자 x가 입력되었을 때 x번째 인덱스에 해당되는 피보나치 수열의 수를 반환하는 함수를 작성

def solution(x):
    def DFS(x):
        if x==0:
            return 0
        elif x==1:
            return 1
        
        res=DFS(x-1)+DFS(x-2)
        return res
    
    return DFS(x)

주의 사항) 재귀의 이해를 위해서 입력되는 x의 크기가 작은 경우를 상정한 문제로

그에 맞춰 피보나치 수열 값들을 별도로 저장하지 않고 재귀만으로 푼 코드입니다.

즉, 위의 코드는 컴퓨터 자원을 효율적으로 활용하지 못합니다.

 

https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

위의 문제는 입력되는 수 x의 크기가 큰 경우를 상정한 문제이므로 꼭 풀어보기를 바랍니다.