백준/투포인터5 백준 2467 c++ "용액" -PlusUltraCode- https://www.acmicpc.net/problem/2467 [필자 사고]정렬되어 있다. 이 키워드를 통해 이 문제는 이분탐색 아니면 투포인터이지 않을까?? 와 같은 사고를 했다. 문제를 읽어보니 부르스트 알고리즘을 적용하면 시간내에 못 풀게 되어 있다.역시나 투포인터 알고리즘을 이용해야 된느 문제이다.O(nlogn) 시간복잡도로 충분히 시간 내에 풀 수 있다. 필자가 실수 했던 부분은 초기화 부분에 있었다. 1. 먼저 long 으로 해야된다.2. arr[left]+ arr[right] 등의 숫자들을 미리 담아나야된다. 이 부분만 신경쓰면 쉽게 해결할 수 있따.[코드 해설] Input 함수N개의 정수를 입력받는다.입력된 정수들을 저장할 arr 벡터를 초기화하고, 순서대로 값을 저장한다.Two_Poi.. 2025. 1. 2. 백준 1806 c++ "부분합" -PlusUltraCode- https://www.acmicpc.net/problem/1806 [필자 사고]투포인터 알고리즘을 이용하여 푸는 문제이다. 문제에서 주어진 조건중 조심해야 될 것은 아래와 같다. S의 범위가 1억이라는 점이다.브루스트 알고리즘을 이용하면 시간초과를 보게 될 것이다.또한 자료형 int 가아닌 long을 사용해야 된다. sum을 기준으로 S보다 작으면 endIdx를 키우고그렇지않으면 startIdx를 이동시키는 방식으로 코드를 구현했따. 아래는 코드 해설이다 전역 변수 및 배열 정의코드에서는 Arr라는 벡터를 통해 각 구간(또는 노드)의 값을 저장하고, N은 배열(또는 그래프)의 크기, S는 목표로 하는 합의 최소값을 나타낸다. Input 함수는 사용자 입력을 통해 배열의 값과 필요한 변수들을 초기화한다.2.. 2024. 12. 25. 백준 12891 c++ "DNA 비밀번호" -PlusUltraCode- https://www.acmicpc.net/problem/12891 [필자 사고] 필자의 처음 이 문제의 접근 방법은 아래와 같았다. 1. 해당 부분문자열 크기만큼 문자열들을 생성하여 ACGT 의 조건에 맞게 검사한다. 논리상으로는 문제가 없는 접근법이다. 다만 시간복잡도 측면에서는 문제가 생길 수 있따. N의 크기가 10^6 이므로 O(n)으로 문제를 해결해야 됬는데필자는 부분문자열 크기만큼 계속 새로운 문자열들을 생성하였기 때문에 이 조건에 위배되어 시간초과가 발생했따. 그래서 해결책은 아래와 같다.2. 이동하는 startIdx 와 endIdx 의 `문자`만 조사하여 이동하자!! [소스코드]#include #include #include #include using namespace std;stri.. 2024. 8. 14. 백준 1253 c++ "좋다" -PlusUltraCode- https://www.acmicpc.net/problem/1253 [필자 사고]이 문제는 주어진 수열에서 특정 수가 수열 내 다른 두 수의 합으로 표현될 수 있는지를 찾는 것이다. 이를 해결하기 위해 다음 절차를 따른다:투 포인터 알고리즘 적용: 각 수에 대해, 그 수가 다른 두 수의 합으로 표현될 수 있는지 확인한다. 이를 위해 수열의 처음과 끝에 위치한 두 포인터(startIdx, endIdx)를 사용하여, 두 수의 합이 현재 수와 일치하는지 비교한다조건 검토: 만약 현재 수가 두 포인터가 가리키는 수의 합과 같다면, 해당 수는 두 수의 합으로 표현될 수 있다. 이때, 현재 수가 두 포인터 중 하나와 겹치지 않을 때만 결과값을 증가시킨다.결과 출력: 모든 수에 대해 이 과정을 반복한 후, 조건을 만족.. 2024. 8. 13. 이전 1 2 다음
