본문 바로가기

분류 전체보기

 (191)
자동차경주( BOJ 2611 ) 문제(2004 중등) : https://www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 문제 파악하기 1번 지점부터 자동차가 출발해서 1번 지점으로 되돌아오는 여러 경로 중 점수를 가장 많이 쌓는 경로를 찾는 문제입니다. 모든 경로는 같은 지점을 도달하지 않게 설계되어있으며, 어느 지점에서든 1번 지점으로 돌아올 수 있다고 합니다. 이는 곧 cycle이 없다고 해석할 수 있습니다. 따라서 가장 먼저 생각할 수 있는 방법은 우선순위 큐를 사용해서 1번..
불만 정렬( BOJ 5012 ) 문제 : https://www.acmicpc.net/problem/5012 5012번: 불만 정렬 정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i aj > ak(i
숨바꼭질 5( BOJ 17071 ) 문제 : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 파악하기 수빈이가 동생을 찾는데 걸리는 최소 시간을 구하는 문제입니다. 동생은 매초 1만큼 가속을 받아 이동하며, 수빈이는 현재 위치에서 ±1 또는 x2 만큼 이동할 수 있습니다. 이 문제에서 중요한 점은 수빈이가 항상 최선의 동선으로만 이동하지 않는다는 것입니다. 예를 들어, 수빈이가 17에 있으며 동생이 5에 있다고 가정해봅시다. 이 경우, ..
The Sound of Silence( BOJ 2433 ) 문제 : https://www.acmicpc.net/problem/2433 2433번: The Sound of Silence 첫째 줄에 샘플의 수 n (1 ≤ n ≤ 1,000,000), m (1 ≤ m ≤ 10,000), c (0 ≤ c ≤ 10,000)가 주어진다. 둘째 줄에는 각 샘플의 값 ai가 주어진다. (0 ≤ ai ≤ 1,000,000 for 1 ≤ i ≤ n) www.acmicpc.net 문제 파악하기 최솟값과 최댓값의 차이가 C이하인 M개의 연속된 숫자가 있는지 탐색하는 문제입니다. 최대 1,000,000개의 숫자에 대해 10,000개의 연속된 숫자가 만족하는지 확인해야하는 문제이기에 완전탐색으로는 해결할 수 없습니다. 그렇기에 특정 범위에서 최댓값과 최솟값을 찾아주는 알고리즘을 사용해야..
히스토그램( BOJ 1725 ) 문제 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 파악하기 히스토그램(막대 그래프) 내부의 가장 큰 직사각형의 넓이를 구하는 문제입니다. 중첩 반복문을 사용해서 나올 수 있는 모든 구간의 내부 직사각형을 구할 수도 있지만 N의 크기가 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 여러 가지 효율적인 알고리즘 중에서 가장 기본적인 방법인 분할 정복을 활용해서 문제를 풀어봅시다. 문제 해결..
다이어트( BOJ 19942 ) 문제 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 파악하기 제시된 영양분을 만족할 수 있도록 식자료를 선택하되, 비용이 가장 작아지는 방법을 찾는 문제입니다. 식자료의 개수(N)이 최대 15개 입력되기 때문에 모든 경우의 수를 탐색하는 방법을 사용할 수 있습니다. 문제 해결하기 우선, 식재료를 선택할 수 있는 모든 경우의 수를 탐색합니다. 여러 가지 방법이 있지만 가장 직관적인 방법은 함수를 사용하는 방법이라고 생각합니다. 함수를..
햄버거 분배( BOJ 19941 ) 문제 : https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 문제 파악하기 햄버거와 사람이 번갈아 위치했을 때, 햄버거를 먹을 수 있는 사람의 최댓값을 구하는 문제입니다. 각각의 사람들은 자신의 위치에서 K만큼 떨어진 위치의 햄버거까지 먹을 수 있으며, 누군가 먹은 햄버거는 먹을 수 없습니다. 이렇게 모든 사람이 동일한 범위(K) 안의 햄버거를 먹을 수 있다면 우리는 가장 왼쪽에 위치한 햄버거부터 하나씩 사람에게 할당하는 방법을 사용할 수 있습니..
대기업 승범이네( BOJ 17831 ) 문제 : https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 문제 파악하기 승범이네 회사의 사원들 중 멘토와 멘티를 적절하게 선택해서 최대의 시너지 효과를 구하는 문제입니다. 승범이네 회사 구조는 트리 구조로 되어있으며 사수와 부사수 관계를 가지고 있는 사원을 멘토-멘티로 선정할 수 있습니다. 결국 이 문제는 현재 노드와 자식 노드를 멘토-멘티로 선정할 것인지, 아니면 현재 노드를 제외할지 탐색해야 하는 문제로 바꿀 ..

티스토리툴바