넘치게 채우기

https://www.acmicpc.net/problem/17387BOJ - 선분 교차 2문제 유형: 선형대수, 수학, 기하학문제 난이도: Gold II시간 제한: 0.25초메모리 제한: 512MB 문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 1, 아니면 0을 출력한다. 풀이처음에는 직선의 방정식을 이용해서..

https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/leetcode -Maximum Employees to Be Invited to a Meeting문제 유형: 위상 정렬, bfs, 연결 컴포넌트, 그래프문제 난이도: Hard 문제A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.The employees are numbered from 0..

https://codeforces.com/contest/2063/problem/CCodeforces Round 1000(Div.2) - C. Remove Exactly Two문제 유형: 그리디, 그래프, 정렬, 트리시간 제한: 2초메모리 제한: 256MB 문제You are given a tree∗ of n vertices. You must perform the following operation exactly twice.Select a vertex v; Remove all edges incident to v, and also the vertex v. Please find the maximum number of connected components after performing the operation e..

https://www.acmicpc.net/problem/2568BOJ - 전깃줄 - 2문제 유형: 가장 긴 증가하는 부분 수열(LIS), 다이나믹 프로그래밍문제 난이도: Platinum V시간 제한: 1초메모리 제한?: 128초 문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.   전깃줄이 전봇대에 연결..

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/description/leetcode - Make Lexicographically Smallest Array by Swapping Elements문제 유형: 우선순위큐, 유니온-파인드문제 난이도: Medium 문제You are given a 0-indexed array of positive integers nums and a positive integer limit.In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - num..

https://codeforces.com/contest/2063/problem/BCodeforces Round 1000(Div.2) - B. Subsequence Update문제 유형: 정렬, 그리디시간 제한: 1.5초메모리 제한: 256MB 문제You are given an integer sequence a1,a2,…,an">a1,a2,…,an, and a segment [l,r]">[l,r] (1≤l≤r≤n">1≤l≤r≤n).You must perform the following operation on the sequence exactly once.Choose any subsequence∗"> of the sequence a">a, and..

https://www.acmicpc.net/problem/10775BOJ - 공항문제 유형: 분리 집합, 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제오늘은 신승원의 생일이다.박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도..

https://leetcode.com/problems/find-eventual-safe-states/description/leetcode - Find Eventual Safe States문제 유형: dfs, 위상 정렬문제 난이도: Medium 문제There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in gra..

https://codeforces.com/contest/2063/problem/ACodeforces Round 1000(Div.2) - A. Minimal Coprime문제 유형: 수학, 그리디시간 제한: 1초메모리 제한: 256MB 문제A segment of positive integers [l,r]">[l,r] is called coprime if l">l and r">r are coprime.A coprime segment [l,r]">[l,r] is called minimal coprime if it does not contain any coprime segment not equal to itself. To better understand this statement, you can refer to..

https://www.acmicpc.net/problem/28707BOJ - 배열 정렬문제 유형: 문자열 처리, 최단 경로, 다익스트라, 해시문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제길이가 N인 양의 정수로 이루어진 배열 A=[A1,A2,⋯,AN]이 주어집니다. 이 배열을 비내림차순, 즉, A1≤A2≤⋯≤AN이 되도록 정렬하기 위해서 다음과 같은 M가지 조작을 순서와 횟수에 상관 없이 원하는 만큼 할 수 있습니다. A의 li번째 수와 ri번째 수를 바꿉니다. 비용은 ci가 듭니다. (1≤i≤M) A를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요. 입력첫 줄에 배열 A의 길이 N이 주어집니다. (2≤N≤8)둘째 줄에 A의 각 원소 A1,⋯,AN이 공백으..