서린이의 기술 블로그

시간 복잡도

• 시간 복잡도란?
  • 반에 있는 사람들이 N명이라고 한다면B 방식은 N^2 만큼의 연산이 필요하다고 할게요.
• 💡 시간복잡도는 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!
  • 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.
  • 우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
  • N 이 예를 들어서 30이라면 A 방식은 30번, B 방식은 900 번의 연산이 필요하겠죠
  • A 방식은 N 번 만큼의 연산이 필요하고
  • 예를 들어서 내가 반에 있는 사람들 중에서 가장 이성에게 호감이 높은 사람을 뽑는다고 해볼게요.

“입력값에 비해 얼마나 일을 수행해야 하는가?”

• 1) 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
  • 첫 번째 방법
    • 이 해결 방법은 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인합니다. 만약 다른 모든 값보다 크다면 반복문을 중단합니다.
    • 이 함수가 시간이 얼마나 걸리는지 어떻게 분석할 수 있을까요?
    • 바로, 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하시면 됩니다. 아래와 같이 계산할 수 있습니다.
    • 위에서 연산된 것들을 더해보면
      • N * N * 2
    • array의 길이 X 비교 연산 1번
      • N
    • 그러면 우리는 이제 이 함수는 2* N^2 + N 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
    • Q. 선생님 여기서 입력값이 뭔가요?
      • A. 함수에서 크기가 변경될 수 있는 값이라고 보시면 됩니다! 배열을 받고 있으니 이 함수에서는 배열이 입력값입니다.
    • Q. 선생님 그러면 여기서 N 이 6이니까, 78이라고 말하면 안되나요?
      • A. N 의 크기에 따른 시간의 상관관계를 시간복잡도라고 하는 것이라 수식으로 표현하셔야 합니다!

def find_max_num(array):
    for number in array:
        is_max_num = True
        for compare_number in array:
            if number < compare_number:
                is_max_num = False
        if is_max_num:
            return number

print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• 2) 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
  • 두 번째 방법

for number in array:                 # array 의 길이만큼 아래 연산이 실행
    for compare_number in array:     # array 의 길이만큼 아래 연산이 실행
        if number < compare_number:  # 비교 연산 1번 실행
            is_max_num = False       # 대입 연산 1번 실행
    if is_max_num:                   # 비교 연산 1번 실행
        return number

공간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다!
  • 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이죠.
  • 우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
  • 저장하는 데이터 양이 1개의 공간을 사용한다고 계산, 예 ) 리스트에서 원소 갯수가 공간의 갯수

alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

def find_max_occurred_alphabet(string):
    max_occurrence = 0 # 1개의 공간을 사용
    max_alphabet = alphabet_array[0] # 1개의 공간을 사용

    for alphabet in alphabet_array:
        occurrence = 0 # 1개의 공간을 사용

## 26 + 3의 공간을 사용

alphabet_occurrence_list = [0] * 26 # 26개의 공간을 사용

for char in string:
    if not char.isalpha():
        continue
    arr_index = ord(char) - ord('a') # 1개의 공간을 사용
    alphabet_occurrence_list[arr_index] += 1

max_occurrence = 0 # 1개의 공간을 사용
max_alphabet_index = 0 # 1개의 공간을 사용

for index in range(26):
    alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용
    if alphabet_occurrence > max_occurrence:
        max_occurrence = alphabet_occurrence # 1개의 공간을 사용
        max_alphabet_index = index # 1개의 공간을 사용

• 29나 30처럼 N과 상관이 없으면 공간복잡도는 성능에 영향을 주지 않는다. = 단순 대입연산만 늘어났으니
• 단 N에 따라서 공간복잡도가 기하급수적으로 늘어나면 고려해봄직하다.

출처 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘

컴퓨터는 숫자밖에 저장하지 못하기에, ASCII 코드 개념이 등장

• ASCII (American Standard Code for Information Interchange) : 7비트를 사용하고, 암호화되지 않은 키로코드를 사용

문자 : ASCII 코드 예시

• A : 65, a : 97

문자('a')-> ASCII 코드로 변환

• print(ord('a'))
• ASCII 코드(97) -> 문자로 변환

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        if not char.isalpha():
            continue arr_index = char - ord('a')
        alphabet_occurrence_array[arr_index] += 1
    return alphabet_occurrence_array

아스키/문자 변환 함수를 이용한 풀이

• ord('char') / chr(num)

# 최빈값 중, 사전순으로 가장 첫번 째 값을 찾기

s = "hello my name is dingcodingco"

def find_alphabet_occurrence_array(string):

