DevBoi

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이건 단순한 이분탐색이다.

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 공유기 설치 문제이다. 이전에 풀었던 레슨 문제와 유사하다. 범위를 구하고 이분탐색을 하면 끝이다. 말하면, 각각의 리스트들을 합하듯이, 앞에서 뒤의 집을 빼주면서 체크를 하고, 이분탐색의 mid 값보다 크다면, cnt를 증가, 반복문이 다돌면, answer보다 큰지 작은지 체크해서, 답에 update해주면 된다.

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 쉽게 생각할수 있는 이분탐색 풀이이다. 이분탐색의 유형은 크게 두가지 풀이이다. 특정 배열이 있고, 해당 배열 내에서, 이분탐색으로 중간값을 구해서 값을 탐색하는 방법이 있고 특정 조건에 대한 리스트들을 생각해서, 만든뒤에 해당 조건들의 범위에서 이분탐색을 하는 경우가 있다. 해당 문제는 두번째 케이스이다. 각 레슨의 길이를 생각해서 최대의 길이를 계산, 그리고 cnt 를 증가 시키면서 세는 방법이다. ..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이 문제 또한, 예산 문제이며, 해당 값을 가지고 최대값을 구하는 문제이다. 반복문마다, 현재 가장 가까운 수를 비교해서 update하고, 마지막에 left가 right 보다 커지면 종료하면서 출력한다.

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 우선 해당 문제는 이분 탐색의 종류중에서, 약간 응용 버전인, Parameter Search이다. 어떤 배열의 값들은 알수없으나, 정렬이 되어있는 경우 사용할수 있고, 특정 조건들을 만족하는 답중에서, 최대 or 최소를 구할때 사용한다. 아래와 같은 구조로 해당 문제의 기준을 세웠다. 1. 정답 범위, int 자료형은 2억까지이므로, 20억의 연산과정값이 발..

이분탐색 ? 정렬이 보장되어있는 배열에서, 이분을 하면서 탐색하는기법 이분탐색은 전형적인 변수 세팅을 사용한다. 왼쪽, 오른쪽의 포인터 두개를 가지고 시작한다. 항상 가운데의 인덱스를 보고, 해당 인덱스와 , 타겟을 비교하고, 해당 비교를 통해 포인터 L 혹은 R을 비교하면서 포인터를 이동시킨다. https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분탐색에 대한 예제이다. 쉽게말하면, 한 집합을..

https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당은 간단하다. 문자열을 int로 받아서, 새로운 배열에 넣어주고, 해당 배열을 역순출력해주면 된다.

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 대표적인 정렬이다. 객체 object로 받아서, 해당 object가 Comparable에 대한 걸 impl하게 하고, 해당 compareTo를 오버라이드해서 객체의 비교조건을 구현, 해당 객체를 비교해주면, 끝난다. foreach가 돌때, 객체의 특정 이름만 필요하기 때문에, word의 이름만 출력해준다.

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ATM 풀이이다. 간단하게, 정렬을 하고, foreach로 부분합을 구하는 것이다. 부분합을 구한뒤에, 다음 each가 돌기전에 list에 add를 해주고, 마지막에 List의 값을 다 합해주면 된다. list2.indexOf(object) 를 사용해서, 해당 인덱스를 구하는 방법이 있다. 인덱스가 필요할때는, 전통적인 for문이 최적화가 되어있어, 빠르기때문에 해당 방법으로 돌려주면 좋고 인덱스를 굳이 사용해야하는지에 대한 ..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당 관련되서는, 퀵정렬을 사용해서 풀었다. 퀵정렬은 처음 값을 pivot으로 놓고, 재귀를 통해서 무한히, pivot보다 작으면 오른쪽 , 크면 왼쪽 배열로정렬하는 것이다. 그러면 그 안에서도 정렬이 필요하기 때문에, 재귀로 구현한다. 해당 안에서 정렬을 하고 왼쪽 pivot 오른쪽 으로 addAll을 통해, 배열을 합친다. 해당 방법으로 합치게 되면, 정렬 된 배열을 만들 수있다. (재귀로 한다면) 소스 참고