코테 스터디 36일차 TIL + 오늘의 학습 키워드 이진탐색, bfs

- 오늘의 학습 키워드 이진 탐색 ,bfs

- 공부한 내용 본인의 언어로 정리하기

1. Queue 를 사용한 BFS: 각 레벨의 노드들을 순서대로 처리한다.

2. 레벨별 분리: 각 레벨의 노드들을 별도 리스트로 관리한다

3. null 체크 자식노드가 존재할때만 큐에 추가한다.

 

수도 코드

function levelOrder(root):
   if root is null:
     return empty list
     
     result =[]
     queue= [root]
     
     whlie queue is not empty:
       level_size = queue.size()
       current_lever=[]
       
       
       for( i from 0 to level_size -1):
         node = queue.dequeue()
         current_lefel.add(noce.val)
         
         if node.left is not null:
           queue.enqueue(node.left)
           
         if node.right is not null:
           queue.enqueue(node.right)
           
         result.add(current_level)
         
         return result

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

while 문 조건을 left <right 라고 생각했음

 

  - 어떻게 해결했는지

 

bfs는 큐가 빌때 까지 실행되어야 하며

노드의 개수나 값으로 비교하는것이 아니었음

queue.isempty가 올바른 종료조건이었음

  - 무엇을 새롭게 알았는지

 

자식을 큐에 추가하는 이유?

 

현재 레벨 처리 중에 다음 레벨의 노드들을 미리 준비

왼-> 오 방향으로 추가하여 레벨 내의 순서를 보장한다.

 

levelSize의 중요성

for 문이 정확히 현재 레벨의 노드 개수만큼만 실행

 

null 체크의 필요성

존재하지 않는 자식은 큐에 추가하지 않는다.

 

자료구조 선택 기준

ArrayList : 

인덱스로 접근이 필요한 경우

순차적 추가가 주된 작업

메모리 효율성이 중요할때

 

LinkedList 사용하는 경우

Queue/ Deque 인터페이스 구현이 필요할때

중간 삽입/ 삭제가 많을때

FIFO/ LIFO 연산이 중심이 될때

 

node.val:  노드의 실제 데이터 값 value

queue.poll :  큐에서 안전하게 꺼내기

queue.offer:  큐에 안전하게 추가

---

list.add: 완성된 레벨을 결과(리스트 끝에 추가하는것)

  - 내일 학습할 것은 무엇인지