22.05.18 개발 일기

오늘의 계획

1. 자료구조(그래프) 강의 수강 [ O ]
2. 자료구조(DFS)강의 수강 [ O ]
3. LeetCode 문제 풀기 [ O ]

그래프(Graph)

• 정점과 간선으로 구성되어 네트워크 구조를 추상화한 비선형 자료 구조
• 그래프 특징
  • 정점(Vertex)== 노드 과 간선(Edge)의 집합
  • 다양한 그래프 종류를 혼합하여 표현 가능
• 그래프 종류
  • 방향 그래프(Directed Graph) : 간선에 특정 방향이 존재하는 그래프( A -> B로 표현, A에서 B로만 이동 가능)
  • 무방향 그래프(Undirected Graph) : 간선에 특정 방향이 존재하지 않는 그래프(A - B 로 표현, 양방향 이동 가능)
  • 가중치 그래프(Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
  • 연결 그래프: 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
  • 비연결 그래프 : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프
  • 순환 그래프 : 단순 경로의 시작 정점과 종료지점이 동일하여 순환 지점이 존재하는 그래프
  • 비순환 그래프 : 순환 지점이 존재하지 않는 그래프
  • 완전 그래프 : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 그래프 표현 방법
  • 인접 리스트 : 정점에 연결된 다른 정점을 리스트로 표현
  • 인접 행렬 : 정점에 연결된 다른 정점을 정점x정점 크기의 매트릭스로 표현

DFS ( Depth First Search)

• 트리나 그래프 등에서 하나의 노드를 최대한 깊게 들어가면서 해를 찾는 탐색 기법
• 장/단점
  • 장점 : 인접한 후보 노드만 기억하면 되므로 적은 기억공간 소요, 노드가 깊은 단계에 있을 경우 빠르게 정담 산출
  • 단점 : 선택한 경로가 답이 아닐 경우 불필요한 탐색 가능, 최단 경로를 구할 시 찾은 해가 정답이 아닐 경우 발생
• 구현 메서드
  • 재귀를 이용한 탐색 : Graph._dfsRecursiveVisit()
  • 스택을 이용한 탐색: Graph._dfsLoopVisit()
• 순열과 완전 탐색시 사용이 자주 된다.

오늘은 어제를 참고하여 계획을 세우고 계획했던것은 다 할 수 있었는데, LeetCode 문제가 LinkedList 리버스 시키는 문제였는데, 이해가 잘 되지 않아서 몇번 더 코드를 보고 익숙해져야 할 것 같다.
오늘도 매주 있는 제로베이스 코딩테스트 날이지만, 머리가 굳은것인지 문제 이해 하는게 너무 힘들어서 최대한 이해한대로 풀어봤지만 폭망했다...ㅜㅜ;;;

오늘은 코딩테스트 알고리즘 자료구조에 대해서 고민이 많은 하루가 된거 같다....