CS & 알고리즘 스터디: 첫 번째 스터디

스터디 시작

정글을 마치고 무엇을 하면 좋을지 몰라 스터디를 모집해봤다.
다행히 같이 하겠다는 사람들이 꽤 있어서 모집은 순탄했으나, 스터디를 해본 적이 없어서(…) 관련 자료들을 찾다가 애를 먹었다.

스터디에서 사람들이 기대하는 효과가 무엇일까?
어떤 방식으로 진행해야 하는가?
무슨 내용을 집중적으로 공부해야 할까?

등등의 고민들을 안고 인터넷을 뒤적거려봤다.

첫 번째 스터디

우선 내용은 정글에서 처음에 한 것들 위주로 해보기로 했다.

찾아본 타 스터디들을 참고하여 스터디 준비사항을 정리해봤다.

이와 같은 방식으로 CS지식과, Problem Solving 문제들을 1부/2부 나누어 진행해보고, 스터디원들의 피드백을 받아 점차 개선해 나갈 생각이다.
이번엔 알고리즘 복습에 포커스를 맞추었기에 1부 내용과 2부 내용이 관련이 있다.

공부 정리

키워드

시간 복잡도

Q. Big-O, Big-Theta, Big-Omega에 대해 설명해 주세요.
A:

Big-O, Big-Theta, Big-Omega 모두 점근 성능을 표기하는 방법이다.
점근성능이란 입력크기 n이 무한히 커짐에 따라 결정되는 성능이며, 알고리즘의 수행시간은 입력 크기에 비례하여 증가하기 때문에 입력 크기 n이 충분히 큰 상황을 전제로 알고리즘의 성능을 분석하는 것이 바람직하기 때문에 이를 고려해야 한다.

이런 점근성능을 사용하면 최고차항만을 이용한 어림값으로 표현이 되기 때문에 알고리즘의 정확한 수행시간은 모를지언정, 입력 크기가 증가함에 따라 어떤 식으로 수행시간이 증가하는지 파악할 수 있다. 즉, 식의 증가 추세를 쉽게 파악할 수 있게 되고 이는 알고리즘의 우열을 따질 때 꽤나 유용하다.

Big-O 표기:

어떤 양의 상수 c, n₀ 이 존재하여 모든 n >= n₀ 에 대하여
f(n) <= c*g(n)을 만족하면 f(n) = O(g(n))이다.

빅오 표기법은 알고리즘의 최악의 경우 복잡도를 나타낸다.
입력 크기 n이 충분히 클 때, 실행 시간이 얼마나 빠르게(또는 가파르게) 증가하는지 보여준다.

Big-Omega 표기:

어떤 양의 상수 c, n₀ 이 존재하여 모든 n >= n₀ 에 대하여
f(n) >= c*g(n)을 만족하면 f(n) = Ω(g(n))이다.

빅오메가 표기법은 알고리즘의 최선의 경우 복잡도를 나타낸다. 즉, 알고리즘이 최소 이만큼의 시간을 필요로 한다는 것을 나타낸다.

Big-Theta 표기:

어떤 양의 상수 c₁, c₂, n₀ 이 존재하여 모든 n >= n₀ 에 대하여
c₁g(n) <= f(n) <= c₂g(n)을 만족하면,
즉 f(n) = Ω(g(n)) = O(g(n))이면 f(n) = Θ(g(n))이다.

빅세타 표기법은 알고리즘의 평균적인 경우, 또는 정확한 복잡도를 나타낸다.
알고리즘의 상한과 하한이 동일할 때 자주 사용된다.

!graph

위 그래프는 Big-O, Big-Omega, Big-Theta 순으로 나열되어 있으며, n₀ 이후의 n값들을 기준으로
항시 그래프 아래, 위, 사이에 f(n)이 위치하는 것을 확인할 수 있다.

Q. 보편적으로 Big-O를 사용하는 이유가 있을까요?
A.

빅오 표기법은 시간 복잡도의 최악의 경우를 입력 크기에 따라 설명하며, 입력 크기가 커질 때 알고리즘 성능의 확장 추세를 간결하게 표현한다.

상수 요소와 하위 차수 항을 무시하며, 알고리즘 실행 시간에 영향을 미치는 주요 요소에 집중함으로
알고리즘이 처리하는 데이터 양의 증가에 따라 효율성이 어떻게 변하는지 이해하는 데에 도움을 준다.

1. 알고리즘 성능 비교: 같은 문제에 대해 여러 다른 알고리즘의 효율성을 비교하기 용이하다. 여러 알고리즘들의 빅오 표기법을 비교하여 대규모 입력 크기에서 더 성능이 좋은 알고리즘을 빠르게 채택할 수 있다.
2. 알고리즘 동작 예측: 입력 데이터가 증가할 때 알고리즘이 어떻게 동작할지를 예측하는 데에 도움을 준다.
3. 코드 최적화: 빅오 표기법에 대한 이해는 코드 최적화에 있어 필수적이다. 복잡한 알고리즘을 식별하여 소프트웨어의 효율성을 높히기 위해 해당 부분을 개선하는데에 집중할 수 있다.
4. 자원 관리: 임베디드 시스템이나 서버 환경과 같은 자원 제한적인 환경에서의 자원 관리에 유용하다. 메모리 사용이나 처리 능력 등에 대해 정보에 입각한 결정을 내릴 수 있다.
5. 문제 해결: 복잡한 문제에 마주쳤을 때 여러 알고리즘의 빅오 시간 복잡도를 안다면 적절한 자료구조와 알고리즘을 채택할 수 있다.

