two pointer12 [자바] 백준 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. [자바] 백준 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. [자바] 백준 14572 - 스터디 그룹 (java) 문제 : boj14572 필요 알고리즘 개념 그리디 풀이를 보면 왜 그리디인지 알 수 있다! 투 포인터 (두 포인터) 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자. 1. 그룹 내의 학생들이 아는 모든 알고리즘의 수 -> 학생 수가 늘어나면 항상 동일하거나 늘어난다. 2. 그룹 내의 모든 학생들이 .. 2022. 9. 17. [자바, C++] 백준 2118 - 두 개의 탑 (java cpp) 문제 : boj2118 필요 알고리즘 개념 투 포인터 (두 포인터) 두 개의 가상의 포인터를 두고, 그 두 포인터를 적절한 규칙으로 이동시키다보면 효율적으로 답이 나오게 되는 문제이다. 다만 원형 연결을 끼얹은.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 난 개인적으로 문제 지문 자체가 잘 이해가 안되서 해맸었다. 혹시 그런분이 있을 수 있으니 적어보면, 아래처럼 지점 번호는 중요하지 않고 아무튼 지점 N개가 있는데(녹.. 2022. 9. 6. [자바] 백준 24839 - Speed Typing (java) 문제 : boj24839 필요 알고리즘 개념 문자열 파싱 String을 character 단위로 볼 줄 알아야 한다. 그리디 알고리즘 (greedy) I의 모든 문자가 순서대로 P에 존재해야 하는지를 매번 '그리디하게' 확인한다. 두 포인터 (two pointer) I와 P의 시작점에 가상의 포인터를 하나씩 두고 양측이 점점 움직이면서 답을 찾아나가야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 I는 읽기 힘드므로,.. 2022. 7. 27. [자바] 백준 2470 - 두 용액 (boj java) 문제 : boj2470 예시 입력 1을 봐보자. 5 -2 4 -99 -1 98 위 상태로만 보자면, 결국 O(N^2)으로 모든 쌍을 확인하는 것 외에 별다른 방법이 떠오르지 않을 것이다. 정렬을 하면 어떨까? -99 -2 -1 4 98 이 경우 가장 좌측에서 시작하는 포인터를 s, 가장 우측을 e라고 해보자. 's의 값 + e의 값'을 기준으로 포인터를 중앙으로 점차 가져와보자. - 두 포인터가 가르키는 값의 합이 0 초과이라면 -> 더 작은 값을 확인해야하니 e를 좌측으로 이동한다. - 두 포인터가 가르키는 값의 합이 0 미만이라면 -> 더 큰 값을 확인해야하니 s를 우측으로 이동한다. 위 두가지 경우에 따라 s와 e를 중앙으로 이동시키면서 0과 가장 가까운 값을 찾으면 된다! 위의 경우 1. s=-9.. 2022. 7. 4. [자바] 백준 2559 - 수열 (boj java) 문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다. 코드1 : github - prefix sum import java.io.BufferedReader; import java.io.In.. 2022. 5. 27. 이전 1 2 다음
