FORTIS FORTUNA ADIUVAT

1. 투 포인터(Two Pointers) 알고리즘이란?

투 포인터는 두 개의 포인터를 이용하여 배열이나 리스트를 탐색하는 알고리즘 기법이다.
주로 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾거나, 연속된 부분 배열을 탐색하는 문제에서 사용된다.

이 방법을 사용하면 O(N^2) 복잡도의 문제를 O(N)으로 최적화할 수 있습니다.

2. 투 포인터 동작 원리

• 시작점과 끝점에서 이동
• 오름차순 정렬된 배열에서 특정 합(target)을 찾을 때 사용
• 좌측 포인터(left)는 작은 값부터, 우측 포인터(right)는 큰 값부터 이동
• 두 포인터를 조절하면서 특정 조건을 만족하는 값을 찾는다.

아래 예제를 통해 원리에 대한 설명 하겠습니다.

특정 합을 가지는 두 숫자 찾기 (Two Sum)

문제: 정렬된 배열에서 합이 9 되는 두 숫자의 인덱스를 찾는다.

입력 예시

int[] nums = {1, 2, 3, 5, 7, 10, 12};
int target = 9;

투 포인터 진행 과정

1. left(🔴)는 처음 인덱스에서 시작, right(🔵)는 끝에서 시작

2. sum을 비교하면서 작으면 left++, 크면 right--

3. sum == target 이면 정답 찾음

최종결과 : [1, 4] → (nums[1] = 2, nums[4] = 7)

Java 코드

• 시간 복잡도: O(N)
• 두 개의 포인터를 사용하여 선형 탐색 진행

import java.util.Arrays;

public class MainClass {
	public static int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                return new int[]{left, right}; // 정답
            } else if (sum < target) {
                left++; // 합이 작으면 왼쪽 포인터 증가
            } else {
                right--; // 합이 크면 오른쪽 포인터 감소
            }
        }
        return new int[]{-1, -1}; // 정답이 없을 경우
    }
	
	public static void main(String[] args) {
		int[] nums = {1, 2, 3, 5, 7, 10, 12};
		int target = 9;
        int[] result = twoSum(nums, target);
        
        // 최종결과: [1, 4]
        System.out.println("최종결과: " + Arrays.toString(result));
	}
}

3. 투 포인터 응용 예시

슬라이딩 윈도우를 활용한 부분 배열 최소 길이 찾기

문제 : 연속된 부분 배열의 합이 target 이상이 되는 최소 길이를 구하는 문제

          (left 포인터를 이동하며 구간을 줄여가면서 최적 해 찾기)

입력 예시

int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;

포인터 이동 과정

최소 길이 부분 배열: [4, 3] (길이: 2)

Java코드

• 시간 복잡도: O(N)
• 슬라이딩 윈도우(Sliding Window) 방식으로 최적화
• 연속된 부분 배열을 유지하면서 최소 길이 갱신

public class MainClass {
	public static int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, minLength = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right]; // 오른쪽 포인터 확장

            while (sum >= target) { // 조건을 만족하면 최소 길이 업데이트
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left]; // 왼쪽 포인터 축소
                left++;
            }
        }

        return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        int result = minSubArrayLen(target, nums);

        System.out.println("최소 길이: " + result); // 최소 길이: 2 (부분 배열: [4,3])
    }
}

4. 투 포인터 알고리즘이 적합한 문제 유형

1) 정렬된 배열에서 특정 조건을 만족하는 두 수 찾기

• Two Sum 문제 (합, 차이)
• 배열에서 두 숫자의 차이가 K인 쌍 찾기
• 배열에서 곱이 특정 값을 만족하는 두 수 찾기

2) 연속된 부분 배열 문제

• 최소 길이의 부분 배열 찾기
• 가장 큰 합을 가지는 연속된 부분 배열 찾기

3) 문자열 처리 문제

• 가장 긴 중복 없는 부분 문자열 찾기
• 애너그램(Anagram) 검사

4) 백준 및 프로그래머스 관련 문제

• 백준 - 3273번: 두 수의 합, 2470번: 두 용액, 1806번: 부분합, 1644번: 소수의 연속합, 2003번: 수들의 합 2
• 프로그래머스 - 레벨 2: 구명보트, 레벨 3: 보석 쇼핑, 레벨 2: 연속된 부분 수열의 합

5. 정리

