내용 정리 - [이것이 코딩 테스트다 with 파이썬]

1. '국내 기술 면접 가이드라인' 깃허브

https://github.com/JaeYeopHan/Interview_Question_for_Beginner

GitHub - JaeYeopHan/Interview_Question_for_Beginner: :boy: Technical-Interview guidelines written for those who started studying

 

---

2. 대표적인 인성 면접 질문 3가지

Q. 개발하면서 가장 행복했던 일은 무엇인가요?

A. 이 질문은 개발자로서의 열정을 느낀 경험을 물어보는 질문이다. 개발하면서 행복감을 느꼈던 순간이나, 보람을 느꼈던 경험을 이야기하면 좋다. 채용자는 같이 일할 만한 사람인지를 확인하고자 이런 질문을 한다.

따라서 자신이 개발하면서 얼마나 행복함을 느끼는지, 어떨 때 기쁜지 등을 설명하면서 개발을 좋아한다는 점을 알리는 것이 좋다.

 

Q. 자신이 가장 열정적으로 참여했던 프로젝트가 있다면 이야기해주세요.

A. 이 질문에는 "자신이 열정적으로 참여했던 프로젝트를 소개"하고, 누구와 함께 했는지, 자신이 맡은 역할이 무엇이었는지 답하면 된다. 특히 프로젝트에서 자신이 기여한 파트를 구체적으로 언급하고, 그 과정에서 겪었던 어려운 점을 어떻게 해결하여 실력 향상을 이룰 수 있었는 지에 대해서 설명할 수 있을 정도로 준비를 하자.

 

Q. 회사에 대해 궁금한 점이 있으면 말해주세요.

A. 면접은 단순히 회사에 채용되는 과정이 아니라, 나 또한 회사를 선택하는 입장이라는 점을 기억하자.

따라서 회사에 대하여 궁금한 점이 있다면, 질문할 수 있도록 사전에 회사에 대해 잘 알아보고 면접에 임하자.

 

1차원 적으로 궁금한 것을 직접 물어보는 것보다는 자신의 개발자로서의 성향 중에서 "긍정적인 성향"을 드러낼 만한 질문을 하는 것이 좋다.

EX) "회사에서 기계식 키보드를 이용해도 좋을까요?" -> 이 경우, 평소에 컴퓨터 장비에 관심이 많은 것처럼 느껴질 수 있다.

EX) "회사에 수면 공간이 있나요? 간식을 제공하나요?" -> 저는 한창 개발을 할 때는 앉은 자리에서 해당 문제가 풀릴 때까지 계속 앉아있기 때문에 회사에 수면 공간이 있거나, 간식 등이 잘 공급된다면 더 일을 잘할 수 있습니다. 같이 질문을 이어나가면서, 끈기 있게 문제를 고민하며 해결하는 습관이 있는 것처럼 어필할 수 있다.

 

---

3. 구현 문제 (Implementation)

코딩 테스트에서 구현이란 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

즉, 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제'이다.

 

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다.
완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

 

코딩 테스트에서 "API 개발 문제" 또한 구현 유형과 상당히 맞닿아 있다.

EX) 카카오 공채 때, API 개발 문제가 출제된 적이 있는데, 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다. 이런 기능을 구현해야 할 때도 파이썬이 상대적으로 무난하게 대처할 수 있을 것이다.

 

---

4. 정렬 알고리즘

4-1. 선택 정렬 (Selection sort)

가장 작은 요소를 선택하여 앞에서부터 순서대로 정렬하는 방식. 시간 복잡도는 O(N^2) 이다.

1) 먼저, 선택 정렬은 주어진 리스트의 모든 요소를 확인하여 가장 작은 요소를 찾고, 첫 번째 위치에 있는 요소와 교환한다. 이 과정을 통해 리스트의 첫 번째 위치에는 가장 작은 요소가 위치하게 된다.

 

2) 다음으로, 첫 번째 위치를 제외한 나머지 요소들 중에서 가장 작은 요소를 찾아 두 번째 위치의 요소와 교환한다. 이 과정을 통해 리스트의 두 번째 위치에는 두 번째로 작은 요소가 위치하게 된다.

 

3) 이러한 과정을 리스트의 끝까지 반복하게 되면, 전체 리스트가 오름차순으로 정렬된 상태가 된다.

 

