문제 노트/정올 (49) 썸네일형 리스트형 전깃줄 - 2( BOJ 2568 ) 문제 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 파악하기 최소한의 전깃줄을 잘라 서로 겹치는 전깃줄이 없게 만드는 문제입니다. 보통 이런 문제는 가장 긴 증가하는 부분 수열(이하 LIS)을 사용하며, 이 문제 역시 대표적인 LIS 문제입니다. 서로 겹치지 않는다는 건 항상 현재 가로등 번호보다 다음 가로등의 번호가 더 커야 한다는 걸 의미하며, 결국 주어진 수열 중 LIS의 길이를 찾는 문제와 동치가 됩니다. 그럼 어떻게 이 .. 공통 부분 수열 확장( BOJ 21762 ) 문제 : https://www.acmicpc.net/problem/21762 21762번: 공통 부분 수열 확장 어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab는 $X$ = ababca의 부분수열이지만, $Y$ = cbabba의 부분수열은 아니다. 두 개의 수열이 주 www.acmicpc.net 문제 파악하기 주어진 문자열 X와 Y의 공통 부분 수열을 확장할 수 있는지 확인하는 문제입니다. W는 X와 Y의 공통 부분 문자열이며 W를 확장시킬 수 있다면 1을, 확장시킬 수 없으면 0을 출력하는 결정 문제입니다. 단순 반복문을 사용하는 알고리즘을 사용하면 정답을 구할 수 있지만, 1초 안에 해결할 수는 없습니다. 그렇기 때문에 문제를 해결하기.. 그래프 균형 맞추기( 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번.. 이전 1 2 3 4 5 6 7 다음