Binary Search 이분 탐색은 어떤 정렬된 데이터에 대해 특정 값을 찾을 때, 반씩 나누어 탐색하여 log 시간에 데이터를 찾는 알고리즘이다. 사이즈 n 의 다음과 같은 배열이 있다고 해보자. K1 K 이면, 찾는 값은 Km 기준 왼쪽에 있다. 따라서 u = Km - 1 으로 설정한다. ..
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 학교 동아리 스터디에서 세그트리 연습문제로 나와 풀게 되었다. 스터디 수업때 다뤘던 연습문제와 세그트리를 적용하는 결이 달라 한참 고민을 하고 풀었다. 보통 '세그먼트 트리' 하면 유명한 연습문제가 '구간 합 구하기' 이다. https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,0..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 같은 부분 문자열이 2개 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 문제이다. 나는 골드 3의 티어로 난이도를 낮게 매겼다. 나는 신촌 연합 알고리즘 캠프에서 배운 라빈 카프 알고리즘에 이분탐색을 더하여 풀었다. 이분탐색을 사용한 이유는 다음과 같다. 부분문자열의 길이가 n일 때 문제 조건을 만족한다면 이 해당 부분문자열의 부분문자열도 문제의 조건을 만..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 여러가지 방법으로 풀 수 있는 세 용액 문제이다. 나는 처음에 이분탐색을 시도 했다가 막혔는데, 구현을 쓸데없이 복잡하게 하다가 실수를 했던 것 같다. 2시간 고민하다가 다른 이분탐색 풀이 알고리즘을 보고 수정하여 맞았다. 이 문제를 투 포인터로 풀 수 있겠다는 생각까진 해봤는데, 구체적으로 어떻게 투 포인터를 써야할 지 떠오르지가 않았다. 그렇게 공부하여 알게된 알고리즘이 ..