선택 정렬은 간단한 알고리즘이지만, 주어진 리스트의 길이에 따라 또는 리스트가 이미 어느정도 정렬이 되어있는 경우에도 항상 동일한 시간이 소요되는 단점이 있다.

 

 

---

4-2. 삽입 정렬 (Insertion sort)

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 동작하는 정렬 알고리즘이다.

시간 복잡도는 최선의 경우 O(N), 일반적인 경우에는 O(N^2)

 

1) 삽입 정렬은 두 번째 인덱스부터 시작한다. 왜냐하면 첫 번째 요소는 이미 정렬된 것으로 간주하기 때문이다.

 

2) 두 번째 인덱스의 요소를 임시 변수에 저장하고, 이전 인덱스의 요소와 비교한다.

 

3) 이전 인덱스의 요소가 더 크다면, 이전 인덱스의 요소를 현재 인덱스로 이동시킨다.

이 과정을 반복하며, 이전 요소들 중에서 임시 변수에 저장된 요소보다 작은 요소를 찾을 때까지 계속한다.

 

4) 작은 요소를 찾으면, 그 위치 바로 다음에 임시 변수에 저장된 요소를 삽입한다.

 

5) 이 과정을 리스트의 마지막 요소까지 반복한다.

 

삽입 정렬은 작은 리스트에 대해 효율적이며, 리스트가 거의 정렬된 상태라면 매우 빠르게 동작한다.

하지만, 리스트의 크기가 커질수록 성능은 상대적으로 떨어질 수 있다.

 

 

---

4-3. 퀵 정렬 (Quick sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방식을 사용하는 효율적인 정렬 알고리즘이다.

 

퀵 정렬의 시간 복잡도는 최선의 경우와 평균의 경우에 O(NlogN) 이다.

이는 리스트를 분할할 때, 균등하게 분할할 수 있다면 가장 효율적으로 동작한다는 것을 의미한다.

최악의 경우에는  O(N^2) 이다. 이는 리스트가 이미 정렬되어 있거나, 역순으로 정렬 되어있는 경우가 해당한다.

왜냐하면 매번 분할할 때, 한 쪽은 0개, 다른 한 쪽은 n-1개로 분할되기 때문이다.

하지만 실제로는 이런 경우가 잘 발생하지 않으며, 퀵 정렬은 대부분의 경우에 효율적으로 동작합니다.

 

1) 퀵 정렬은 먼저 리스트에서 하나의 요소를 선택한다. 이를 '피벗(pivot)'이라고 부른다.

보통 리스트의 첫 번째 요소, 마지막 요소, 중간 요소 중 하나를 피벗으로 선택한다.

리스트의 첫 번째 요소를 선택하는 규칙을 호어 분할(Hoare Partition)이라고 한다.

 

2) 리스트의 나머지 요소들은 피벗보다 작은 요소들과 피벗보다 큰 요소들로 분할(partition)된다. 

 

3) 이제 피벗은 그 자리에서 움직이지 않는다. 왜냐하면 피벗은 이미 정확한 위치에 있기 때문이다.

    (피벗의 왼쪽에는 피벗보다 작은 모든 요소들이, 오른쪽에는 피벗보다 큰 모든 요소들이 위치하게 됨)

 

4) 같은 과정을 피벗의 왼쪽 부분과 오른쪽 부분에 대해 재귀적으로 반복한다.

 

5) 모든 요소가 정확한 위치에 있게 되면, 리스트는 완전히 정렬된 상태가 된다.

 

 

---

4-4. 병합 정렬 (Merge sort)

병합 정렬은 '분할 정복' 방법을 사용하는 효율적인 정렬 알고리즘이다.

병합 정렬의 시간 복잡도는, 최선의 경우, 평균의 경우, 최악의 경우 모두 O(NlogN) 이다.

이는 분할 과정에서 리스트를 반으로 나누고, 병합 과정에서 모든 요소를 비교하기 때문이다.

따라서서 병합 정렬은 대용량 데이터나, 데이터의 초기 상태에 관계없이 항상 일정한 성능을 보장하는 알고리즘이다.

하지만 이 과정에서 추가적인 메모리 공간이 필요하다는 단점은 있다.

 

1) 병합 정렬은 먼저 주어진 리스트를 반으로 나눈다. -> '분할(Divide)'

