파이썬으로 알고리즘 연습 블로그에 정리하자

탐욕알고리즘

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0 
    details = list()
    coin_list.sort(reverse=True) #500 100 50 1
    for coin in coin_list:
        coin_num = value // coin 
        total_coin_count += coin_num 
        value -= coin_num * coin 
        details.append([coin, coin_num])
    return total_coin_count, details

print(min_coin_count(4720, coin_list))

boj 2920

a = list(map(int, input().split(' ')))

ascending = True
descending = True

for i in range(1, 8):
    if a[i] > a[i - 1]:
        descending = False
    elif a[i] < a[i - 1]:
        ascending = False

if ascending:
    print('ascending')
elif descending:
    print('descending')
else:
    print('mixed')

boj 2798

# 카드의 합이 21이 넘지 않는 한도 내에서, 카드의 합이 최대가 되게 
# N장의 카드 중 3개를 골라 숫자 M이 넘지 않도록 최대의 값 

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

result = 0 
length = len(data)

count = 0

for i in range(0, length):
    for j in range(i + 1, length):
        for k in range(j + 1, length):
            sum_value = data[i] + data[j] + data[k]
            if sum_value <= m:
                result = max(result, sum_value)

print(result)

boj 1874

n = int(input())

count = 1
stack = []
result = []

for i in range(1, n+1):
    data = int(input())
    while(count <= data):
        stack.append(count)
        count += 1
        result.append('+')
    if stack[-1] == data:
        stack.pop()
        result.append('-')
    else: 
        print('NO')
        exit(0)

print('\n'.join(result))

boj 1966

test_case = int(input())

for _ in range(test_case):
    n, m = list(map(int, input().split(' ')))
    queue = list(map(int, input().split(' ')))
    queue = [(i, idx) for idx, i in enumerate(queue)]
    # enumerate을 이용하면 [2, 1, 4, 3] -> [(2, 0), [1, 1], [4, 2], [3, 3]]
    count = 0 
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == m:
                print(count)
                break
            else: 
                queue.pop(0)
        else:
            queue.append(queue.pop(0))

boj 5397

# boj5397 키로거 
# 1. 스택 두 개를 만들고, 스택 두 개의 중간 지점을 커서(Cursor)로 간주합니다. 
# 2. 문자 입력 : 왼쪽 스택에 원소를 삽입합니다.
# 3. -입력 : 왼쪽스택에서 원소를 삭제합니다.
# 4. <입력 : 왼쪽스택에서 오른쪽 스택으로 원소를 이동합니다.
# 5. >입력 : 오른쪽스택에서 왼쪽스택으로 원소를 이동합니다. 
# 6. 왼쪽출력 + 오른쪽출력 
# 유의 오른쪽 스택은 출력전 뒤집어서 #

test_case = int(input())

for _ in range(test_case):
    left_stack = []
    right_stack = []
    data = input()
    for i in data:
        if i == '-':
            left_stack.pop()
        elif i == '<':
            if left_stack:
                right_stack.append(left_stack.pop())
        elif i == '>':
            if right_stack:
                left_stack.append(right_stack.pop())
        else:
            left_stack.append(i)
    left_stack.extend(reversed(right_stack))
    print(''.join(left_stack))

boj 1920

# 하 / 해시, 배열, 구현, 20m
# 1. 특정 정수의 등장 여부만을 간단히 체크하면 됩니다. 
# 2. Python에서는 dictionary 자료형을 해시처럼 사용할 수 있습니다. 
# 3. 본 문제는 set자료형을 이용해 더욱 간단히 풀 수 있습니다. #
# set : 집합 중복x 포함유무만 확인한다면 유용 
N = int(input())
array = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))

for i in x: 
    if i not in array:
        print('0')
    else:
        print('1')

boj 4195

# 친구 네트워크 / 중 / 해시, 집합, 그래프, 50m

# 어떤 사이트의 친구 관계가 생긴 순서대로 주어질 때
# 두 사람의 친구 네트워크에 몇 명이 있는지 구해라 
# 1 : 테스트 케이스의 개수 
# F : 친구 관계의 수 
# 친구관계가 생긴 순서 : 두 사용자의 아이디로 
# 
# 1. 해시를 활용한 Union-Find알고리즘을 이용해 문제를 풀 수 있습니다. 
# 2. Python에서는 dictionary자료형을 해시처럼 사용할 수 있습니다. #
# Union-find : 합집합 찾기 

def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p 
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        parent[y] = x
        number[x] += number[y]

test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()

    f = int(input()) # 친구 관계의 수 

    for _ in range(f):
        x, y = input().split(' ')

        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            parent[y] = 1
        
        union(x, y)
        print(number[find(x)])