유자의 코딩모험

20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제풀이 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하는 문제다. 이중 for문으로도 해결할 수도 있지만 시간복잡도가 O(n^2)이기 때문에 시간초과가 발생할 가능성이 크다. 이럴 때는 투 포인터를 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 먼저 과정을 정리해보자면, 다음과 같다. left, right 모두 0에서 시작한다. cnt[arr[right]]이 K 미만이면 cnt 증가시키고 수열 길이를 갱신한 다음 right++..

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제풀이 용액들의 특성값이 주어졌을 때 세 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다. 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하다. 세 용액들을 더하면 오버플로우가 날 수 있기 때문에 배열은 long long 자료형으로 선언해준다. 3SUM - Wikipedia Unsolved problem in computer science: Is there an algorithm to sol..

2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제풀이 BOJ 2470 두 용액이랑 같은 코드로 풀 수 있다. [BOJ 2470] 두 용액 C++ 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000 woojeenow.tistory.com C++ 코드

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제풀이 용액들의 특성값이 주어졌을 때 두 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다. 투 포인터 알고리즘으로 left는 첫번째 인덱스부터, right는 마지막 인덱스부터 탐색해나간다. diff는 특성값과 0의 차, minx와 miny는 두 용액의 인덱스 정보이다. 두 용액의 합이 diff보다 작은 경우 정보를 갱신해준다. 두 용액의 합이 0이라면 특성값이 0에 가장 가까운 용액을 찾은 것이므로 탐색을 ..

14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 문제풀이 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값을 찾는 문제다. 투 포인터 알고리즘으로 left는 첫 번째 인덱스부터, right는 마지막 인덱스부터 탐색해나간다. 최대 특성값은 200,000,000이므로 answer는 200,000,000으로 초기화해준다. 탐색을 하면서 answer보다 0에 가까운 특성값을 찾으면 갱신해준다. sum이 0보다 작으면 a[left] 값이 더 커져야 하므로 left++, sum이 ..