728x90
알고리즘
알고리즘은 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 의미한다.
버블 소트(bubble sort)
- 버블 소트는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다.(시간 복잡도 O(n^2))
힙 소트(heap sort)
- 힙 소트는 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘이다.(시간 복잡도 O(nlog2 n))
머지 소트(merge sort)
- 머지 소트는 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘이다.
퀵 소트(Quick sort)
- 퀵 소트는 매우 빠른 정렬 속도를 가진 분할 정복 알고리즘 중 하나로 합병 정렬과 달리 리스트를 비 균등하게 분할한다.
- 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬을 한다.
삽입 소트(insertion sort)
- 삽입 정렬은 두 번째 값부터 시작하여 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘이다.
- 삽입 정렬의 평균 시간 복잡도는 O(n^2)이고, 가장 빠른 경우 O(n)까지 높아질 수 있다.
동적 프로그래밍(Dynamic Programming)
동적 프로그래밍은 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 해결하는 방식이다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제를 해결하는 데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모제이션 기법으로 속도를 향상할 수 있다.
동적 프로그래밍의 두 가지 조건
- Overlapping Subproblem(중복되는 부분 문제) : 주어진 문제는 같은 부분 문제가 여러 번 재사용된다.
- Optimal Substructure(최적 부분 구조): 새로운 부분 문제의 정답을 다른 부분 문제의 정답으로부터 구할 수 있다.
재귀 알고리즘
재귀 알고리즘은 함수 내부에서 함수가 자기 자신을 또다시 호출하여 문제를 해결하는 알고리즘이다. 재귀 알고리즘은 자기가 계속해서 자신을 호출하므로 반복을 중단할 조건이 필요하다.
private static int recursiveFactorial(int num) {
if(num > 1) {
return recursiveFactorial(num - 1) * num;
}
return 1;
}
private static int loopFactorial(int num) {
int answer = 1;
for (int i = 2; i <= num; i++) {
answer *= i;
}
return answer;
}자료구조
자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이다.
- Stack
- 세로로 된 바구니와 같은 구조로 먼저 넣은 값이 마지막으로 나오는 FILO(First In Last Out) 구조이다.
- Queue
- 가로로 된 통과 같은 구조로 먼저 넣은 값이 가장 먼저 나오는 FIFO(First In First Out) 구조이다.
- Heap
- 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키 값이 자식의 키 값보다 작지 않거나 그 자식의 키 값보다 크지 않은 완전 이진트리이다.
- Tree
- 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다.
우선순위 큐와 내부 구조 및 시간 복잡도
- 우선순위 큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조이다. 우선순위 큐를 구현하기 위해서는 일반적으로 힙을 사용한다.
- 힙은 완전 이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간 복잡도는 O(logn)이다.
해시 테이블과 해시 테이블의 시간 복잡도
- 해시 테이블은 key-value 형태로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다.
- 해시 테이블은 Key값에 해시 함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
- 해시 테이블은 고유한 인덱스 값을 조회하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖는다. 다만, 충돌이 발생한 경우 충돌된 인덱스 값에 대해 연결된 데이터를 조회하여 원하는 값을 조회하기 때문에 O(N)까지 증가할 수 있다.
LinkedList와 ArrayList
ArrayList는 데이터들이 순서대로 늘어선 배열의 형식을 취하고 있지만, LinkedList는 자료의 주소 값으로 서로 연결된 형식을 가지고 있다.
- ArrayList
- 원하는 데이터에 무작위로 접근할 수 있다.
- 리스트의 크기가 제한되어 있으며, 리스트의 크기를 재조정하는 것은 많은 연산이 필요하다.
- 데이터 추가/삭제를 위해서는 임시 배열을 생성하고 복제하고 있어 시간이 오래 걸린다.
- LinkedList
- 리스트의 크기에 영향 없이 데이터를 추가할 수 있다.
- 데이터를 추가하기 위해 새로운 노드를 생성하여 연결하므로 추가/삭제 연산이 빠르다.
- 무작위 접근이 불가능하고 , 순차 접근만 가능하다.
Reference
728x90
'Dev' 카테고리의 다른 글
| 빅데이터 처리 (0) | 2022.02.11 |
|---|---|
| [기술면접] JAVA (0) | 2022.01.24 |
| [기술면접] SpringFramework (0) | 2022.01.23 |
| [기술면접]운영체제(Operating System) (0) | 2022.01.21 |
| [기술면접]데이터베이스(Database) (0) | 2022.01.12 |
