본문 바로가기

알고리즘51

BOJ 2170 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 1차 시도 "중복되는 곳을 어떻게 저장했다가 사용할 것인가" 가 이 문제의 핵심이라고 생각했다. 그래서 배열을 만들어 할당된 곳을 체크하면서 길이를 측정하려고 하였다. 근데 문제는 크기였다. 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000) 라는 조건 때문에 배열 선언이 불가능해서 불가능하다고 판단 2차 시도 배열로 체크하는게 .. 2024. 2. 5.
[그리디 #3] 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 접근 방법 예제를 보면 쉽게 해결할 수 있는 문제이다. 최종적으로 모든 카드의 합이 최소가 되어야 한다. 최소가 되기 위해선 당연하게 가장 작은 카드 2개를 선택하면 된다. 매우 간단하게 해결할 수 있는 그리디 문제이다. #include #include #include using namespace std; vector v; int n, m; int main().. 2024. 2. 5.
[알고리즘] 방향그래프 방향그래프 - 모든 간선이 방향간선 방향그래프의 속성 - 모든 간선은 한 방향으로만 - G가 단순(간선이 많지 않음) : M v인 방향경로가 존재하면, "u는v에 도달한다" , "v는 u로부터 도달 가능하다" 강연결성 어느 두 정점 u, v 간에 u에서 v 도달가능 이고 v에서u 로 도달가능이면 강연결 강연결 검사 알고리즘 1. 임의 정점 v 선택 2. v에서 DFS 실행 3. 간선들 방향을 역행시킨 그래프 G'을 얻음 4. G'에서 v에서부터 DFS 수행 -> O(n+m) 강연결 요소 - 최대한 모든 정점을 도달할 수 있는 부그래프 a->f로 간다고 하면, a로 다시 올 수 없음. 이행적폐쇄 다음 성질을 만족. 1. G'은 G와 동일한 정점들로 구성 2. G의 u에서 v(v!=u)로의 경로가 존재하면 .. 2023. 11. 21.
[DP #18] (BOJ 2482) 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 입력 입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다. 출력 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. 접근법 DP[i][j]를 i개 색을 이용해서 .. 2023. 8. 30.
[👊DP뿌시기 #14] (BOJ 11057) 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째 줄에 N (1.. 2023. 8. 27.
[👊DP뿌시기 #9] (BOJ 2565) 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는.. 2023. 8. 21.

티스토리툴바