🐭 이번 주는 뭐 했어?

알고리즘 기초

저번 주는 첫 주차로 자료구조의 기본을 가지고 문제를 풀었고 이번 주부터 본격적으로 알고리즘 문제를 풀었다 생각보다 난이도가 있었고 특히 코딩테스트에서 많이 나오는 DFS/BFS를 풀어볼 수 있는 좋은 시간이었다 이번 포스팅 역시 일주일간 어떤 것을 공부했는지 적어볼 예정이다

🐭 그래서 이번 주에 뭘 배웠어?

- 그래프

DFS/BFS를 알기 전 그래프의 개념부터 알고있어야한다 그래프는 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 자료구조이고 그래프 용어에는 크게 3가지가 있습니다

1. 노드

연결 관계를 가진 각 데이터를 의미합니다 정점(Vertex)이라고도 합니다

2. 간선

노드 간의 관계를 표시한 선

3. 인접 노드

간선으로 직접 연결된 노드

- DFS

DFS(Depth First Search)는 깊이 우선 탐색입니다 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다 DFS는 스택이나 재귀함수로 구현합니다

백준 - 2606 바이러스

- BFS

BFS(Breadth First Search)는 너비 우선 탐색입니다 현재 있는 위치에서 가장 인접한 노드를 먼저 방문해야 합니다 BFS는 큐로 구현합니다

백준 - 2667 단지 번호 붙이기

- 백트래킹

백트래킹은 DFS처럼 모든 경로를 탐색하는 경우 불필요할 것 같은 경로를 사전에 차단해 경우의 수를 줄여 끝까지 탐색하지 않고 되돌아가 다른 노드에서 검사를 시작합니다

백준 - 9663 N-Queen

- 이진 트리

트리

트리는 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조입니다
앞서 큐와 스택 같은 경우는 선형 구조로 순차적으로 나열한 상태이지만 트리는 데이터가 계층적 혹은 망으로 구성되어있는 비선형 구조입니다

트리 용어

• 노드 : 트리에서 데이터를 저장하는 기본 요소
• 루트 노드 : 트리 맨 위에 있는 노드
• 레벨 : 최상위 노드를 레벨0으로 하였을 때 하위 Branch로 연결된 노드의 깊이를 나타냄
• 부모 노드 : 특정 노드의 상위 레벨에 연결된 노드
• 자식 노드 : 특정 노드의 하위 레벨에 연결된 노드
• 리프 노드 : 자식 노드가 하나도 없는 맨 끝 노드
• 형제 노드(Sibling) : 동일한 부모 노드를 가진 노드

- 완전 이진 트리

완전 이진 트리는 이진 트리를 조건에서 무조건 왼쪽부터 차례대로 삽입해야 한다는 것입니다 트리의 높은 레벨0인 루트 노드부터 마지막 리프 노드 레벨까지 길이로 계산합니다

릿코드 543 - 이진 트리 직경