파이썬 알고리즘
시험 범위 총정리

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin   # 해당 화폐로 거슬러 줄 수 있는 동전 개수
    n %= coin            # 남은 금액

print(count)

500×2 → 260
100×2 → 60
50×1  → 10
10×1  → 0

6

n, k = map(int, input().split())
result = 0

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

25 5

2      (25 → 5 → 1)

n, k = map(int, input().split())
result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 한 번에 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

17 4

3      (17 → 16 → 4 → 1)

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0   # 총 그룹의 수
count = 0    # 현재 그룹에 포함된 모험가의 수

for i in data:        # 공포도를 낮은 것부터 하나씩 확인하며
    count += 1        # 현재 그룹에 해당 모험가를 포함시키기
    if count >= i:    # 인원 수 ≥ 현재 공포도 → 그룹 결성
        result += 1
        count = 0

print(result)

5
2 3 1 2 2

2      ([1] / [2,2] — 남은 2,3은 그룹 불가)

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

02984

576    ((((0+2)×9)×8)×4)

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2
for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

x = 행(세로), y = 열(가로)

2 3
1 2
2 1
3 2

n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

5
R R R U D D

3 4

h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

5

11475

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1),
         (2, 1), (1, 2), (-1, 2), (-2, 1)]

result = 0
for step in steps:
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if 1 <= next_row <= 8 and 1 <= next_column <= 8:
        result += 1

print(result)

a1

2      (c2 입력 시 6)

data = input()
result = []
value = 0
has_number = False

for x in data:
    if x.isalpha():        # 알파벳인 경우 결과 리스트에 삽입
        result.append(x)
    else:                  # 숫자는 따로 더하기
        value += int(x)
        has_number = True

result.sort()              # 알파벳을 오름차순으로 정렬

# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if has_number:
    result.append(str(value))

print(''.join(result))     # 리스트를 문자열로 변환하여 출력

K1KA5CB7

ABCKK13

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1])  # 최상단 원소부터 출력
print(stack)        # 최하단 원소부터 출력

7, 4

[1, 3, 2, 5]
[5, 2, 3, 1]

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)      # 먼저 들어온 순서대로 출력
queue.reverse()   # 역순으로 바꾸기
print(queue)      # 나중에 들어온 원소부터 출력

5, 2

deque([3, 7, 1, 4])
deque([4, 1, 7, 3])

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:        # 종료 조건: n이 1 이하인 경우 1을 반환 (0! = 1)
        return 1
    return n * factorial_recursive(n - 1)   # n! = n × (n-1)!

print(factorial_iterative(5))
print(factorial_recursive(5))

n! = n × (n−1)!

120
120

# A를 B로 나눈 나머지를 R이라 하면, GCD(A, B) = GCD(B, R)
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

print(gcd(192, 162))

(192,162) → (162,30) → (30,12) → (12,6)

6

graph = [
    [],          # 0번 노드는 사용하지 않음
    [2, 3, 8],   # 1
    [1, 7],      # 2
    [1, 4, 5],   # 3
    [3, 5],      # 4
    [3, 4],      # 5
    [7],         # 6
    [2, 6, 8],   # 7
    [1, 7]       # 8
]
visited = [False] * 9

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

dfs(graph, 1, visited)

스택 (재귀 호출 스택)

1 2 7 6 8 3 4 5

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

visited = [False] * 9
bfs(graph, 1, visited)

큐 (deque)

1 2 3 8 7 4 5 6

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        graph[x][y] = 1      # 해당 노드 방문 처리
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:  # 현재 위치에서 DFS 수행
            result += 1

print(result)

4 5
00110
00011
11111
00000

3

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

print(bfs(0, 0))

5 6
101010
111111
000001
111111
111111

10

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i   # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]  # 스와프

print(array)

9+8+…+1 = 45 = N(N−1)/2

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):          # 인덱스 i부터 1까지 감소하며 반복
        if array[j] < array[j - 1]:    # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else:                          # 자기보다 작은 데이터를 만나면 멈춤
            break

print(array)

첫 원소는 이미 정렬된 것으로 보고
i = 1부터 시작

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:   # 원소가 1개인 경우 종료
        return
    pivot = start      # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:   # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:              # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

[1, 4, 2, 0, 3, 5, 6, 9, 7, 8]
 ← 5보다 작음 | 5 | 5보다 큼 →

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0]   # 피벗은 첫 번째 원소
    tail = array[1:]   # 피벗을 제외한 리스트
    left_side = [x for x in tail if x <= pivot]   # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]   # 분할된 오른쪽 부분
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

코드는 짧지만 매번 새 리스트를 만들고
tail을 두 번 순회 → 시간·공간 더 사용

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1   # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)):      # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ')        # 등장한 횟수만큼 인덱스 출력

idx: 0 1 2 3 4 5 6 7 8 9
cnt: 2 2 2 1 1 2 1 1 1 2

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()               # 배열 A는 오름차순 정렬
b.sort(reverse=True)   # 배열 B는 내림차순 정렬

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    if a[i] < b[i]:    # A의 원소가 B의 원소보다 작은 경우 교체
        a[i], b[i] = b[i], a[i]
    else:              # 크거나 같으면 더 바꿀 이유가 없으므로 탈출
        break

print(sum(a))

5 3
1 2 5 4 3
5 5 6 6 5

26     (A = [6, 6, 5, 4, 5])

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

10 7
1 3 5 7 9 11 13 15 17 19

4      (7은 4번째 원소)

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

[0,9] mid=4 → 9 > 7, 왼쪽
[0,3] mid=1 → 3 < 7, 오른쪽
[2,3] mid=2 → 5 < 7, 오른쪽
[3,3] mid=3 → 7 찾음!

3 (인덱스)

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡의 양 계산
        if x > mid:
            total += x - mid
    # 떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
    else:
        result = mid   # 최대한 덜 잘랐을 때가 정답이므로 여기에서 기록
        start = mid + 1

print(result)

4 6
19 15 10 17

15     (4+0+0+2 = 6cm)

from bisect import bisect_left, bisect_right

n, x = map(int, input().split())
array = list(map(int, input().split()))

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = bisect_right(array, x) - bisect_left(array, x)

if count == 0:   # 값이 x인 원소가 존재하지 않는다면
    print(-1)
else:
    print(count)

7 2
1 1 2 2 2 2 3

4      (x = 4라면 -1)