알고리즘 면접 질문 정리

[Choisehyeon]

• 이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 정렬 알고리즘은?
• 54321 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
• 랜덤으로 배치된 배열이 있을때, 어떤 정렬을 사용하면 좋을까요?
• 자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
• 정렬을 하는 이유는 무엇인가요?
• 버블 정렬 알고리즘은 왜 사용할까요?
• 버블 정렬과 삽입 정렬의 차이점은?
• 왜 삽입정렬이 평균 O(N^2) 시간 복잡도를 갖는 알고리즘 중 가장 빠를까요?
• Quick Sort의 특징과 시간 복잡도에 대해 설명해주세요.
• Quick Sort 성능 개선 기법
• Merge Sort의 특징과 시간 복잡도에 대해 설명해주세요.
• Quick Sort와 Merge Sort의 차이점?
• Kotlin에서 사용하는 정렬 알고리즘은?
• 최소 신장 트리는 무엇이며 어떻게 구현할 수 있나요?
• 다익스트라, 벨만포드, 플로이드 워셜의 개념에 대해서 간단히 설명해주세요
• 안정하다는 것이 무엇을 뜻하고, 안정 정렬과 불안정 정렬의 차이점과 종류를 나열해주세요.
• 분할 정복에 대해 설명과 예시를 들어주세요.
• Dynamic Programming이 무엇이고 왜, 어떻게 사용하나요?
• 최악의 복잡도는 나쁘지만 실제로 자주 사용되는 알고리즘이 무엇인가요?
• 알고 있는 정렬 알고리즘의 종류를 말해주세요.
• 그래프에서 특정 정점에서 다른 정점까지의 최단 거리를 구하는 방법은 무엇이 있나요?
• (상황을 주고) 어떤 상황에서 어떤 알고리즘을 사용하는 게 좋은가요?
  • 해당 상황에서 시간복잡도는 어떻게 되나요?
  • 해당 알고리즘을 사용해 최적화한 경험이 있나요?
  • 해당 알고리즘에 자료구조는 어떤게 좋을까요?
• 선택 정렬이 불안정 정렬인 이유는 무엇인가요?
• 기수 정렬에 대해 간단하게 설명해주세요.
• 힙정렬을 사용하는 예시가 있을까요?
• 다익스트라 알고리즘에서 음수가 사용되면 안되는 이유가 무엇인가요?
• 오늘 저녁 매뉴는 무엇인가요?

[no1msh]

이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 정렬 알고리즘은?

삽입정렬입니다.
삽입정렬은 처음에 정렬이 되어있지 않은 원소를 찾기때문에 이때 정렬이 이미 되어있다면, 배열의 크기가 n일 경우 O(n)만큼의 순회하기 때문에 가장 좋은 성능을 보입니다.

[s9hn]

54321 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?

삽입 정렬은 배열의 처음부터 각 요소를 적절한 위치해 삽입해가면서 정렬하는 방식이다.
이미 정렬된 부분이 많을 때, 작은 크기의 배열에 효과적이다.

[Choisehyeon]

랜덤으로 배치된 배열이 있을때, 어떤 정렬을 사용하면 좋을까요?

Merge Sort를 사용하는 것이 좋을 것 같습니다.
Merge Sort는 최악과 최고의 시간복잡도가 모두 O(n logn)이기 때문입니다.

Quick Sort도 최고의 시간복잡도가 O(n logn)이지만 최악의 시간복잡도는 O(n^2)이기 때문에 최악과 최고의 시간 복잡도가 O(n logn)인 Merge Sort를 사용하는 것이 좋다고 생각합니다.

[krrong]

자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?

기수정렬을 사용하면 좋습니다.

[hyemdooly]

정렬을 하는 이유는 무엇인가요?

탐색하기 위해서입니다.

[sujin9]

버블 정렬 알고리즘은 왜 사용할까요?

우선, 배열 내에서 정렬이 이루어져 추가적인 메모리 사용이 없습니다.
또한 구현이 간단하고 쉬운 편에 속한다는 장점이 있습니다.

[no1msh]

버블 정렬과 삽입 정렬의 차이점은?

버블 정렬은 오름차순 정렬이라고 가정할 때 가장 뒤부터 정렬됩니다.
반면 삽입 정렬은 맨 앞부터 정렬됩니다.

[s9hn]

왜 삽입정렬이 평균 O(N^2) 시간 복잡도를 갖는 알고리즘 중 가장 빠를까요?

삽입 정렬은 첫번째 원소부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입합니다. 따라서 삽입할 위치까지만 탐색하면 되기때문에 선택 정렬, 버블 정렬에 비해 빠릅니다. 또한 삽입 정렬은 데이터가 모두 정렬된 경우 한 번씩만 비교하면 되므로 O(N)을 가집니다.

[Choisehyeon]

Quick Sort의 특징과 시간 복잡도에 대해 설명해주세요.

Quick Sort는 매우 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘* 중 하나로 합병정렬과 달리 리스트를 비균등하게 분할합니다. 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬을 합니다.
최고의 시간 복잡도는 O(n logn)이지만 피봇 값이 최소나 최댓값으로 지정되어 파티션이 나누어지지 않았을 때, O(n²)에 대한 시간복잡도를 가지는 데 이는 정렬하고자 하는 배열이 오름차순 정렬되어 있거나 내림차순 정렬되어 있으면 생기는 경우입니다.

