💡 두 포인터의 합과 차 - 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결합니다. - 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있습니다.
https://colabear754.tistory.com/69
1. [백준 2018번] 수 들의 합5 문제 이해
💡 백준 2018번 : 수들의 합5 문제 이해
아래의 문제는 입력 값이 주어지면 숫자들의 합을 하였을 때, 입력 값을 구하는 가짓수를 구하는 문제입니다.
💡 문제
- 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어 한다. 이때, 사용하는 자연수는 N이하여야 한다. - 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. - N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
💡 입력
- 첫 줄에 정수 N이 주어진다.
💡 출력
- 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
https://www.acmicpc.net/problem/2018
2. [백준 2018번] 수 들의 합5 문제 풀이
💡 백준 2018번 : 수들의 합5 문제 풀이
- 해당 문제는 포인터가 되는 ‘인덱스’ 값을 기반으로 상황에 따라 startIndex와 endIndex 값이 오른쪽으로 이동을 하며, 입력값에 도달했을 때 그때의 가짓수를 구합니다.
1. while문을 통해 endidx 값과 input 값이 동일할때 반복 수행합니다.
2.1. 합과 input 값이 동일한 경우 : 조건에 만족하는 경우로 가짓수를 올리며, endIndx를 오른쪽으로 이동합니다.
2.2. 합이 input 보다 큰 경우 : startIndex 값을 빼고 startIndex의 값을 오른쪽으로 이동합니다.
2.3. 합이 input 보다 작은 경우 : endIdx 값을 오른쪽으로 이동하고 합에 더합니다.
/**
* 06. 연속된 자연수의 합 구하기 : 2018번
* DESC : 1 ~ input 까지의 합을 하였을때 input 값이 나오는 경우는 몇개가 있는가?
*
* @return ResponseEntity<ApiResponse>
* @link
* @since 2024.01.04
*/
@GetMapping("/6")
public ResponseEntity<Object> question06() {
int answer = 0;
int input = 15;
int startIdx = 1;
int endIdx = 1;
int sum = 1;
int count = 1;
// [STEP1] 1 ~ 15까지 수행한다.
while (endIdx != input) {
// [CASE1] 합이 input 값과 동일한 경우 : 조건에 만족하는 경우로 합계를 구하고 endIdx를 오른쪽으로 이동합니다.
if (sum == input) {
count++;
endIdx++;
sum += endIdx;
}
// [CASE2] 합이 input 보다 큰 경우 : startIndex 값을 빼고 startIndex의 값을 오른쪽으로 이동합니다.
else if (sum > input) {
sum -= startIdx;
startIdx++;
}
// [CASE3] 합이 input 보다 작은 경우 : endIdx 값을 오른쪽으로 이동하고 합에 더합니다.
else {
endIdx++;
sum += endIdx;
}
}
answer = count;
return new ResponseEntity<>(answer, HttpStatus.OK);
}
3. [백준 2018번] 수 들의 합5 : 그림으로 처리과정 이해하기
💡 아래의 그림과 같이 sum으로 15를 구하기 위해 루프를 기준으로 처리과정을 확인합니다.
💡 이미지의 처리 과정-1
⭕️ Loop1 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 2의 값을 가집니다. - 합은 3이 되므로 ‘합이 input 보다 작은 경우’로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop2 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 2 → 3으로 이동하여 3의 값을 가집니다. - 합이 6이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop3 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 3 → 4으로 이동하여 4의 값을 가집니다. - 합이 10이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop4 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 4 → 5으로 이동하여 5의 값을 가집니다. - 합이 15이 되므로 ‘합과 input 값이 같은 경우’로 Count를 1 증가합니다. 또한 endIndex를 다음 단계에 오른쪽으로 이동합니다.
⭕️ Loop5 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 5 → 6으로 이동하여 6의 값을 가집니다. - 합이 21이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(1→2)
💡 이미지 처리 과정 -2
⭕️ Loop 6 - 시작 인덱스는 2의 값을 가집니다 - 마지막 인덱스 값은 6의 값을 가집니다. - 합은 20이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(2→3)
⭕️ Loop 7 - 시작 인덱스는 3의 값을 가집니다. - 마지막 인덱스 값은 6의 값을 가집니다. - 합은 18이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(3→4)
⭕️ Loop 8 - 시작 인덱스는 4의 값을 가집니다. - 마지막 인덱스 값은 6의 값을 가집니다. - 합이 15이 되므로 ‘합과 input 값이 같은 경우’로 Count를 1 증가합니다. 또한 endIndex를 다음 단계에 오른쪽으로 이동합니다.
💡 이미지 처리 과정 -3 ⭕️ Loop 8 - 시작 인덱스는 4의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합은 3이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(4→5)
⭕️ Loop 9 - 시작 인덱스는 5의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합은 18이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(5→6)
⭕️ Loop 10 - 시작 인덱스는 6의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합이 13이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop 11 - 시작 인덱스는 6의 값을 가집니다. - 마지막 인덱스 값은 8의 값을 가집니다.합은 21이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(6→7)
- 아래와 같은 과정으로 endIdx 값이 15에 이를 때까지의 만족하는 가짓수를 구합니다.
2) 투 포인터 알고리즘 유형 : 투 포인터 슬라이딩 윈도우
💡 투 포인터 슬라이딩 윈도우 (Sliding Window with Two Pointers) - 고정된 길이의 윈도우를 배열이나 리스트에서 슬라이딩하면서 특정 조건을 만족하는 부분 구간을 찾는 문제에 사용됩니다. - 예를 들어, 최대 연속 부분 배열의 합을 구하는 등의 문제에 적용할 수 있습니다.
1. [백준 1940번] 주몽 문제 이해
💡 백준 1940번 : 주몽 문제 이해 - 아래의 문제는 연속된 자연수의 합을 구하는 문제입니다.
💡 문제
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
💡 입력
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
💡 출력
- 첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
https://www.acmicpc.net/problem/1940
2. [백준 1940번] 주몽 문제 풀이
💡 [백준 1940번] 주몽 문제 풀이
1. 배열을 구성하며 문자열 배열을 정수 배열로 캐스팅합니다.
2. 정수 배열을 오름차순으로 정렬합니다.
3. 시작 인덱스보다 마지막 인덱스 값이 크면 종료합니다.
4.1. 시작 인덱스와 마지막 인덱스를 더했을 때, m보다 작은 경우 : 시작 값 오른쪽 이동
4.2. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 큰 경우 : 마지막 값을 왼쪽으로 이동
4.3. 시작 인덱스와 마지막 인덱스를 더했을때, m과 같은 경우 : 카운트 값을 올리고 시작 값을 오른쪽 이동, 끝값을 왼쪽으로 이동
5. 최종 카운팅 된 값을 반환합니다.
/**
* 07. 주몽 : 백준 1940번
* 재료들을 기반으로 만들 수 있는 갑옷의 개수를 구하는 문제
*
* @return ResponseEntity
* @link <https://www.acmicpc.net/problem/1940>
* @since 2024.01.06
*/
@GetMapping("/7")
public ResponseEntity question07() {
int answer = 0;
int n = 6; // 재료의 개수
int m = 9; // 갑옷을 만드는데 필요한 수
String input3 = "2 7 4 1 5 3"; // 재료들
// 1. 배열을 구성하며 문자열 배열을 정수 배열로 캐스팅 합니다.
String[] materialStrArr = input3.split("");
int[] materialArr = new int[materialStrArr.length];
for (int i = 0; i < input3.split("").length; i++) {
materialArr[i] = Integer.parseInt(input3.split("")[i]);
}
// 2. 정수 배열을 오름차순으로 정렬합니다.
Arrays.sort(materialArr);
int count = 0; // 갑옷을 만들수 있는 가짓수
int startIdx = 0; // 투포인터의 시작 인덱스
int lastIdx = n - 1; // 투포인터의 마지막 인덱스
// 3. 시작 인덱스 보다 마지막 인덱스 값이 크면 종료합니다.
while (startIdx < lastIdx) {
// 4.1. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 작은 경우 : 시작 값 오른쪽 이동
if (materialArr[startIdx] + materialArr[lastIdx] < m) {
startIdx++;
}
// 4.2. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 큰 경우 : 마지막 값을 왼쪽으로 이동
else if (materialArr[startIdx] + materialArr[lastIdx] > m) {
lastIdx--;
}
// 4.3. 시작 인덱스와 마지막 인덱스를 더했을때, m과 같은 경우 : 카운트 값을 올리고 시작 값을 오른쪽 이동, 끝값을 왼쪽으로 이동
else {
count++;
startIdx++;
lastIdx--;
}
// 5. 최종 카운팅 된 값을 반환합니다.
answer = count;
}
return new ResponseEntity<>(answer, HttpStatus.OK);
}
3. [백준 1940번] 주몽 문제 풀이 : 그림으로 처리과정 이해하기
💡 아래와 그림과 같이 sum으로 9를 구하기 위해 루프를 기준으로 처리과정을 확인합니다. ⭕️ Loop 1 - 시작값 1과 마지막 값 7로 시작을 합니다. - 두 개의 합이 8인 경우이며 m인 9보다 작습니다. - 해당 경우는 Loop2에서 startIdx 값이 1 증가됩니다.
⭕️ Loop2 - 시작 값 2와 마지막 값 7로 시작을 합니다. - 두 개의 합이 9인 경우이며 m의 값인 9와 같습니다. - 그렇기에 count의 값을 증가합니다. 해당 경우는 Loop3에서 시작값을 1 증가하고 마지막 값을 1 감소합니다.
⭕️ Loop3 - 시작 값 3과 마지막 값 5로 시작을 합니다. - 두 개의 합이 8인 경우이며 m의 값보다 작습니다. - 해당 경우는 Loop4에서 시작 값이 1 증가됩니다.
⭕️ Loop4 - 시작 값 4와 마지막 값 5로 시작을 합니다. - 두 개의 합이 9인 경우이며 m 값인 9와 같습니다. - 그렇기에 count의 값을 증가합니다. 해당 경우는 다음이 불가하기에 루프를 종료합니다.
3) 투 포인터 알고리즘 유형: 투 포인터의 합
💡 두 포인터의 합과 차 - 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결합니다. - 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있습니다.
1. [백준 1253번] ‘좋은 수’ 문제 이해
💡 문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.
💡 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
💡 출력 좋은 수의 개수를 첫 번째 줄에 출력한다.
2. [백준 1253번] ‘좋은 수’ 문제 풀이
💡 [백준 1253번] ‘좋은 수’ 문제 풀이
1. 문자열을 배열로 변환합니다.
2. 문자열 배열을 다시 숫자 배열로 변환합니다.
3. 숫자 배열을 순회하면서 값을 구합니다.
4. 값을 기준으로 다음 값과 비교합니다.
4-1 : 시작 값과 종료 값의 합이 찾는 값과 같은 경우
1. 시작 인덱스, 종료 인덱스와 같이 않을 경우 : 종료
2. 시작 인덱스와 같은 경우 : 시작 인덱스 오른쪽으로 이동종료
3. 인덱스와 같은 경우 : 마지막 인덱스 왼쪽으로 이동
4-2: 시작값과 종료값의 합이 찾는 값보다 작은 경우 : 시작 값을 오른쪽으로 이동
4-3: 시작값과 종료값의 합이 찾는 값보다 큰 경우 : 종료 값을 왼쪽으로 이동
/**
* 08. 좋은 수: 백준 1253번
* N 개의 수에서 다른 두수의 합으로 표현되는 수가 있다면 좋은수이고 총 몇개인지 출력
*
* @return ResponseEntity
* @link <https://www.acmicpc.net/problem/1940>
* @since 2024.01.15
*/
@GetMapping("/8")
public ResponseEntity question08() {
int count = 0;
int input1 = 10;
// [STEP1] 문자열을 배열로 변환
String input2 = "1 2 3 4 5 6 7 8 9 10";
String[] inputArr = input2.split(" ");
// [STEP2] 숫자 배열로 변형
int[] inputIntArr = new int[inputArr.length];
for (int i = 0; i < inputArr.length; i++) {
inputIntArr[i] = Integer.parseInt(inputArr[i]);
}
// [STEP3] 숫자 배열을 순회하면서 값을 구함
for (int i = 0; i < inputIntArr.length; i++) {
int startIdx = 0; // 시작 인덱스
int endIdx = input1 - 1; // 마지막 인덱스
int findItem = inputIntArr[i]; // 순회되는 값
// [STEP4] 값을 기준으로 다음 값과 비교합니다.
while (startIdx < endIdx) {
// [STEP4-1] 시작 값과 종료값의 합이 찾는 값과 같은 경우
if (inputIntArr[startIdx] + inputIntArr[endIdx] == findItem) {
// [CASE1] 시작 인덱스, 종료 인덱스와 같이 않을 경우 : 종료
if (startIdx != i && endIdx != i) {
count++;
break;
}
// [CASE2] 시작 인덱스와 같은 경우 : 시작 인덱스 오른쪽으로 이동
else if (startIdx == i) {
startIdx++;
}
// [CASE3] 종료 인덱스와 같은 경우 : 마지막 인덱스 왼쪽으로 이동
else if (endIdx == i) {
endIdx--;
}
}
// [STEP4-2] 시작값과 종료값의 합이 찾는 값보다 작은 경우 : 시작 값을 오른쪽으로 이동
else if (inputIntArr[startIdx] + inputIntArr[endIdx] < findItem) {
startIdx++;
}
// [STEP4-3] 시작값과 종료값의 합이 찾는 값보다 큰 경우 : 종료 값을 왼쪽으로 이동
else {
endIdx--;
}
}
}
return new ResponseEntity<>(count, HttpStatus.OK);
}
3. [백준 1253번] ‘좋은 수’ 문제 풀이 : 그림으로 처리과정 이해하기
⭕️ Loop 1 - 시작값(startIdx)과 마지막 값(endIdx)이 만나는 경우에 i가 1이 되는 경우가 없기에 종료한다.
⭕️ Loop 2 - 시작값(startIdx)과 마지막 값(endIdx)이 만나는 경우에 i가 2로 되는경우가 없기에 종료한다.
⭕️ Loop 3 - 시작값(startIdx)이 1이고 마지막 값(endIdx) 2일 때 두 수의 합이 3이므로 i가 3일때이므로 count++를 한다.
⭕️ Loop 4 - 시작값(startIdx)이 1이고 마지막 값(endIdx) 3일때 두 수의 합이 4이므로 i가 4일때이므로 count++를 한다.
⭕️ Loop 5 - 시작값(startIdx)이 1이고 마지막 값(endIdx) 4일때 두수의 합이 5이므로 i가 5일 때이므로 count++를 한다.
