어흥

문제 링크: 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.hackerrank.com/challenges/anagram/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign Anagram | HackerRank Find the minimum number of characters of the first string that we need to change in order to make it an anagram of the second string. www.hackerrank.com 1. 주의할 점 - Alpha[] 배열 초기화 필요 2. 구현 - 파라미터로 넘겨받은 S의 길이가 짝수가 아니면 -1을 반환한다 - Alpha[] 배열을 0으..

문제 링크: 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]가 크다면, 가장 긴 ..

문제 링크: www.hackerrank.com/challenges/palindrome-index/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign Palindrome Index | HackerRank Determine which character(s) must be removed to make a string a palindrome. www.hackerrank.com 1. 주의할 점 - 삭제를 할 경우, 반으로 나눴을 때를 기준으로 왼쪽 or 오른쪽에 있는 원소를 삭제할 수 있다 - 어느쪽을 삭제해도 상관없는 경우를 조심한다(아래에 TC 존재) #1 1 cbbcb Answer : 4 2. 구현..