2023.01.03 TIL(알고리즘 CS Q&A 정리)

개발일지/기술 면접 대비

2023.01.03 TIL(알고리즘 CS Q&A 정리)

플리피나리 2023. 1. 4. 10:00

1. 시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?

어떤 알고리즘이 있을 때, 우리는 해당 알고리즘의 성능을 평가할 필요가 있다. 우리는 이러한 알고리즘의 성능을 '복잡도(Complexity)'의 척도를 사용해 평가한다.(당연히 복잡도가 낮으면 good, 높으면 bad) 이러한 복잡도의 종류에는 아래와 같이 2가지가 있다.

시간 복잡도 : 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
공간 복잡도 : 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하는지를 분석

각각에 대해서 조금 더 자세히 살펴보자.

1) 시간 복잡도

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간이다. 이것은 실제로 프로그램을 실행해보아야 알 수 있지만 많은 사람들은 프로그램을 짜기 전이나 짜는 도중에 이를 짜고 싶어한다.(코드를 완성했는데 시간 복잡도가 너무 높다면 시간, 인력 등 많은 점에서 괜한 손해를 보게 되니까....) 또한 실행환경에 따라서도 다르게 측정될 수 있다. 따라서 사람들은 이를 유추하는 방법에 대해 생각해내는데 그것이 바로 특정한 크기의 입력(n)에 대해 기본 연산의 실행 횟수를 분석하는 방법이다. 기본 연산은 데이터 입출력(copy, move...), 산술연산(add, multiply...), 제어연산(if, while, for...) 등이 있다. 이러한 분석 방법은 3가지가 존재한다.

빅-오 표기법 : 알고리즘 실행 시 최대로 걸릴 수 있는 시간 => 가장 실용적, 일반적... 우리는 이 값을 도출하는 방법을 알아야 한다!! 최악의 경우(Worst Case)를 예측
빅-오메가 표기법 : 알고리즘 실행 시 최소로 걸릴 수 있는 시간 => 어디에 자랑할 것도 아니고, 알아서 뭐하냐....ㅡ.ㅡ;; 최선의 경우(Best Case)를 예측
빅-세타 표기법 : 알고리즘 실행 시 평균적인 수행 시간 => 제일 필요하긴 한데... 솔직히 찾을 방법이 거의 없다... 평균적인 경우(Average Case)를 예측

이제 우리는 빅-오 표기법에 대해 정리하면 된다.

빅-오 표기법의 수학적 정의는 다음과 같다.

이때 f(n)은 내가 만든 알고리즘의 실제 running time을 의미한다.

간단하게 예를 들면

이라고 가정한다면

가 성립되는 k와 n이 존재하기 때문에 내가 만든 알고리즘 f(n)은 빅-오 표기법으로

으로 나타낼 수 있다.

아래 그래프를 통해 해당 내용을 좀 더 정리해보자.

내가 만든 알고리즘의 시간을 보여주는 그래프가 f(n)이다. 이떄 n0 보다 충분히 큰 입력값 n에 대해 내가 만든 알고리즘인 f(n)의 running time이 최악인 경우에도 점근 상한선인 kg(n)을 넘지 못한다. 따라서 이때 빅-오 표기법을 사용해 O(g(n))이라고 나타낼 수 있다.

이때 아마 몇몇 이들은 의문을 가질 것이다. 왜 빅-오를 n^2으로 잡는가, 어떻게 n^2+2n+3의 상한치가 될 수 있는가. 그 이유는 시간 복잡도가 점근적 표기법을 따르기 때문이다. 점근적 표기법이란 데이터의 개수 n → ∞ 일 때의 시간복잡도를 표현하는 방법이다.(실제로 입력데이터는 어마무시하게 많을테니 이 방법이 어느정도 맞을 것이다...)

빅-오 표기법의 특징은 다음과 같다.

