[TIL - 231115] DFS 구현

오늘 한 일

• DFS 구현
• 인접 행렬, 인접 리스트 구현
• 기업지원 진행

DFS

• DFS 구현 방법을 Javascript로 정리하였다.
• 재귀함수와 스택을 이용하는 방법으로 정리
• 코딩테스트를 풀어보면서 적용해야 할 것 같다.

깊이 우선 탐색이란 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미하며, 예시로 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법입니다.
깊이 우선 탐색의 특징은 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있으며, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 점입니다.
DFS 구현 방법은 재귀함수를 이용하는 방법과, 스택을 이용하는 방법이 있습니다.

Graph 표현 방법

• 인접 행렬과 인접 리스트를 구현해보는 시간을 가졌다.
• 간선이 적은 최소 그래프인 경우 인접 리스트를, 그렇지 않은 경우 인접 행렬을 구성하는게 전략적으로 좋다.

그래프가 희소할 때는 인접 리스트, 조밀할 때는 인접 행렬이 좋다.
그래프가 희소할 때 (sparse) 할 때는 인접행렬이 인접리스트보다 메모리를 더 많이 써야한다.
간선이 없어서 인접행렬의 대부분의 요소가 0인데도 불구하고 해당 부분을 포함해 2차원 배열을 만들어야 되기 때문
그래프가 조밀할 때 (dense) 할 때는 인접행렬이 인접 리스트보다 더 좋다. 어차피 다 연결되어 있기 때문에 메모리적 효율성은 동일해지고 정점 i에서 정점 j까지의 간선이 있는 확인하는 속도가 더 빠르기 떄문에 인접행렬이 더 빠름

기업지원 진행

• 금일 2군데 지원했는데 한 곳에서 바로 채용 과제가 날라왔다.
• graphQL을 사용해야 하는데 한번도 사용해 본 적이 없어서 빠르게 공부해야겠다고 판단.