투 포인터 알고리즘은 정렬된 배열에서 최적의 방법으로 특정 조건을 만족하는 요소를 찾는 강력한 알고리즘 입니다.

• 브루트포스 대비 O(N²) → O(N)으로 성능 최적화 가능
• 슬라이딩 윈도우와 결합하여 다양한 문제 해결 가능
• 데이터 크기가 클수록 효과적인 알고리즘

위와같은 장점도 있지만, 투포인터 알고리즘은 중복된 값이 있는 경우 차가적인 고려가 필요합니다. 또한 배열이나 리스트에서는 효과적이지만 트리, 그래프, 해시맵과 같은 비선형 자료구조에서는 적용 하기 어렵다는 단점이 있습니다.

소수(Prim Number)란?

소수(Prime Number)는 약수로 1과 자기 자신만을 약수로 가지는 정수입니다. 
예를 들어, 
8의 약수는 "1, 2, 4, 8" 입니다. 1과 8 이외에 2,4를 약수를 가지고 있어 8은 소수가 되지 않습니다.
11의 약수는 "1, 11"인데, 1과 11을 약수로 가지는데요. 즉, 1과 자기 자신만을 가지게 되므로 11은 소수 입니다.

소수(Prim Number) 구하기 풀이1

2~1000000의 범위에서 소수를 구해 봤습니다.(1은 소수가 아니므로 제외)
반복문(for문)을 두번 사용하여 1을 제외한 단순히 범위에 따라서 모든 수를 나누어 주었습니다.

8 => 2,3,4,5,6,7,8 / 2로 나누어 짐 소수 X (break; 실행)
9 => 2,3,4,5,6,7,8,9 / 3으로 나누어짐 소수 X (break; 실행)
10 => 2,3,4,5,6,7,8,9,10 / 2으로 나누어짐 소수 X (break; 실행)
11 => 2,3,4,5,6,7,8,9,10,11 / 어떤수로도 나누어 지지 않음 O(소수)

풀이 1은 위와 같이 2~1000000까지 모두 수행하여 소수를 구했습니다. 
실행 결과를 보면 127.133초 / 나누기 횟수는 37567404990번 했다는 것을 알 수 있습니다.
풀이 2에서 이제 성능을 개선 해보도록 하겠습니다.

소스코드