분할은 리스트의 요소가 하나만 남을 때까지 계속된다.

 

2) 분할이 완료되면, 이제 '정복(Conquer)' 과정이 시작된다. 이 과정에서는 두 개의 작은 리스트를 정렬하고, 이를 병합하여 하나의 정렬된 리스트로 만든다.

 

3) 이 과정은 모든 작은 리스트들이 병합되어 원래의 크기로 돌아올 때까지 반복한다.

 

 

---

4-5. 계수 정렬 (Count sort)

계수 정렬은 정수나 정수로 표현할 수 있는 객체에 대한 정렬에서 사용 가능한 특별한 정렬 알고리즘이다.

계수 정렬은 앞서 다루었던 4가지 정렬 알고리즘 같은 "비교 기반의 정렬 알고리즘"이 아니다!

 

최선의 경우, 평균의 경우, 최악의 경우 모두 계수 정렬의 시간 복잡도는 O(N + K) 이다. -> 공간 복잡도도 O(N + K)

N : 주어진 리스트의 크기

K : 주어진 리스트의 최대값

이는 주어진 리스트의 모든 요소를 한 번씩 순회(N)하고, 새로운 리스트를 생성하여 다시 한 번 순회하기 때문이다.

 

계수 정렬은 N에 비해 K가 매우 클 경우, 메모리 낭비가 심하고 비효율적일 수 있다.

또한, 계수 정렬은 정수에 대해서만 사용할 수 있으며, 실수나 문자열 등의 데이터에 대해서는 사용할 수 없다.

 

EX) 0~100 사이의 시험 성적 데이터를 정렬할 때는 계수 정렬이 효과적일 것이다.

 

1) 먼저 주어진 리스트에서 가장 큰 값을 찾는다. 이 값을 보통 K라고 한다.

 

2) 그리고 'K+1'의 크기를 가진 새로운 리스트를 생성하고, 이 리스트의 모든 요소를 0으로 초기화한다.

이 리스트는 주어진 리스트의 각 요소의 개수를 저장하는 데 사용된다.

 

3) 주어진 리스트의 각 요소에 대해, 해당 요소의 값을 인덱스로 사용하여 새로운 리스트에서 해당 인덱스의 값을 1씩 증가시킨다.

 

4) 이제 새로운 리스트는 주어진 리스트의 각 요소의 개수를 나타낸다.

 

5) 새로운 리스트의 첫 번째 요소부터 마지막 요소까지 순회하면서, 각 요소의 값을 그 요소의 인덱스로 사용하여 정렬된 리스트를 생성한다.

 

 

※ 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix sort)과 더불어 가장 빠르다고 볼 수 있다.

 

---

 

※ 파이썬의 sorted()는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용한다.

 

코딩 테스트에서 정렬 알고리즘이 사용되는 유형은 대표적으로 3가지가 있다.

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 묻는 문제

 

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있다.

 

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 기존 정렬 기법으로는 풀 수 없다.

계수 정렬같이 다른 정렬 알고리즘을 이용하거나, 문제에서 기존에서 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

 

---

5. 동적 계획법 (Dynamic Programming)

동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 기법이다.

 

동적 계획법과 "분할 정복"의 차이점 -> 동적 계획법은 문제들이 서로 영향을 미치고 있다. (그래서 메모이제이션이 필요)

 

동적 계획법을 사용하려면, 다음 조건 2가지를 만족하는 지 확인해야 한다.

1) 큰 문제를 작은 문제로 나눌 수 있다.

 

2) 작은 문제에서 구한 정답은, 그것을 포함하는 큰 문제에서도 동일하다.

 

메모이제이션 (Memoization) : 동적 계획법을 구현하는 방법 중 한 종류로,

한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법이다.

 

메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

 

---

 

※ 동적 계획법을 반복문으로 구하는 것은 -> 타뷸레이션(Tabulation) 이라고 한다.

[Top-Down 방식 vs Bottom-Up 방식]
1. 동적 계획법을 재귀 함수로 풀 때는 -> Top-Down (하향식 접근)
  1) 직관적이라 코드 가독성이 좋다.
  2) 재귀 함수 같은 방식을 Lazy-Evaluation 이라고도 한다.
  3) 재귀 호출을 너무 많이 하면, 부하가 크고 느려진다...

