배열과 연결 리스트의 차이는 무엇인가요?
배열은 연속된 메모리 공간에 데이터를 저장하고, 인덱스를 사용하여 접근할 수 있는 자료구조입니다. 크기가 고정되어 있으며, 삽입 및 삭제에 비용이 높을 수 있습니다.
연결 리스트는 노드들이 연결된 구조로 데이터를 저장하는 자료구조입니다. 각 노드는 자신의 데이터와 다음 노드에 대한 참조를 가지고 있습니다. 크기가 동적으로 조절될 수 있으며, 삽입 및 삭제가 쉽지만 인덱스로 직접 접근할 수는 없습니다.
스택과 큐의 차이는 무엇인가요?
스택은 후입선출(LIFO, Last-In-First-Out) 구조의 자료구조입니다. 데이터의 삽입과 삭제가 스택의 한 쪽 끝에서만 이루어지며, 가장 최근에 삽입된 데이터가 가장 먼저 삭제됩니다.
큐는 선입선출(FIFO, First-In-First-Out) 구조의 자료구조입니다. 데이터의 삽입은 한 쪽 끝에서, 삭제는 다른 쪽 끝에서 이루어집니다. 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.
이진 트리의 중위 순회(in-order traversal)는 무엇인가요?
이진 트리의 중위 순회는 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리의 순서로 노드를 방문하는 방법입니다. 중위 순회는 이진 트리의 노드들을 오름차순으로 순회하는데 사용될 수 있습니다.
해시맵(HashMap)과 해시테이블(Hashtable)의 차이는 무엇인가요?
해시맵과 해시테이블은 키-값 쌍의 데이터를 저장하는 자료구조입니다. 주요한 차이점은 다음과 같습니다:
동기화: 해시테이블은 동기화되어 여러 쓰레드가 동시에 접근할 수 있습니다. 해시맵은 동기화되지 않으며, 단일 쓰레드 환경에서 사용하는 것이 성능상 유리합니다.
Null 허용: 해시테이블은 키와 값에 null을 허용하지 않습니다. 해시맵은 키와 값 모두 null을 허용합니다.
속도: 해시맵은 일반적으로 해시테이블보다 더 빠른 속도를 제공합니다.
정렬 알고리즘 중 퀵 정렬(Quick Sort)은 어떻게 동작하나요?
퀵 정렬은 분할 정복(divide and conquer) 방식을 사용하는 정렬 알고리즘입니다. 다음과 같은 과정으로 동작합니다:
피벗(pivot)을 선택합니다. 일반적으로 배열의 가운데 원소를 선택합니다.
피벗을 기준으로 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 분할합니다.
분할된 두 개의 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
분할이 더 이상 불가능할 때까지 이 과정을 반복하고, 부분 배열을 합치면 정렬이 완료됩니다.
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 재귀 호출에 따른 스택 메모리 사용이 필요합니다.
BFS와 DFS의 차이점은 무엇인가요?
BFS(Breadth-First Search)는 너비 우선 탐색으로, 레벨 순서대로 그래프의 모든 노드를 탐색하는 방식입니다. 인접한 노드를 모두 탐색한 후 다음 레벨의 노드로 이동합니다.
DFS(Depth-First Search)는 깊이 우선 탐색으로, 한 경로를 최대한 깊게 탐색한 후 다음 경로로 이동하는 방식입니다. 스택 또는 재귀 호출을 사용하여 구현됩니다.
주요한 차이점은 탐색 순서와 사용되는 자료구조입니다. BFS는 너비 우선으로 탐색하며 큐를 사용하고, DFS는 깊이 우선으로 탐색하며 스택 또는 재귀 호출을 사용합니다.
그래프와 트리의 차이점은 무엇인가요?
그래프와 트리는 둘 다 노드들과 그들 사이의 연결을 나타내는 자료구조입니다. 주요한 차이점은 다음과 같습니다:
순환성: 그래프는 순환 구조를 가질 수 있으며, 노드 간에 순환 경로가 존재할 수 있습니다. 트리는 비순환적인 구조로, 노드 간에 순환 경로가 존재하지 않습니다.
루트 노드: 트리는 하나의 루트 노드를 가지며, 모든 노드는 루트에서 시작하는 경로로 접근할 수 있습니다. 그래프는 특정 노드를 루트로 정의하지 않으며, 여러 개의 연결된 컴포넌트를 가질 수 있습니다.
동적 프로그래밍(Dynamic Programming)이란 무엇인가요?
동적 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하고, 중복 계산을 피하여 효율적으로 문제를 해결하는 알고리즘 설계 기법입니다. 작은 부분 문제의 해결 방법을 저장하고 재활용함으로써 중복 계산을 피할 수 있습니다. 동적 프로그래밍은 최적화 문제 또는 조합 문제를 풀기 위해 사용됩니다.
힙(Heap) 자료구조란 무엇인가요?
힙은 완전 이진 트리 형태의 자료구조로, 특정한 순서를 유지하는 이진 트리입니다. 주로 최댓값 또는 최솟값을 효율적으로 찾기 위해 사용됩니다. 힙은 최대 힙과 최소 힙으로 나뉘며, 최대 힙은 각 노드의 값이 자식 노드보다 크거나 같은 특성을 가지고 있습니다. 최소 힙은 각 노드의 값이 자식 노드보다 작거나 같은 특성을 가지고 있습니다.
빅오 표기법(Big O notation)이란 무엇인가요?
빅오 표기법은 알고리즘의 시간 복잡도를 나타내는 표기법입니다. 알고리즘의 입력 크기에 대한 함수로서, 알고리즘의 성능을 분석하고 비교하는 데 사용됩니다. O 표기법은 알고리즘의 최악의 경우 실행 시간의 상한을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 예를 들어, O(n)은 선형 시간 복잡도를, O(n^2)는 이차 시간 복잡도를 의미합니다.
다익스트라(Dijkstra) 알고리즘은 어떻게 동작하나요?
다익스트라 알고리즘은 하나의 출발점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 출발점에서부터 가장 가까운 정점을 선택하고, 해당 정점을 거쳐 다른 정점까지의 경로를 업데이트합니다. 이 과정을 모든 정점을 포함할 때까지 반복합니다. 다익스트라 알고리즘은 음의 가중치를 가지지 않는 그래프에서 최단 경로를 찾는데 사용됩니다.
해시맵(HashMap)과 해시테이블(Hashtable)의 차이점은 무엇인가요?
해시맵과 해시테이블은 키-값 쌍의 데이터를 저장하는 자료구조입니다. 주요한 차이점은 다음과 같습니다:
동기화: 해시테이블은 동기화되어 여러 쓰레드가 동시에 접근할 수 있습니다. 해시맵은 동기화되지 않으며, 단일 쓰레드 환경에서 사용하는 것이 성능상 유리합니다.
Null 허용: 해시테이블은 키와 값에 null을 허용하지 않습니다. 해시맵은 키와 값 모두 null을 허용합니다.
속도: 해시맵은 일반적으로 해시테이블보다 더 빠른 속도를 제공합니다.
이진 탐색 트리(Binary Search Tree)란 무엇인가요?
이진 탐색 트리는 이진 트리의 일종으로, 모든 노드에 대해 왼쪽 서브트리의 값은 현재 노드의 값보다 작고, 오른쪽 서브트리의 값은 현재 노드의 값보다 큰 특성을 가지는 자료구조입니다. 이진 탐색 트리는 탐색, 삽입, 삭제 등의 연산을 평균적으로 O(log n)의 시간 복잡도로 수행할 수 있습니다.
그리디 알고리즘(Greedy Algorithm)은 어떤 방식으로 동작하나요?
그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다. 각 단계에서 현재 상황에서 가장 좋은 선택을 하며, 이 선택들을 계속 수행하여 전체적으로 최적의 해를 구합니다. 그리디 알고리즘은 부분 최적해를 구하고, 그 부분 최적해들이 전체적으로 최적인지 검증해야 합니다. 그리디 알고리즘은 항상 최적의 해를 보장하지는 않지만, 효율적인 실행 시간을 가지는 경우가 많습니다.
HashMap vs TreeMap : 트리맵은 정렬하여 저장하고, 해시맵은 정렬하지 않고 저장한다. 따라서 삽입/삭제에 트리맵의 속도가 느리지만, 정렬되어서 관리해야하는 경우나 범위 검색을 하는 경우에 트리맵이 더 유용하다.
HashSet vs LinkedHashSet : 해시셋은 순서가 없이 저장되지만, 링크드해쉬셋은 순서를 보장한다.
(set에 있는 데이터 가져올 때는, 인덱스가 없으므로 lterator라는 반복자 사용하여 가져옴)
linkedList : 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 자료 구조
vector vs arrayList : 둘 다 가변적이고, 순서가 있고 중복을 허용한다. 하지만 백터는 동기화로 작동하고 arraylist는 동기화로 작동하지 않는다. 벡터같은 경우는 싱글 스레드 환경에서도 동기화 되기 때문에 어레이리스트보다 성능이 떨어진다.
해시셋이 중복을 걸러내는 방법: hashcode로 해시값을 구해서 같으면 equals메서드로 true를 반환하는지 확인한다. true를 반환하면 같은 객체라고 판단하여, 중복으로 처리하여 삽입하지 않는다.
Hashset vs Treeset : 해시셋은 정렬해주지 않고, 트리셋은 정렬한다. (해쉬맵, 트리맵이랑 같네!) 트리셋은 이진탐색트리를 사용하여 조회가 더 빠르고 삽입/삭제는 느리다.