Q. O(1)은 O(n²)보다 무조건 빠른가요?
A.

일반적으로는 맞다. 빅오 표기법은 우선 n이 충분히 클 때를 기준으로 하기 때문이다. 그러나 입력 크기가 매우 작은 경우가 있다면 이에 한해 O(1)이 O(n²)보다 빠를 것이다. 추가적으로, 빅오 표기법은 하위차수 항과 상수항을 무시한다. 만약 O(1)알고리즘의 상수항이 매우 크고, O(n²)의 상수항이 매우 작다면 작은 입력 크기에 한해 O(1)이 더 느릴 것이다.

즉, 일반적인 상황에서는 O(n²)이 느릴 것이지만, 상수 시간과 입력 크기를 모두 고려해야 한다.

정렬 알고리즘

Q. 안정적인 정렬이란 무엇이고, 어떤 알고리즘이 안정적인지 설명해주세요.
A.

안정적인 정렬이란 동일한 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되는 정렬 알고리즘이다.
배열 또는 리스트에서 같은 값을 가지는 요소들이 정렬 후에도 정렬 전의 순서를 유지하면 안정적인 정렬이라고 한다.

예:
정렬 전: [(1, a), (3, c), (4, d), (1, b)] 정렬 후: [(1, a), (1, b), (3, c), (4, d)]

안정적인 정렬 알고리즘으로는 다음이 있다:

• 버블 정렬
• 삽입 정렬
• 병합 정렬

안정적인 정렬은 다음의 이유로 중요하다:

1. 정렬 필드에 의존하는 경우: 데이터 정렬 시 다른 필드에 의해 정렬해야 할 때, 원본 데이터의 상대적인 순서를 유지해야 한다.
2. 안정성 보장: 정렬 과정에서 예상하지 못한 결과를 방지한다.

Q. 셸 정렬에 대해 설명해주세요.
A.

셸 정렬은 삽입 정렬의 단점을 보안하기 위한 정렬 알고리즘이다.
삽입 정렬의 각 단계에서 삽입될 제자리를 찾을 때, 최악의 경우 삽입하고자 하는 데이터가 정렬 부분의 모든 데이터보다 작은 값이라면, 정렬 부분의 오른쪽 끝에서부터 한 번에 하나씩을 비교하여 왼쪽으로 한 칸씩 이동해서 제자리를 찾아가게 되고, 이때 정렬 부분의 데이터가 많을수록 비교와 이동 횟수가 증가하게 된다.

Q. 기수 정렬에 대해 설명해주세요.
A.

기수 정렬은 비교 기반 정렬 알고리즘이 아닌, 비교 없이 정렬하는 알고리즘이다.

Q. 퀵 정렬과 합병 정렬의 비교
A.

퀵 정렬:

• 분할 정복 기법을 기반으로 하며, 피벗을 선택하여 이를 기준으로 배열을 분할한다.
• 피벗을 기준으로 왼쪽 부분배열은 피벗보다 작은 값, 오른쪽 부분배열은 피벗보다 큰 값만을 원소로 가진다.
• 시간 복잡도는 O(n log n)이다.
• 최악의 경우에 시간 복잡도는 O(n²)이다.
• 평균적으로 매우 빠른 알고리즘이다.
• 제자리 정렬임으로 추가적인 메모리 공간이 필요하지 않다.
• 많은 경우에서 합병 정렬보다 빠른 속도를 갖는다.
• 최악의 경우에 매우 느려 성능이 좋지 않다.
• 안정적인 정렬이 아니기 때문에 같은 값을 가진 원소들의 순서가 보장되지 않는다.

합병 정렬:

• 분할 정복 기법을 기반으로 한다.
• 재귀적으로 배열을 반으로 나눈 후 정렬 및 결합하여 정렬된 하나의 배열을 만든다.
• 합병 과정에서 추가적인 메모리 공간이 필요하다.
• 시간 복잡도는 항상 O(n log n)이다.
• 안정적인 정렬임으로 동일한 값의 상대적인 순서가 유지된다.
• 평균적으로는 퀵 정렬보다 느릴 수 있다.

선택 기준:

• 퀵 정렬은 데이터의 임의성이 보장된다면 빠르지만, 최악의 경우에 성능이 급격하게 저하된다.
• 합병 정렬은 안정적이며 일정한 성능을 보장하지만, 추가 메모리 공간을 사용한다.

자료 구조

Q. 연결 리스트를 사용하여 구현할 수 있는 다른 자료구조에 대해 설명해주세요.
A.

스택, 큐, 해시 테이블, 그래프, 트리 모두 연결 리스트를 사용하여 구현할 수 있다.

