투 포인터
-
[코드트리 챌린지] 세 수의 최대 곱(S3)코딩테스트/코드트리_Java 2023. 10. 2. 18:08
문제 : 가장 짧은 부분합 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제는 아래와 같다 원소가 n개 들어 있는 수열에서 특정 구간을 잡았을 때 그 합이 s 이상이 되는 것 중, 가장 짧은 구간의 길이를 구하는 프로그램을 작성해보세요. 첫 번째 줄에 n과 s가 공백을 두고 주어집니다. 두 번째 줄에 수열의 각 원소가 공백을 두고 차례대로 주어집니다. 1 ≤ n ≤ 100,000 1 ≤ s ≤ 109 1 ≤ 원소 값 ≤ 10,000 실력 진단에서 틀린 문제이고 처음 투 포인터를 생각하긴 했지만, 원소 값이 10,000이길래 n^2으로도 풀리리라 생..
-
Q. 20366 자바 : 같이 눈사람 만들래?코딩테스트/백준_Java 2023. 3. 27. 22:27
문제 :boj.kr/20366 골드 3 난이도의 문제이다. 투 포인터 강의를 듣고나서, 투 포인터 유형의 다른 문제들을 찾아보다가 발견한 문제이다. 처음에 문제를 봤을 때는 어떻게 접근해야 할 지 감이 안잡혔었는데, 감이 안잡혀서 검색을 했더니, 세 용액 문제와 비슷한, 네 용액 문제로 풀면 된다는 내용이 있길래 그 내용만 보고 추측해서 풀었더니 다행히 풀렸다.(다른 블로그 코드 참고x) 문제를 보면 하나의 눈사람은 두 개의 눈덩이로 구성되고 눈덩이가 주어지면, 두 눈사람의 키 차이가 가장 작은 값을 구하라는 문제이다. 1. 투 포인터 알고리즘을 이용해 값을 조정하려면, 눈덩이들이 정렬된 상태여야 하므로 먼저 정렬을 해준다. - O(N log N) 2. 네 개의 값을 뽑아야 하므로 먼저 두 개의 값을 선..