본문 바로가기

백준77

백준 1074: Z(python) 문제풀이 2x2 배열이 될 때까지 계속 분할하며 순서를 카운트하는 전형적인 분할 정복 문제이다. 아래와 같이 nxn 크기 배열 원소들의 방문 순서를 계산하는 visit() 함수를 정의한다.def visit(n, x, y): global count if n == 2: # 최소 단위 if c not in (x, x + 1) or r not in (y, y + 1): count += 4 else: if c == x and r == y: print(count) elif c == x + 1 and r == y: print(count + 1) elif c == x and r == y + 1: .. 2025. 7. 1.
백준 14500: 테트로미노(python) 문제풀이 dfs로 풀이할 수도 있다던데, 그냥 브루트포스로 풀었다.다섯 종류의 테트로미노를 회전 및 대칭하여 만들 수 있는 모양은 위의 열아홉가지이며, 이들 전부를 배열에 미리 세팅해 놓고 for문 순회하며 모든 경우를 탐색한다.moves = [ # (dx, dy) # ㅡ [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)], # ㅁ [(0, 0), (0, 1), (1, 0), (1, 1)], # L [(0, 0), (-1, 0), (-1, -1), (-1, -2)],# 1 [(0, 0), (1, 0), (1, -1), (1, -2)], # 2 [(0, 0), (0, 1), (-1, .. 2025. 6. 30.
백준 7453: 합이 0인 네 정수(python) 문제풀이 백준 분류 상으로는 이분 탐색을 사용하는 문제라 되어 있으나 다소 다르게 풀이이분 탐색 버전으로 풀어보지 않아서 무엇이 더 효율적인 풀이인지는 모르겠다.A, B, C, D, = [], [], [], []for i in range(n): arr = list(map(int, input().split())) A.append(arr[0]) B.append(arr[1]) C.append(arr[2]) D.append(arr[3])일단 입력을 열로 분리해서 A, B, C, D 배열을 각각 만들어 주었다. 생략해도 무방한 단계지만 직관성을 위해... A, B 원소의 조합을 구한 뒤 해당 원소와 절댓값이 같고 부호가 다른 값을 C, D 조합에서 찾는 방식으로 풀이한다.A, B, C,.. 2025. 6. 23.
백준 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.

티스토리툴바