➡️ 루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.
각 부모 노드에서 파생되는 자식 노드의 개수는 최대 2개까지로 구성된 트리이다.
완전 이진 트리(Complete): 부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리를 말하며, 마지막 레벨을 제외하고 모든 노드가 가득 차 있어야 한다.
정 이진 트리(Full): 각 내부 노드가 두 개의 자식 노드는 가지는 트리입니다. (0개 or 2개)
➡️ 부모 노드를 기준으로 왼쪽의 자식들은 부모 노드보다 작고 오른쪽 자식들은 부모 노드보다 크다는 규칙을 따르는 이진 트리이다.
➡️ 해시 테이블은 효율적인 탐색을 위한 자료구조로 key를 Value에 대응시킨다.
해시 테이블은 충돌(Collision)이 일어날 수 있다.
<해결법>
➡️ Array 는 삽입, 삭제가 O(n)의 시간 복잡도를 가지지만 LinkedList는 O(1)를 가진다.(정확히는 상황에 따라 다르다)
반면 특정 요소에 접근할 때에는 Array는 O(1), LinkedList는 O(n)의 시간 복잡도를 가진다.
Array는 인덱스로 접근이 가능하지만 LinkedList는 Search를 해야 된다.
➡️ 분할 정복의 방식으로 정렬을 수행한다. (불안정 정렬)
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. (분할 정복)
#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];
void quickSort(int i, int j)
{
if(i>=j) return;
int pivot = quick[(i+j)/2];
int left = i;
int right = j;
while(left<=right)
{
while(quick[left]<pivot) left++;
while(quick[right]>pivot) right--;
if(left<=right)
{
swap(quick[left],quick[right]);
left++; right--;
}
}
quickSort(i,right);
quickSort(left,j);
}
시간복잡도: O(nlogn)
최악: O(n^2) - 이미 정렬된 리스트에 대해 퀵 정렬 실행하는 경우
✅ 최악의 상황을 개선하기 위해서는 피벗을 배열을 중간 값으로 설정하는 것이 좋다.
➡️ 안정 정렬에 속하고 퀵소트와 마찬가지로 분할 정복 알고리즘 중 하나이다.
시간복잡도: O(nlogn)
➡️ 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
시간복잡도: O(nlogn)
➡️ 서로 인접한 두 원소를 비교해서 정렬하는 알고리즘
function bubble_sort(list, n){
let i, j, temp;
for(i=n-1; i>0; i--){
// 0 ~ (i-1)까지 반복
for(j=0; j<i; j++){
// j번째와 j+1번째의 요소가 크기 순이 아니면 교환
if(list[j]>list[j+1]){
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
시간 복잡도: O(n^2)
➡️ 컴파일러와 인터프리터 모두 고레벨 언어를 기계어로 변환하는 역할을 수행
컴파일러는 전체 코드를 보고 한번에 해석하지만 인터프리터는 소스코드의 각 행을 연속적으로 분석하며 실행한다.
인터프리터는 고레벨 언어를 중간 레벨 언어로 한 번 변환하고 이를 각 행마다 실행하기 때문에 일반적으로 컴파일러가 인터프리터보다 실행 시간이 빠른 경우가 많다.
쓰레드: 프로세스 내에서 할당받은 자원을 이용해 동작하는 실행 단위
➡️ Context Switching이란 인터럽트를 발생시켜 CPU에서 실행중인 프로세스를 중단하고, 다른 프로세스를 처리하기 위한 과정
➡️ 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원을 임계자원(Critical Resource)라고 한다. 그리고 이에 대해 접근하고 실행하는 프로그램 내의 코드 부분을 임계영역(Critical Section)이라고 한다.
➡️ 둘 이상의 프로세스가 자원을 각자 가지고 있는 채로 계속해서 기다리고 있는 상태를 의미한다. (외부적 조치가 없는 한)
➡️ LRU 알고리즘은 실제메모리의 페이지들 중에서 가장 오랫동안 사용되지 않은 페이지를 선택하는 방식
➡️ 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다. 할당 시간이 지나면 프로세스는 선점당하고(CPU 뺏김) ready queue에 들어가게 된다.
다단계 피드백 큐
➡️ 같은 IP 내에서 프로세스 구분을 하기 위해 사용된다.
IP => 아파트
PORT => 호수
➡️ IP는 기억하기 어렵고 변경될 수 있다.
그래서 도메인으로 찾는 것이다. 도메인에 IP 주소를 등록시킨다.
➡️ 프로그래밍에서 필요한 데이터를 추상화시켜 상태와 행위를 가진 객체를 만들고 그 객체들 간의 유기적인 상호작용을 통해 로직을 구성하는 프로그래밍 방법
💡 오버로딩과 오버라이딩의 차이
- 오버로딩: 같은 이름의 메소드를 여러 개 가지면서 매개 변수를 다르게 지정하는 것
- 오버라이딩: 상위 클래스(부모 클래스)가 갖고 있는 메소드(자식 클래스)를 하위 클래스에서 재정의해 사용하는 것
https://jeong-pro.tistory.com/95
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#stack-and-queue