[Day 66] 2022-0921: 트리/그래프 자료구조, 알고리즘, 스터디?

🐈오늘 공부한 것

✔️트리 / 그래프 자료구조

일반적인 트리, 이진 트리 그리고 '이진 탐색 트리'에 대해서 접해볼 수 있었다. 이진 탐색 트리란 트리 + 이진 검색 알고리즘 같은 느낌인데, 루트 노드를 기준으로 새로 추가할 값이 작으면 왼쪽, 크면 오른쪽으로 배치하고, 이렇게 생긴 트리를 재귀적으로 노드에 추가하여 생성할 수 있다. 장점은 어떤 값을 찾을 때 대,소 비교만 하면 되기 때문에 루트 노드를 기준으로 큰지 작은지, 그 루트 노드의 왼쪽 혹은 오른쪽을 다시 루트로 해서 비교하며 찾아나갈 수 있다.

 

그래프 자료구조와 함께 그래프 탐색 알고리즘인 DFS, BFS 기법에 대해서 공부했다. BFS란 너비우선탐색 기법으로, 어떤 노드에 도달하기 까지 최단거리를 구하거나, 그래프의 규모가 상대적으로 작을 때 사용할 수 있는 알고리즘이다. 여러 레벨의 트리가 존재할 때 1레벨에 해당하는 노드를 모두 방문하고, 찾는 것이 없으면 다음 레벨로 넘어가서 탐색을 이어나가는 것이다. 반대로 DFS는 하나의 노드에서 출발해 그 노드의 leaf 노드에 도달할 때까지 탐색을 계속하고, 찾는 값이 아니면 다시 루트로 돌아와 그 다음 경로를 탐색하는 방식이다. DFS 에서는 한 경로에 대해 경로의 특징을 기억하기 쉽다는 장점이 있다. 어떤 경로를 탐색할 때 경로에 대한 조건이 붙는 문제가 있다면 DFS 알고리즘을 활용해 볼 수 있다. DFS, BFS 의 특징은 한 번 방문한 노드는 재방문 하지 않는다는 것이다. 이는 노드의 방문 여부를 배열에 저장함으로써 구현할 수 있음. 

 

그래프의 경우 인접행렬과 인접 리스트 방식으로 구현할 수 있는데, 행렬로 구현하는 쪽이 이차원 배열을 사용하기 때문에 조금 직관적이고 쉽다고 할 수 있다. 노드간 간선의 연결을 표현하기에는 객체 형태로 구현하는 인접리스트가 더 유리할 수 있음. 인접리스트쪽이 메모리에도 더 유리하다고 한다.

✔️알고리즘

https://friedegg556.tistory.com/240

스택 자료구조를 사용한 크레인 인형뽑기 게임 문제를 정리했다.

문제가 어려울 것이라고 예상했는데 생각보다 접근 방법을 떠올리는 것이 힘들지 않았음.

🐈더 공부할 것

1. 스택/큐/트리/그래프 기본적인 알고리즘 복습 및 응용

🐈오늘의 느낀 점

1. 매일 작성하는 TIL 모임의 참여율이 현저히 낮아졌다. 문제점이 뭘까 생각해봤는데 일단 나조차도 하루 일정이 빡빡하기 때문에 매일 TIL을 꼼꼼히 작성한다는 것이 쉽지 않았다. 또 TIL을 공유한다는 행위 자체만으로는 엄청난 동기부여가 되지 않을 수도 있는 것 같음. 이대로가면 이 모임의 목적이 희미해질 것 같아서 주간 회고를 추가하기로 했다. 

 

매일 배운 것을 정리하는 것도 중요한데, 내가 올바른 방향으로 가고 있는지 점검하는 것 또한 회고의 목적 중 하나라고 생각한다. 점검을 하려면 데이터가 쌓여야되고 그래서 기간이 중요한데, 주간 회고를 좀 더 발전시켜서 꼼꼼히 작성할 수 있도록 5F 양식을 도입하려고 한다. 요즘 내가 밀고 있는(?) 것이 개발자로서 자신의 주관, 관점인데 회고를 통해서 함께 나누고 발전시킬 수 있기를 바래본다. 

 

2. 부트캠프에 참여한지 3개월이 넘어가는 시점에서 이제 정신적 힘듦(?)이 찾아오는 것 같다. 힘들다기 보다는 지친다고 해야하나... 아침에 눈뜨면 개발 점심먹고 개발 저녁먹고 또 개발의 연속이다보니 해가 뜨고 지는 것이 너~무나도 순식간에 지나가버린다. 사실 지나간 3개월동안 내가 엄청나게 성장했다고 생각하지 않는데 이제는 시간관리, 집중력의 영역을 넘어서 지루함마저 느껴진다. 매일 똑같으니까... 오늘은 새로움을 주기 위해 밖에서 뛰고 왔는데, 뛰는 코스도 매번 똑같다; ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