# 알파벳 갯수만큼 배열을 생성
alphabet_occurrence_array = [0] * 26

for char in string:

    # 알파벳이 아니면 continue 처리
    if not char.isalpha():
        continue

    # a의 아스키 코드 값을 빼서 arr_index를 구함
    arr_index = ord(char) - ord('a')

    # 인덱스에 해당하는 값을 1 만큼 증가
    alphabet_occurrence_array[arr_index] += 1

    # 최대값인 것들 중 맨 처음 값(키값)을 취하고 아스키 코드 값을 더한다.
max_index = [k for k, v in enumerate(alphabet_occurrence_array) if v == max(alphabet_occurrence_array)][0] + ord('a')

    # 아스키 코드를 문자로 변환
return chr(max_index)

print(find_alphabet_occurrence_array(s))

# 최빈값을 모두 찾기

s = "hello my name is dingcodingco"

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    # 최빈값을 모두 구하여 딕셔너리에 담는다.
    max_list = {chr(k + ord('a')) : v for k, v in enumerate(alphabet_occurrence_array) if v == max(alphabet_occurrence_array)}

    # 딕셔너리에 담긴 키(v)와 v에 해당하는 값을 찾는다.
    for k, v in enumerate(max_list):
        print(f'{v} : {max_list[v]}')

find_alphabet_occurrence_array(s)

출처 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘

# 알고리즘과 친해지기

# 1. 최대값 찾기
array = [3,5,6,1,10,4]
max = 0
def find_max_num(array):
    for num in array:
        for compare_number in array:
            if num < compare_number:
                max = compare_number
    return max
        
print(f'최대값은 {find_max_num(array)}입니다.') # formatted string, 변수는 {}로 출력

# 위 알고리즘은 시간복잡도가 O(n^2)

def find_max_num2(array):
    max = array[0]
    for num in array:
        if num > max:
            max = num
    return max

print(f'최대값은 {find_max_num2(array)}입니다.')

# 위 알고리즘은 시간복잡도가 O(n)

# 알고리즘 문제풀이의 목표 중 하나는
# 같은 문제라도 시간복잡도가 더 작은 알고리즘을 찾아야한다.

출처 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘

1. 완탐과 원복

첫번째 최종 탐색 후, 계속 원복을 하면서 탐색 가능한 모든 경우의 수를 구한다.

2. 인접 노드

3. 탐색 순서 :

0 -> 1 -> 2 (첫번째 탐색 끝)

  > 2번을 pop() 및 방문 미처리하여 원복 : 0 -> 1

  > 1번으로 가서 인접노드 3을 방문 : 0 -> 1 -> 3

  > 3번을 pop() 및 방문 미처리하여 원복 : 0 -> 1

  > 2와 3을 모두 탐색했으니 1도 pop() 및 방문 미처리하여 원복 : 0

4. 소스 코드

# 완전탐색
# 완탐과 원복
# 원복의 필요성 : 상태값이 그 다음 경우의 수에 반영되지 않도록 하기 위함

# 1. 인접 노드 방향 벡터
# 0 <-> 1 <-> 2
#         <-> 3

# 2. 3개의 정점을 탐색하면 print3 하라!

# 3. 방문한 정점은 다시 방문하지 않는다.


import sys
input = sys.stdin.readline

visited = [0] * 4
adj = [[] for _ in range(4)]
v = []

def print3():
    for i in v:
        print(chr(ord("A") + i), end=' ')
    print("\n")

def go(idx):
    if len(v) == 3:
        print3()
        return # 여기서 끝난다는 뜻.
    for there in adj[idx]:
        if visited[there] == 1:
            continue
        visited[there] = 1
        v.append(there) # [0, 1, 2] -> [0, 1, 3]
        print("push_back :: there : " + str(there))
        for i in v:
            print(i, end=' ')
        print("\n")
        go(there)
        visited[there] = 0
        v.pop()
        print("pop_back :: there : " + str(there))
        for i in v:
            print(i, end=' ')
        print("\n")

adj[0].append(1)
adj[1].append(0)

adj[1].append(2)
adj[2].append(1)

adj[1].append(3)
adj[3].append(1)

visited[0] = 1 # 맨처음 0을 방문처리
v.append(0)
go(0)

5. 두번 째 문제

