투포인터4 백준 [자바 java] 1253번 : 좋다 문제설명n개의 수가 주어지고, 그 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있으면 그 수를 좋다라고 한다.n개의 수 중 좋은 수의 갯수는? 풀이이 문제는 1년전 실패했었다..다시 보니까 그 이유가 좀 보였다!일단 3퍼에서 자꾸 틀렸습니다가 나왔는데 그 이유는 배열을 정렬하고 첫번째 수를 전혀 고려하지 않았기 때문이다. 하지만 이렇게 하면0 0 0 0일때 배열 내의 가장 작은 수도 좋은 수가 될 수 있는데 이를 간과해버린다. 또 60프로대에서 계속 틀렸습니다가 나왔는데 이건 좋은 수는 서로 다른 두 수를 더했을 때 좋다고 할 수 있는데, 투포인터를 하는 과정에서 지금 탐색하고 있는 수까지 포함시켜버렸다.예를 들어 2가 좋은 수인지 탐색하는데 2+0을 확인하고 좋은수라고 인식한 것이다. 그거 말고는 투.. 2025. 2. 27. 코드트리 [자바 java] 가장 짧은 부분합 https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 배열이 주어지고 이 배열에서 연속한 합을 구했을 때 S이상인 경우중 가장 짧은 경우의 길이를 구하는 문제이다. https://ethereal-coder.tistory.com/140 [알고리즘 개념] Shorten time technique 누적합 좌표압축 LR Technique +1-1테크닉 전처리 투포인터 누적합 배.. 2023. 9. 1. [알고리즘 개념] Shorten time technique 누적합 좌표압축 LR Technique +1-1테크닉 전처리 투포인터 누적합 배열이 주어지고, n번 인덱스부터 m번 인덱스까지 더한 값을 구하라는 문제가 있을 때, 브루트포스로 풀면 하나하나 더해야 하므로 시간복잡도가 O(n)이 된다. 하지만, (위와 같이 현재 인덱-스의 값 + 이전 인덱스를 모두 더한 값을 저장하는 배열)을 만들면, m번 인덱스에서 n번 인덱스를 빼면 문제에서 원하는 값이 바로 나온다. 이렇게 누적합을 사용하면 시간복잡도가 O(1)이 된다. 이차원 배열에서는 조금 더 복잡하다. 이러한 배열이 있고, (a,b)에서 (c,d) 만큼 더한 값을 구하라고 하였을 때, 부분합을 이용해서 구하면 빠르다. 위 배열이 부분합이다. 각각의 인덱스는 (0,0)에서 해당 인덱스까지의 합을 의미한다. 각각.. 2023. 8. 23. 백준 [자바 java] 17609 : 회문 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 처음에는 자료구조 시간에 회문 문제 스택으로 풀라고 했던 것 기억나서 그렇게 했는데 시간초과가 났다. 그래서 문제를 자세히 살펴보니 투포인터로 하는게 훨씬 효율적이었다. 여기서 두 포인터의 char값이 다를 때 값을 옮겨주는 과정에서 옮긴 후 모든 것들은 회문이어야 한다는 조건을 빼먹어서 틀렸습니다가 나왔다. 주의할 점 구현 까다로우면 더 쉬운 방법 있나 한번 더 생각하기 반례 더 있나 깊게 생각하기 import java.ut.. 2023. 7. 14. 이전 1 다음