2. 동적 계획법을 반복문으로 풀 때는 -> Botton-Up (상향식 접근)
  1) 대체로 재귀 함수 방식보다 빠르다!
  2) 반복문 같은 방식은, 미리 모든 부분 문제의 답을 구해 두므로 Eager-Evalution 이라고 한다.
  3) 부분 문제들을 어느 순서로 구해야 하는지, DP 테이블을 채워나가는 순서를 신경써야 한다!

 

---

문제를 푸는 첫 번째 단계는 (당연하겠지만) 주어진 문제가 Dynamic Programming 유형임을 파악하는 것이다.

특정한 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면, 동적 계획법을 적용할 수 있는지 확인해보자. (부분 문제들의 중복 여부 체크)

 

일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (Top-Down) -> 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어이다.

 

그러나 가능하다면, 재귀 함수를 사용하는 Top-Down 방식보다는 -> Bottom-Up 방식으로 구현하는 것을 권장한다.

시스템 상 재귀 함수의 스택 크기(Recursion depth)가 한정되어 있을 수 있기 때문이다.

import sys

sys.setrecursionlimit(10**6)

 

이런 코드를 추가하여, 그나마 재귀 제한을 완화할 수는 있다.

 

---

6. 플로이드 워셜 (Floyd-Warshall) 알고리즘

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있다.

 

노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 수행하며, 각 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐가는 모든 경로'를 고려한다. 따라서 총 시간 복잡도는 O(N^3) 이다.

 

다익스트라 알고리즘은 그리디 알고리즘이지만, 플로이드 워셜 알고리즘은 동적 계획법이라는 특징이 있다.

N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 동적 계획법으로 볼 수 있다.

즉, [기존 A에서 B로 가는 최소 비용] 과 [A에서 K를 거쳐 B로 가는 비용] 을 비교하여 최소값으로 갱신하겠다는 것이다.

 

---

예제 코드

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

 

---

7. 신장 트리 (Spanning Tree)

신장 트리란 "하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프" 를 의미한다.

 

---

7-1. 크루스칼 알고리즘 (Kruskal Algorithm)

신장 트리 중에서 "최소 비용"으로 만들 수 있는 신장 트리를 찾는 것을 "최소 신장 트리 알고리즘" 이라고 한다.

대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다. 

크루스칼 알고리즘은 그리디 알고리즘이다.

 

1) 간선 데이터를 비용에 따라, 오름차순으로 정렬한다.

 

2) 간선을 하나씩 확인하면서, 현재의 간선을 추가하면 사이클이 생기는지 확인한다.

   2-1) 사이클이 발생하지 않는 경우 -> 최소 신장 트리에 포함시킨다.

   2-2) 사이클이 발생하는 경우 -> 최소 신장 트리에 포함시키지 않는다.

 

3) 모든 간선에 대하여, 2번의 과정을 반복한다.

 

최소 신장 트리도 일종의 트리 자료구조이므로,

최종적으로 포함되는 간선의 개수가 '노드의 개수 - 1'과 같다는 특징이 있다.

 

크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE) 의 시간 복잡도를 가진다.

간선을 비용 순으로 정렬하는 시간이 가장 오래 걸리는 부분이기 때문이다.

 

---

8. 위상 정렬 (Topology Sort)

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때, 사용하는 알고리즘이다.

조금 더 이론적으로 말하자면 "방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것" 이다.

 

위상 정렬 알고리즘을 자세히 살펴보려면, 진입차수(Indegree)를 알아야 한다.

진입차수 : 특정한 노드로 '들어오는' 간선의 개수

 

1) 진입차수가 0인 노드를 큐에 넣는다

 

2) 큐가 빌 때까지 아래의 과정을 반복한다.

   2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

   2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

 

이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다.

사이클이 존재한다면, 사이클에 포함되어 있는 어떠한 원소도 큐에 들어가지 못하기 때문이다.

 

※ 다만, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많다.

 

위 과정을 수행하는 동안, 큐에서 빠져나간 노드를 순서대로 출력한 것이 위상 정렬을 수행한 결과이다.

따라서 위상 정렬의 답안은 여러 가지가 될 수 있다.

 

---

위상 정렬의 시간 복잡도는 O(V + E) 이다.

차례대로 모든 노드를 확인하면서(V), 해당 노드에서 출발하는 간선을 차례대로 제거(E)해야 한다.

 

---