스파르타코딩클럽 알고리즘 강의

알고리즘이란?

시간 복잡도(연산횟수)와 공간 복잡도(메모리)를 효율적으로 관리하여 문제를 해결하는 것.

• 시간 복잡도: 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계. 입력값이 늘어났을 때 문제를 해결하는 데 걸리는 시간은 얼마나 더 늘어나는 지 확인하는 것.
• 공간 복잡도: 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계. 입력값이 늘어났을 때 문제를 해결하는 데 걸리는 공간은 얼마나 더 늘어나는 지 확인하는 것.

점근 표기법

• 빅오(Big-O) 표기법: 최악의 성능이 나올 때의 연산량
• 빅오메가(Big-Ω) 표기법: 최선의 성능이 나올 때의 연산량
  당연히 빅오메가는 아예 안씀. 최악의 경우를 개선시키는 것이 중요하기 때문이다.

보통 반복문의 갯수가 O(n)에서 n의 제곱이 된다.

• 예시) 2중 반복문 => O(n^2)

따라서 반복문의 무분별한 사용은 줄이는게 좋다.

연결리스트

배열 vs. 연결리스트

배열

• 길이가 정해져있음. 길이를 초과하면 재설정.
• 장점: 접근 쉬움 O(1)
• 단점: 삽입 어려움 O(n)

데이터의 접근이 잦은 경우 사용.

연결리스트

• 가변 길이.
• 장점: 삽입 쉬움 O(1)
• 단점: 접근 어려움 O(n)

데이터의 삽입과 삭제가 잦은 경우 사용.

실습

알파벳 찾기

s = input()

list = [-1]*26

i = 0
for l in s:
    if l.islower():
        if list[ord(l) - 97] == -1:
            list[ord(l) - 97] = i
    i += 1

for l in list:
    print(l, end = " ")

116ms -> 통과

연결 리스트 구현

class ListNode:
    def __init__(self, val, next):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next
        node.next = ListNode(val, None)

    def remove(self, val):
        node = self.head
        if node.val == val:
            self.head.next = node.next
            del (node)
            return
        while node.next:
            prev = self.head
            curr = prev.next
            if curr.val == val:
                prev.next = curr.next
                del (curr)
                return

    def print(self):
        node = self.head
        while node:
            print(node.val, end=' ')
            node = node.next

• !확인 필요!

페어 프로그래밍

문제풀이

1. 더하기 사이클

별로 코멘트할 게 없을 정도로 간단한 문제였다.

전체 코드

num = int(input())
count = 0
temp = num

while True:
    a = temp // 10
    b = temp % 10
    temp = b * 10 + (a + b) % 10
    count += 1
    if temp == num:
        break

print(count)

2. Fly me to the Alpha Centauri

오늘 풀었던 문제 중에 가장 어렵고 복잡했던 문제다.

2시간 정도 머리를 쥐어짜보았지만 진전이 아예 없어서 구글링을 통해 알게 된 규칙이다.
그림의 맨 오른 쪽에 적혀있는 반복 횟수를 구하는 부분이 핵심이다. 표를 보면 n(반복 횟수)과 d(총 이동해야 하는 거리) 간의 관계를 쉽게 이해할 수 있다.

n을 구하는 방법: n을 1부터 시작해서 d가 n^2+n보다 작을 때 까지 n 증가.
예) d가 3~6인 경우 n은 2가 된다.

n을 구했다면 다음으로는 d와 n의 관계를 이해해야 한다.

if d <= n ** 2:
    print(n * 2 - 1)
else:
    print(n * 2)

1. d가 n제곱과 같거나 작음: count = 2n - 1
2. d가 n제곱보다 큼: count = 2n

예시1) d = 4, n = 2, n제곱 = 4 --> d <= n^2

• 1번 조건: 3(2n-1).
  예시2) d = 5, n = 2, n제곱 = 4 --> d > n^2
• 2번 조건: 4(2n).

전체 코드

T = int(input())
for i in range(T):
    s, d = map(int, input().split())
    d -= s
    n = 1
    count = 0

    while d > n ** 2 + n:
        n += 1
    if d <= n ** 2:
        print(n * 2 - 1)
    else:
        print(n * 2)

3. 터렛

위의 문제 때문에 겁이 났지만 풀고 보니 수학만 조금 안다면 금방 풀 수 있는 문제이다. (물론 난 수학을 모르기 때문에 구글의 힘을 빌렸다).

중심거리와 두 원의 위치 관계

반지름의 길이가 r1인 원과 r2인 원의 중심거리를 d라고 할 때, |r1 - r2| 또는 r1 + r2와의 크기를 비교하면, 두 원의 위치 관계를 알 수 있다.

