Algorithm-암호 만들기

Nov 18, 2020 in Algorithm, Back Tracking

문제유형 :
- 백 트레킹
설명
- C개의 문자들중에서 L개를 선택하는 모든 조합을 고려한다
- 모음의 개수와 자음의 개수 조건을 확인한다

풀이

import copy

result = []
string = []

def combination(array, length, index):
    if len(string) == length:
        result.append(copy.deepcopy(string))
        return
    for i in range(index, len(array)):
        string.append(array[i])
        combination(array, length, index + 1)
        string.pop()

vowels = ('a', 'e', 'i', 'o', 'u')
l, c = map(int, input().split(' '))

array = input().split(' ')
array.sort()

combination(array, l, 0)

for password in result:
    count = 0:
    for i in password:
        if i in vowels:
            count += 1
    
    if count >= 1 and count <= l - 2:
        print(''.join(password))

Comment and share

Algorithm-알파벳

Nov 18, 2020 in Algorithm, Back Tracking

백준 1987 : 문제링크

문제유형 :
- 백 트레킹
설명
- 말을 상하좌우 네 가지 방향으로 이동시킨다
- 지금까지 지나온 모든 칸에 적힌 알파벳과 다른 알파벳이 적인 칸으로 이동
- 백 트레킹을 이용하여 다른 알파벳이 적힌 칸으로 이동하도록 한다

풀이

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    global result
    q = set()
    q.add((x, y, array[x][y]))

    while q:
        x, y, step = q.pop()
        result = max(result, len(step))

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if (0 <= nx and nx < r and 0 <= ny and ny < c 
                and array[nx][ny] not in step)
                q.add(nx, ny, step + array[nx][ny])
    
r, c = map(int, input().split())
array = []
for _ in range(r):
    array.append(input())

result = 0
bfs(0, 0)
print(result)

Comment and share

Algorithm-N Queen

Nov 18, 2020 in Algorithm, Back Tracking

백준 9663 : 문제링크

문제유형 :
- 백 트레킹
설명
- DFS를 이용하여 백트래킹 알고리즘을 구현한다
- 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려한다
- 이 때 위쪽 행을 모두 확인하며, 현재 위치에 놓을 수 있는지 확인한다

풀이

def check(x):
    for i in  range(x):
        if row[x] == row[i]:
            return False
        if abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x):
    global result
    if x == n:
        result += 1
    else:
        for i in range(n):
            row[x] = i
            if check(x):   
                dfs(x+1)
    
n = int(input())
row = [0] * n
result = 0
dfs(0)
print(result)

Comment and share

Algorithm-컵라면

Nov 18, 2020 in Algorithm, Greedy

백준 1781 : 문제링크

문제유형 :
- 탐욕 알고리즘
설명
- 정렬 및 우선순위 큐를 이용하여 O(NlogN)의 시간에 해결할 수 있다
- 데드라인 기준으로 오름차순 정렬을 수행한다
- 각 문제의 컵라면 수를 우선순위 큐에 넣으면서, 데드라이을 초과할 결우 최소원소를 제거한다

풀이

import heapq

n = int(input())
array = []
q = []

for i in range(n):
    a, b = map(int, input().split(' '))
    array.append((a, b))
array.sort()

for i in array:
    a = i[0]
    heapq.heappush(q, i[1])
    if a < len(q):
        heapq.heappop(q)

Comment and share

Algorithm-도서관

Nov 17, 2020 in Algorithm, Greedy

백준 1461 : 문제링크

문제유형 :
- 탐욕 알고리즘
설명
- 일직선상에 책들을 순서대로 위치시킨다
- 0보다 큰 책들과 0보다 작은 책들을 나누어서 처리한다
- 음수와 양수 좌표를 위해 두 개의 우선순위 큐를 이용한다
- 마지막 책을 놓을 때는 다시 0으로 돌아올 필요가 없기 때문에, 가장 먼 책을 마지막으로 놓는다

풀이

import heapq

n, m = map(int, input().split(' '))
array = list(map(int, input().split(' ')))
positive = []
negative = []

largest = max(max(array), - min(array))

for i in array:
    if i > 0:
        heapq.heappush(positive, -i)
    else:
        heapq.heappush(negative, i)

result = 0

while positive:
    result += heapq.heappop(positive)
    for _ in range(m - 1):
        if positive:
            heapq.heappop(positive)

while negative:
    result += heapq.heappop(negative)
    for _ in range(m - 1):
        if negative:
            heapq.heappop(negative)

print(-result * 2 - largest)

Comment and share

Algorithm-센서

Nov 17, 2020 in Algorithm, Greedy

백준 1092 : 문제링크

문제유형 :
- 탐욕 알고리즘
설명
- 정렬만 수행하면 되므로 시간복잡도는 O(NlogN)
- 각 센서를 오름차순으로 정렬한다
- 각 센서 사이의 거리를 계산한다
- 가장 거리가 먼 순서대로 k - 1개의 연결 고리르 제거한다

풀이

import sys

n = int(input())
k = int(input())

if k >= n:
    print(0)
    sys.exit()

array = list(map(int, input().split(' ')))
array.sort()

distance = []
for i in range(1, n):
    distances.append(array[i] - array[i - 1])
distance.sort(reverse=True)

for i in range(k - 1):
    distances[i] = 0
print(sum(distances))

Comment and share

Algorithm-배

Nov 17, 2020 in Algorithm, Greedy