스택: 연결 리스트의 head 또는 tail을 설정하여 데이터를 해당 끝에서만 삽입 및 삭제함으로 구현 가능하다. 큐: 연결 리스트이 한쪽 끝에서 데이터를 추가하고 반대 쪽 끝에서 삭제하도록 설계하여 구현 가능하다.
그래프: 2차원 배열을 만들어 특정 정점 A에서 간선으로 연결된 정점들을 인덱스 A의 원소로 넣어주면 인접 리스트 형식으로 구현 가능하다.
트리: 트리는 사이클이 없는 무방향 그래프이기 때문에 그래프와 같은 방식으로 구현 가능하다.

Q. 스택 2개로 큐를 만드는 방법
A.

간단하게 생각해보면, 첫 번째 스택에 우선 모든 원소를 관리를 한다.
원소를 삽입할 때는 이 첫 스택에 push연산을 하면 되고,
원소를 삭제할 때는 첫 번째 스택에서 원소를 하나씩 pop하여 두 번째 stack에 순차적으로 push,
가장 마지막으로 두 번째 스택의 top원소를 pop하면 구현이 된다.

간단하게 코드로 표현해보자면 다음과 같다:

class Queue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, item):
        self.stack_in.append(item)
    
    def dequeue(self, item):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if self.stack_out:
            return self.stack_out.pop()

Q. 큐 2개로 스택을 만드는 방법
A.

from collections import deque

class Stack:
    def __init(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, item):
        self.queue1.append(item)

    def pop(self):
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        
        popped_item = self.queue1.popleft()

        self.queue1, self.queue2 = self.queue2, self.queue1
        
        return popped_item

본인이 사용하는 언어에서 해시 충돌을 처리하는 방법은? (Java, JavaScript, C++ …)
A.

균형 이진 탐색 트리

Q. Red Black Tree는 어떻게 균형을 유지할 수 있을까요?
A.

RB 트리는 다섯 개의 주요 규칙이 있다.

1. 모든 노드는 빨간색 또는 검정색 노드이다.
2. 루트 노드는 검정색이다.
3. 모든 리프 노드들은 검정색이다.
4. 빨간색 노드의 자식은 검정색이다.
5. 루트 노드에서 리프 노드까지 거쳐가는 검정색 노드의 개수는 모든 리프 노드에 대해서 동일해야 한다.

RB트리는 위 다섯 가지 규칙을 지키기 위해 회전을 하며, 이로 인해 트리의 균형이 유지된다.
무조건적으로 완벽한 균형을 유지하지는 않지만, 이로 인해 오히려 연산량이 줄어들고 성능이 AVL트리와 같은 트리보다 좋다.

Q. 2-3-4트리, AVL트리 등이 있지만, 왜 Red Black Tree가 가장 많이 사용되나요?
A.

AVL트리는 보다 엄격한 균형을 맞추기 때문에 연산량이 많으며, 이는 필연적으로 성능 저하를 불러온다.
Red Black 트리는 이에 비해 균형을 맞추는 정도는 덜 엄격하지만, 오히려 이 때문에 성능적으로 우열을 갖는다.

RB트리가 타 트리 구조들보다 많이 사용되는 데에는 다음의 이유들이 있다:

1. 균형 잡힌 트리 구조
2. 상대적으로 간단한 구현
3. 널리 알려진 사용성
4. 적절한 성능
5. 다양한 응용 가능성

문제 풀이

K번째 수

import sys

input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

A.sort()

print(A[K-1])

버블 소트

import sys
input = sys.stdin.readline

N = int(input())
A = [(int(input()), i) for i in range(N)]

prime = sorted(A)
result = []

for j in range(N):
    result.append(prime[j][1]- A[j][1])

print(max(result) + 1)

예산

import sys

N = int(input())
area = list(map(int, sys.stdin.readline().split())) 
M = int(input())

low = 0
high = max(area)
mid = (low + high)//2

ans = 0 

def is_possible(mid):
    return sum(min(a, mid) for a in area) <= M

while low <= high:
    if is_possible(mid):
        low = mid + 1
        ans = mid
    else:
        high = mid - 1

    mid = (low + high)//2


print(ans)

기타 레슨

n, m = map(int,input().split())
time = list(map(int,input().split()))

start = max(time)
end = sum(time)

while start <= end:
    mid = (start + end) // 2 

    total = 0
    count = 1
    for t in time:
        if total + t > mid:
            count += 1
            total = 0
        total += t 

    if count <= m:
        ans = mid
        end = mid - 1
    else:
        start = mid + 1
    
print(ans)

---

스터디 후기

보람찬 스터디였다. 내가 공부했던 내용을 누군가에게 말을 한다는 부분에서부터 이미 내 원래 목적은 이루었다고 생각하는데,
이에 더해 스터디원들의 의견 또한 수렴할 수 있어 알찬 시간이었다고 생각한다.

추가적으로, 문제 ‘K번째 수’가 파이썬으로는 너무나도 구현하기 쉬워 sort()를 사용하지 않고 해결해보기로 했고,
연결 리스트를 사용하여 스택, 큐, 그래프를 구현해보기로 했다.