로딩중...
-
[백준, python] 14502번 - 연구소
백준 문제풀이 시작
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
풀이
풀이 확인하기
해당 문제는 DFS를 통해 풀 수 있다. 문제에서 제시한 지도의 넓이가 넓지 않으므로 벽을 세울 수 있는 모든 경우에 대해 바이러스를 DFS를 통해 퍼트리고 각 경우에 안전 영역이 얼마나 남는가를 계산해 가장 많이 안전 영역이 확보된 경우를 계산하여 출력하면 된다.
import sys
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
lis = []
after = [[0] * m for _ in range(n)]
for _ in range(n):
lis.append(list(map(int, input().rstrip().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0
def virus(x, y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < n and ny >= 0 and ny < m:
if(after[nx][ny] == 0):
after[nx][ny] = 2
virus(nx, ny)
def get_score():
score = 0
for i in range(n):
for j in range(m):
if(after[i][j] == 0):
score += 1
return score
def dfs(count):
global result
if count == 3:
for i in range(n):
for j in range(m):
after[i][j] = lis[i][j]
for i in range(n):
for j in range(m):
if after[i][j] == 2:
virus(i, j)
result = max(result, get_score())
return result
for i in range(n):
for j in range(m):
if lis[i][j] == 0:
lis[i][j] = 1
count += 1
dfs(count)
lis[i][j] = 0
count -= 1
dfs(0)
print(result)
-
[백준, python] 11404번 - 플로이드
백준 문제풀이 시작
문제
n(2 ≤ n ≤ 100)개의 도시가 있다.
그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
출력
n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.
풀이
풀이 확인하기
해당 문제는 전형적인 플로이드-와셜 알고리즘 문제로, 입력을 받은 뒤 플로이드-와셜 알고리즘을 그대로 수행해주면 된다. 단, 입력에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 점을 생각하여 가장 짧은 간선의 정보만 기록할 수 있도록 한다.
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
graph[i][i] = 0
for _ in range(m):
a, b, c = map(int, input().split())
if graph[a][b] > c:
graph[a][b] = c
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][j] == INF:
print(0, end=" ")
else:
print(graph[i][j], end=" ")
print()
-
[백준, python] 2887번 - 행성 터널
백준 문제풀이 시작
문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 $A(x_A, y_A, z_A)$와 $B(x_B, y_B, z_B)$를 터널로 연결할 때 드는 비용은 $\min($|$x_A-x_B$|$, $|$y_A-y_B$|$,$ |$z_A-z_B$|$)$이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
풀이
풀이 확인하기
해당 문제를 푸는 과정에서 모든 점에서 각 점까지의 거리를 구하게 되면 메모리 초과가 발생한다. 이를 줄이기 위해 약간의 스킬이 필요한데, 바로 정렬이다.
문제에서 터널의 비용이 각 방향으로의 거리들 중 가장 작은 값이므로 약간의 정렬 스킬을 이용하면 풀 수 있는 것이다.
먼저 X축 방향으로 각 행성들을 정렬한다. 그렇게 되면 각 행성 사이간의 거리들, 즉 행성의 수가 N이라고 한다면 N-1개의 간선만 고려를 하면 되는 것이다.
같은 방식으로 Y, Z 방향도 간선을 뽑아내면 고려해야할 간선의 수가 확 줄어들게 되는 것이다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
num = int(input())
parent = [0] * (num + 1)
edges = []
result = 0
planet = []
for i in range(1, num+1):
parent[i] = i
x = []
y = []
z = []
for i in range(num):
a, b, c = map(int, input().split())
x.append((a, i))
y.append((b, i))
z.append((c, i))
x.sort()
y.sort()
z.sort()
for i in range(num-1):
edges.append((x[i+1][0] - x[i][0], x[i][1], x[i+1][1]))
edges.append((y[i+1][0] - y[i][0], y[i][1], y[i+1][1]))
edges.append((z[i+1][0] - z[i][0], z[i][1], z[i+1][1]))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
-
-
[백준, python] 9536번 - 여우는 어떻게 울지?
백준 문제풀이 시작
문제
고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다.
하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다.
그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다.
그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다.
입력
첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 아래와 같이 구성되어 있다.
테스트케이스의 첫 줄에는 몇 개의 단어로 이루어진 녹음된 소리가 입력된다. 단어는 알파벳 소문자로만 이루어져 있으며 공백으로 구분된다. 단어의 길이는 최대 100글자이고, 단어의 개수는 최대 100개이다. 다음 줄부터는 여우를 제외한 동물들의 울음소리가 goes 의 형태로 입력된다. 최소 1마리, 최대 100마리이며, 이름은 최대 100글자이고 실제로 존재하는 동물의 이름이다. 여우를 제외한 동물의 울음소리는 한 단어이고 최대 100글자이다.
마지막 줄에는 한신이가 알고 싶어하는 질문이 주어진다. what does the fox say?
출력
각 테스트케이스마다 여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력한다. 여우의 울음소리가 녹음되어 있음이 보장된다. (알려진 것과는 달리, 여우는 모스 부호로 의사소통하지 않는다.)
풀이
풀이 확인하기
입력받은 테스트 케이스만큼 반복문을 돌리고 반복문 내에서 모든 동물들의 울음소리를 리스트화 한다. 이후 반복문으로 받으며 what does the fox say? 가 아닐 때까지 반복적으로 동물들의 울음소리를 제거한다. 이후 리스트를 출력한다.
import sys
input = sys.stdin.readline
num = int(input())
for _ in range(num):
lis = input().strip().split()
while True:
question = input().strip().split()
if(question == ["what", "does", "the", "fox", "say?"]):
break
else:
lis = [i for i in lis if i != question[2]]
print(*lis)
-
[백준, python] 1706번 - 크로스워드
백준 문제풀이 시작
문제
동혁이는 크로스워드 퍼즐을 좋아한다.
R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.
세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다.
다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.
출력
첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다.
풀이
풀이 확인하기
이번 문제는 조건에 알맞는 문자열을 찾을 수 있도록 분기를 잘 해줘야 한다. 입력받은 크로스워드를 이차원 배열로 담고, 가로로 된 단어를 찾는 이중 반복문을 한번, 세로로 찾는 이중 반복문을 한번, 총 두번의 반복문을 돌린다. 반복문으로 순회하다가 #을 만난다면 지금까지 읽은 단어가 1글자보다 크다면 단어 리스트에 추가하고 아닐 경우 추가하지 않는다.(한글자는 단어가 아니기 때문.)
순회가 전부 끝나고 단어가 모였다면 정렬 후 첫번째 값을 출력한다.
import sys
input = sys.stdin.readline
width, height = map(int, input().split())
lis = [[]for _ in range(width)]
for i in range(width):
a = list(input().strip())
lis[i] = a
words = []
for i in range(width):
word = ""
for j in range(height):
if lis[i][j] == "#":
if len(word) > 1:
words.append(word)
word = ""
elif j == height-1 and lis[i][j] != "#":
word += lis[i][j]
if len(word) > 1:
words.append(word)
else:
word += lis[i][j]
for i in range(height):
word = ""
for j in range(width):
if lis[j][i] == "#":
if len(word) > 1:
words.append(word)
word = ""
elif j == width-1 and lis[j][i] != "#":
word += lis[j][i]
if len(word) > 1:
words.append(word)
else:
word += lis[j][i]
words.sort()
print(words[0])
-
[백준, python] 4949번 - 균형잡힌 세상
백준 문제풀이 시작
문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호(“( )”), 대괄호(“[ ]”)로 이루어져 있으며, 온점(“.”)으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(“.”)가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력한다.
풀이
풀이 확인하기
입력받은 문자열이 .일 경우 종료, .이 아닐 경우 반복문을 통해 순회하며 [, (, ), ]를 만날 경우 상황에 따라 조건을 처리한다. [, (를 만날 경우 각각 ), ]를 짝지어 만난다면 pop, 아닐 경우 그대로 push를 한다. 그리고 stack의 길이가 0이 아닐 경우 no, 0일 경우 yes를 출력한다.
import sys
from functools import cmp_to_key
input = sys.stdin.readline
while True:
inp = list(input().rstrip())
stack = []
if(inp == ["."]):
break
for i in inp:
if(i == "[" or i == "("):
stack.append(i)
elif(i == "]"):
if(len(stack) != 0 and stack[-1] == "["):
stack.pop()
else:
stack.append(i)
elif(i == ")"):
if(len(stack) != 0 and stack[-1] == "("):
stack.pop()
else:
stack.append(i)
if(len(stack) == 0):
print("yes")
else:
print("no")
P.S. 조건문 처리 과정에서
if(stack[-1] == "["):
와 같이 줄 경우 stack의 길이가 0일 때 indexError가 발생하므로 이에 유의하여 처리해야 한다.
-
-
[백준, python] 9935번 - 문자열 폭발
백준 문제풀이 시작
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
풀이
풀이 확인하기
이 문제는 스택을 통해 효율적으로 문자열을 지울 수 있다. 먼저 스택을 통해 문자열을 한글자씩 push한다. 그리고 문자열의 끝 폭발 문자열의 개수만큼 비교하며 만약 문자열의 끝부분이 폭발 문자열과 동일하다면 폭발 문자열의 길이만큼 문자열에서 pop을 한 뒤, 완성된 스택을 조건에 따라 출력한다.
import sys
input = sys.stdin.readline
lis = list(input().strip())
find = list(input().strip())
stack = []
for i in range(len(lis)):
stack.append(lis[i])
if(len(stack) >= len(find)):
if(stack[len(stack)-len(find):] == find):
for _ in range(len(find)):
stack.pop()
if(len(stack) == 0):
print("FRULA")
else:
for i in range(len(stack)):
print(stack[i], end="")
-
-
[백준, python] 10773번 - 제로
백준 문제풀이 시작
문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 “0” 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 “0”일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
풀이
풀이 확인하기
이 문제는 전형적인 스택 문제이다. 파이썬은 리스트를 가지고 스택의 기능을 사용할 수 있다. 입력을 받으면서 0이면서 동시에 리스트의 길이가 0이면 continue, 리스트의 길이가 0이 아니면서 0이 입력이 되면 pop, 아닐 경우 push를 한다. 이후 리스트의 모든 값들을 더해 출력한다.
import sys
input = sys.stdin.readline
num = int(input())
lis = []
for _ in range(num):
a = int(input())
if(a == 0 and len(lis) == 0):
continue
elif(a == 0):
lis.pop()
else:
lis.append(a)
ans = 0
for i in lis:
ans = ans + i
print(ans)
-
[백준, python] 12015번 - 가장 긴 증가하는 부분 수열 2
백준 문제풀이 시작
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
풀이 확인하기
이 문제는 백준 11053번과 동일한 문제로 보이지만 똑같이 코드를 짤 경우 시간 초과가 뜰 것이다. 그래서 시간을 줄일 수 있는 방법을 생각해야 한다.
기존 문제를 푸는 과정에서 매번 max 함수를 통해 값을 비교하는 과정에서 모든 뒤 숫자들을 비교하게 된다. 이는 비효율적이므로 이분 탐색을 통해 해당 수가 뒤 어디에 들어올만한지 효율적으로 찾을 수 있다. 위치를 찾은 뒤 해당 수와 수를 교체하는 과정으로 코드를 수정해주면 O(NlogN) 시간으로 문제를 해결할 수 있다.
(P.S. 해당 코드의 ans는 실제 lis가 아니다.)
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
f = int(input())
line = list(map(int, input().strip().split()))
ans = []
lens = 1
ans.append(line[0])
for i in range(1, len(line)):
if(ans[lens-1] < line[i]):
ans.append(line[i])
lens += 1
else:
j = bisect_left(ans, line[i])
ans[j] = line[i]
print(lens)
-
백준 풀이 주요 알고리즘 정리
백준에서 문제를 풀어보니 자주 보이는 문제 유형들에 사용되는 알고리즘을 정리할 수 있을 것 같다는 생각이 들었다.
그래서 코딩 테스트, 백준 문제풀이 등에서 자주 보이던 유형들을 정리해보려고 한다.
(계속 공부해 나가는 과정에서 업데이트 할 수 있다면 할 예정.)
1. 브루트포스 알고리즘
가장 단순한 방법이다. 바로 모든 경우의 수를 다 넣어보는 단순무식한 방법이다. 4자리 숫자 자물쇠 번호를 맞추는 가장 쉬운 방법이 무엇일까? 바로 0000부터 9999까지 다 넣어보면 되는 것이다. 이 방법이 바로 브루트포스 알고리즘이다.
1059번
1233번
등 문제를 브루트포스 알고리즘으로 풀 수 있다.
2. 그리디 알고리즘
그리디 알고리즘은 브루트포스 알고리즘과 비슷한 알고리즘이다. 하지만 브루트포스 알고리즘은 모든 경우를 다 본다면 그리디 알고리즘은 매 순간마다 자기에게 가장 이득이 되는 선택을 취하게 된다.
1417번
2839번
등 문제를 그리디 알고리즘으로 풀 수 있다.
3. DFS와 BFS
DFS와 BFS는 그래프 탐색 알고리즘이다.
DFS는 Deep-First Search의 줄임말로 그래프의 노드와 다음 노드를 넘어갈 때 해당 노드의 하위 노드까지 완벽히 탐색한 뒤 다음 노드로 넘어가는 것이다.
그리고 BFS는 Breadth-First Search의 줄임말로 그래프의 갈림길이 발생할 때마다 모든 경우를 넓게 탐색한 뒤 다음으로 넘어가게 된다.
말로는 이해가 힘들어 실제 트리를 통해 탐색 결과를 비교해보면
해당 그래프를 DFS를 통해 탐색할 경우
2 > 7 > 2 > 6 > 5 > 11 > 5 > 9 > 4
의 순서로 탐색을 진행할 것이다.
하지만 BFS로 탐색할 경우
2 > 7 > 5 > 2 > 6 > 9 > 5 > 11 > 4
의 순서로 탐색을 한다는 차이점이 있다.
DFS의 구현은 일반적으로 재귀를 통하여 구현한다.
def dfs(start):
visited[start] = 1
print(start, end=" ")
for i in graph[start]:
if not visited[i]:
dfs(i)
와 같은 형태로 DFS를 구현할 수 있다.
BFS의 구현은 queue 자료구조를 통해 구현한다.
def bfs(start):
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
visited[i] = True
queue.append(i)
와 같은 형태로 BFS를 구현할 수 있다.
DFS는 그래프의 모든 경우를 하나하나 탐색해야할 때, BFS는 그래프 내의 최단 거리를 찾아야할 때 자주 사용된다.
2644번
1260번
등 문제를 DFS 알고리즘으로 풀 수 있다.
4. 이분 탐색
이분 탐색은 오름차순으로 정렬된 리스트에서 원하는 수를 효율적으로 찾을 수 있는 알고리즘이다.
예를 들어
2, 3, 4, 7, 9, 11, 23
이란 리스트에서 3을 찾고 싶을 경우를 예시로 들자.
이분 탐색의 시작은 중앙값을 찾는 것이다. 저 리스트에서 중앙값은 7인데, 이때 7은 3보다 큼을 알 수 있다. 찾는 수가 중앙값보다 크다면 중앙보다 더 큰 값들은 탐색할 필요가 없으므로 처음부터 중앙값 전까지만 찾으면 되는 것이다. 이 방식을 반복하여 3이 두번째에 있음을 알 수 있는 것이다.
파이썬에서는 bisect 라이브러리를 통해 쉽게 구할 수 있다.
12015번
1920번
등 문제를 이분 탐색으로 풀 수 있지만, 시간 복잡도를 줄이기 위해서도 자주 쓴다.
5. 다이나믹 프로그래밍
아마 알고리즘 공부를 입문한 뒤 가장 처음으로 어려운 부분이 아닐까 싶다. 다이나믹 프로그래밍이란 시간 복잡도를 줄이기 위해 효율적으로 알고리즘을 작성하는 방법을 의미한다. 예를 들어보자.
def fib(n):
if n==1 or n==2:
return 1
else:
return fib(n-1) + fib(n-2)
피보나치 수를 구하는 파이썬 코드이다. 쉽게 짤 수 있지만 문제가 있다. 예를 들어 fib(6)을 알기 위해선 fib(4), fib(5)를 알아야 한다. 그리고 fib(4)는 다시 fib(3), fib(2)를, fib(5)는 fib(3), fib(4)를 알아야 한다. 여기서 문제가 발생한다. fib(3), fib(4)를 중복해서 구하게 되는 문제가 발생한다. 실제로 저 코드를 돌려보면 해당 문제 때문에 30 이상의 숫자는 결과를 확인하기 힘들 정도로 오래 걸림을 알 수 있다.
하지만 만약 저 겹치는 숫자들을 저장을 해둔다면 어떨까? 굳이 계산할 필요 없이 이미 구한 수는 저장한 값을 그대로 가져오기만 하면 되는 것이다. 이를 통해 비약적으로 프로그램 실행 속도를 단축할 수 있는 것이다. 이런 식으로 중복되는 연산들을 줄이자 라는 생각에서 출발한 것이 바로 다이나믹 프로그래밍인 것이다. 다이나믹 프로그래밍 방식에는 탑다운(Top-down), 바텀업(Bottom-up), 메모이제이션(Memoization) 등의 방식이 있다.
9184번
11053번
등의 문제를 다이나믹 프로그래밍으로 풀 수 있다.
-
[백준, python] 11478번 - 서로 다른 부분 문자열의 개수
백준 문제풀이 시작
문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.
출력
첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.
풀이
풀이 확인하기
이번 문제는 set을 사용하면 쉽게 풀 수 있다. set 자료형은 중복되는 값은 자동으로 들어가지 않는데, 이를 이용해 “aaa”와 같이 겹치는 요소들을 쉽게 제거할 수 있다. 이중 반복문을 통해 가능한 경우의 수의 부분 문자열들을 전부 set에 넣고, set의 요소들의 개수만 출력하면 되는 것이다.
(set 자료구조는 O(1)의 시간복잡도를 가지는 매우 빠른 자료구조인데, 이 원리에 대하여 궁금하다면 hash table을 검색해보자. 참고로 파이썬의 다른 자료구조인 dictonray 역시 비슷한 구조를 가지고 있다.)
import sys
input = sys.stdin.readline
line = input().strip()
num = set([])
for i in range(0, len(line)+1):
for j in range(i+1, len(line)+1):
num.add(line[i:j])
print(len(num))
-
[백준, python] 11053번 - 가장 긴 증가하는 부분 수열
백준 문제풀이 시작
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
풀이 확인하기
입력받는 리스트와 memoization을 위한 리스트를 만들어 주고, memoization용 리스트의 길이는 입력 리스트의 길이와 동일하게 만들고 1로 초기화해준다. 이후 반복문으로 돌면서 i번째에 존재하는 값이 j번째에 존재하는 값보다 더 크다면 memoization의 i번째와 j번째값 + 1 을 비교하여 더 큰 값으로 update한다. 이후 memoization용 리스트의 가장 큰 값이 lis의 길이가 된다.
import sys
input = sys.stdin.readline
num = int(input())
lis = list(map(int, input().strip().split()))
mem = [1 for _ in range(len(lis))]
for i in range(1, len(lis)):
for j in range(0, i):
if(lis[i] > lis[j]):
mem[i] = max(mem[i], mem[j]+1)
print(max(mem))
-
[백준, python] 1912번 - 연속합
백준 문제풀이 시작
문제
n개의 정수로 이루어진 임의의 수열이 주어진다.
우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
풀이
풀이 확인하기
입력받는 리스트와 memoization을 위한 리스트를 만들어 주고, memoization용 리스트의 첫번째에 입력받은 리스트의 첫번째 값을 담는다.
이후 나머지는 memoization 리스트의 현재보다 한칸 전 값에 현재 값을 더한 값과 현재 값을 비교 해 더 큰 값을 담는다. 이후 memoization 리스트에서 가장 큰 값을 출력한다.
num = int(input())
arr = list(map(int, input().split(" ")))
mem = [0]*num
mem[0] = arr[0]
for i in range(1, num):
mem[i] = max(arr[i], mem[i-1] + arr[i])
print(max(mem))
-
[백준, python] 1932번 - 정수 삼각형
백준 문제풀이 시작
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
풀이
풀이 확인하기
이번 문제는 DP를 통해 풀 수 있다. 입력을 받은 뒤 두번째 줄부터 반복문을 통해 돌며 위치가 양 끝이라면 위에서 내려올 수 있는 곳은 하나밖에 없으므로 해당 값과 현재 위치를 더한 값으로 업데이트하고, 다른 수들은 위에서 내려올 수 있는 두 수 중 큰 값과 현재 위치를 더한 값으로 업데이트하는 과정을 반복해 내려온 뒤, 맨 밑 줄에 있는 수중 가장 큰 값을 출력한다.
import sys
input = sys.stdin.readline
a = int(input())
data = []
for _ in range(a):
data.append(list(map(int, input().strip().split())))
b = 0
for i in range(1, a):
for j in range(0, len(data[i])):
if(j == 0):
data[i][j] = data[i-1][0] + data[i][j]
elif(j == len(data[i])-1):
data[i][j] = data[i-1][b-1] + data[i][j]
else:
data[i][j] = max(data[i-1][j-1], data[i-1][j]) + data[i][j]
b = len(data[i])
print(max(data[a-1]))
-
[백준, python] 9184번 - 신나는 함수 실행
백준 문제풀이 시작
문제
재귀 호출만 생각하면 신이 난다! 아닌가요?
다음과 같은 재귀함수 w(a, b, c)가 있다.
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)
a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.
입력
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
출력
입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.
풀이
풀이 확인하기
이번 문제는 DP를 통해 풀 수 있다. 문제에서 1부터 20까지만 필요하므로 memoization을 위한 배열은 3차원으로 1부터 20까지 적을 수 있도록 크기를 만들고, 함수를 정의한다. w 함수는 문제에서 준 sudo code와 동일하게 작성하지만 memoization이 되어있는 값이라면 재귀를 통한 연산 없이 바로 반환하고, 없다면 똑같이 연산을 진행한 뒤 배열의 해당 값에 해당하는 위치에 값을 저장해둔다.
import sys
input = sys.stdin.readline
mem = [[[0 for _ in range(21)] for _ in range(21)]for _ in range(21)]
def w(a, b, c):
if a <= 0 or b <= 0 or c <= 0:
return 1
if a > 20 or b > 20 or c > 20:
return w(20, 20, 20)
if mem[a][b][c]:
return mem[a][b][c]
if a < b and b < c:
mem[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return mem[a][b][c]
else:
mem[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
return mem[a][b][c]
while(True):
aa, bb, cc = map(int, input().split())
if(aa == -1 and bb == -1 and cc == -1):
break
print("w(" + str(aa) + ", " + str(bb) + ", " + str(cc) +") = ", end="")
print(w(aa, bb, cc))
-
[백준, python] 1774번 - 우주신과의 교감
백준 문제풀이 시작
문제
황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.
하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.
우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다.
또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있는 세상에 살고 있다. 통로들의 길이는 2차원 좌표계상의 거리와 같다.
이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재한다. 우리는 황선자 씨를 도와 아직 연결이 되지 않은 우주신들을 연결해 드려야 한다. 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자.
입력
첫째 줄에 우주신들의 개수(N<=1,000) 이미 연결된 신들과의 통로의 개수(M<=1,000)가 주어진다.
두 번째 줄부터 N개의 줄에는 황선자를 포함하여 우주신들의 좌표가 (0<= X<=1,000,000), (0<=Y<=1,000,000)가 주어진다. 그 밑으로 M개의 줄에는 이미 연결된 통로가 주어진다. 번호는 위의 입력받은 좌표들의 순서라고 생각하면 된다. 좌표는 정수이다.
출력
첫째 줄에 만들어야 할 최소의 통로 길이를 출력하라. 출력은 소수점 둘째짜리까지 출력하여라.
풀이
풀이 확인하기
이번 문제는 최소 스패닝 문제이지만 두가지 차이점이 존재하는데
가중치가 나와있지 않다.
이미 연결된 간선이 존재한다.
라는 문제가 존재한다. 하지만 1의 경우 두 우주신 사이의 거리가 가중치가 된다. 그러므로 두 간선 사이의 가중치를 반복문을 통해 구해 edge에 추가해주면 평범한 MST 문제가 된다. 2번 역시 그저 나온 두 우주신들을 union 연산만 해주면 된다.
import sys
input = sys.stdin.readline
def find(p, a):
if(p[a] != a):
p[a] = find(p, p[a])
return p[a]
def union(p, a, b):
a = find(p, a)
b = find(p, b)
if(a < b):
p[b] = a
else:
p[a] = b
v, e = map(int, input().split())
p = [0] * (v + 1)
edge = []
cost = 0.0
for i in range(1, v+1):
p[i] = i
data = []
for _ in range(v):
a, b = map(int, input().split())
data.append([a, b])
for i in range(len(data)):
for j in range(i+1, len(data)):
costs = abs(((data[j][1] - data[i][1])**2 + (data[j][0] - data[i][0])**2)**(1/2))
edge.append((costs, i+1, j+1))
for _ in range(e):
f, g = map(int, input().split())
union(p, f, g)
edge.sort()
for ed in edge:
c, a, b = ed
if(find(p, a) != find(p, b)):
union(p, a, b)
cost += c
print("{:.2f}".format(cost))
P.S. 문제 내용이 정말 스펙타클하군요…
-
[백준, python] 6800번 - Huffman Encoding
백준 문제풀이 시작
문제
There is an ingenious text-compression algorithm called Huffman coding, designed by David Huffman in 1952.
The basic idea is that each character is associated with a binary sequence (i.e., a sequence of 0s and 1s). These binary sequences satisfy the prefix-free property: a binary sequence for one character is never a prefix of another character’s binary sequence.
It is worth noting that to construct a prefix-free binary sequence, simply put the characters as the leaves of a binary tree, and label the “left” edge as 0 and the ”right” edge as 1. The path from the root to a leaf node forms the code for the character at that leaf node. For example, the following binary tree constructs a prefix-free binary sequence for the characters {A, B, C, D, E}:
That is, A is encoded as 00, B is encoded as 01, C is encoded as 10, D is encoded as 110 and E is encoded as 111.
The benefit of a set of codes having the prefix-free property is that any sequence of these codes can be uniquely decoded into the original characters.
Your task is to read a Huffman code (i.e., a set of characters and associated binary sequences) along with a binary sequence, and decode the binary sequence to its character representation.
입력
The first line of input will be an integer k (1 ≤ k ≤ 20), representing the number of characters and associated codes. The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10) representing the associated code of that character. You may assume that the character is an alphabet character (i.e., ‘a’…‘z’ and ‘A’..‘Z’). You may assume that the sequence of binary codes has the prefix-free property. On the k + 2nd line is the binary sequence which is to be decoded. You may assume the binary sequence contains codes associated with the given characters, and that the k + 2nd line contains no more than 250 binary digits.
출력
On one line, output the characters that correspond to the given binary sequence.
풀이
풀이 확인하기
입력을 받은 뒤 binary sequence를 key로 가지는 dictionary를 만든다. 그리고 0과 1로 이뤄진 문자열을 받아 queue로 만들어 하나씩 pop을 하면서 해당 데이터가 dictionary에 없다면 다시 pop해서 더하고, 해당 데이터가 dictionary에 있으면 변환을 하여 정답 문자열에 더한 뒤 pop한 데이터들을 전부 초기화해주는 과정을 반복한다.
import sys
from collections import deque
input = sys.stdin.readline
num = int(input())
data = {}
for _ in range(num):
a = input().strip().split()
data[a[1]] = a[0]
encode = deque(input().strip())
temp = ""
ans = ""
while True:
temp = temp + encode.popleft()
if temp in data:
ans = ans + data[temp]
temp = ""
if(len(encode) == 0):
break
print(ans)
-
[백준, python] 14621번 - 나만 안되는 연애
백준 문제풀이 시작
문제
깽미는 24살 모태솔로이다.
깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다.
미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.
이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.
사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.
만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.
이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.
입력
입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)
둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.
다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)
출력
깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)
풀이
풀이 확인하기
이번 문제는 1197번 문제와 거의 동일하다. 해당 링크.를 참조하자.
여기서 다른 점은 edge 추가 과정에서 edge가 연결하는 두 vertex가 둘 다 M이거나 W일 경우 추가하지 않고, 또한 MST를 만든 뒤 edge의 수가 vertex의 수 - 1가 아닐 경우 모든 학교가 연결되어있지 않다는 뜻이므로 -1을 출력한다.
import sys
input = sys.stdin.readline
def find(p, a):
if(p[a] != a):
p[a] = find(p, p[a])
return p[a]
def union(p, a, b):
a = find(p, a)
b = find(p, b)
if(a < b):
p[b] = a
else:
p[a] = b
v, e = map(int, input().split())
p = [0] * (v + 1)
edge = []
cost = 0
s = 0
for i in range(1, v+1):
p[i] = i
lis = input().strip().split()
for _ in range(e):
a, b, c = map(int, input().split())
if(lis[a-1] != lis[b-1]):
edge.append((c, a, b))
edge.sort()
for ed in edge:
c, a, b = ed
if(find(p, a) != find(p, b)):
union(p, a, b)
cost += c
s+=1
if(s != v-1):
print(-1)
else:
print(cost)
-
[백준, python] 1197번 - 최소 스패닝 트리
백준 문제풀이 시작
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
풀이
풀이 확인하기
해당 문제는 최소 스패닝 트리(MST)인지 확인하는 문제이다. MST를 구하기 위해 사용하는 알고리즘이 크루스칼 알고리즘(Kruskal Algorithm)인데, 이는 즉 해당 문제가 크루스칼 알고리즘을 구현하는 문제라고 볼 수 있는 것이다. 크루스칼 알고리즘을 위해 cycle을 판단하는 구조인 union-find 구조를 구현하고, 형태에 맞게 입력을 받은 뒤, 입력받은 edge를 가중치를 기준으로 오름차순 정렬을 해준다. 그리고 edge를 순회하며 만약 해당 edge를 추가했을 때 cycle이 발생하지 않는다면 해당 edge를 union하며 값을 추가한다.
(cycle이 발생하면 edge를 하나 삭제함으로써 가중치를 줄일 수 있기 때문.)
import sys
input = sys.stdin.readline
def find(p, a):
if(p[a] != a):
p[a] = find(p, p[a])
return p[a]
def union(p, a, b):
a = find(p, a)
b = find(p, b)
if(a < b):
p[b] = a
else:
p[a] = b
v, e = map(int, input().split())
p = [0] * (v + 1)
edge = []
cost = 0
for i in range(1, v+1):
p[i] = i
for _ in range(e):
a, b, c = map(int, input().split())
edge.append((c, a, b))
edge.sort()
for ed in edge:
c, a, b = ed
if(find(p, a) != find(p, b)):
union(p, a, b)
cost += c
print(cost)
-
[백준, python] 1002번 - 터렛
백준 문제풀이 시작
문제
조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.
이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.
조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.
출력
각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
풀이
풀이 확인하기
해당 문제에서 조규현과 백승환의 위치를 원의 중점, 류재명까지의 각각의 거리를 반지름, 그리고 류재명의 위치라 원의 교점이라고 바꾸면 문제가 쉽게 풀린다. 원의 교점이 발생하는 경우는
원이 같을 경우 교점은 -1
원이 외접할 경우 교점은 1
원이 내접할 경우 교점은 1
원이 밖에 떨어져 있으면 교점은 0
원이 안에 있으면 교점은 0
그 외에는 2
로 생각할 수 있다. 이를 조건에 따라 잘 분기해주면 풀 수 있다.
import sys
input = sys.stdin.readline
num = int(input())
for _ in range(num):
a = list(map(int, input().strip().split(' ')))
dist = abs((((a[4]- a[1])**2) + ((a[3]- a[0])**2)) ** (1/2))
maxd = 0
mind = 0
if(a[5]>a[2]):
maxd = a[5]
mind = a[2]
else:
maxd = a[2]
mind = a[5]
if(dist == 0 and maxd == mind):
print(-1)
elif(maxd + mind == dist):
print(1)
elif(maxd - mind == dist):
print(1)
elif(maxd + mind < dist):
print(0)
elif(dist + mind < maxd):
print(0)
else:
print(2)
-
[백준, python] 16139번 - 인간 - 컴퓨터 상호작용
백준 문제풀이 시작
문제
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.
‘문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.’
승재를 도와 특정 문자열 \(S\), 특정 알파벳 \(\alpha\)와 문자열의 구간 \([l,r]\)이 주어지면 \(S\)의 \(l\)번째 문자부터 \(r\)번째 문자 사이에 \(\alpha\)가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 \(0\)번째부터 세며, \(l\)번째와 \(r\)번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 \(q\)번 할 것이다.
입력
첫 줄에 문자열 \(S\)가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 \(q\)가 주어지며, 문제의 수는 1 \(\leq q\leq\) 200,000을 만족한다. 세 번째 줄부터 (\(q\)+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 \(\alpha_i\)와 \(0\leq l_i\leq r_i<|S|\)를 만족하는 정수 \(l_i,r_i\)가 공백으로 구분되어 주어진다.
출력
각 질문마다 줄을 구분해 순서대로 답변한다. \(i\)번째 줄에 \(S\)의 \(l_i\)번째 문자부터 \(r_i\)번째 문자 사이에 \(\alpha_i\)가 나타나는 횟수를 출력한다.
풀이
풀이 확인하기
해당 문제를 풀면서 알파벳을 입력받았을 때 얼마나 있는지 문자열을 그때그때 전부 순회하여 찾으면 O(N)의 시간이 걸리게 된다. 그러므로 좀 더 빠르게 계산을 하는 방법이 필요한데, 누적합을 사용하면 계산을 O(1) 시간 내에 계산할 수 있다.
누적합을 구하기 위해 배열을 하나 만든다. 그리고 배열에서 문자열을 순회하며 해당 알파벳이 나올 때마다 1씩 더해 계속 append 해준다. 그러면 몇번째 글자까지 해당 알파벳이 얼마나 나왔는지 알 수 있을 것이다.
하지만 문제에서는 특정 구간을 구해야 하는데, 이때 예를 들어 A[i, j]를 구하고 싶다면 누적합 배열을 B라 가정하면 B[j+1] - B[i]를 계산해주면 바로 구할 수 있다.
import sys
input = sys.stdin.readline
string = list(input().rstrip())
num = int(input())
ans = {}
for i in range(97, 123):
temp = 0
sum = [0]
for j in string:
if(chr(i) == j):
temp += 1
sum.append(temp)
ans[chr(i)] = sum
for _ in range(num):
inp = input().rstrip().split(' ')
sys.stdout.write(str(ans[inp[0]][int(inp[2])+1] - ans[inp[0]][int(inp[1])]) + '\n')
-
[백준, python] 1629번 - 곱셈
백준 문제풀이 시작
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
풀이
풀이 확인하기
문제를 얼핏 보면 매우 쉬운 문제같지만 시간 제한에 주목하면 평범한 방식으로는 절대 통과하지 못함을 알 수 있다. 그래서 우리는 중고등학교에서 배웠던 지수법칙을 응용할 것이다.
이때 지수법칙이란
\({x^n}\times{x^m} = {x^{n+m}}\)
인데 이를 제곱 식에 맞게 잘 응용하면
\[{x^n}= \begin{cases} x^{\frac{x}{2}}\times x^{\frac{x}{2}} & \text{if } \,\, n \% 2 = 0, \\ x^{\frac{x}{2}}\times x^{\frac{x}{2}}\times {x^1} & \text{if } \,\, n \% 2 = 1 . \end{cases}\]
의 형태로 바꿀 수 있다. 이렇게 계산을 할 경우 기존 거듭제곱보다 훨씬 적은 양의 계산만 가지고도 거듭제곱을 풀 수 있다.
이를 프로그램에 옮겨 문제가 원하는 요구사항대로 출력하면 풀 수 있다.
import sys
input = sys.stdin.readline
def mul(a, b, c):
if (b == 1):
return a % c
else:
s = mul(a, b//2, c)
x = s*s
if(b % 2 == 0):
return x % c
else:
return (x * mul(a, 1, c)) % c
a, b, c = map(int, input().split(" "))
print(mul(a, b, c))
P.S. 원래는 문제를 풀 때 mul 함수에선 거듭제곱만 구하고 이후 마지막 수로 나눈 나머지를 구했는데, 이렇게 할 경우 시간 초과가 발생한다. 그래서 함수 내에 옮기니까 시간 제한이 걸리지 않고 통과함을 알 수 있었다. 왜 그런지는 찾아보아야 할 듯 하다.
-
[백준, python] 5430번 - AC
백준 문제풀이 시작
문제
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다.
AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, “AB”는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, “RDD”는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.
배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
다음 줄에는 [x1, … ,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)
전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
풀이
풀이 확인하기
해당 문제를 풀며 R을 만나는 순간마다 뒤집을 경우 큰 문제가 발생한다. reverse 함수를 사용하면 리스트를 새로 다시 만든다고 생각하면 된다. 이렇게 되면 만약 예를 들어 RRRRRRRRRRRRR과 같이 R을 많이 쓸 경우 엄청난 시간 문제가 발생할 것이다. 그러므로 R을 마주칠 때마다 몇번 뒤집는지 계산하고, 이후 뒤집는 수가 홀수면 뒤집고, 아니면 안뒤집으면 한번만 뒤집으면 된다.
이 과정에서 D를 만났을 때 처리가 애매해지는데, 무작정 앞에서부터 지우면 RD같은 경우에 문제가 발생할 것이다. 그러므로 뒤집는 수를 여기서 다시 확인해서 홀수면 뒤집을 것이므로 맨 뒤에서, 짝수면 안뒤집으므로 맨 앞에서 pop을 한다. 이 때문에 우린 deque을 사용할 것이다.
또한 확인해줘야하는 요소가 일부 있는데, 먼저 리스트의 0의 경우 D는 불가능하지만 R은 가능하다. 그러므로 0이라고 무작정 error를 출력하는 것이 아닌 []로 리스트를 만들어줘야 한다.
그리고 출력을 잘 봐야 하는데, [1,2]처럼 리스트 사이에 공백이 존재하지 않는다. 그러므로 바로 리스트를 int형으로 바꿔 출력하면 안되고 join 함수를 사용하여 공백을 적절히 처리해준다.
import sys
from collections import deque
input = sys.stdin.readline
num = int(input())
answer = []
for _ in range(num):
is_Error = False
command = input().rstrip()
num1 = int(input())
lis = input().replace('[', ',').replace(']', ',').rstrip().split(',')[1:-1]
if(num1 == 0):
lis = []
else:
lis = deque(map(int,lis))
is_reverse = 0
for i in command:
if(i == "R"):
is_reverse += 1
elif(i == "D"):
if(len(lis) == 0):
is_Error = True
break
else:
if(is_reverse % 2 == 1):
lis.pop()
else:
lis.popleft()
if(is_Error):
print('error')
else:
if(is_reverse % 2 == 1):
lis.reverse()
print('['+','.join(map(str, lis))+']')
-
[백준, python] 22233번 - 가희와 키워드
백준 문제풀이 시작
문제
가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.
지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 N개가 존재합니다.
가희는 새로운 글을 작성할 때, 최대 10개의 키워드에 대해서 글을 작성합니다.
이 키워드들 중에 메모장에 있었던 키워드는 가희가 글을 쓴 이후, 메모장에서 지워지게 됩니다.
가희는 블로그에 글을 쓰고 나서, 메모장에 있는 키워드 개수가 몇 개인지 알고 싶습니다. 가희를 도와주세요.
입력
첫 번째 줄에 가희가 메모장에 적은 키워드 개수 N, 가희가 블로그에 쓴 글의 개수 M이 공백으로 구분해서 주어집니다.
2번째 줄부터 N+1번째 줄까지 메모장에 적은 키워드 N개가 주어집니다.
N+2번째 줄부터 N+M+1번째 줄까지, 가희가 쓴 글과 관련된 키워드가 , (쉼표)로 구분해서 주어집니다. 공백으로 구분되지 않음을 유의해 주세요.
출력
x번째 줄에는 x번째 글을 쓰고 난 후에 메모장에 남아 있는 키워드의 개수를 출력해 주세요.
풀이
풀이 확인하기
입력을 받은 뒤 dictionary에 입력받은 키워드들을 담는다. 이후 사용한 키워드들이 주어질 때 요소들이 dictionary에 있다면 제거하고 남은 키워드들의 개수를 따로 담아 출력한다.
import sys
input = sys.stdin.readline
num1, num2 = map(int, input().strip().split(' '))
line = {}
answer = []
for _ in range(num1):
a = input().strip()
line[a] = ""
for _ in range(num2):
unused = 0
b = input().strip().split(',')
for i in range(0, len(b)):
if b[i] in line:
del line[b[i]]
answer.append(len(line))
for i in answer:
print(i)
-
[백준, python] 9996번 - 한국이 그리울 땐 서버에 접속하지
백준 문제풀이 시작
문제
선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다.
호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다.
선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.
어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.
패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.
파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, “abcd”, “ad”, “anestonestod”는 모두 패턴 “a*d”와 일치한다. 하지만, “bcd”는 일치하지 않는다.
패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.
출력
총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 “DA”, 일치하지 않으면 “NE”를 출력한다.
참고로, “DA”는 크로아티어어로 “YES”를, “NE”는 “NO”를 의미한다.
풀이
풀이 확인하기
해당 문제는 정규식으로 풀면 쉽게 풀 수 있다. 입력받은 뒤 정규식으로 변환하고, 이후 입력받은 뒤 매칭을 시켜 매칭시킨 결과가 입력받은 문자와 동일하면 DA, 아니면 NE를 출력하도록 한다.
import re
import sys
input = sys.stdin.readline
num = int(input())
toFind = input().strip().split("*")
reg1 = toFind[0]+".*"+toFind[1]+"+"
reg = re.compile(reg1)
lis = []
for _ in range(num):
b = input().strip()
a = reg.match(b)
if(a and a.group() == b):
print("DA")
else:
print("NE")
-
[백준, python] 18870번 - 좌표 압축
백준 문제풀이 시작
문제
수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.
출력
첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.
풀이
풀이 확인하기
입력을 받은 뒤 리스트를 복사하고, 해당 리스트를 set으로 바꿔 중복되는 요소를 지우고, 다시 리스트로 바꾼 뒤 해당 리스트를 정렬해서 순서를 추출했다. 이후 기존 리스트와 순서를 비교하여 출력한다. 이때 비교를 하는 과정에서 그냥 반복문으로 비교하면 시간 초과가 발생하므로 이분 탐색으로 비교한다.
import sys
import copy
input = sys.stdin.readline
num = int(input())
lis = list(map(int, input().strip().split(" ")))
lis2 = copy.deepcopy(lis)
lis2 = list(set(lis2))
lis2.sort()
for i in range(0, len(lis)):
left = 0
right = len(lis2)-1
while(left <= right):
mid = (left+right)//2
if (lis2[mid] == lis[i]):
print(mid)
break
elif (lis2[mid]>lis[i]):
right = mid-1
else:
left = mid+1
P.S. 지금 보니 복사 이후 set으로 바꾸고 다시 리스트로 바꾸는 과정이 매우 비효율적인 것 같다. 입력받는 과정에서 저장을 딕셔너리로 저장한 뒤 key값만 추출하면 조금 더 빠르게 할 수 있지 않을까 싶다.
-
[백준, python] 7785번 - 회사에 있는 사람
백준 문제풀이 시작
문제
상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 “enter”나 “leave”가 주어진다. “enter”인 경우는 출근, “leave”인 경우는 퇴근이다.
회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
출력
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.
풀이
풀이 확인하기
파이썬에서 자체 제공하는 딕셔너리를 사용하여 문제를 해결했다. 딕셔너리의 key값에 이름, value에 enter 또는 leave를 입력받아 저장하고, 딕셔너리를 순회하며 value가 enter인 key만 리스트로 가져와 정렬하고 출력한다.
import sys
input = sys.stdin.readline
company = {}
num = int(input())
for _ in range(num):
people = input().strip().split(" ")
company[people[0]] = people[1]
ans = []
for i in company:
if(company[i] == "enter"):
ans.append(i)
ans.sort(reverse=True)
for i in range(len(ans)):
print(ans[i])
-
[백준, python] 1448번 - 삼각형 만들기
백준 문제풀이 시작
문제
세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다.
입력
첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 작거나 같은 자연수이다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
첫째 줄에 삼각형 세 변의 길이의 합의 최댓값을 출력한다. 만약 삼각형을 만들 수 없으면 -1을 출력한다.
풀이
풀이 확인하기
삼각형은 가장 큰 변을 제외한 두 변의 합이 가장 큰 변의 크기보다 커야 한다. 리스트를 입력받아 내림차순으로 정렬한 뒤 두번째, 세번째 요소를 더한 값이 첫번째 요소보다 작거나 같다면 다음으로, 크다면 결과를 저장한다.
import sys
input = sys.stdin.readline
num = int(input())
lis = []
for _ in range(0, num):
a = int(input())
lis.append(a)
lis.sort(reverse=True)
ans = -1
is_Find = False
for i in range(0, len(lis)-2):
if(lis[i] < (lis[i+1] + lis[i+2])):
ans = lis[i] + lis[i+1] + lis[i+2]
break
print(ans)
-
[백준, python] 2644번 - 촌수 계산
백준 문제풀이 시작
문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다.
이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.
풀이
풀이 확인하기
해당 문제는 dfs 함수 내에서 재귀적으로 연산을 하였다. 입력을 받은 뒤 정답 리스트를 만들고, 방문이 이뤄질 때마다 방문 수를 증가시키고, 사람을 찾을 경우 리스트에 방문 수를 담는다.
import sys
input = sys.stdin.readline
vertex = int(input())
people1, people2 = map(int, input().split(' '))
edge = int(input())
graph = [[] for _ in range(vertex + 1)]
visited = [0] * (vertex + 1)
for _ in range(edge):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
ans = []
def dfs(start, num):
num+=1
visited[start] = 1
if(people2 == start):
ans.append(num)
for i in graph[start]:
if not visited[i]:
dfs(i, num)
dfs(people1, 0)
if(len(ans) != 0):
print(ans)
else:
print(-1)
-
-
[백준, python] 4948번 - 베르트랑 공준
백준 문제풀이 시작
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
풀이
풀이 확인하기
해당 문제는 소수를 일일히 검사하려는 순간 시간 초과가 발생함을 확인했다.
예를 들어 10000과 10001을 입력했을 때 10000에서부터 20000까지 검사한 뒤 10001에서 20002까지 검사하는 과정에서 10000을 검사할 때 중첩된 부분이 발생하는 것이다.
그래서 n의 최대값인 123456의 2를 곱한 만큼의 값을 에라토스테네스의 체로 검사를 하여 전부 True 및 False를 미리 계산해놓고, 이후에 검사하는 과정에서는 계산 결과를 그대로 가져다 쓰기만 하였다.
import math
import sys
input = sys.stdin.readline
sieve = [True] * 246912
m = int(math.sqrt(246912))
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, 246912, i):
sieve[j] = False
sieve.append(False)
num = 0
answer = []
while True:
is_prime = 0
num = int(input())
if(num == 0):
break
for i in range(num+1, (2*num)+1):
if(sieve[i] == True):
is_prime += 1
answer.append(is_prime)
for i in range(0, len(answer)):
print(answer[i])
-
[백준, python] 1735번 - 분수 합
백준 문제풀이 시작
문제
분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.
두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.
입력
첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.
출력
첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.
풀이
풀이 확인하기
해당 문제는 두 수의 최대공약수를 구하는 방법인 유클리드 호제법에 대한 이해가 필요하다. 유클리드 호제법이란 두 수가 나눠떨어지지 않는다면 두 수를 나눈 나머지를 구하고, 그 수와 나머지를 나누는 과정을 반복해 나가며 나누어 떨어질 때까지 계산해나가면 그 수가 최대공약수가 되는 것이다.
자세한 내용은
링크
를 참조하면 좋을 것 같다.
def euc(x, y):
if((y % x) == 0):
return x
else:
return euc(y % x, x)
a, b = map(int, input().split(' '))
c, d = map(int, input().split(' '))
e = a*d + c*b
f = b*d
g = euc(e, f)
print(int(e/g), end=" ")
print(int(f/g))
-
[백준, python] 1260번 - DFS와 BFS
백준 문제풀이 시작
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
풀이 확인하기
이번 문제는 그래프 순회 방식 중 dfs와 bfs를 사용하여 문제를 해결해야 한다. dfs는 재귀, bfs는 queue를 사용하여 문제를 해결하였다.
링크
를 참조하여 문제를 풀었다.
import sys
input = sys.stdin.readline
def dfs(start):
visited[start] = 1
print(start, end=" ")
for i in graph[start]:
if not visited[i]:
dfs(i)
def bfs(start):
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
visited[i] = True
queue.append(i)
vertex, edge, first = map(int, input().split())
graph = [[] for _ in range(vertex + 1)]
for _ in range(edge):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in graph:
i.sort()
a = []
visited = [0] * (vertex + 1)
dfs(first)
print()
visited = [0] * (vertex + 1)
bfs(first)
P.S. BFS 및 DFS 알고리즘은 이론으로만 공부하고 실제 코드로 짜본 적이 없어서 이번 풀이는 인터넷에 의존하여 거의 복사 붙여넣기 수준으로 이뤄졌다. 당분간 그래프 탐색을 시작으로 알고리즘 공부를 위주로 해야하지 않을까 싶다.
-
[백준, python] 1032번 - 명령 프롬프트
백준 문제풀이 시작
문제
시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.
dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. “dir 패턴”과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.
이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 “.” 그리고 “?”만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.
입력
첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳 소문자와 ‘.’ 로만 이루어져 있다.
출력
첫째 줄에 패턴을 출력하면 된다.
풀이
풀이 확인하기
해당 문제는 입력으로 들어오는 문자열의 길이가 모두 같다는 점을 가지고 쉽게 풀 수 있다.
숫자를 입력받고 입력받은 숫자만큼 반복문을 통해 문자열을 리스트에 담는다.
그리고 들어온 문자열의 길이만큼 반복문을 돌고, 반복문 내에서 리스트를 순회하며 해당 문자열의 인덱스가 모든 문자열이 공통으로 가진 값인지 확인한 뒤, 같으면 정답 문자열에 해당 글자를, 다르면 정답 문자열에 ?를 더한다.
stringList = []
num = int(input())
for i in range(0, num):
string = input()
stringList.append(string)
answer = ""
for i in range(0, len(stringList[0])):
temp = True
for j in range(0, len(stringList)):
if(stringList[0][i] != stringList[j][i]) :
temp = False
break
if(temp == True) :
answer = answer + stringList[0][i]
else:
answer = answer + "?"
print(answer)
Touch background to close
개발하는 쿼카