백준 1092 : 문제링크

문제유형 :
- 탐욕 알고리즘
설명
- 크레인과 박스를 무게 기준으로 내림차순 정렬한다
- 무거운 박스부터 크레인이 옮기도록한다
- 크레인의 수 N, 박스의 수 M일때 시간복잡도는 O(NM)이다

풀이

import sys

n = int(input())
cranes = list(map(int, input().split()))

m = int(input())
boxes = list(map(int, input().split()))

if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

positions = [0] * n
checked = [False] * m

cranes.sort(reverse=True)
boxes.sort(reverse=True)

result = 0
count = 0

while True:
    if count == len(boxes):
        break
    for i in range(n):
        while position[i] < len(boxes):
            if not checked[position[i]] and cranes[i] >= boxes[position[i]]:
                checked[position[i]] = True
                position[i] += 1
                count += 1
                break
            position[i] += 1
    result += 1

print(result)

Comment and share

Algorithm-우주신과의 교감

Nov 17, 2020 in Algorithm, Graph, Kruskal

백준 5719 : 문제링크

문제유형 :
- 그래프
- 크루스칼 알고리즘
설명
- 정점의 개수 N이 최대 1000이므로, 가능한 통로의 개수는 약 N^2이다
- 크루스칼 알고리즘은 간선의 개수가 E일 때 O(ElogE)로 동작하므로 해결할 수 있다 (정렬 알고리즘 시간복잡도)

풀이

import math
import sys

input = sys.stdin.readline

def get_distance(p1, p2):
    a = p1[0] - p2[0]
    b = p1[1] - p2[1]
    return math.sqrt((a * a) + (b * b))

def get_parent(parent, n):
    if parent[n] == n:
        return n
    return get_parent(parent, parent[n])

def union_parent(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def find_parent(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a == b:
        return True
    else:
        return False

edges = []
parent = {}
locations = []
n, m = map(int, input().split())

for _ in range(n):
    x, y = map(int, input().split())
    locations.append((x, y))

length = len(locations)

for i in range(length - 1)
    for j in range(i + 1, length):
        edges.append((i + 1, j + 1), get_distance(location[i], location[j]))
    
for i in range(1, n + 1):
    parent[i] = i

for i in range(m):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

edges.sort(key=lambda data: data[2])

result = 0
for a, b, cost in edges:
    if not find_parent(parent, a, b):
        union_parent(parent, a, b)
        result += cost

print("%0.2f" %result)

Comment and share

Algorithm-거의 최단 경로

Nov 17, 2020 in Algorithm, Graph, Dijkstra

백준 5719 : 문제링크

문제유형 :
- 그래프
- 다익스트라 최단 경로 알고리즘
설명
- 다익스트라 최단 경로에 포함되는 모든 간선을 추적한다
- 최단 경로에 포함되는 모든 간선을 추적할 때 DFS를 사용하여 추적하여 제외시킨다
- 제외된 간선 외에서 다익스트라 최단 경로 알고리즘으로 차선 최단 경로를 찾는다

풀이

from collections import deque
import heapq
import sys

input = sys.stdin.readline

def dijkstra():
    heap_data = []
    heapq.heappush(heap_data, (0, start))
    distance[start] = 0
    while heap_data:
        dist, now = heapq.heappop(heap_data)
        if distance[now] < dist:
            continue
        for i in adj[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost and not dropped[now][i[0]]:
                distance[i[0]] = cost
                heapq.heappush(heap_data, (cost, i[0]))

def bfs():
    q = deque()
    q.append(end)
    while q:
        now = q.popleft()
        if now == start:
            continue
        for prev, cost in reverse_adj[now]:
            if distance[now] == distance[prev] + cost
                dropped[prev][now] = True
                q.append(prev)

while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    start, end = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    reverse_adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        x, y, cost = map(int, input().split())
        adj[x].append((y, cost))
        reverse_adj[y].append((x, cost))
    dropped = [[False] * (n + 1) for _ in range(n + 1)]
    distance = [1e9] * (n + 1)
    dijkstra()
    bfs()
    distance = [1e9] * (n + 1)
    dijkstra()
    if distance[end] != 1e9:
        print(distance[end])
    else:
        print(-1)

Comment and share

Algorithm-해킹

Nov 13, 2020 in Algorithm, Graph, Dijkstra

백준 10282 : 문제링크

문제유형 :
- 그래프
- 다익스트라 최단 경로 알고리즘
설명
- 정점의 개수 N, 간선의 개수 D
- 우선순위 큐를 이용하여, 시간복잡도 O(NlogD)로 해결할 수 있습니다

풀이

import heapq
import sys
input = sys.stdin.readline

def dijkstra(strat):
    heap_data = []
    heapq.heappush(heap_data, (0, start))
    distance[start] = 0
    while heap_data:
        dist, now = heapq.heappop(heap_data)
        if distance[now] < dist:
            continue
        for i in adj[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(heap_data, (cost, i[0]))

for _ in range(int(input())):
    n, m, start = map(int, input().split())
    adj = [[] for i in range(n + 1)]
    distance = [1e9] * (n + 1)
    for _ in range(m):
        x, y, cost = map(int, input().split())
        adj[y].append((x, cost))
    dijkstra(start)
    count = 0
    max_distance = 0
    for i in distance:
        if i != 1e9:
            count += 1
            if i > max_distance:
                max_distance = i
    print(count, max_distance)

Comment and share

Yechan Kim