투포인터의 s, e 포인터 위치 질문
안녕하세요 현재 투포인터 알고리즘 강의를 듣고 궁금한 점이 생겨서 질문을 남깁니다.
투포인터 설명을 듣고 그럼 모든 투포인터 알고리즘 문제에서 "start포인터와 end포인터를 양 끝에 위치시켜놓고 시작하는거구나"라고 생각하고 강의에 있지는 않지만 "프로그래머스 - 보석쇼핑" 문제를 풀던 중에 해당 문제는 투포인터 문제임에도 start와 end를 처음 지점부터 동시에 시작하는 방식으로 풀어야만 했습니다.
제가 생각했을 때 start, end를 양 끝점에 두냐, 혹은 시작점에 두개를 모두 위치시키느냐 를 결정짓는 조건이 문제에서 주어지는 값들이 "sort를 하는 것이 의미있냐 없냐"의 여부에 따라 결정된다고 생각했습니다.
문제에서 주어진 값들이 sort하는 것이 의미가 있다면: 양 끝점에 위치
문제에서 주어진 값들이 sort하는 것이 의미가 없다면: 모든 포인터 시작점에 위치 (sort한 후에)
이렇게 생각해도 맞는 것인지 아니면 그냥 문제를 보고 이를 판단해야 하는 것인지 궁금합니다.
답변 1
0
양 끝점에 두는것 말고 모두 시작점에 위치시키는 방법을 "인치웜"이라고 합니다.
sort 여부와 관계가 있는가...?! 저는 한번도 고민해 본 적이 없는데 답변을 단 후에 저도 조금 궁리해보겠습니다.
질문주신 방법이랑 별개로 저는 그냥 처음에 그림을 그려서 투포인터랑 인치웜을 둘 다 먼저 해봅니다! (슬라이딩 윈도우도 해봐요!)
문제를 풀기전에 저는 10분정도 고민하는 시간을 가지는데 그 때 여러 방법을 대입해보는 방법을 써서 저는 단순 투포인터인지 아닌지 판단하고 있습니다.
1
아예 다른 알고리즘으로 분류가 되는거였군요..! 접근 방법까지 알려주셔서 감사합니다!!
제가 생각한 sort의 의미 여부로 투포인터와 인치웜을 나누는 기준에 대해 혹시 생각이 떠오른시다면 제게도 알려주신다면 정말 감사하겠습니다!! 강의 잘듣고 있습니다:)
dp[x]가 최대값이라고 확신할수 있는 이유
0
45
1
1090번 문제 질문
0
150
1
유니온파인드
0
112
1
투포인터 25:15 질문
1
128
1
#1090번 문제 반례가 궁금합니다.
0
148
1
예제코드 자바입니다
1
186
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
102
0
코드 오류
0
185
1
2강 정수론 문제3 #1407 질문
0
127
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
193
2
[Python] 백준 1090번 문제
1
226
3
강의자료에서
1
162
2
2503 문제 제한 조건 질문!
1
249
2
백준 22988 번 문제
1
193
1
추가 강의 순서
1
180
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
221
2
7강 RGB 색칠하기 질문 있습니다.
1
160
2
정수론 약수 빠르게 구하기 질문
1
257
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
373
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
223
2
누적합 문제 3번 질문
1
216
2
기억 ( 누적합 ) 강의 11660 문제
1
163
2