BOJ14 [BOJ 1477] 휴게소 세우기(c++) https://www.acmicpc.net/problem/1477 문제 개요고속도로 길이 L에 N개의 휴게소가 주어졌을 때, M개를 추가로 지어 휴게소 없는 구간의 최댓값을 최소화하는 문제입니다.(0 ≤ N ≤ 50)(1 ≤ M ≤ 100)(100 ≤ L ≤ 1,000)문제 풀이파라메트릭 서치(이분탐색)로 해결하였습니다."휴게소 없는 구간의 최댓값"을 이분탐색의 대상으로 설정하고, 해당 최댓값 x가 주어졌을 때 M개 이하의 휴게소로 모든 구간을 x 이하로 나눌 수 있는지를 check 함수로 판단합니다.정렬된 휴게소 배열을 순서대로 순회하며, 현재 위치에서 다음 휴게소까지의 거리가 x를 초과할 경우 중간에 휴게소를 추가추가 횟수가 M을 초과하면 불가능, 이하면 가능고속도로 끝(L)도 배열에 포함시켜 마지막.. 2026. 3. 6. [BOJ 23355] 공장(c++) https://www.acmicpc.net/problem/23355 문제 개요n개의 건물과, n - 1개의 도로가 있고, q개의 입력을 받아 다음 쿼리를 해결해야 합니다.1 i j k: k 번 건물이 공사 중일때, i 번 건물에서 j 번 건물로 이동할 수 있는가? (1 )2 i j k l: k 번 건물과 l 번 건물을 잇는 도로가 공사 중일때, i 번 건물에서 i 번 건물로 이동할 수 있는가? 동원이가 고른 도로 중 k 번 건물과 l 번 건물을 잇는 도로가 존재함이 보장된다. (1 )문제 풀이간선의 수가 n - 1인 연결 그래프이므로 반드시 트리 형태로 만들어집니다.(사이클이 없음)https://doyun98.tistory.com/94 [BOJ 15480] LCA와 쿼리(c++)https://www.ac.. 2025. 10. 24. [BOJ 14925]목장 건설하기(c++) https://www.acmicpc.net/problem/14925 문제 개요m x n 땅에서 정사각형 땅에 목장을 건설하려 한다. 땅에는 들판, 나무, 돌이 있고 들판에만 목장을 지을 수 있다. 목장을 가장 크게 지을 수 있는 경우의 한 변의 길이 L을 출력하자. (1 행렬의 원소 0은 들판 1은 나무 2는 돌 문제 풀이행렬에서 0인 부분으로 만들 수 있는 가장 큰 정사각형을 구해야 하는 문제이다. 완전 탐색으로 이 문제를 접근할 경우 한점을 왼쪽 대각선 위로 보고 만들 수 있는 정사각형의 최대 크기를 확인해야 한다. 이는 매우 오래 걸리고, 시간 초과가 나게 된다.해당 문제는 다이나믹 프로그래밍을 통해 간단히 해결할 수 있다. 만약 (x, y)가 0이라면 (x-1, y)와 (x, y-1), (x-1.. 2024. 10. 31. [BOJ 13505] 두 수 XOR(c++) https://www.acmicpc.net/problem/13505 문제 개요N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성해야 한다.즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다. (2 (0 문제 풀이트라이 자료구조를 활용해 풀이했다.각 수를 31bit의 2진수로 변환해 트라이에 담아준다. 그리고 그 수를 활용해 만들 수 있는 가장 큰값을 트라이를 순회하며 찾아준다. 저장된 값과 현재의 값을 XOR했을 때, 높은 자리부터 탐색했을 때 1을 만들 수 있을 때 만들면서 내려가면 최댓값을 찾을 수 있다.예를 들어, 000101을 삽입한다 했을때, 111010이 저장되어 있다면 최댓값은 1111111이 될 것이다. .. 2024. 10. 14. [BOJ 16978]수열과 쿼리 22(c++) https://www.acmicpc.net/problem/16978 문제 개요길이가 n인 수열에서 m개의 쿼리를 수행하는 프로그램을 작성하면 된다. 1번 쿼리 - 1 x v: Ax = v로 변경 2번 쿼리 - 2 k i j: k번째 1번 쿼리가 적용되었을 때에, Ai, Ai+1, ..., Aj까지의 합을 출력 (1 (1 문제 풀이구간의 합을 저장하는 세그먼트 트리를 구현하여 해결하는 문제이다. *세그먼트 트리 설명 https://doyun98.tistory.com/37 세그먼트 트리(c++)세그먼트 트리란?배열에서 구간에 대한 정보를 효율적으로 관리(구간합, 최솟값, 최댓값 등)하기 위한 트리 구조의 자료구조이다. 특정 배열의 구간합을 구한다고 해보자인덱스012345678데이터3doyun98.. 2024. 9. 22. [BOJ 1854] K번째 최단경로 찾기 https://www.acmicpc.net/problem/1854 문제 설명n개의 도시들을 연결하는 m개의 도로가 있다. 1번 도시부터 모든 도시까지의 k번째 최단 거리를 구하라 (1 (0 (1 문제 풀이아이디어: 각 노드에 도착하는 시간들을 낮은 순서대로 k개를 가지고 있으면, k번째 최단거리를 알 수 있다. 다익스트라 알고리즘을 이용해 거리를 구하며, 각 도시마다 우선순위 큐를 하나씩 두어 도착한 시간을 k개까지 기록한다.=> 현재 도시까지 도착한 시간의 갯수가 k개일 경우, 도시의 최대 시간보다 작을 경우 pop후 push=> 도착한 시간의 갯수가 k보다 작을경우 push 도시마다 우선순위 큐의 크기가 k보다 작은 경우는 k번째 도착을 못하는 것이므로 -1을 출력한다. 그 외에는 우선순위 큐의 .. 2024. 9. 1. 이전 1 2 3 다음
