본문 바로가기

👨‍💻📱✍️🎢314

BOJ 16472 - 고냥이 문제 백준 온라인 저지 - 16472번 풀이 과정 최대 N 개의 종류의 알파벳을 가진 연속된 문자열중에서 인식할 수 있는 최대 문자열의 길이를 구하는 문제입니다. 최대 문자열의 길이가 100,000 이기 때문에 완전 탐색 을 이용할 경우 시간 초과가 발생하게 됩니다. 대신 투 포인터 를 이용해서 N 을 초과할 경우 알파벳의 종류가 N 보다 작아질 때까지 left 를 증가시키고 N 보다 같거나 작을 경우 right 을 증가시키는 방법을 사용하면 최적화가 가능합니다. 이때 각 알파벳의 등장 횟수를 기록하기 위해 deque 를 값으로 사용하는 dict 를 사용했습니다. 각각의 deque 에는 알파벳의 인덱스가 저장되며 알파벳의 종류가 N 보다 많아졌을 시 가장 왼쪽에 있는 알파벳을 키로 하는 deque 에서 .. 2021. 3. 14.
BOJ 17086 - 아기 상어2 문제 백준 온라인 저지 - 17086번 풀이 과정 아기 상어에 도달하는 가장 가까운 거리를 안전 거리 라고 표현합니다. 이 안전 거리 중에서 가장 큰 값을 찾아야하기 때문에 상어가 없는 각 칸마다 BFS 를 수행해서 안전 거리 를 계산하면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dx = [0, 0, 1, -1, -1, -1, 1, 1] dy = [1, -1, 0, 0, 1, -1, 1, -1] def bfs(x, y): visit = [.. 2021. 3. 8.
BOJ 13335 - 트럭 문제 백준 온라인 저지 - 13335번 풀이 과정 다리에 무게 제한이 있을 때 모든 트럭이 다리를 건너서 다른 지역으로 넘어가는 최단 시간을 찾는 문제입니다. 현재 다리에 존재하는 모든 트럭의 무게를 추척하고 트럭의 시간을 별도의 배열로 관리해서 구현했습니다. 여기서 next 변수는 현재 다리를 건너기 위해 대기중인 트럭을 나타냅니다. 코드 import sys from collections import deque N, W, L = list(map(int, sys.stdin.readline().split())) weights = list(map(int, sys.stdin.readline().split())) def solution(): goal, next = W + 1, 1 on_bridge = deque.. 2021. 3. 8.
BOJ 6497 - 전력난 문제 백준 온라인 저지 - 6497번 풀이 과정 모든 도시를 최소 비용으로 연결하는 방법을 찾는 문제입니다. 크루스칼 알고리즘 을 활용해서 MST 를 구축하고 절약 가능한 비용을 계산하면 됩니다. 코드 import sys import heapq sys.setrecursionlimit(10**6) parent = [] def union(u, v): u, v = find(u), find(v) if u == v: return parent[u] = v def find(u): if parent[u] == u: return u parent[u] = find(parent[u]) return parent[u] def solution(N, edges): ret = 0 for _ in range(N): cost, src,.. 2021. 3. 8.
BOJ 6156 - Cow Contest 문제 백준 온라인 저지 - 6156번 풀이 과정 두 소들 간의 싸움 경기 결과가 주어질 때 순위를 결정할 수 있는 소들의 수를 구하는 문제입니다. 특정 소의 순위를 결정하기 위해서는 해당 소에게 진 소들의 수와 해당 소를 이긴 소들의 합이 N - 1 이어야 합니다. 때문에 각 소들을 그래프의 정점이라고 생각한다면 모든 소들 사이의 도달 가능성을 플로이드 와샬 알고리즘을 이용해 파악하고 각 소들에 대해서 특정 소 A 에 도달 가능한 정점의 수와 A 에서 도달 가능한 소들의 수를 세어주면 됩니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) results = [list(map(int, sys.stdin.readline().split().. 2021. 3. 8.
BOJ 9625 - BABBA 문제 백준 온라인 저지 - 9625번 풀이 과정 동적 계획법 을 활용한 문제입니다. 각 문자가 일정 규칙으로 변환되는데 이를 활용해서 점화식을 세우면 됩니다. 저 같은 경우 문장의 길이가 피보나치 수열을 따르면서 B 의 개수도 피보나치 수열의 개수대로 증가된다는 것을 이용해서 문제를 풀었는데 다른 분들의 풀이를 보니 그냥 A 와 B 각각에 대해서 점화식을 세우고 순회를 하면 간단하게 해결할 수 있었습니다. K 가 작기 때문에 완전 탐색 으로 구현해도 풀 수 있을 것 같기는 한데 이후에 비슷한 유형에 대비해서 접근 방법을 기억해놔야 할 것 같습니다. 코드 K = int(input()) def solution(): dp = [-1] * (K + 1) dp[0], dp[1] = 1, 1 for i in ran.. 2021. 3. 8.

티스토리툴바