728x90
반응형

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
check = [0]*N
dfs(0)

 

728x90
반응형
728x90
반응형

브루트포스 알고리즘 & 백트래킹 문제이다.

def dfs(depth):
    if depth == N:
        res.append(sum(abs(li[i+1]-li[i]) for i in range(N-1)))
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0

N = int(input())
nums = list(map(int, input().split()))
li, res = [], []
check = [0]*N
dfs(0)
print(max(res))
728x90
반응형
728x90
반응형

브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다.

def dfs(depth, k):
    if depth == k and sum(li) == S:
        s.append(li)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1, k)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, S = map(int, input().split())
nums = list(map(int, input().split()))
li, s = [], []
for i in range(1, N+1):
    check = [0]*N
    dfs(0, i)
print(len(s))
728x90
반응형
728x90
반응형

기본적인 소수 판정(에라토스테네스의 체) 문제이다.

def prime(n):
    li = [1]*(n+1)
    for i in range(2, int(n**0.5)+1):
        if li[i]:
            for j in range(i+i, n+1, i):
                li[j] = 0
    p = [i for i in range(2, n+1) if li[i]]
    return p

while 1:
    s = input()
    if s == '0':
        break
    p = prime(100000)
    res = 2
    for n in p:
        if str(n) in s:
            res = n
    print(res)
728x90
반응형
728x90
반응형

백트래킹 & 소수 판정(에라토스테네스의 체) 문제이다. 꽤 좋은 퀄리티의 문제인 것 같다.

def dfs(depth):
    if depth == M:
        s.add(sum(li))
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

def prime(n):
    li = [1]*(n+1)
    for i in range(2, int(n**0.5)+1):
        if li[i]:
            for j in range(i+i, n+1, i):
                li[j] = 0
    p = [i for i in range(2, n+1) if li[i]]
    return p

N, M = map(int, input().split())
nums = list(map(int, input().split()))
s = set()
li = []
check = [0]*N
dfs(0)
p = prime(1000*M)
ok = 0
if s:
    for n in sorted(s):
        if n in p:
            ok = 1
            print(n, end=' ')
if ok == 0:
    print(-1)
728x90
반응형
728x90
반응형

기본적인 소수 판정(에라토스테네스의 체) 문제이다.

INF = 10**7
li = [1]*INF
for i in range(2, int(INF**0.5)+1):
    if li[i]:
        for j in range(i+i, INF, i):
            li[j] = 0
prime = [i for i in range(2, INF) if li[i]]
K = int(input())
print(prime[K-1])    
728x90
반응형
728x90
반응형

간단한 소수 판정(에라토스테네스의 체) 문제이다. 그냥 무식하게 풀었다.

def f(K, prime):
    for i in prime:
        for j in prime:
            for k in prime:
                if i+j+k == K:
                    print(i, j, k)
                    return ;
    print(0)

li = [1]*1001
for i in range(2, int(1000**0.5)+1):
    if li[i]:
        for j in range(i+i, 1001, i):
            li[j] = 0
prime = [i for i in range(2, 1001) if li[i]]

for _ in range(int(input())):
    K = int(input())
    f(K, prime)
728x90
반응형
728x90
반응형

간단한 소수 판정(에라토스테네스의 체) 문제이다.

A, B, D = map(int, input().split())
li = [1]*(B+1)
for i in range(2, int(B**0.5)+1):
    if li[i]:
        for j in range(i+i, B+1, i):
            li[j] = 0
prime = [i for i in range(A, B+1) if li[i]]
cnt = 0
for n in prime:
    if str(D) in str(n):
        cnt += 1
print(cnt)
728x90
반응형
728x90
반응형

이분 탐색 Or 우선순위 큐 문제라는데, 이분 탐색이 훨씬 효율적일 것 같아서 그냥 이분 탐색으로 풀었다.

N, M = map(int, input().split())
li = list(map(int, input().split()))
s, e = 0, max(li)*M
res = 0
while s <= e:
    m = (s+e)//2
    if sum([m//n for n in li]) >= M:
        res = m
        e = m-1
    else:
        s = m+1
print(res)
728x90
반응형
728x90
반응형

기본적인 우선순위 큐 문제이다.

import heapq

n, m = map(int, input().split())
q = list(map(int, input().split()))
heapq.heapify(q)
for _ in range(m):
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    heapq.heappush(q, a+b)
    heapq.heappush(q, a+b)
print(sum(q))
728x90
반응형
728x90
반응형

기본적인 우선순위 큐 문제이다. 파이썬에서 우선순위 큐는 heapq 라이브러리 또는 queue 라이브러리의

PriorityQueue를 사용하면 쉽게 구현할 수 있다. 나는 그냥 heapq 라이브러리를 사용해서 풀었다.

import heapq

n = int(input())
q = []
for _ in range(n):
    s = input()
    if s == '0':
        print(-heapq.heappop(q) if q else -1)
    else:
        li = list(map(int, s.split()))
        for n in li[1:]:
            heapq.heappush(q, -n)
728x90
반응형
728x90
반응형

그냥 lambda로 정렬해서 풀면 된다. lambda 짱!

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
sorted_li = sorted(li, key=lambda x:(-x[0], x[1], x[2]))
print(li.index(sorted_li[0])+1)
728x90
반응형
728x90
반응형

기본적인 우선순위 큐 문제이다. 최대 힙으로 구현해주면 된다.

import heapq

N = int(input())
D = int(input())
q = []
for _ in range(N-1):
    n = int(input())
    heapq.heappush(q, -n)
res = 0
while q:
    n = -heapq.heappop(q)
    if D > n:
        break
    D += 1
    res += 1
    heapq.heappush(q, -(n-1))
print(res)
728x90
반응형
728x90
반응형

기본적인 다익스트라 문제이긴 하다만, N-1번째 분기점을 제외하고 상대의 시야에 보이지 않는 분기점에만

방문해야 한다는 차이점이 있다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v] and check[v] == 0:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
check = list(map(int, input().split()))
check[-1] = 0
for _ in range(M):
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
    graph[b].append((a, t))
dijkstra(0)
print(dis[N-1] if dis[N-1] != INF else -1)
728x90
반응형
728x90
반응형

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dis = [INF]*(n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
s, t = map(int, input().split())
dijkstra(s)
print(dis[t])
728x90
반응형

+ Recent posts