# 긍정왕 홍철이의 구걸 여행
# 홍철이는 3 * 3 맵에서 {0, 0} 지점에서 길을 잃어버렸다. 긍정왕 홍철이는 길을 잃어버린 김에 구걸을 하면서 돈을 모으며 여행을 가려고 한다.
# 목적지는 {2, 2}이며 방문한 정점은 다시 방문할 수 없고, 해당 맵에 구걸로 얻을 수 있는 돈들이 있다. 홍철이는 4방향(상하좌우)로 움직일 수 있다.
# {2, 2}까지 간다고 했을 때, 이 돈들을 모으는 모든 경우의 수를 출력하여라

# 맵
# {10, 20, 21},
# {70, 90, 12},
# {80, 110, 120}

6. 탐색 순서

10 20 21 12 120

  > 120 원복 및 90 -> 110 -> 120 탐색

  > 10 20 21 12 90 110 120

  > 120, 110 원복 및 70 -> 80 -> 110 -> 120 탐색

  > 10 20 21 12 90 70 80 110 120

  > 반복 ..

7. 소스 코드

import sys
input = sys.stdin.readline

n = 3
a = [
    [10, 20, 21],
    [70, 90, 12],
    [80, 110, 120]
]
visited = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
v = []

def print_result():
    for i in v:
        print(i, end=' ')
    print()

def go(y, x):
    if y == n - 1 and x == n - 1:
        print_result()
        return
    for i in range(0, 4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or nx < 0 or ny >= n or nx >= n:
            continue
        if visited[ny][nx] == 1:
            continue
        visited[ny][nx] = 1
        v.append(a[ny][nx])
        go(ny, nx)
        visited[ny][nx] = 0 # 원복
        v.pop()

visited[0][0] = 1
v.append(a[0][0])
go(0, 0)

8. 결과 값, 모든 경우의 수 12가지

10 20 21 12 120 
10 20 21 12 90 110 120
10 20 21 12 90 70 80 110 120
10 20 90 12 120
10 20 90 110 120
10 20 90 70 80 110 120
10 70 90 20 21 12 120
10 70 90 12 120
10 70 90 110 120
10 70 80 110 90 20 21 12 120
10 70 80 110 90 12 120
10 70 80 110 120

출처 : 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 | 큰돌

1. 재귀를 활용한 완전탐색 문제 2개

2. 백트래킹(=가지치기)를 활용한 완전탐색 문제 1

출처 : 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 | 큰돌

1. 완전 탐색 : 순열, 조합 등을 포함하여 모든 경우의 수를 고려하는 방법

  - 1억 미만 : 완전 탐색

  - 1억 이상 : 완전 탐색이 가능 or 불가능

2. 반복문을 활용한 완전 탐색

  - 문제

랄로의 수

BJ랄로는 2400이라는 숫자를 좋아한다. 그래서 2400이 포함된 숫자를 보면 "랄로!"를 외치기에, 2400이 포함 된 수를 랄로의 수라고 한다. 첫번 째 랄로의 수는 2400이고, 두번 째 랄로의 수는 12400이며, 세번 째 랄로의 수는 22400이다.

이때, N번 째, 랄로의 수는 몇인가?

# 입력

# 200

# 출력

# 492400

  - for loop 풀이

import sys
input = sys.stdin.readline

INF = 1000000
cnt = 0

n = int(input())

for i in range(2400, INF):
    if "2400" in str(i):
        cnt += 1
        if n == cnt:
            print(i)
            break

  - while loop 풀이

import sys
input = sys.stdin.readline

INF = 1000000
cnt = 0
i = 2400

n = int(input())

while True:
    if "2400" in str(i):
        cnt += 1
        if n == cnt:
            print(i)
            break
    i += 1

출처 : 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

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

1. 메인 아이디어

  - 조건 그대로 조건문 로직을 만든다.

  - dictionary를 활용하여 max_number, max_count로도 문제풀이가 가능하다

- 단순 구현법

import sys
input = sys.stdin.readline

a, b, c = map(int, input().split())

if a == b == c:
    print(10000 + a * 1000)
elif (a == b != c) or (b == c != a):
    print(1000 + b * 100)
elif a == c != b:
    print(1000 + a * 100)
else:
    print(max(a,b,c) * 100)

- 딕셔너리를 이용한 방법

import sys
input = sys.stdin.readline

a, b, c = map(int, input().split())

# 주사위 숫자의 개수를 센다
count = {a: 0, b: 0, c: 0}
count[a] += 1
count[b] += 1
count[c] += 1

# 가장 많이 나온 숫자와 그 개수 찾기
max_num = max(count, key=lambda x: count[x])
max_count = count[max_num]

if max_count == 3:
    prize = 10000 + max_num * 1000
elif max_count == 2:
    prize = 1000 + max_num * 100
else:
    prize = max(a, b, c) * 100

print(prize)

1. 메인 아이디어

  - m을 60으로 나눈 몫을 시간에 더함

  - t에 다시 t를 24로 나눈 나머지로 대입 (24시간 형식 맞추도록)

  - m을 60으로 나눈 나머지가 분

import sys
input = sys.stdin.readline

t, m = map(int, input().split())
m2 = int(input())

m += m2

t += m // 60
t %= 24
m %= 60

print(t, m)

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

1. 메인 아이디어

  - prev를 도입하여 이전 숫자/단어가 알파벳인지 아닌지 검증한다.

  - 알파벳이 아닐 경우 무조건 str += w로 담고본다.

  - 알파벳 -> 숫자가 나오는 시점에는 str += w를 더한다.

  - 숫자 -> 알파벳이 나오는 시점에는 digits 리스트에 str을 int형으로 담고, str을 ''로 초기화한다.

    > digits 리스트에 str을 담을 때, str이 애초에 ''이 아닌지도 검증이 필요하다 (if str != '' and str_lstrip != '':)

    > str 검증을 하지않으면 '' 빈 공백이 digits에 담기기 때문임

  - digits 리스트의 오름차순으로 정렬한 후, print한다.

    > digits 리스트의 원소 타입이 '' 스트링 타입이면, 숫자 크기가아닌 사전순 정렬이 되므로 주의한다.

       > ex:) 0 2 2 4 23223 5 (X) -> 0 2 2 4 5 23223 (O)

  - 안쪽 for 문이 끝나면 ( for w in s: ) input_digit_or_zero 함수를 한번더 호출한다

    > 왜냐면, ... 002 이런식으로 문장이 끝나면 2를 담지 못하기 때문에 한번 더 담아줘야함

