알고리즘/자료구조 기술 면접 대비 개념 정리

코딩테스트와 알고리즘 기술 면접 대비를 위한 정리(-ing)

 

Array	크기가 고정되어 있고, 연속된 메모리 공간에 데이터를 저장하며 인덱스를 통한 빠른 접근(O(1))이 가능합니다.
Linked list	크기가 가변적이고, 각 노드가 데이터를 포함하고 다음 노드를 가리키는 포인터를 가지는 구조로 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 느립니다.
Stack	한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조로 LIFO(Last In First Out)이라고도 불립니다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색
Queue	한쪽 끝으로 자료를 넣고, 반대쪽에서 자료를 뺄 수 있는 선형 구조로 FIFO(First In First Out)이라고도 불립니다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색
Graph
Tree	스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.
Hash Table	(Key,Value) 로 데이터를 저장하는 자료구조로 딕셔너리라고도 부릅니다.
Heap	데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
DFS	탐색하는 원소를 최대한 깊게 따라가서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조(Depth-First Search)
BFS	현재 인접한 노드 먼저 방문하는 구조
Backtracking	DFS 중에서도 조건이 맞지 않거나 더 이상 탐색할 필요가 없을 때 되돌아가는 전략

 

시간복잡도	입력 크기 N이 커질 때 알고리즘이 소요하는 연산 횟수를 수학적으로 나타낸 척도로 일반적으로 Big-O 표기법을 사용하며, 최악의 경우를 기준으로 분석합니다. 시간복잡도를 분석함으로써 알고리즘의 성능을 비교하고 대규모 데이터에 대한 실행 가능성을 판단할 수 있습니다.
DP	동적 계획법, Dynamic Programming 주어진 문제를 풀기 위해, 문제를 여러 개의 하위문제로 나누어 푸는 방법을 말합니다. 동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한번만 계산하고, 그 결과를 재활용하는 Memoization기법으로 속도를 향상시킬 수 있습니다.
메모이제이션	Memoization 동일한 계산을 반복 수행 할 때, 이전의 계산한 값을 재사용함으로써 동일한 계산 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
이진 탐색
재귀함수	자기 자신을 다시 부르는 함수로 문제 정의가 자기 자신을 참조하거나, 계층적으로 쪼개지는 구조일 때 유리합니다.
병합 정렬	분할 정복(Divide and Conquer) 방식의 정렬 알고리즘입니다. 배열을 반으로 나누고 각각을 재귀적으로 정렬한 후, 두 정렬된 배열을 병합하여 하나로 합칩니다.
그리디 알고리즘	매 순간 최적이라고 생각되는 것을 선택하는 방법으로 문제를 해결하는 알고리즘입니다. 그리디 알고리즘은 모든 경우를 고려하지 않기 때문에, 실행 시간이 다른 알고리즘에 비해 빠르다는 장점이 있습니다. 하지만, 이로 인해 항상 최적의 해를 구할 수 있는 것은 아닙니다.

 

---

Last Updated. 2025.06.17

🔖 기술면접 참고하면 좋은 자료

신입 개발자 기술면접 질문 정리 - 알고리즘

[CS 정리] 기술 면접 질문 정리 - 알고리즘

[면접 정리] 신입 개발자 CS 지식 정리 - 자료구조