public class PrimNumber1 {
	public static void main(String[] args) {
		long count = 0L;				// 나눗셈 횟수
		
		double beforeTime = System.currentTimeMillis();
		
		for(int i = 2; i <= 1000000; i++) { 
			int j;
			for(j=2; j<=i; j++) {
				count++;
				if(i%j == 0)
					break;
			}
			if(i==j)
				System.out.println(i);
		}
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행 결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 127.133
나누기 횟수 : 37567404990

소수(Prim Number) 구하기 풀이2

풀이 2에서는  11.382초 / 나누기 횟수 3084786715번 했다는 것을 확인 했습니다.
풀이 1알고리즘 보다는 조금더 성능이 좋아 졌습니다.
풀이 2에서는 2는 소수임을 인지하고 배열에 2를 prime배열에 저장하고 
2를 제외한 나머지 짝수는 전부 2로 나누어 지기때문에 소수가 될 수 없음을 알고, 
홀 수만을 소수를 구해야 되는 범위로 잡고, 홀수 임에도 기존에 찾은 수소들과 다시 나누어 
나누어 지지 않으면 소수로 판별 하여 구하였습니다.
정리하면,

1. prime 배열에 소수 2를 저장
2. prime 배열에 저장되어 있는 기존에 구했던 소수를 이용해 정수를 나누어 준다.
  - i = 3 / prime => {2} : i / prime[0](3/2) 는 나누어 지지 않는다 => 소수O => prime 배열에 저장
  - i = 4 / prime => {2,3} : i / prime[0](4/2) 는 나누어 진다 => 소수X
  - i = 5 / prime => {2,3} : i / prime[0](5/2) 는 나누어 지지 않는다 => 소수O => prime 배열에 저장

위와 같은 방법으로 성능을 개선 하였습니다. 하지만, 알고리즘 성능은 풀이1보다 더 좋아졌지만
배열을 사용하기 때문에 메모리(자원)를 더 많이 사용 하는 것을 알 수 있습니다.
풀이 3에서는 에라토스테네스의 접근 방법을 사용하여 성능과 자원사용을 더 개선 해보겠습니다.

소스코드

public class PrimNumber2 {
	public static void main(String[] args) {
		long count = 0L;				// 나눗셈의 횟수
		int ptr = 0;					// 찾은 소수의 개수
		int[] prime = new int[500000];	// 소수를 저장
		
		prime[ptr++] = 2;			// 2는 소수이다
		
		double beforeTime = System.currentTimeMillis();
		
		// 홀수만 검사 -> 짝수는 2를 제외 전부 소수 이기때문(2로나눠짐)
		for(int i = 3; i<=1000000; i+=2) {
			int j;
			// 기존에 찾은 소수로 나누어 나눠지지 않으면 소수
			for(j=1; j < ptr; j++) {
				count++;
				if( (i%prime[j]) == 0)
					break;
			}
			if( ptr == j )
				prime[ptr++] = i;
		}
		
		for(int i = 0; i < ptr; i++)
			System.out.println(prime[i]);
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 11.382
나누기 횟수 : 3084786715

소수(Prim Number) 구하기 풀이3

위와 같이 제곱근(루트) 값을 알 수 있는데요.

아래와 같은 방법으로 "2~N의 제곱근"의 범위로 잡고 나누어 소수를 판별 할 수 있습니다.

i = 2, j=2, j <= 1.xxx  →  j <= 1.xxx (2 < 1.xxx) 거짓  →  소수O
i = 3, j=2, j <= 1.xxx  →  j <= 1.xxx (2 < 1.xxx) 거짓  →  소수O
i = 4, j=2, j <= 2  → j <= 2 (2 <= 2) 참 → 4%2==0 참 → 소수X
i = 5, j=2, j <= 2.xxx → j <= 2.xxx(2<=2.xxx) 참 → 5%2==0 거짓 → 소수O
i = 6, j=2, j <= 2.xxx → j <= 2.xxx(2<=2.xxx) 참 → 6%2==0 참 → 소수X

소스코드

public class PrimNumber3 {
	public static void main(String[] args) {
		int count = 0;
		
		double beforeTime = System.currentTimeMillis();
		
		for(int i = 2; i<=1000000; i++) {
			boolean isPrim = true;
			for(int j=2; j<=Math.sqrt(i); j++) {
				count++;
				if( (i%j)==0 ) {
					isPrim = false;
					break;
				}
			}
			
			if( isPrim )
				System.out.println(i);
			
		}
		
		double afterTime = System.currentTimeMillis();
		double secDiffTime = (afterTime - beforeTime) / 1000;
		
		System.out.println("실행 시간(m) : " + secDiffTime);
		System.out.println("나누기 횟수 : " + count);
	}
}

실행결과

2
3
5
7
11
...
999959
999961
999979
999983
실행 시간(m) : 1.008
나누기 횟수 : 67740404

문제

N개의 숫자가 공백 없이 써 있다. 이숫자를 모두 합해 출력하는 프로그램 작성

입력

1번째 줄에 숫자의 개수 N(1 <= N <= 100), 2번째 줄에 숫자 N개가 공백 없이 주어진다

출력

입력으로 주어진 숫자 N개의 합을 출력

코드 작성

import java.util.Scanner;

public class MainClass {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt(); // 숫자의 개수
		String inputNumber = scan.next(); // N개의 숫자
		
		char [] numbers = inputNumber.toCharArray();
		int result = 0;
		
		for(char number : numbers) {
			String temp = String.valueOf(number);
			result += Integer.parseInt(temp);
		}	
		
		System.out.println(result);
	}
}

풀이(설명)

1. 입력을 받기위해 Scanner 클래스를 사용하여 "숫자의 개수, 공백 없이 주어진 N개의 숫자"를 입력을 받음.

2. N개의 숫자(inputNumber)를 String으로 받아 toCharArray() 함수를 사용하여 char 배열 numbers에 저장.

3.  numbers 배열에 저장된 값들을 가져와 result에 중복 더하여 숫자의 합을 구함.

해당 문제는 배열과 형변환만 잘 활용하면 쉽게 풀수 있는 문제 입니다. 즉, String에 저장된 값을 char 배열 형태로 저장한 다음 배열에 있는 값들을 반복문을 사용하여 더해주면 되는데 이때 합을 구하기 위해 "String -> int"로 형변환을 한 다음 더해주는 방식으로 쉽게 풀 수 있습니다.