2. 소스 코드

import sys
input = sys.stdin.readline

alphabet = 'abcdefghijklmnopqrstuvwxyz'


n = int(input())
lines = []
digits = []
for _ in range(n):
    lines.append(input().strip())

def input_digit_or_zero(str):
    str_zero = str.lstrip('0')
    if str != '':
        if str_zero == '':
            digits.append(0)
        else:
            digits.append(int(str_zero))

for s in lines:
    str = ''
    prev = -1

    for w in s:
        if prev == -1:
            if w not in alphabet:
                str += w
        else:
            if w not in alphabet:
                str += w
            elif prev not in alphabet and w in alphabet:
                input_digit_or_zero(str)
                str = ''
            elif prev in alphabet and w not in alphabet:
                str += w
        prev = w
    input_digit_or_zero(str)
        
for i in sorted(digits):
    print(i)

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

1. 메인 아이디어

  - 각 원소에 대해 [빈도, 순번]을 정렬할 자료구조를 생각한다 -> dictionary가 적합

  - dictionary를 key=lambda(=익명함수)를 기준으로 정렬한다

    > -x[1][0] = 각 원소의 빈도를 우선으로 내림차순

    > x[1][1] = 각 원소의 순번을 그 다음으로 오름차순

  - result에 정렬된 dictionary를 원소 * 빈도로 extend한다 ( dictionary 내부 원소는 list 이므로 extend 써야함)

    > result = [], extend ([2,3], [1,2] ..) => result = [2, 2, 2, 1, 1]

2. 소스 코드

# 백준 2910 빈도 정렬
# 수열은 N개로 이루어져 있고 숫자는 모두 C보다 작거나 같다
# 수열 내에 두 수 X와 Y가 있을 때 X가 더 앞에 있어야 함
# 메시지의 길이 N과 C가 주어진다 

# 5 2
# 2 1 2 1 2
import sys
input = sys.stdin.readline

# 입력 받기
n, c = map(int, input().split())
seq = list(map(int, input().split()))

# 빈도와 첫 번째 인덱스를 저장할 딕셔너리
count = {}
for idx, num in enumerate(seq):
    if num in count:
        count[num][0] += 1  # 빈도 증가
    else:
        count[num] = [1, idx]  # 빈도와 첫 등장 인덱스 저장

# 빈도와 인덱스를 기반으로 정렬
sorted_numbers = sorted(count.items(), key=lambda x: (-x[1][0], x[1][1])) # -x[1][0] 은 빈도를 기준으로 내림차순, x[1][1] 순서를 기준으로 오름차순
# x[1]은 count[num] -> ex:) [3, 0]
# x[1][0]은 특정 숫자의 빈도를 의미

# 결과 리스트 생성
result = []
for num, (freq, _) in sorted_numbers:
    result.extend([num] * freq)  # 각 숫자를 빈도만큼 추가

# 결과 출력
print(*result)