어흥

문제 링크: www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 1. 주의할 점 - N num>>play; for(int i=1;i>arr[i]; if(num

문제 링크: www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS 알고리즘에 대해 알고 있어야 한다 - DP[] 배열을 TC마다 초기화한다 2. 구현 - 입력 받는 수들을 Arr[] 배열에 저장하면서 DP[] 배열을 전부 0으로 초기화한다 - DP[0] = Arr[0]과 idx=0을 초기화한다 - i: 1~Num-1까지 Arr[]에 있는 모든 수들에 대해 Arr[i]의 값이 DP[idx]보다 크다면 DP[++idx]..

문제 링크: www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 1. 주의할 점 - TC가 여러개 + 언제 끝나는지 알려주지 않음 -> EOF가 입력될 때까지 받는다 - 서로 다른 2 조각 사용 - TC마다 V 벡터 초기화 2. 구현 - if(cin>>len)을 통해 EOF를 입력 받았다면 false를, 아니라면 true를 입력 받기 때문에 EOF를 입력 받는다면 Break로 While문을 빠져 나간다 - 입력 받는 조각들을 오름차순으로..

문제 링크: www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. 주의할 점 - 일반적으로 알고 있는 LIS의 공식은 길이를 구하는 것으로, 실제 LIS를 구하는 것은 추가 작업이 필요하다 2. 구현 - 모든 수를 Info 구조체 형태의 Vector로 입력 받고, 첫 번째 인자를 기준으로 오름차순 정렬한다 - DP[] 배열을 통해 LIS의 간략한 형태를 구하고, Pos[] 배열을 통해 추가 또는 수정된 원소가 몇 번째 DP 원소와 바뀌었는지 저장한다 - ..

문제 링크: www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. 주의할 점 - 세 포인터가 아닌 1개 고정 + 두 포인터를 이용해 해결한다 - 포인터가 겹칠 수 없다 - 정답을 오름차순으로 출력한다 2. 구현 - 모든 수를 Arr[] 배열에 받은 후, 오름차순으로 정렬한다 - Result를 3000000001로 설정하여 이보다 0에 가까운 값을 가질 경우, Ans[] 배열과 Result값을 갱신하도록 한다 - 가장 왼쪽의 포인터 K를 ..

문제 링크: www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 1. 주의할 점 - LIS(가장 증가하는 부분수열)에 대해 알고 있어야 한다 2. 구현 - 모든 수에 대한 입력을 Arr[] 배열에 받는다 - DP[idx] 배열 통해 가장 긴 증가하는 부분 수열을 나타낼 때, idx번째로 작은 수를 DP[idx]에 저장한다 - 만약 새로 비교하는 값(Arr[i])가 DP[] 배열의 가장 마지막 원소(DP[idx])보다 크면, DP배열에 새로 추가한다..

문제 링크: www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 1. 주의할 점 - 모두 비교할 경우, 최악의 경우 O(N*M)으로 TLE가 발생한다 - 둘중 하나는 lgN이나 lgM으로 바꿔야 TLE가 발생하지 않는다 - 사대의 X값이 정렬되어 있지 않다. 왜? 2. 구현 - 입력 받은 사대 Arr[]를 오름차순으로 정렬한다 - 동물들의 위치를 X[], Y[]에 할당 받는다 - 각 동물을 기점으로 사대까지의 거리가 Len보다 작거나 같다면, Result++하고..

문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 1. 주의할 점 - LIS 알고리즘에 대해 알고 있어야 한다 - 이분탐색을 통한 LIS를 수행한다 2. 구현 - 모든 수를 Arr[] 배열에 담는다 - DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다 - DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다 - 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 ..