문제 노트/정올 (47) 썸네일형 리스트형 그래프 균형 맞추기( BOJ 22344 ) 문제 : https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 문제 파악하기 그래프 내 간선의 가중치가 주어질 때, 그래프의 균형을 맞출 수 있는 여러 가지 방법 중 모든 정점 가중치 값의 절댓값 합이 가장 작은 경우를 구하는 문제입니다. 그래프의 균형은 두 정점을 연결하는 간선의 가중치와 두 정점의 가중치의 합이 같은 경우를 의미합니다. 문제 예시 그림과 같이 모든 간선의 가중치 값이 연결된 정점의 합과 일치하는 경우를 의미하며, 균.. 개구리 점프( BOJ 17619 ) 문제 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 문제 파악하기 개구리가 점프를 해서 원하는 통나무까지 이동할 수 있는지 확인하는 문제입니다. 통나무들은 항상 가로방향으로 연못에 떠 있으며, 개구리는 항상 수직적인 방향으로 점프할 수 있습니다. 그렇기에 개구리는 항상 통나무의 값이 조금이라도 겹친다면 무조건 점프할 수 있습니다. 따라서, 우리는 모든 통나무에 대해서 서로 겹쳐있는지 확인하고, 겹.. 헬기 착륙장( BOJ 22348 ) 문제 : https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 2개의 페인트통을 사용해서 헬기 착륙장을 그릴 수 있는 경우의 수를 구하는 문제입니다. 헬기 착륙장은 반지름이 서로 다른 원으로 구성되어 있으며, 반지름이 1부터 R까지 1씩 차이나게 그릴 수 있습니다. 하나의 헬기 착륙장은 항상 하나의 색으로만 만들 수 있으며, 각각의 페인트통이 최대 50,000개 있기 때문에 그릴 수 있는 헬기착륙장의 최대 크기는 대략 450입니다. 따라서, 우리.. 등산 마니아( BOJ 20188 ) 문제 : https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 문제 파악하기 N개의 오두막과 (N-1)개의 오솔길로 이루어진 등산로가 주어질 때, 경로의 다양성을 구하는 문제입니다. 여기서 말하는 경로의 다양성이란 i번째 오두막에서 j번째 오두막으로 정산을 거쳐 이동할 때, 지나는 서로 다른 오솔길의 개수를 의미합니다. N개의 오두막 사이에 나올 수 있는 모든 경로의 다양성을 구해야하는데, 단순히 모든 경우의 수를 구하기에는 오두막의 개수가 3.. 등수 찾기( BOJ 17616 ) 문제 : https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 파악하기 N명의 사람 중 주어진 X가 될 수 있는 등수의 범위를 찾는 문제입니다. 등수의 범위라고 하니 뭔가 확률적으로 생각해야 될 것처럼 보이지만 등수의 의미를 생각한다면 그리 어렵지 않게 풀 수 있는 문제입니다. 문제 해결하기 그렇다면 등수의 의미는 무엇일까요? 등수란 자신보다 앞에 몇 명이 있으며, 뒤에 몇 명이 .. 자동차경주( 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 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) 안의 햄버거를 먹을 수 있다면 우리는 가장 왼쪽에 위치한 햄버거부터 하나씩 사람에게 할당하는 방법을 사용할 수 있습니.. 이전 1 2 3 4 5 6 다음