키워드 : 그래프, BFS, DFS, 트리
그래프 vs 트리
그래프는 자료구조다!
연결리스트 : 객체들이 일직선 단방향 / 양방향으로 연결된 자료구조 (모든 노드가 연결되어 있다!)
그래프 : 객체들의 '일부' 페어가 연관되어 있는 객체집합구조 (트리같지만 꼬아서 연결 가능)
트리 : 순환 구조를 갖지 않는, 루트값과 부모-자식 관계로 구성된 '그래프' (단방향 일부 연결 자료구조)
힙 : 힙의 특성을 만족하는 완전 이진 트리 (정렬은 아니고 우선 순위만 만족하는 트리)
따라서 그래프와 트리는 리액트와 리액트 네이티브의 관계와도 같다고 볼 수 있겠다.
또한 힙-힙큐는 큐-데크의 관계와 비슷해서, 개념을 확실하게 익히고 실전에서는 모듈 쓰자!
실전에서 많이 사용할 거는 그래프랑 힙이다.
그 중에서도 힙은 힙큐가 있기 때문에 직접 구현은 어려워도 이해만 하면 사용 가능!
그래프가 어렵다.
그래프를 표현하는 법!
그림으로 그리면 참 쉽지만 컴퓨터는 0과 1의 세계에 산다.
알고리즘을 푼다는건 컴퓨터와 데이터 사이를 중재해주는 번역가나 사절이 된 기분이다.
양 쪽의 언어를 이해해야 된다.
1. 인접 행렬(Adjacency matrix)
노드와 노드 사이의 관계를 행렬 형태로 표현하는 방법
그리드 같은 엣지가 엄청 많은 밀집 그래프에 쓰이면 좋다! 시각적이다!
모든 방이 표현되어 있어서 공간을 많이 차지하지만 시간은 적게 걸린다.
2. 인접 리스트(Adjacency list)
각 노드 별로 연결되어있는 노드들만 표현
인접 행렬에서 불필요한 데이터를 제거하고, 실제 존재하는 그래프만을 표현하기 위한 방식
공간을 적게 차지해서 좋다, 모든 관계가 표현된 것이 아니기 때문에 시간은 오래 걸린다.
3. 간선 리스트(Edge list)
위의 방법들과 달리 선만을 리스트 형태 혹은 배열 형태로 저장하는 방법
모든 엣지를 살펴보는 알고리즘에서 간편하고 직관적으로 활용할 수 있다.
그래프 탐색 방법
그래프를 탐색할 줄 알면 트리를 탐색하는 방법도 아는게 된다!
트리가 그래프의 일종이니까!
함수가 따로 있는게 아니다! 그냥 내가 반복문을 돌리는 방식이 일직선이거나 빙빙 돌거나...
너무 단어에 집착하지 말고 그냥 데이터를 이렇게 빼면 최적화되어서 좋다 정도로만 기억하자.
dfs는 Depth-First-Search
하나를 깊이 판다!
1이 234로 연결되어 있다면
1찾고 2찾고 2의 자식노드(연결된 모든 하위노드)들을 다 찾은 다음에 3을 찾는다.
얘는 탐정같은 애다.
혼자서 실마리를 따라 돌진한다.
뭔가 찾아야 하는게 있을때 bfs보다 빠르다.
dfs에는 스택, 재귀를 사용할 수 있다.
bfs는 Breadth-First-Search
같은 단계에 있는 인접 노드를 풀스캔한다!
1이 234로 연결되어 있다면
1찾고 234찾고 234의 인접노드(딱한칸범위 =직접인접)들을 다 찾은 다음에
걔들이 인접한 노드가 있는지 찾는다.
코테에서는 dfs를 주로 쓴다고 한다.
얘는 실종자수색같은 애다.
손에 손을 잡고 한걸음씩 걸으면서 넓게 조금씩 전진한다.
어떤 길로 가는 최단경로 찾기에 자주 쓴다.
bfs에는 큐와 데크를 사용할 수 있다.
배운것 / 느낀것 / 내게 아쉬웠던 것
배운 것 : 프로그래머스는 알고리즘 테스트하기 편해서 좋음 다크다크한 ui도 좋고
리트코드는 비주얼라이저도 있고 유료구독자에게 주는 기능이 많은 것 같지만 문제가 어렵다!
백준은 별로... 로딩느리고 테스트 힘들고 다 인풋값으로 줘서 데이터처리가 귀찮다...
알고리즘은 투포인터로 접근해야 되는 것 같다. 실용성과 로직!
효율 높은 내장함수나 라이브러리를 아는 것도 좋지만 예외처리를 위해 이거저거 조합을 잘 짜야 한다.
느낀 것 : 잘하려고 하면 얼마든지 잘할 수 있지만
또 대충하려고 하면 어떻게든 돌아가는게 알고리즘이고, 개발인것 같다
나는 어떤 개발자가 되어있을까!
내게 아쉬웠던 것 : 스스로 구현해봐야 되는데ㅠㅠ
