코드스테이츠 소프트웨어엔지지어링 부트캠프 +40일

오늘한것

공포의 자료구조2

 

그래프와 Tree, Binary Search Tree 에 대해 배웠다.

• Tree : 계층형 구조, 상->하 단방향흐름, root Node를 시작으로 가지들이 뻗쳐나감
• Binary Search Tree : 효율적인 탐색 방법, 이진트리(자식노드가 최대 2개인 트리)에서 모든 왼쪽 트리는 부모보다 값이 작고 오른쪽트리는 부모보다 값이 크다.

근데 개념은 그냥 형식적인것같다.

결국 코플릿이 문제다.

 

축구로 치면 패스하는 법 설명 아무리 들어도 직접 공 안차면 실력 안느는거랑 마찬가지

 

오늘 최고의 수확은 5시부터 시작하는 수업에서 크루님이 알려주신 팁이다.

 

자료구조 문제풀이 팁

Graph 

• Matrix : 연결관계를 확인하는 문제, 2차원배열 사용한다. (인덱스 만으로 조회를 쉽게 할 수 있으니깐)

다음과 같은 상황에서는 From이 vertex(정점), To가 edge(간선) 이라 생각하고 문제를 풀면 편함

• List : vertex를 추가하거나 삭제하는 문제, 객체 사용. ( 배열은 추가 삭제할때마다 인덱스가 당겨지거나 밀려서 관리하기가 복잡해지지만 객체는 고정되 있기 때문에 관리가 편하다.)

 

Queue 사용 (BFS) :

• while(queue.length>0) : queue의 탈출조건은 남아있는 것이 없을때임
• 한번간곳은 다시 가지 않는다 : [false,false,false,...,false]배열 만들고 체크할때 마다 true로 바꿔준다.

 // 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다.
  const isVisited = new Array(matrix.length).fill(false);

  // 첫 정점 방문 여부를 표시합니다.
  isVisited[from] = true

  // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
  while (queue.length > 0) {

Stack 사용 (DFS) :

• 반복문 쓰고 싶을때 재귀함수 사용