카테고리 없음

[항해99 취업 리부트 코스 학습일지] 2주차 TIL(2)

봄의 개발자 2024. 3. 28. 18:38
728x90
반응형

오늘 알고리즘 문제는 크케 어렵지 않아서 오전에 다 풀고 오후에는 개인 공부를 했다.

어제부터 MSA 강의를 듣기 시작했다. 이번 개인 프로젝트에서 MSA 사용하기 위해 미리 개념을 익히기 위한 목적으로 강의를 듣게 되었다.

 

알고리즘 기술 매니저님 피드백

  • for 문 안에서 메서드 호출하는 게 성능에 좋지 않다.
  • 투포인터, 슬라이딩 윈도우 -> 서킷브레이커 구현할 때 많이 사용함
  • StringTokenizer로 받아와서 StringBuilder 두 개로 만드는 것보다 new StringBuilder(br.readline()); 로 한 번에 받아와서 reverse를 해주는 게 효율적
  • key, value -> entrySet 사용하는 방법 괜찮았다!

 

- 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

자료형에 대해 배웠음

 

 

- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

 

TreeMap

  • 이진 탐색 트리 형태로 데이터를 저장한다.
  • 자동으로 오름차순으로 정렬된다. 
  • 레드 블랙 트리로 구현되어있다. 

  • 부모 노드 보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치한다.
  • 데이터의 추가나 삭제시 트리가 한 쪽으로 치우쳐지지 않도록 균형을 맞추어준다.
  • 시간 복잡도: O(log n)

 

레드블랙 트리 조건

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

 

 

슬라이딩 윈도우 알고리즘

  • 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘
  • 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법
  • 배열이나 리스트의 요소의 일정 범위를 값을 비교할 때 사용하면 매우 유용
  • 투포인터 알고리즘과 연동하여 많이 쓰임
  • 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며, 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점

 

 

728x90
반응형