알고리즘이란?

어떠한 문제를 해결하기 위해 정해진 일련의 절차. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉 문제 풀이에 필요한 계산 절차 또는 처리과정의 순서를 뜻한다. 프로그램 명령어의 집합을 의미하기도 한다.

점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법이다.

빅오(big-O) 표기법

최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지 표기.

빅오메가(big-Ω) 표기법

최선의 성능이 나올 때 어느 정도의 연산량이 걸릴지 표기.

시공간 복잡도

시간 복잡도란?

입력값과 문제를 해결하는 데 걸리는 시간과 상관관계를 말한다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것.

공간 복잡도란?

입력값과 문제를 해결하는 데 걸리는 공간과 상관관계를 말한다.

** for문을 여러개 쓰면 거기에 비례해서 시간 복잡도가 기하급속적으로 증가한다.(알고리즘 문제를 풀때 for문이 2개 이상이면 나의 풀이를 의심을 해봐라!!!)

문제

설탕 배달

https://www.acmicpc.net/problem/2839

def sugar(N):
    
    if N < 3:
        return -1
    
    if N % 5 == 0:
        return N // 5
   
    for i in range(N // 5, -1, -1):
        a = N - (i * 5)
        if a % 3 == 0:
            return i + (a // 3)
            
    	return -1
# 오답

베르트랑 공준

https://www.acmicpc.net/problem/4948

import math

def is_prime_num(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def sosu(n):
    a = []
    for i in range(n+1, (2*n)+1):
        if is_prime_num(i) == True:
            a.append(i)
    return len(a)
# 오답

달팽이는 올라가고 싶다

https://www.acmicpc.net/problem/2869

def dal(A, B, V):
    today = 0
    dis = 0
    while dis <= V:
        dis += A
        today += 1
        if dis < V:
            dis -= B
        else:
            return today
# 오답

ACM 호텔

https://www.acmicpc.net/problem/10250

def hotel(H, W, N):
    a = []
    for i in range(1, W+1):
        for j in range(1, H+1):
            if i < 10:
                a.append(int(str(j)+'0'+str(i)))
            else:
                 a.append(int(str(j)+str(i)))
    return a[N-1]
# 오답

소수 구하기

https://www.acmicpc.net/problem/1929

import math

def is_prime_num(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def sosu(M, N):
    for i in range(M, N+1):
        if is_prime_num(i) == True:
            print(i)
# 오답            

마치며

오늘부터 캠프 워밍업 기간이다. 첫날로 알고리즘 문제를 풀게 되었는데 전혀 모르겠다. 혼자 VS코드에서는 실행값이 나오는 것 같았는데 답안제출 하니 죄다 오답이 나왔다. 혼자 뭐가 틀렸는지 계속 끙끙되었지만 결국 답을 알지 못했다. 몇시간 동안 이것만 보닌까 머리가 점점 더 복잡해지는 것 같다. 내일은 수정할 수을까?...