Skip to content

Latest commit

 

History

History
342 lines (203 loc) · 10.8 KB

알고리즘.md

File metadata and controls

342 lines (203 loc) · 10.8 KB

문제 1 시간복잡도

유형: 서술형

문제: 보기에 주어진 시간복잡도를 작은 것부터 큰 것 순서로 나열하시오.

보기

  1. O(nlogn)
  2. O(n!)
  3. O(2^n)
  4. O(n^3)
  5. O(n)

정답 작성예시 : 12345

정답 및 해설

정답: 51432

해설: 시간복잡도라는건 입력값이 커질수록 알고리즘의 수행시간이 어떻게 증가하는지를 나타내는 지표이다. 따라서 입력값이 커질수록 수행시간이 증가하는 정도가 작은 것부터 큰 것 순서로 나열하면 된다. (주의 : n이 2일땐 4번이 제일 복잡하지만 시간복잡도라는건 일반적으로 입력값이 커질 때를 가정한다.)

문제 2 재귀함수

유형: 서술형

문제: 다음 코드를 실행했을 때 출력되는 결과는?

void func(int n) {
	if (n == 1) return;
	if (n % 2 == 0) func(n/2);
	else func(n + 1);
	cout << n << " ";
}

int main() {
	func(5);
	return 0;
}
정답 및 해설

정답: 2 4 3 6 5

해설: 공백에 주의한다. func(5) -> func(6) -> func(3) -> func(4) -> func(2) -> func(1) 순으로 호출되며 출력되는 순서는 2 4 3 6 5 이다. 재귀 함수의 실행순서는 호출 순서의 역순이다.

문제 3 힙정렬

유형: 서술형

문제: 다음 수열을 힙정렬을 이용하여 오름차순으로 정렬할 때, 3번 swap한 상태에서의 수열을 쓰시오.

[9, 8, 7, 6, 5, 4, 3, 2, 1]

정답 작성예시 : 123456789

정답 및 해설

정답: 867154329

해설: 힙정렬은 정렬을 위해 완전 이진트리를 이용하는 알고리즘이다. 오름차순 정렬은 최대힙을 구성한다. 최대힙은 부모노드가 자식 노드보다 큰 경우를 말한다. 계속해서 힙을 유지할 수 있도록, 부모노드와 자식노드를 비교하며 swap을 해준다. 이 때, 3번 swap한 상태에서의 수열은 867154329 이다.

참고자료 : https://www.inflearn.com/courses/lecture?courseId=32456&tab=curriculum&type=LECTURE&unitId=4081

https://velog.io/@char1ey95/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-Sort

문제 4 정렬

유형: 객관식

문제: 다음 정렬 알고리즘 중 최악의 경우 시간복잡도가 O(n²)인 알고리즘을 모두 고르시오.

보기

  1. 퀵정렬
  2. 합병정렬
  3. 버블정렬
  4. 삽입정렬
  5. 힙정렬
정답 및 해설

정답: 1,3,4

해설 정렬 알고리즘 시간복잡도 퀵정렬은 피벗을 기준으로 정렬을 하는 알고리즘인데, 이미 정렬된 배열을 정렬할 시에 최악으로 O(n²)의 시간복잡도를 가진다. 버블정렬과 삽입정렬은 이미 정렬된 배열을 정렬할 시에 최악으로 O(n²)의 시간복잡도를 가진다.

문제 5 DP

유형: 객관식

문제:다음 중 동적 프로그래밍(Dynamic Programming) 알고리즘을 이용하여 풀 수 있는 문제를 모두 고르시오.

보기

  1. 배낭문제
  2. 최장 공통 부분 수열(LCS)
  3. 피보나치 수열
  4. N-Queen 문제
  5. 외판원 순회 문제
정답 및 해설

정답: 1,2,3,5

해설 : N-Queen문제는 백트래킹 알고리즘의 대표적인 예시이다. 외판원 순회문제 같은 경우 완전탐색으로 해결할시 시간복잡도가 O(n!)이기 때문에 동적 프로그래밍으로 해결하는 것이 효율적이다.

문제 6 분할정복

유형: 객관식

문제: 다음 중 분할 정복(Divide and Conquer) 알고리즘의 예가 아닌 것은?

보기

  1. 병합 정렬
  2. 퀵 정렬
  3. 이진 검색
  4. 다익스트라 알고리즘
정답 및 해설

정답: 4

해설 : 다익스트라 알고리즘은 그리디 알고리즘의 한 종류로서 항상 최단 거리를 택하여 탐색하는 알고리즘이다. 분할 정복은 문제를 작은 단위로 나누어 해결하는 방법이다. 다익스트라 알고리즘은 그리디 알고리즘의 특성을 가지고 있어 분할 정복의 특성을 가지고 있지 않다.

문제 7 NP

유형: 객관식

문제: 다음 중 NP 문제에 대한 설명으로 올바른 것은?

보기

  1. 다항 시간에 해결할 수 없는 문제들의 집합
  2. 비결정적 튜링 머신으로 다항 시간에 검증할 수 있는 문제들의 집합
  3. 다항 시간 내에 해결할 수 있는 문제들의 집합
  4. 지수 시간만에 해결할 수 있는 문제들의 집합
정답 및 해설

정답 : 2

