본문으로 건너뛰기

2026-06-09 학습 일지

오늘 한 일​

  • 자료구조 & 알고리즘 기초 개념 정리
  • 배열, 연결리스트, 스택, 큐, 해시 테이블 학습

배운 내용​

시간·공간 복잡도​

  • 빅 오(Big O): 실행 시간의 점근적 상한 — 최악의 경우
  • 빅 세타(Θ): 평균, 빅 오메가(Ω): 하한 (최선의 경우)
  • 실무에서는 Big O가 기본 지표

배열 vs 연결리스트​

배열연결리스트
메모리순차 할당비순차 (포인터 연결)
임의 접근O(1)O(n)
삽입/삭제 (위치 주어질 때)O(n) — 이동 필요O(1)
  • 자주 헷갈리는 점: 연결리스트의 삽입·삭제가 O(1)인 건 위치(노드 포인터)가 이미 주어졌을 때. 탐색까지 포함하면 O(n)

스택 & 큐​

  • 스택(LIFO): 한 쪽 끝에서만 삽입·삭제 (push / pop)
  • 큐(FIFO): 앞에서 삭제(dequeue), 뒤에서 삽입(enqueue)
  • 변형: 원형 큐(메모리 재사용), 덱(양방향), 우선순위 큐

해시 테이블​

  • 해시 함수 → 버킷 인덱스 결정, 평균 탐색 O(1)
  • 충돌 해결 방법 두 가지
    • 체이닝: 같은 인덱스에 연결리스트로 이어 붙임 → 최악 O(n)
    • 개방 주소법: 충돌 시 다른 빈 버킷 탐색
      • 선형 조사법: 군집화(clustering) 발생 가능
      • 이중 해싱: 두 번째 해시 함수로 탐사 거리 결정 → 군집화 완화

내일 할 것​

  • what-i-want 프로젝트: OG 이미지 → 랜딩 → E2E
  • 트리·그래프 개념 예습 (다음 자료구조 주제)