계수 무시 : 빅-오 표기법은 데이터 입력값의 개수(n)가 충분히 크다고 가정있기 때문에 계수 같은 사소한 부분은 무시한다. => 예를 들어 O(2N)은 O(N)와 같이 앞의 계수를 무시한다.
영향력 없는 항 무시 : 마찬가지로 가장 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다.

와 같이 제곱항 이외 영향력이 없는 항들은 무시한다.

시간복잡도의 성능을 비교하면 다음과 같다.(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

그래프로 확인하면 다음과 같이 확연한 속도 차이를 볼 수 있다.

2) 공간 복잡도

공간 복잡도란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하는지를 분석하는 것이다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성한다.

2. 재미있게 공부한 알고리즘이 있다면 설명해주실 수 있을까요?

**그래프와 큐 자료구조 먼저 익히기**

그래프 탐색 : 하나의 정점에서 차례대로 모든 정점들을 한 번씩 방문하는 것

1) BFS(너비 우선 탐색)

그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. BFS는 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘이다. 즉, '미로를 빠져나가는 최단 거리(경로)'를 구하는 문제 등에서 효율적이다.

동작 원리는 다음과 같다.

탐색 시작 노드 정보를 큐에 삽입해 방문처리를 한다.
큐에서 노드를 꺼내(당연히 가장 먼저 넣은 요소가 꺼내질 것) 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.
위의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

여기서 방문처리란 탐색한 노드를 재방문하지 않도록 구분한다는 말이다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크한다.

그림으로 살펴보면 다음과 같다.

(1)에서 루트노드에 방문하고,

(2), (3), (4), (5)에서 인접하고, 방문된적 없고, 큐에 저장되지 않은 노드를 큐에 집어넣고,

(6)에서 가장 먼저 큐에 저장된 1번 노드로 이동해 인접 노드들을 확인하는 과정을 반복한다.

파이썬으로 코드 구현 시 다음과 같다.

# deque 라이브러리 불러오기 -> 감사하게도 파이썬에 큐 자료구조와 비슷한 deque가 존재(이건 양방향)
from collections import deque