해설 : NP(Nondeterministic Polynomial time) 클래스는 '다항 시간에 검증할 수 있는 문제들의 집합'을 의미한다. 주어진 해답이 맞는지 검증하는 과정이 다항 시간 내에 가능한 문제들을 의미한다. P문제는 '다항 시간 내에 해결할 수 있는 결정 문제'를 의미한다. P는 NP의 부분집합이다. NP-Hard문제는 모둔 NP 문제를 다항 시간 내에 환산할 수 있는 문제를 의미한다.(ex. halting problem, 외판원순회문제) NP-Complete문제는 NP-Hard문제이면서 NP문제인 문제를 의미한다. (ex. 배낭문제)

참고자료 : https://gazelle-and-cs.tistory.com/64

문제 8 벨만포드 알고리즘

유형: O/X

문제: 벨만-포드(Bellman-Ford) 알고리즘은 음의 사이클을 가진 그래프에서도 정확한 최단 경로를 찾을 수 있다.

O / X

정답 및 해설

정답: X

해설 : 벨만-포드 알고리즘은 음의 가중치를 가진 간선이 있는 그래프에서도 정확한 최단 경로를 찾을 수 있다. 다만, 음의 사이클이 있는 경우에는 최단경로를 찾아 낼 수 없다. 음의 사이클을 돌면 해당 사이클을 돌 때마다 경로의 총 가중치가 계속 감소되어 최단 경로가 존재할 수 없게된다.

문제 9 다익스트라 알고리즘

유형: O/X

문제: 다익스트라(Dijkstra) 알고리즘은 음의 가중치를 가진 간선이 있는 그래프에서도 정확한 최단 경로를 찾을 수 있다.

O / X

정답 및 해설

정답: X

해설 : 다익스트라 알고리즘은 음의 가중치를 가진 간선이 있는 그래프에서는 정확한 최단 경로를 찾을 수 없다. 다익스트라 알고리즘은 현재까지 찾은 경로가 최단경로라는 가정을 한채로 동작한다. 음의 가중치가 존재할 경우 이미 처리한 노드라도 더 짧은 경로가 발견될 수 있어 최단경로를 찾을 수 없다.

문제 10 DFS,BFS

유형: O/X

문제: 깊이 우선 탐색(DFS)은 최단 경로 문제(가중치가 없는)를 해결하는 데 너비 우선 탐색(BFS)보다 항상 효율적이다.

O / X

정답 및 해설

정답: X

해설 : DFS는 깊이 방향으로 탐색하기 때문에, 최단 경로를 보장하지 않는다. 따라서 모든 가능한 경로를 탐색한 후에야 최단 경로를 알 수 있다.

문제 11

유형: O / X

문제: 에라토스테네스의 체는 O(n log n)의 시간복잡도를 가진다.

정답 및 해설

정답: X -> O(n log log n)

해설: 소수 판별법

  1. O(N) 방식
    • 한 숫자에 대한 소수 판별시 2부터 해당 숫자 바로 전까지의 모든 수로 나눠보고 나머지가 0인지 확인하는 방법.
  2. O(N/2) 방식
    • 짝수를 먼저 제외하고 2 이후의 홀수만 검사하여 연산 횟수를 절반으로 줄이는 방법.
  3. O(N^0.5) 방식
    • 소수의 약수 중 하나는 반드시 √N 이하에 존재하므로, 2부터 √N까지만 나눠보는 방법으로 최적화.
  4. O(n log log n) 방식 -> 에라토스테네스의 체
    • 하나의 숫자에 대해 소수판별을 위 세가지 방식으로 충분하지만, 이건 특정 범위의 모든 소수의 개수를 구할때 유용. 1부터 N까지의 모든 소수를 찾을 때 사용, 배수들을 반복적으로 제거하여 소수만 남기는 방식.

참고자료: https://alive-wong.tistory.com/18

문제 12

유형: 서술형

문제: 캐시 교체 알고리즘이 필요한 이유와 주요 알고리즘의 종류를 설명하세요.

정답 및 해설

정답: 캐시는 제한된 리소스를 사용하기 때문에, 저장 공간이 가득 찼을 때 어떤 데이터를 유지하고 어떤 데이터를 제거할지 결정하는 과정이 필요합니다. 이때 캐시 교체 알고리즘이 사용됩니다. 주요 알고리즘에는 다음과 같은 방식이 있습니다.

  1. FIFO (First in First Out) - 가장 먼저 캐시에 들어온 데이터를 먼저 제거
  2. LRU (Least Recently Used) - 가장 오랫동안 사용되지 않은 데이터를 제거
  3. LFU (Least Frequently Used) - 사용 횟수가 가장 적은 데이터를 제거

문제 13 최단거리 알고리즘

유형: 객관식

문제: 다음 알고리즘 중, 모든 정점 쌍 간의 최단거리를 가장 효율적으로 계산할 수 있는 알고리즘은?

보기:

  1. 다익스트라 알고리즘
  2. 플로이드-워셜 알고리즘
  3. 벨만포드 알고리즘
  4. 펜윅트리 알고리즘
  5. 라인 스위핑 알고리즘
정답 확인하기

정답: 2

해설: 플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구할 수 있는 알고리즘입니다. 2차원 테이블에 각 지점에서 다른 모든 지점까지의 최단 거리를 저장합니다.

참고 자료: [알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

문제 14 DP

유형: 서술형

문제: 동적 계획법이 가지는 2가지 조건을 서술하세요.

정답 확인하기

정답:

  1. 중복되는 부분 문제 중복되는 부분 문제는 나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 사용해 중복 계산을 없앱니다.
  2. 최적 부분 구조 최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.

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