본문 바로가기

분류 전체보기213

백준 3015: 오아시스 재결합(python) 문제어렵다... "n명의 사람들 a, b, c, ... n이 서 있을 때 b의 키가 a보다 크다면 a는 b부터 n까지의 모든 사람을 보지 못함"의 아이디어를 떠올리는 게 중요한 듯 하다.N명의 사람들을 arr 배열에 저장하고, arr의 원소 i에 대해 i 다음의 사람들을 스택에 넣었다 빼면서 볼 수 있는 사람 수를 카운트한다.for i in arr: # i와 stack[-1]에 대해 카운트 case 1: 현재 사람이 스택 최상단의 사람보다 키가 클 경우while stack and i > stack[-1][0] # stack에는 (키, 개수) 형태로 저장 res += stack.pop()[1] # 다음 사람을 제거하고(조합에 포함되었으므로) 그 카운트를 결과에 추가현재 사람(i)이 스택 최상단 사람(sta.. 2025. 3. 2.
백준 1504: 특정한 최단 경로(python) 문제풀이 출발 지점 s와 도착 지점 e에 대해 v1, v2를 모두 지나는 최단 경로는 ①s -> v1 -> v2 -> e 또는 ②s -> v2 -> v1 -> e이다.출발 지점을 인자로 전달받는 dijkstra() 함수를 작성해 다익스트라 알고리즘을 사용하면def dijkstra(start): dist = [sys.maxsize for _ in range(N + 1)] visited = [False for _ in range(N + 1)] pq = PriorityQueue() dist[start] = 0 pq.put((0, start)) # pq = (거리, 노드) while pq.qsize() > 0: d, s = pq.get() if visi.. 2025. 2. 28.
백준 1238: 파티(python) 문제풀이 각 집에 대해, X에서 집으로 가는 경로와 집에서 X로 가는 경로를 더한 값이 최대인 집을 찾아야 한다. X->집과 집->X를 모두 구해야 하므로 모든 지점에서 다른 모든 지점까지의 최단 거리를 구하기 위해 플로이드-워셜 알고리즘을 사용하였으나, 플로이드-워셜 알고리즘의 시간 복잡도는 노드 개수 V에 대해 \(O(V^3)\)이므로 시간 초과 오류가 발생한다.더보기플로이드-워셜 코드 참고import sysinput = sys.stdin.readlineN, M, X = map(int, input().split()) # N=학생(노드), M=도로(간선), X=목적지(노드)dist = [[sys.maxsize for _ in range(N + 1)] for _ in range(N + 1)]for i i.. 2025. 2. 28.
백준 1644: 소수의 연속합(python) 문제풀이 에라토스테네스의 체 알고리즘을 사용해 N 이하 소수들을 배열에 저장한 후, 해당 배열에서 투 포인터 기법으로 부분합을 구하여 풀이한다.a = [False, False] + [True] * (N - 1) # [0, 1, 2, 3, ... N]primes=[]for i in range(2, N + 1): if a[i]: primes.append(i) for j in range(2 * i, N + 1, i): a[j] = False에라토스테네스의 체로 N 이하 소수를 구해 primes 배열에 저장한다.primes.sort()이후 투 포인터를 사용할 것이므로 primes 배열을 오름차순 정렬해 준다.left, right = 0 # 왼쪽, 오른쪽 인덱스res = 0while.. 2025. 2. 24.
백준 16724: 피리 부는 사나이(python) 문제풀이 지도의 각 칸을 노드로, 성우가 설정한 방향을 간선으로 생각하고 union-find를 사용해 유향 그래프 상 집합을 판별하여 풀이하는 문제다. 각 집합 당 하나의 SAFE ZONE을 배치한 것이 회원들이 지도 어느 구역에 있더라도 SAFE ZONE에 들어갈 수 있는 최소 개수이다.N, M = map(int, input().split())maps = []for _ in range(N): maps.append(list(map(str, input().strip())))입력은 maps 배열에 저장해 주었다. 이후 저장된 UDLR을 간선으로 변환한다.idx = 0graph = [[] for _ in range(N * M)]for i in range(N): for j in range(M): .. 2025. 2. 24.
백준 1266: 다각형의 면적(python) 문제풀이 중학교에서 배우는 사선 공식(신발끈 공식)을 사용하면 간단히 풀이할 수 있다. 정석적인 풀이가 맞는지는 모르겠으나 일단 이렇게 풀었다(...)import sysinput = sys.stdin.readlineN = int(input())vertex = []for _ in range(N): vertex.append(list(map(int, input().split())))vertex.append(vertex[0])res = 0for i in range(N): res += vertex[i][0]*vertex[i+1][1] - vertex[i+1][0]*vertex[i][1]print(abs(res)/2)사선 공식을 그대로 사용해주면 되므로 추가적인 설명은 생략 2025. 1. 8.

티스토리툴바