# BFS 메서드 정의
def bfs (graph, node, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([node])
    # 현재 노드를 방문 처리
    visited[node] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True

# 노드 간 연결 정보, 리스트 내 인덱스(index)는 노드 번호를 의미
# 각 인덱스에 해당하는 원소에 해당 노드에 인접한 노드 번호
graph = [
    [],  # 리스트 내 원소의 인덱스와 노드 번호를 일치시키기 위해 인덱스 0에 빈 리스트 넣기
    [2, 3],  # 1번 노드에 인접한 2, 3번 노드
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

# 노드별로 방문 정보를 리스트로 표현 -> 예를 들면 0번 노드를 방문했다면 [T, F, F, F, F, F, ...]
visited = [False] * 9

# 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
bfs(graph, 1, visited)

2) DFS(깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 좀 더 쉽게 말하면, 갈림길이 있을 때 한방향으로 끝까지 간 후 답을 확인하는 과정을 반복한다. 만약 끝까지 도달해 해당 경로가 답이 아니라면 그 이전 노드로 다시 복귀해 다른 경로를 찾는다. 만약의 미로를 탐색하는 경우로 가정한다면 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색하는 과정을 반복한다. 해당 알고리즘은 모든 노드를 방문하고자 하는 방법을 찾는 경우에 사용되며, 단순 검색 속도 자체는 BFS에 비해 느리다.(끝까지 가야하기 때문에...)

그림으로 살펴보면 다음과 같다.

(1)에서 시작노드를 방문하고,

(2)에서 인접한 1번 노드를 방문한다.

(3)에서 1번과 인접한 2번 노드를 방문하고,

이런 방식을 반복하다가 (5)에서 더 이상 나아갈 경로가 없기 때문에 4번 노드 이전에 방문한 3번 노드로 back하고

(6)에서 마찬가지로 더 이상 나아갈 경로가 없기 때문에 3번 노드 이전에 방문한 2번 노드로 back한다.

(7)도 마찬가지...

결국 시작 노드에서 아직 방문하지 않은 정점이 없다면 알고리즘이 종료된다.

파이썬으로 코드 구현 시 다음과 같다.

# DFS는 스택 or 재귀함수로 구현 가능
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 방문노드
visited = [False] * len(graph)

def dfs(graph, node, visited):
	visited[node] = True
    print(node, end=' ')
    
    for i in graph[node]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
# 0번 노드가 없으니 1번 노드부터 탐색
dfs(graph, 1, visited)

3. 포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?

일단 아직 발견하지 못했다. 다른 팀원의 도움을 빌리자면 크롤링 부분에서 이중 for문을 안 쓰기 위해 노력했다는 정도이다. 이게 옳은 답은 아닌 것 같지만 만약 이러한 답변을 받는다면 이렇게 답변해 볼 것!

4. 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?

이분탐색(Binary Search)은 이진탐색이라고도 불리며 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이때 주의할 점은 이진탐색이 가능한 배열은 내부가 정렬되어 있어야만 한다는 것이다.(오름차순 or 내림차순) 먼저 어떻게 동작되는지 그림을 통해 확인하자.

먼저, 정렬되어 있는 배열에서 중앙에 위치한(중앙의 인덱스를 구한다...) 값을 뽑고, 찾고자하는 값이 뽑은 값보다 작은 지, 큰 지를 확인한다. 만약 작은 값이라면 중앙값 기준 왼쪽 요소들을 기준으로 다시 중앙값을 뽑고, 큰 값이라면 중앙값 기준 오른쪽 요소들을 기준으로 다시 중앙값을 뽑는다. 이러한 과정을 특정값을 찾을 때까지 반복한다.

코드로 작성하면 다음과 같다.

# 비재귀적 이진탐색의 Python 코드
# 인자로 배열과 찾고자 하는 값을 전달
def binary_search (arr, val):
    first = 0
    last = len(arr) - 1
    while first <= last:
        mid = (first + last) // 2
        if arr[mid] == val:  # 찾는 값이 중앙값일 경우
            return mid
        if arr[mid] > val:   # 찾는 값이 중앙값 보다 작을 경우
            last = mid - 1
        else:  # 찾는 값이 중앙값 보다 클 경우
            first = mid + 1
    return -1

시간 복잡도에 대한 이야기하면 다음과 같다.

맨 처음 원소의 개수가 8개라고 하자. 8개에서 4, 2, 1 으로 반씩 점차 줄어드는 것을 확인할 수 있다. 즉, N=8일 때 탐색이 3회 수행 됐으므로 시간 복잡도는 3이 된다.

일반화하여 생각해보자. N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, … , 1(최악의 경우) 으로 실행 될 것이다. 여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면, K는 N에 대해 어떻게 나타낼 수 있을까?
1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N

즉, 이진 탐색의 시간 복잡도는 O(logN) 이 된다.

5. 시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?

1) 반복문의 최소 사용

2) 자료구조의 적절한 사용 : 가장 효율적인 자료구조를 적절히 사용한다.

3) 알고리즘의 적절한 사용 : 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등 효율적인 알고리즘을 공부해뒀다가 적절할 떄 사용한다.

6. 공간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?

1) 고정공간보다 가변공간을 사용할 수 있는 자료구조들을 사용한다.

2) 함수 호출 시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간ㅇ니 필요하기에 최대한 적게 사용한다.

3) 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로 짜는게 더 효율적이다.

'개발일지 > 기술 면접 대비' 카테고리의 다른 글

2023.01.08 TIL(Django Q&A 정리) (0)	2023.01.09
2023.01.07 TIL(자료구조 CS Q&A 정리) (2)	2023.01.09
2023.01.06 TIL(네트워크 CS Q&A 정리) (0)	2023.01.06
2023.01.05 TIL(Django Q&A 정리) (0)	2023.01.06
2023.01.02 TIL(데이터베이스 CS Q&A 정리) (0)	2023.01.03

현재글2023.01.03 TIL(알고리즘 CS Q&A 정리)

고양이 퍼레이드