r1 + r2 < d 이면 두 원은 서로의 외부에 위치한다.
r1 + r2 = d 이면 두 원은 외접한다.
|r1 - r2| < d < r1 + r2 이면 두 원은 서로 다른 두 점에서 만난다.
|r1 - r2| = d 이면 한 원이 다른 원에 내접한다.
|r1 - r2| > d, r1 ≠ r2 이면 한 원이 다른 원의 내부에 있다.

즉, 각 점(x,y)에서 반지름(r)으로 원을 그렸을 때:
1. 두 원이 내접/외접: 1개
2. 서로 다른 두 점에서 만남: 2개
3. 동일한 점과 반지름: -1개(무한대)
4. 서로의 외부에 위치 또는 한 원이 다른 원의 내부에 위치: 0개

d는 get_dist_between_points 함수를 만들어 구했다.
그러고 난 뒤 교차점은 위에 나와있는 조건들로 구했다.

전체 코드

import sys

def get_dist_between_points(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5

T = int(sys.stdin.readline())
for i in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, sys.stdin.readline().split())

    d = get_dist_between_points(x1, y1, x2, y2)

    if x1 == x2 and y1 == y2 and r1 == r2:
        print(-1)

    # 1. 서로의 외부에 위치, 혹은 한 원이 다른 원의 내부에 위치
    elif r1 + r2 < d or (abs(r1 - r2) > d and r1 != r2):
        print(0)
    
    # 2. 외접 혹은 내접
    elif r1 + r2 == d or abs(r1 - r2) == d:
        print(1)
    
    # 3. 서로 다른 두 점에서 만남
    elif abs(r1 - r2) < d < (r1 + r2):
        print(2)
    
    else:
        print(-1)

4. 스택

무난한 문제였으나 시간 초과로 통과하지 못했다.
파이썬이 array를 list의 타입으로 사용하기 때문에 push/pop/top/size 등 배열 길이를 구할 때 문제가 있는 것인 줄 알았지만 의외로 input() 함수를 사용해서 생긴 문제였다.

input() vs. sys.stdin.readline()

• input(): 내장 함수. 프롬트 메시지를 매개변수로 받을 수 있다. 그렇기 때문에 입력을 받기 전 프롬트 메시지를 출력해야 한다. 또한, 입력받은 값의 개행 문자를 삭제한 후 반환한다.
• sys.stdin.readline(): sys 라이브러리 함수. input()과는 다르게 프롬트 메시지도 받지 않고 개행 문자를 삭제하지도 않는다. 따라서 처리과정이 더 빠르다.

전체 코드

import sys

N = int(sys.stdin.readline())

stack = []

for i in range(N):
    T = sys.stdin.readline().split()
    if T[0] == 'pop':
        print(-1 if len(stack) == 0 else stack.pop())
    elif T[0] == 'size':
        print(len(stack))
    elif T[0] == 'empty':
        print(1 if len(stack) == 0 else 0)
    elif T[0] == 'top':
        print(stack[-1] if len(stack) != 0 else -1)
    else:
        stack.append(T[1])

5. 제로

4번 스택 문제의 응용 문제다.

전체 코드

import sys

K = int(sys.stdin.readline())
stack = []

for i in range(K):
    T = int(sys.stdin.readline())
    if T != 0:
        stack.append(T)
    elif T == 0:
        stack.pop()

print(sum(stack))

6. 큐2

스택과 마찬가지로 list로 구현했다.
스택과 큐 자료구조의 기본 개념을 알고 있어서 금방 구현했다.
하지만 우려했듯이 pop 명령을 실행할 때 배열의 길이가 아주 큰 경우 [0]값을 삭제하게 되면 [1]부터 [N-1]까지 한 칸씩 앞으로 땡겨야 하기 때문에 이 부분에서 시간이 초과되었다.

list로는 절대 구현하지 못할 거라고 금방 확신했다.
구글링을 통해 deque이라는 자료구조가 생각이 났고 이를 활용하니 바로 해결이 되었다.

전체 코드

import sys
from collections import deque

N = int(sys.stdin.readline())

queue = deque([])

for i in range(N):
    T = sys.stdin.readline().split()
    if T[0] == 'pop':
        print(-1 if len(queue) == 0 else queue.popleft())
    elif T[0] == 'size':
        print(len(queue))
    elif T[0] == 'empty':
        print(1 if len(queue) == 0 else 0)
    elif T[0] == 'back':
        print(queue[-1] if len(queue) != 0 else -1)
    elif T[0] == 'front':
        print(queue[0] if len(queue) != 0 else -1)
    else:
        queue.append(T[1])