[krrong]

Quick Sort 성능 개선 기법

피벗을 랜덤한 위치에서 잡아 최악의 경우가 나올 확률을 줄입니다.

[hyemdooly]

Merge Sort의 특징과 시간 복잡도에 대해 설명해주세요.

분할 정복 기법을 사용합니다. 주어진 배열을 원소가 하나밖에 남지 않을 때까지 계속해서 쪼개고, 크기 순으로 재배열하며 합칩니다.
시간복잡도는 O(nlogn)입니다.

[sujin9]

Quick Sort와 Merge Sort의 차이점?

[no1msh]

Kotlin에서 사용하는 정렬 알고리즘은?

코틀린에서 정렬은 자바와 같습니다.
정렬하려는 대상이 primitive type 이라면 �Dual - pivot Quick sort이며, reference type이라면 Tim - sort입니다.

[s9hn]

최소 신장 트리는 무엇이며 어떻게 구현할 수 있나요?

최소신장트리(Minimum Spanning Tree, MST)는 연결 그래프에서 모든 노드를 연결하는 트리를 만들 때, 간선의 가중치 합이 최소가 되도록 하는 사이클이 존재하지 않는 트리를 말한다.
구현으로는 크루스칼 및 프림 알고리즘 등이 있다.

[Choisehyeon]

다익스트라, 벨만포드, 플로이드 워셜의 개념에 대해서 간단히 설명해주세요

다익스트라 알고리즘

• 간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘
• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나갑니다.
• 순차 탐색 하는 방법으로 구현 시 O(N^2)의 시간 복잡도를 가지고 우선순위 큐를 사용하여 구현 시 간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 O(E log V)의 시간 복잡도를 가집니다.

벨만- 포드 알고리즘

• 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘
• 간선의 가중치가 음수인 경우에도 적용이 가능합니다.
• (정점 - 1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나갑니다.
• V번 반복에 대해서 해당 정점과 연결되어 있는 모든 간선(E)을 탐색해주기 때문에 시간복잡도는 O(VE)입니다.

플로이드-와샬 알고리즘

• 모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘
• 동적 계획법을 이용해 구현할 수 있으며 시간복잡도는 O(n^3)입니다.

[krrong]

안정하다는 것이 무엇을 뜻하고, 안정 정렬과 불안정 정렬의 차이점과 종류를 나열해주세요.

안정하다는 것은 동일한 값을 갖는 데이터들의 순서가 정렬된 후에도 유지되는 것을 말합니다.

• 안정 정렬
  • 버블 정렬, 삽입 정렬, 합병 정렬
• 불안정 정렬
  • 퀵 정렬, 선택 정렬, 계수 정렬

[hyemdooly]

분할 정복에 대해 설명과 예시를 들어주세요.

큰 문제를 작게 쪼개어 풀 수 있는 단위로 나눈 다음에 작은 단위를 합쳐가며 풀어가는 방식입니다.
예시로는 이진 탐색, 병합 정렬, 퀵 정렬이 있습니다.

[sujin9]

Dynamic Programming이 무엇이고 왜, 어떻게 사용하나요?

[no1msh]

최악의 복잡도는 나쁘지만 실제로 자주 사용되는 알고리즘이 무엇인가요?

Quick Sort입니다.
이미 자바 및 코틀린에서 Dual pivot Quick Sort를 사용하고 있습니다.

Quick Sort는 이미 정렬되어있는 상태일 때 분할을 해도 pivot을 기준으로 분할된 배열의 사이즈가 1과 n - 1 이기 때문에 매우 비효율적입니다.

하지만 시간 복잡도가 O(nLogn)인 정렬 알고리즘 중에 가장 빠르기에 자주 사용됩니다.

[s9hn]

선택 정렬이 불안정 정렬인 이유는 무엇인가요?

안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )
불안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬 )

따라서 선택 정렬은 기존순서가 유지되지않아 불안정 정렬이다.

[Choisehyeon]

기수 정렬에 대해 간단하게 설명해주세요.

기수 정렬은 비교하지 않는 정렬 알고리즘으로 낮은 자릿수부터 정렬을 수행합니다.
숫자별로 버킷(bucket)이라는 큐 생성하여 정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬, 이를 자릿수만큼 반복합니다. 데이터 개수 n, 최대 자릿수를 d라고 할 때 시간복잡도는 O(dn)입니다. 속도가 빠르지만 버킷을 구성하기 위한 추가 메모리 필요, 정렬할 수 있는 데이터 타입 한정적이라는 단점이 있습니다.

[krrong]

힙정렬을 사용하는 예시가 있을까요?

가장 큰 값 몇 개만 필요한 경우 유용하게 사용할 수 있습니다.

[hyemdooly]

다익스트라 알고리즘에서 음수가 사용되면 안되는 이유가 무엇인가요?

음수 간선에서 최소비용이 무한대가 되기 때문에 최단거리를 계산할 수 없습니다.