[TIL_Carrotww] 13 - 22/09/16

📝Carrotww의 코딩 기록장

🧲 알고리즘

🔍 프로그래머스 피보나치 수

• 간단한 피보나치 수 문제이지만 개편되어 재귀로는 풀리지 않는 문제이다.
• 해결 법 : 다이나믹 프로그래밍

def solution(n):
    temp = {1: 1, 2: 1}
    for i in range(3, n + 1):
        temp[i] = (temp[i - 1] + temp[i - 2]) % 1234567
    
    return temp[n]

🔍 다른 사람은 리스트에 저장하여서 temp[i].append( ~~)
같은 식으로 문제 풀이를 하였는데 문제가 간단하여 상관은 없겠지만 코드가 길어지만 그 방식이 조금 더 직관적으로 보인다.
🔍 이런식의 동적 프로그래밍 문제 접근을 할 때 2차원 배열, dict 를 난 먼저 떠올리는데 다양한 방법으로 떠올려야겠다.

🧲 DFS

🔍 DFS 구현해 보기 Stack, Recursion 두 가지 방식

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

🔍 재귀 구현 - python

visited = []
def dfs_recursion(adjacent_graph, cur_node, visited_array): # 함수 호출 시 cur_node 1 대입
    visited_array.append(cur_node)
    for ad in adjacent_graph[cur_node]:
        if ad not in visited_array:
            dfs_recursion(adjacent_graph, ad, visited_array)
    return

🔍 스택 구현 - python

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node] # 이 함수 호출 시 start_node 1 대입
    visited = []
    while stack:
        temp = stack.pop()
        visited.append(temp)
        for ad in adjacent_graph[temp]:
            if ad not in visited:
                stack.append(ad)

    return visited

🧲 잡설

🔍 처음 알고리즘을 접하고 공부를 시작할때 가장 이해가 안됐던 것은 재귀 였다. 재귀를 이용한 문제풀이는 아직도 재밌고 흥미가 있다.
시간이 없어 stack, queue, heap 등 자료 구조들을 구현을 못해봤었는데 이런식으로 하나씩 해보니 기억에 남고 좋은 것 같다.
지금은 다이나믹프로그래밍 문제가 가장 재미(?) 흥미로움을 많이 준다.
문제를 맞닥뜨렸을때 처음 알고리즘을 접했을때와 같은 기분을 많이 준다.
간단해 보이지만 어떤 식으로 접근해야할지 감이 안잡히는...
많이 풀다보면 익숙해질 것이라 생각한다 ㅎㅎ

• 오늘 끝!
• 사실 이렇게 쓰고 문제를 또 푼다...ㅎ