파이썬 자료구조 알고리즘, 코딩테스트 문제, n번째 피보나치 수 구하기

자료구조 & 알고리즘

 

그래프

자료구조는 크게 비선형구조, 선형구조로 구분된다.

선형은 말 그대로 선 Line 처럼 생긴 그래프이고 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다.

 

 

비선형은 이런 구조의 그래프를 말한다.

 

 

 

[그래프에서 사용되는 용어]

 

1. 노드(Node) : 연결관계를 가진 각 데이터를 의미한다. 정점(Vertex)라고도 함

2. 간선(Edge) : 노드 간의 관계를 표시한 선

3. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

 

예를 들어 이렇게 연결 되어있다고 했을 때

 

제니, 연우, 지수, 사나는 각각 노드

이들을 연결하는 선들은 엣지

지수와 연우는 인접해있고, 제니와 지수는 인접해있지 않다.

 

 

[그래프 유형]

• 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능
• 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다.

 

 

[그래프 표현 방식]

아까 그 제니 연우 사나 지수라는 노드를 숫자로 표기하면

 

1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

 

인접 행렬, 2차원으로 이렇게 표현하거나

 

    0  1   2   3

0  X  O  X  X

1  O  X  O  X

2  X  O  X  O

3  X  X  O  X

 

배열로 이렇게 표현할 수 있다.

graph = [
        [False, True, False, False],
        [True, False, True, False],
        [False, True, False, True],
        [False, False, True, False]
]

 

 

2. 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

 

0 → 1

1 → 0 → 2

2 → 1 → 3

3 → 2

 

딕셔너리로 표현하면 이렇게 된다.

graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

필요에 따라 쓰면 되는데, 주로 인접리스트를 많이 쓴다.

---

 

피보나치 수열 문제

 

n을 input으로 입력받아, n번째 피보나치 수를 구하는 함수 재귀함수로 만들기

 

휴.. 생각보다 쉽지 않았다..

일단 피보나치 수열의 첫번째 값과 두번째 값은 1로 고정이니까 맨 처음에 .

 

def fibo(n):
    if n == 0:
        return f"0번째 수는 없음 None"
    elif n == 1:
        return 1
    elif n == 2:
        return 1

    fibo_num_list = [1, 1]
    for i in range(2, n+1):
        fibo_num_list.append(fibo_num_list[i-2] + fibo_num_list[-1])

    return fibo_num_list[n-1]

print(fibo(0)) # 0번째?: None
print(fibo(1)) # 1
print(fibo(2)) # 1
print(fibo(3)) # 2
print(fibo(5)) # 5
print(fibo(6)) # 8
print(fibo(10)) # 55

 

이렇게 하고 잘 되서 좋아했는데.. input으로 n을 받아야 했다. 그래서 다시 이렇게 수정했다.

def fibo(n):
    if n == 0:
        return f"0번째 수는 없음 None"
    elif n == 1 or n == 2:
        return 1

    fibo_num_list = [1, 1]
    for i in range(2, n+1):
        fibo_num_list.append(fibo_num_list[i-2] + fibo_num_list[i-1])

    return fibo_num_list[n-1]

n = int(input(f"n번째 피보나치 수는? 숫자 n을 입력하세요"))
print(fibo(n))

 

근데... 재귀함수를 안 썼네...

재귀함수는 함수 안에서 자기 자신을 함수로 호출하며

반복하는 일이 무엇인지 알아야 하고 종료조건이 무엇인지 알아야 한다..

 

음..