안다고 쉽게 지나칠 수 있는 점을 다시 확인하고 기존 면접 정리 블로그를 강화하기 위해 정리
하기 블로그에 내용을 추가함으로 책의 내용을 정리함
https://yukyongsoo.atlassian.net/l/cp/qF9DWzkL
https://yukyongsoo.atlassian.net/l/cp/z4Uddxiz
- 빅오 표기법
- 알고리즘의 확장성과 효율성을 측정하는 가장 유명한 지표
- 상수시간: 작업에 일정한 시간이 걸리는 작업
- 점근적 실행 시간: 작업 시간이 특정 조건에 비례하는 작업
- 기본 규칙
- 상수는 제외한다
- 비 우세항은 제외한다
- 입력이 다르면 변수도 다르다
- 서로 다른 단계를 더하거나 곱해야 한다
- 입력을 절반으로 줄이는 알고리즘은 대부분 O(logN)으로 표현이 가능하다
- 많은 정렬 알고리즘의 실행시간은 대부분 O(NlogN)이고 재귀적으로 수행한다
- 재귀 알고리즘은 대부분 O(2 pow N)이지만 메모이제이션이나 태뷸레이션을 통해 O(N)으로 줄일 수 있다
- 재귀와 동적 프로그래밍
- 재귀: 스스로를 호출하는 메서드
- 동적 프로그래밍: 재귀를 최적화하는 프로그래밍
- 메모이제이션(하향식): 동일한 입력에 관한 계산을 한번만 호출하도록 보장
- 태뷸레이션(상향식): 직관적이고 공간 복잡도가 메모이제이션보다 낮다
- 비트조작
- 자바는 byte(8비트), short(16비트), int(32비트), long(64비트), char(16)비트 자료형 조작이 가능
- 비트 시프트 연산자는 예외를 발생시키지 않음
- 왼쪽 시프트(num << n ) 은
num * (2 pow n) 한 것과 같은 효과
- 오른쪽 시프트(num >> n ) 은
num / (2 pow n) 한 것과 같은 효과
- 자바의 2의 보수로 음수를 표현
- 모든 비트 반전
- 1를 더하고 가장 처음에 1을 붙임
- 배열과 문자열
- 변경할 수 없는 zero 배열 길이를 지원한다
- 문자열은 65535 미만의 유니코드는 16비트 char로, 초과하는 유니코드는 32비트 정수값으로 저장한다
- 연결 리스트와 맵
- 일반적으로 단일 연결 리스트보다 이중 연결 리스트로 풀 수 있는 문제가 더 많다
- 스택과 큐
- 스택은 후입선출, 큐는 선입선출하는 선형 자료구조이다
- 큐는 배열, 연결리스트, 스택을 기반으로 구현가능하다
- 트리와 그래프
- 그래프
- 무향 그래프: 양방향 연결된 그래프
- 유향 그래프: 단방향 연결된 그래프
- 인접 행렬 또는 인접 리스트로 표현
- 순회 방법
- 중복 방문을 방지하기 위해 방문한 노드를 저장하는 추가 자료구조가 필요
- 너비 우선 탐색
- 깊이 우선 탐색
- 재귀 기반
- 반복 기반: 스택을 기반으로 하여 구현
- 트리
- 순환을 가지지 않는 유향 그래프
- 용어
- 단말(leaf): 자식 노드가 없는 노드
- 높이(height): 단말 노드까지의 가장 긴 경로의 길이
- 깊이(depth): 루트 노드까지의 경로의 길이
- 높이와 깊이는 서로 반대 값을 가진다
- 종류
- 이진 트리(binary tree): 자식 노드의 수가 2개 이하인 트리
- 이진 탐색 트리(binary search tree): 왼쪽 하위 트리가 부모 요소보다 작거나 같고, 오른쪽 하위 트리는 부모 요소보다 큰 트리
- 균형 이진 트리(balanced binary tree): ex) red-black tree, AVL tree
- 삽입, 검색 시 O(logN)을 보장하는 트리
- 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차가 1 이하이다
- 완전 이진 트리(complete binary tree):
- leaf 를 제외한 모든 레벨이 완전히 채워진 트리
- 항상 왼쪽에서 오른쪽으로 채워야 한다
- 정 이진 트리(full binary tree): 모든 노드의 자식이 2개이거나 아예 없는 트리
- 포화 이진 트리(perfect binary tree): 완전 이진 트리 이면서 정이진 트리를 만족하는 트리
- 순회 방법
- 너비 우선 탐색(breadth-first-search)
- 레벨 순회라고도 부름
- 큐를 이용하여 순회
- 큐에서 팝 → 노드 방문 → 왼쪽 노드 큐에 추가 → 오른쪽 노드 큐에 추가 → 큐가 빌 때까지 반복
- 깊이 우선 탐색(depth-first-search)
- 전위 순회: 현재 노드(루트) → 왼쪽 하위 트리 → 오른쪽 하위 트리 순으로 순회
- 중위 순회: 왼쪽 하위 트리 → 현재 노드(루트) → 오른쪽 하위 트리 순으로 순회
- 후위 순회: 왼쪽 하위 트리 → 오른쪽 하위 트리 → 현재 노드(루트) 순으로 순회
- 정렬과 검색
- 정렬
- 힙 정렬
- 이진 힙(완전 이진 트리)를 사용하는 비 안정 알고리즘
- 최선, 평균, 최악의 경우 모두 O(NlogN)의 성능을 보장
- 메모리의 제약이 있는 경적
- 병합 정렬
- 분할 정복 전략에 기반하는 안정적 재귀 알고리즘
- 최선, 평균, 최악의 경우 모두 O(NlogN)의 성능을 보장
- 공간 복잡도는 자료구조에 따라 다르며 최대 O(n)
- 데이터 크기가 큰 경우 효과적 → 병렬성으로 더욱 고 성능을 노릴 수 있음
- 퀵 정렬
- 최선, 평균의 경우 O(NlogN)의 성능, 최악의 경우 O(N pow 2)의 성능을 보장
- 공간 복잡도는 O(logN) 또는 O(N)
- 비 안정적 알고리즘
- 3-way 퀵 정렬은 중복이 많은 경우와 중간 크기의 데이터에서 효과
- 버킷 정렬
- 삽입 정렬
- 기수 정렬
- 검색