CPP_1. AssortRock 21일차 오프라인 수업_221005

20일차_221004 수업 내용은 그간 했던 연습문제들에 대한 반복숙달과 질문을 통한 문제풀이 시간이었으므로

별도로 적을 내용이 없음 (본 글에 적힌 내용과 다수 중복)

하지만 기존 내용들을 다시 되새기고 복습할 수 없는 유의미한 시간이었다

 

DFS와 스택

• 재귀함수 자체가 스택을 쓰고 있기 때문에 재귀함수를 쓰면 DFS를 쉽게 사용할 수 있었던 것
• 함수 호출과정 자체가 스택과 깊은 관련이 있음 (호출스택)
• 따라서 재귀를 스택으로도 풀 수 있음
• 개인적으로 시간을 내서 스택을 이용해 재귀 풀어보기

 

그래프 DFS에 대한 이야기

• 그래프는 트리와 달리 싸이클이 존재하므로, 왔던 곳은 다시 가지 않도록 구현해줘야 함(via 배열 사용)
• 연결되지 않은 정점을 통해 초보자사냥터 구현 (고레벨이 돼서는 연결을 끊어서 오지 못하도록)

 

Tree 자료구조에 대한 내용

• 트리는 그래프 자료구조의 일종
• 트리의 조건으로 단방향이어야 하며, 싸이클이 없어야 하고, 부모자식인 그래프여야 한다

 

 

Binary Tree에 대한 내용

• 트리 중에서 한 부모가 두 명의 자식만 있는 트리를 가리킴

struct Node
{
	int data;
	Node* left;
   	Node* right;
}

• 이런 노드로 만들어진 트리

 

1차원 배열에 Binary Tree 집어넣기

• 루트 노드를 인덱스 1번에 넣고 나머지는 아래와 같은 공식으로 접근이 가능하다
• 좌측 노드 = 부모 노드 * 2
• 우측 노드 = 부모 노드 * 2 + 1
• 반대로 좌측, 우측 노드를 2로 나눈 몫을 취하면 그게 부모 노드이다.