투 포인터18 [자바] 백준 2473 - 세 용액 (java) 목차 문제 : boj2473 필요 알고리즘 투 포인터 또는 이분 탐색 투 포인터를 쓰거나, 이분 탐색을 써서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 처음 생각난 아이디어는, 어차피 n이 5000이므로 2개를 고정시켜놓고, 나머지 하나의 값을 이분 탐색으로 찾는 방법이었다. 이 경우 O(N^2 * logN). 예를들어 현재 고정시켜둔 2개의 값이 -97와 -2라면, -(-97-2) = 99 .. 2024. 3. 20. [자바] 백준 20956 - 아이스크림 도둑 지호 (java) 목차 문제 : boj20956 필요 알고리즘 두 포인터 (투 포인터, two pointer), 정렬 투 포인터로 해결할 수 있는 문제이다. 다만 일반적인 투 포인터 사용 형태와는 약간 다르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력받은 N개의 아이스크림 정보에 대해 양을 a, 번호를 idx 라고 하자. 그럼 우선 입력받은 후 a desc, idx asc로 정렬한다. @Override public int compa.. 2023. 11. 21. [자바] 백준 17609 - 회문 (java) 문제 : boj17609 필요 알고리즘 개념 두 포인터 (투 포인터) 회문이 아닐 시 예외처리가 들어가긴 하지만, 기본은 회문을 검사하는 투 포인터 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 기본적인 회문은 아래와 같이 찾을 수 있다. 양끝에서 두개의 포인터가 중간으로 오면서 두 포인터가 가르키는 값이 동일한지 확인하는 것이다. 근데 이 문제는 1번은 건너띄어도 된다. 어떻게 처리하면 될까? summmmu.. 2023. 1. 13. [자바] 백준 9024 - 두 수의 합 (java) 문제 : boj9024 필요 알고리즘 개념 정렬, 투 포인터 투 포인터로 해결 가능한 문제이다. 투 포인터 사용을 위해 정렬도 해줘야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 두 정수의 합이 K와 가장 가까운 두 정수의 조합의 수를 찾는 문제이다. 얼핏 K와 동일한 수가 아니라 K와 가장 가까운 두 정수를 찾는거여서 투 포인터로 해결이 안된다고 생각할 수 있다. (예를들어 K=8이고, 두 정수의 합이 8인 경우가.. 2023. 1. 4. [자바] 백준 25822 - 2000문제 푼 임스 (java) 문제 : boj25822 필요 알고리즘 개념 누적 합(prefix sum) 내 경우엔 이걸 메인 아이디어로 사용했다. 문제 태그에 없긴하다. 투 포인터 (two pointer) 누적합을 사용한 아이디어에 대해 시간복잡도를 줄이기 위해 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 누적합을 사용해 특정 구간에 대해 스트릭이 유지됬다고 가정할 때 필요한 스트릭 프리즈의 수를 O(1)로 알 수 있게 하는게 메.. 2022. 12. 15. [자바] 백준 1981 - 배열에서 이동 (java) 문제 : boj1981 필요 알고리즘 개념 투 포인터, 이분 탐색 투 포인터 혹은 이분 탐색을 섞은 그래프 탐색 문제이다. 일단 태그는 이분 탐색이긴 한데, 난 투 포인터로 풀었다. 그래프 탐색(BFS, DFS) 투포인터 혹은 이분 탐색으로 제한된 범위 내에서 시작점부터 끝 점까지 탐색이 가능한지 확인해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이하 풀이는 투 포인터를 사용한 풀이이다. 태그를 보니 대부분 이분.. 2022. 12. 13. [자바] 백준 2842 - 집배원 한상덕 (java) 문제 : boj2842 필요 알고리즘 개념 투 포인터, 그래프 탐색 당연히 bfs나 dfs 문제처럼 생겼는데, dfs나 bfs는 그저 탐색을 위해 거들뿐인 문제이다. 투 포인터 혹은 이분탐색 등을 사용해 범위를 조정해나가는 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 투 포인터는 써둔게 없지만.. 2022. 12. 12. [자바] 백준 1253 - 좋다 (java) 문제 : boj1253 필요 알고리즘 개념 투 포인터, 이분 탐색, 해싱 등 이하 풀이는 투 포인터 풀이이다. 정렬 투 포인터 또는 이분 탐색 사용시엔 정렬도 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 말로만 적어보면 간단하다. 1. 입력받은 N개의 값을 정렬한다. 2. idx : 0 to N-1 에 대해 arr[idx]를 제외한 나머지 값들 중 두 개를 합쳐서 arr[idx]가 되는 경우가 존재한다면 cnt+.. 2022. 12. 2. [자바] 프로그래머스 - 쿠키 구입 (Lv4, Java) 문제 : Programmers-쿠키 구입 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 두 포인터 (투 포인터) 투 포인터 알고리즘을 알고 있다면 어렵지 않게 풀어볼 수 있다. 일반적으로 문제를 좀 더 단순화해서 생각해보면 풀이를 생각하기 쉬운 경우가 많다. 한번 m이 고정이라고 생각해보고 어떻게 풀지 생각해보자. 그렇다면 l과 r을 적절히 조정해서 l~m의 합과 m+1~r 까지의 합을 동일하게 만드는 문제가 된다. 그리고 입력값으로 0 또는 음수가 주어지지 않으므로 단순히 l~m의 합이 m+1~r의 합보다 작다면 l을 줄이고, 그 반대라면 r을 늘려주기만 하면 된다. 즉 l과 r 두개의 포인터가 있는 투 포인.. 2022. 10. 14. [자바] 백준 14572 - 스터디 그룹 (java) 문제 : boj14572 필요 알고리즘 개념 그리디 풀이를 보면 왜 그리디인지 알 수 있다! 투 포인터 (두 포인터) 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자. 1. 그룹 내의 학생들이 아는 모든 알고리즘의 수 -> 학생 수가 늘어나면 항상 동일하거나 늘어난다. 2. 그룹 내의 모든 학생들이 .. 2022. 9. 17. 이전 1 2 다음
