CS 공부 정리

https://gyoogle.dev/blog/

👨🏻‍💻 Tech Interview

위 블로그를 보고 간략하게 정리한 글 입니다.

 

 

Algorithm

거품 정렬(Bubble Sort): 인접한 원소의 대소 비교를 통해 (오름차순일 경우) 제일 큰 원소를 뒤로 보냄. 안정정렬. O(n^2)

선택 정렬(Selection Sort): (오름차순일 경우) 제일 작은 원소를 찾고 맨 앞의 원소와 교환. 불안정정렬. O(n^2)

삽입 정렬(Insertion Sort): 2번째 원소부터 앞 원소들을 탐색하며 자신의 자리를 찾아감. 안정정렬. 최선 O(n). 평균 최악O(n^2)

퀵 정렬(Quick Sort): 1번째 원소를 피벗으로 하고 피벗보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽에 있도록 원소들을 스왑해 나가다가 피벗을 중앙으로 스왑. 이후 피벗의 왼쪽 배열과 오른쪽 배열을 각각 다시 정렬. 분할정복. 평균 O(nlogn). 최악 O(n^2) 오름차순이나 내림차순으로 정렬되어 있는 경우. 불안정 정렬. 피벗에 따라 효율이 달라짐.

JAVA Arrays.sort()는 Dual Pivot Quick Sort 사용

병합 정렬(Merge Sort): 영역을 최대한 쪼갠 이후 합치면서 정렬. 안정정렬. O(nlogn)

힙정렬(Heap Sort): 힙 구성 - 루트 삭제(루트는 배열에) - 마지막요소를 루트에 - 힙구성 - 반복. 불안정 정렬. O(nlogn)

DFS: 루트노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색. 모든 경로를 탐색할 때에 적합.

BFS: 루트노드에서 가까운 노드부터 탐색. 최소 비용 경로를 탐색할 때에 적합.

LIS

 

 

Database

Index: table의 column을 색인화. 인덱싱하는 경우 MYI 파일이 생성되어서 column을 탐색 시 MYI 파일의 내용을 검색함.

Index 사용하면 좋은 경우: where 절에서 자주 사용. 외래키가 사용. join에 사용

Index 사용 피해야 하는 경우: data 중복도가 높음. DML이 자주 일어남.

Index INSERT: Index의 순서에 맞게 데이터가 들어가야 하므로 index table을 잘랐다가 데이터를 추가한 후 다시 이어붙이는 작업이 필요. 그동안 DML 블로킹.

Index DELETE: 데이터를 지우지 않고 사용 안함 표시.

Index UPDATE: Index INSERT -> Index DELETE.

1정규화: 테이블 컬럼이 하나의 값만을 갖도록 테이블 분리.

2정규화: 모든 컬럼이 완전 함수적 종속(기본 키의 부분집합이 결정자가 되어선 안되는 것)을 만족. 

3정규화: 이행적 종속(A -> B, B -> C)을 없애도록 분해. 

트랜잭션: 데이터베이스의 상태를 변화시키기 위해 수행하는 작업단위. 원자성(모두 반영 또는 반영 x), 일관성(결과가 일관), 독립성(다른 연산에 끼어들 수 없다), 지속성(결과 영구적 반영).

UNDO: 이전의 상태로 되돌리는 복구. 트랜잭션은 시작되었지만 commit 되지 않은 것을 연산취소. 수정된 페이지를 디스크에 쓰는 시점으로 분류하는 2개 정책. 수정된 페이지를 언제든지 디스크에 쓸 수 있는 정책(대부분 채택, UNDO 로깅과 복구를 수반). 수정된 페이지를 트랜잭션의 끝날 때까지 버퍼에 유지하는 정책.

REDO: commit 된 것을 다시 실행. 트랜잭션이 종료되는 시전에 수정한 페이지를 디스크에 쓸 것인지에 대한 2가지 정책. 수정했던 모든 페이지를 commit 시점에 디스크에 반영(REDO가 필요없음). commit 시점에 반영하지 않는 정책(대부분 채택, REDO 필수)