[ 이것이 코딩테스트다 ] 6일차

안영우·2020년 12월 30일

동빈나 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

6/39

✏️ 서론

어제는 소수 판별(primeNumber)을 배웠다.
오늘은 리스트에 순차적으로 접근하는 방식인 투 포인터(Two Pointer) 알고리즘을 배워보자.

✏️ 본론

투 포인트(Two Point): 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

예를 들어, 한 반에 40명이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야하는 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목할 때 우리는 번호로 한명씩 부르기보다는 2번부터 7번 학생! 이라고 부를 수 있다. 이처럼 순차적으로 접근 할때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현 할 수 있다.

특정한 합을 가지는 부분 연속 수열 찾기 문제를 보자.
양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중 특정한 합을 갖는 수열의 개수를 출력하는 문제이다.

투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이다.

그래서, 부분 연속 수열의 시작점과 끝점을 기록한다.
특정한 부분합을 M이라고 할 때 풀이 순서는 다음과 같다.

시작점(start), 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키자

현재 부분합 M과 같으면 카운트한다.

현재 부분합이 M보다 작으면 end를 1 증가시킨다.

현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.

모든 경우를 확인 할 때까지 2번과 4번의 과정을 반복한다.

코드로 표현하면 다음과 같다.

# 찾고자 하는 데이터의 개수
n = 5
data = [1, 2, 3, 2, 5] 

# 찾고자 하는 합의 값
m = 5

# 초기선언
interval_sum = 0
count = 0
end = 0

for start in range(n):
    while interval_sum < m and end < n:
        interval_sum = interval_sum + data[end]
        end = end + 1
    if interval_sum == n:
        count = count + 1
    interval_sum = interval_sum - data[start]

print(count)
👉🏽 3

결과적으로 카운트 된 경우의 수는 3이다.
투 포인터 알고리즘의 특징은 구현가능한 방식이 매우 많다는 점이다.

이 문제를 투포인터로 해결 할 수 있는 이유는 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키미녀 항상 합이 증가하기 때문이다.

만약, 리스트 내 원소에 음수 데이터가 포함되어있으면 투 포인터 알고리즘으로 문제를 해결 할 수 없다.

이밖에도, 알고리즘은 정렬되어 있는 두 리스트의 합집합 같은 문제에 효과적으로 사용 할 수 있다.

이때, 두 리스트의 모든 원소를 합쳐 정렬한 결과를 계산하는 것이 문제의 요구사항이다.

이 문제를 풀기 위해서는 2개의 리스트 A, B가 주어졌을 때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키면된다. 문제에서 이미 정렬된 결과가 주어지므로 앞에서부터 확인하면 된다.

풀이 순서는 다음과 같다.

정렬된 리스트 A와 B를 받는다.

리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가르키도록 한다.

리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가르키도록 한다.

A[i]와 B[j] 중 더 작은 원소를 결과 리스트에 담는다.

리스트 A와 B에서 더 이상 처리할 원소가 없을 때 까지 2번 ~ 4번의 과정을 반복한다.

코드로 표현하면 다음과 같다.

# 기본버전: 값이 정해져 있을 때
# A 데이터
a = [1, 3, 5]
n = 3
i = 0

# B 데이터
a = [2, 4, 6, 8]
n = 4
j = 0

# 응용버전: input값을 통해서 넣어 줄때
# A 데이터
a = list(map(int, input(). split()))
n = len(a) 
i = 0

# B 데이터
b = list(map(int, input(). split()))
m = len(b) 
j = 0

# result 데이터
result = (m+n) * [0]
k = 0

while i < n or j < m:
    if j > m or (i < n and a[i] < b[j]):
        result[k] = a[i]
        i = i + 1
    else:
        result[k] = a[j]
        j = j + 1
    k = k + 1

for i in result:
    print(i, end = ' ')
👉🏽 1 2 3 4 5 6 8