[TIL] 그래프, DFS, BFS, 동적계획법.....반갑다....

*20221117의 회고

 

   오늘은 그래프, dfs, bfs 그리고 동적계획법에 대해 배웠다. 

 

• 그래프 
  • 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조
  • 비선형 구조 -> 연결 관계에 초점이 맞춰져 있다. (선형구조 -> 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다. ex) 배열) 

 

• 그래프를 컴퓨터에서 표현하는 방법
  
  • 인접행렬 : 2차원 배열로 그래프의 연결관계를 표현
  • 인접리스트 : 링크드리스트로 그래프의 연결관계를 표현
  • 인접행렬과 인접리스트의 차이 ? -> 시간 vs 공간
    • 인접행렬은 데이터의 접근이 빠른 대신, O(노드^2)의 공간만큼을 사용해야 함
    • 인접리스트는 연결된 간선만큼 탐색해야 하므로 데이터 접근 시 O(간선) 만큼의 시간이 걸리지만, O(노드 + 간선) 만큼의 공간만 필요함 

 

• DFS(Depth First Search) : 깊이 우선 탐색
  • 끝까지 파고드는 것 -> 그래프의 최대 깊이 만큼의 공간을 요구함 => 공간을 적게씀
  • 끝까지 보기 때문에 최단 경로를 탐색하기 쉽지 않음
  • 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른방향으로 다시 탐색
  • 스택으로 구현
  • tree에서 inorder, preorder, postorder 가 여기에 포함됨

 

• BFS(Breadth First Search) : 너비 우선 탐색
  • 갈라진 모든 경우의 수를 탐색 -> 공간을 많이 씀, 시간도 오래 걸릴 수 있음
  • 레벨 단위로 탐색
  • 큐로 구현

 

• 동적 계획법
  • 여러개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘
  • 재귀함수와의 차이점 : 그 결과를 기록하고 이용한다. (재귀는 이용 X)
  • 동적 계획법을 이용하기 위해 필요한 원칙 2가지
    • 부분문제(반복되는 형태로 문제가 계속해서 파생되는게 있는지)
    • 메모이제이션(memoization)
  • 위에서 아래로 내려가며 구하는 방식 : Top down
  • 아래에서 위로 올라가며 구하는 방식 : Bottom up

 

 

   역시나 개념은 이해하기 어렵지 않았다. 구현이 문제다 ㅎㅎ 구현이 문제라는 것은 곧 자바 문법이 아직 미숙하다는 뜻! 어려운 코드들을 여러번 보고 계속 이해하려 공부하다 보면 언젠가 해결 될 문제다! 조급함은 갖지 않으려고 한다. 알고리즘 책의 맨 앞페이지에 이런 말이 있다. '준마는 하루에 천리를 가지만 둔마도 열흘 동안 부지런히 가면 천리를 갈 수 있다. - 순자' 이 말을 보고 조급함을 갖지 말자고 생각했다. 속도보다는 확실하게 아는게 중요하기 때문이다. 뒤로 물러나지 않는 것도 노력이 필요하기에, 하루하루 최선을 다해 엉덩이로 공부해보자! ㅋㅋㅋ 오늘도 고생 많았고 내일도 열심히 해보자 !