백준77 백준 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. 백준 1647: 도시 분할 계획(python) 문제풀이 MST를 구하고, MST 중 가중치가 가장 큰 간선을 절단해 마을을 2개로 분리하면 된다.MST를 구하기 위해 Kruskal 알고리즘과 Prim 알고리즘을 사용할 수 있는데, 2가지 방법으로 모두 구현해 보았다.1. Kruskal 알고리즘N, M = map(int, input().split())edges = [] #간선 리스트에 저장for _ in range(M): u, v, w = map(int, input().split()) edges.append((u, v, w))edges 배열에 출발 노드, 도착 노드(무향 그래프지만 편의상 출발-도착으로 지칭), 가중치를 저장한다. Kruskal 알고리즘을 사용하기 위해 이와 같이 저장하였고, 추후 Prim 알고리즘으로 풀이할 때는 연결 리.. 2025. 1. 8. 백준 2343: 기타 레슨(python) 문제풀이 이진 탐색을 사용해 풀이하는 문제다. 파이썬의 bisect 라이브러리를 사용해 별도의 구현 없이 풀이할 수 있다. 이때 주의해야 하는 것은 블루레이 녹화 시 강의의 순서가 바뀌어서는 안 된다는 점인데, 초기 입력값을 정렬할 수 없으므로 이진 탐색을 수행하기 위해서는 배열이 먼저 정렬되어야 한다는 조건을 만족할 수 없다. 이진 탐색 문제로 분류되는 것을 보면 어떤 식으로든 정렬된 배열을 다루어야 할 것이므로, 관점을 바꾸어 입력된 배열이 아닌 입력값의 부분합 배열 sum[]을 이진 탐색에 사용할 수 있다. sum[i] = arr[0:i]인 sum은 항상 오름차순 정렬된 배열이므로 이진 탐색이 가능하다.문제를 풀이할 때 부분합 배열 sum[]을 직접 생성해 사용하지는 않지만, 전반적인 아이디어는 이.. 2024. 11. 18. 백준 17298: 오큰수(java) 문제풀이 수열을 저장할 배열 A[]와 스택 stack을 사용하고, 이때 stack의 원소로는 배열의 원소가 아닌 인덱스가 들어간다. for문을 순회하며 A[stack.peek()]과 A[i]을 비교하고, A[stack.peek()] 자세한 내용은 예제 1을 풀이하며 설명하겠다. i = 0스택이 비어 있으므로 스택에 첫 번째 인덱스를 push한 후 시작한다.0 i = 1stack.isEmpty() = false이므로 A[stack.peek()]과 A[i]을 비교한다. A[0] (=3) 1 i = 2stack.isEmpty() = false이므로 A[stack.peek()]과 A[i]을 비교한다. A[1] (=5) 12 i = 3stack.isEmpty() = false이므로 A[sta.. 2024. 10. 13. 이전 1 2 3 4 5 ··· 13 다음
