이론정리

들어가기 전

순차 탐색 (Sequential Search)

가장 기본적인 탐색 방법

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 경우 사용

수 많은 데이터를 가진 리스트 내에 찾을 데이터가 존재하고 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음

사용하는 곳

• 리스트 내에 특정 원소가 있는지 체크
• 원소의 개수 세기
• 등등 수많은 곳에서 순차 탐색이 이용됨

시간 복잡도

• O(N)

순차 탐색 예제 코드

# 순차 탐색 소스코드 구현
def sequential_search(n, target, arr):
	# 각 원소를 하나씩 확인하며
	for i in range(n):
		# 현재 원소가 찾고자 하는 원소와 동일한 경우
		if arr[i] == target:
			return i + 1 # 현재의 위치 반환 (인덱스 때문에 +1)

print('생성할 원소 개수와 찾을 문자열을 공백으로 구분하여 입력')
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print('앞서 적은 원소 개수만큼 문자열을 공백으로 구분하여 입력')
arr = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, arr)

트리(Tree) 자료 구조

• 노드
  • 정보의 단위, 어떠한 정보를 가지고 있는 개체
  • 종류
    • 부모 노드
      • 현재 노드의 바로 위 상위 노드
    • 자식 노드
      • 현재 노드의 바로 아래 하위 노드
    • 루트 노드
      • 최상단 노드
    • 단말 노드
      • 최하단 노드
• 서브 트리
  • 트리에서 일부를 때어낸 구조의 트리
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합
• 큰 데이터를 처리하는 소프트웨어(데이터베이스 같은)는 대부분 데이터를 트리 형태로 저장해 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능

이진 탐색 (Binary Search)

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾아내는 탐색 방법
• 시작점, 끝점, 중간점의 위치를 나타내는 변수 3개를 사용
• 조건 : 정렬이 되어 있어야 함
• 시간 복잡도 : O(logN)

탐색 과정

1. 시작점과 끝점을 확인하고 둘 사이의 중간점을 지정
   1. 소숫점 이하는 버리는 방식으로 중간점을 지정
2. 중간점과 찾으려는 데이터를 비교하여
   1. 중간점보다 크면 중간점을 시작점으로 변경
   2. 중간점보다 작으면 중간점을 끝점으로 변경
3. 2의 과정을 데이터를 찾을 때까지 반복

구현 방법

구현 방법 2가지

재귀 이용

# 재귀를 통한 이진 탐색 구현
def binary_search(array, target, start, end):
    if start > end:              # 시작점이 끝점보다 큰 경우 None반환
        return None
    mid = (start + end) // 2       # 중간점 지정
    if array[mid] == target:       # 데이터를 찾은 경우
        return mid                   # 위치 반환
    elif array[mid] > target:      # 더 큰 경우
        return binary_search(array, target, start, mid - 1) # 끝점을 중간점 -1 로 바꾸고 재귀
    elif array[mid] < target:      # 더 작은 경우
        return binary_search(array, target, mid + 1, end)   # 시작점을 중간점 +1 로 바꾸고 재귀

# n: 원소 개수, target: 찾을 데이터
n, target = map(int, input().split())
# 전체 원소 입력
array = list(map(int, input().split()))

# 결과 받아옴 (None or 중간점)
result = binary_search(array, target, 0, n - 1)
if result == None:
	print('원소가 존재하지 않습니다')
else:
	print(result + 1) # 위치 출력

반복문을 이용

# 반복문을 통한 이진 탐색 구현
def binary_search(array, target, start, end):
	while start <= end:              # 시작점이 끝점보다 클 때까지 반복
		mid = (start + end) // 2       # 중간점 지정
		if array[mid] == target:       # 데이터를 찾은 경우
			return mid                   # 위치 반환
		elif array[mid] > target:      # 더 큰 경우
			end = mid - 1                # 끝점을 중간점 -1 로 바꿈
		elif array[mid] < target:      # 더 작은 경우
			start = mid + 1              # 시작점을 중간점 +1 로 바꿈

# n: 원소 개수, target: 찾을 데이터
n, target = map(int, input().split())
# 전체 원소 입력
array = list(map(int, input().split()))

# 결과 받아옴 (None or 중간점)
result = binary_search(array, target, 0, n - 1)
if result == None:
	print('원소가 존재하지 않습니다')
else:
	print(result + 1) # 위치 출력

코딩테스트에서 이진 탐색

• 앞의 코드를 보면 이진 탐색이 단순하다고 생각하고 넘길 수 있음
• 하지만 참고할 코드가 없는 상태에서 구현하는 것은 상당히 어려운 작업일 수 있음
  • 존 벤틀리에 의하면 이진 탐색 코드를 제대로 작성한 프로그래머는 10% 내외였다고 함
• 이진 탐색은 코딩 테스트에 자주 등장함 → 코드가 길지 않아 여러번 입력해 보며 외우는 것을 추천함
• 높은 난이도의 문제에서 이진 탐색을 같이 사용하는 문제가 출제되기도 함
• 탐색 범위가 2,000만을 넘어간다면 이진 탐색으로 문제에 접근하는 편이 좋음
• 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많음
• 파라메트릭 서치(Parametric Search) 유형으로 많이 출제됨
  • 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
  • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
  • 코딩테스트에서 파라메트릭 서치 유형은 이진 탐색을 주로 이용

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조

특징

• 부모 노드보다 왼쪽 자식 노드가 작음
• 부모 노드보다 오른쪽 자식 노드가 큼

탐색 과정

1. 루트 노드부터 시작. 찾을 데이터와 비교
   1. 크면 오른쪽 자식 노드로 탐색
   2. 작으면 왼쪽 자식 노드로 탐색
2. 1의 과정을 데이터를 찾을 때까지 반복

→ 구현 방법은 알고리즘보다 자료구조에 가까우며 이진 탐색 트리 구현 문제는 출제 빈도가 낮으므로 패스함

문제 풀이

부품 찾기

전자 매장에 부품이 N개 있음

각 부품은 정수 형태의 고유 번호가 있음

손님이 M개 종류의 부품을 대량으로 구매를 원함

이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하거라

입력 조건

• 첫째 줄에 정수 N이 주어짐 (1 ≤ N ≤ 1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어짐 (1 ≤ 정수 ≤ 1,000,000)
• 셋째 줄에는 정수 M이 주어짐 (1 ≤ N ≤ 100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어짐 (1 ≤ 정수 ≤ 1,000,000)

출력 조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes, 없으면 no를 출력

입력 예시

5
8 3 7 9 2
3
5 7 9

출력 예시

no yes yes

문제 풀이

import sys
input = sys.stdin.readline

def bSearch(arr, t, s, e):
    while s <= e:
        mid = (s + e) // 2
        if arr[mid] == t:
            return mid
        elif arr[mid] > t:
            e = mid - 1
        elif arr[mid] < t:
            s = mid + 1

n = int(input())
parts = sorted(list(map(int, input().split())))
m = int(input())
fparts = list(map(int, input().split()))

for t in fparts:
    result = bSearch(parts, t, 0, n - 1)
    if result:
        print('yes', end=' ')
    else:
        print('no', end=' ')

• 부품의 번호의 범위가 작으면 계수 정렬을 이용할 수도 있을 것이다
• 집합(Set) 자료형을 이용해 in 검사를 이용해 풀 수도 있을 것이다
  • 집합 자료형은 특정 데이터가 존재하는지 검사할 때 유용함

떡볶이 떡 만들기

요청한 떡의 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구해라

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어짐 (1 ≤ N ≤ 1,000,000 , 1 ≤ M ≤ 2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어짐. 떡의 총 합은 항상 M이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있음. 높이는 10억보다 작거나 같은 양의 정수 또는 0임

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력

입력 예시

4 6
19 15 10 17

출력 예시

15

문제 풀이

import sys
input = sys.stdin.readline

def bSearch(arr, t, s, e):
    result = 0                     # 떡 길이가 조건을 만족할 경우 담을 변수
    while s <= e:
        mid = (s + e) // 2         # 중간 높이 설정
        rc_len = 0                 # 잘린 떡의 총 길이를 저장할 변수
        for i in arr:              # 떡들 중에
            if i > mid:            # 중간 설정 높이보다 크면
                rc_len += i - mid  # 잘린 부분을 합함
        
				if rc_len < t:             # 떡들의 합이 조건을 만족하지 않으면
            e = mid - 1            # 더 자르기 위해 중간 높이 -1을 끝 높이로 설정
        elif rc_len > t:           # 떡들의 합이 조건을 만족하면
            s = mid + 1            # 더 최적화 된 합이 있을 수 있으므로 중간 높이 +1을 시작 높이로 설정
            result = mid           # 조건을 만족하므로 일단 결과에 저장
        else:
            return mid             # 최적화된 높이 일 경우 바로 리턴
    return result                  # 반복이 끝나고 남은 값을 리턴

n, m = map(int, input().split())
rc = sorted(list(map(int, input().split())))
print(bSearch(rc, m, 0, rc[-1]))   # 0부터 가장 긴 떡의 길이을 매개변수로 보냄

• 전형적인 이진 탐색 문제
• 파라메트릭 서치(Parametric Search) 유형
  • 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
  • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
  • 코딩테스트에서 파라메트릭 서치 유형은 이진 탐색을 주로 이용

금주의 문제

1654번: 랜선 자르기

2805번: 나무 자르기

2110번: 공유기 설치

버블(Bubble)

옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 알고리즘

(앞에서 부터 큰 값을 뒤로 보내는 것과 같음)

구현이 가장 쉽지만 가장 비효율적인 알고리즘 : 매번 스왑을 해야하기 때문

시간 복잡도 : O(N^2)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("버블 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 버블 정렬
for i in range(0, n):
    for j in range(1, n-i):
        if list[j-1] > list[j]:
            list[j - 1], list[j] = swap(list[j-1], list[j])
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

선택 (Selection)

가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

가장 윈시적이고 기초적인 방법이며 비효율적임

시간 복잡도 : O(N^2)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("선택 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 선택 정렬
index = 0
for i in range(0, n):
    min = 9999
    for j in range(i, n):
        if min > list[j]:
            min = list[j]
            index = j
    list[i], list[index] = swap(list[i], list[index])
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

삽입 (Insert)

각 숫자를 적절한 위치에 삽입하는 알고리즘

(뒤로 가면서 앞의 숫자 크기를 보고 그 사이에 적절히 삽입)

선택, 버블 정렬에 비해 필요한 경우에만 위치를 바꿔 좀 더 효율적임

미리 어느정도 정렬이 되어 있다면 아주 빠르게 끝낼 수 있음

시간 복잡도 : O(N^2) (최악의 경우)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("삽입 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 삽입 정렬
    # while 문
for i in range(1, n):
    key = list[i] # key : 정렬할 원소
    j = i - 1
    while j >= 0 and list[j] > key:
        list[j+1] = list[j]
        j = j - 1
    list[j+1] = key
    # for 문
'''for i in range(0, n-1):
    #for j in range(0, i+1):
    #    print(list[j], end=' ')
    for j in range(0, i+1):
        if list[i-j] > list[i-j + 1]:
            list[i-j], list[i-j + 1] = swap(list[i-j], list[i-j + 1])
    #print("")'''
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

퀵 (Quick)

대표적인 '분할 정복' 알고리즘(Divide and conquer algorithm)으로, 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 것을 반복 하는 알고리즘.

[방법]

기준 값인 피벗(Pivot)이 필요 (보통 첫 번째 원소를 피벗으로 사용함)

기준 값보다 큰 값을 배열의 왼쪽부터, 작은 값을 오른쪽부터 찾음.

작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환.

작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환.

위 과정을 기준 값의 좌우측에 반복

시간 복잡도:

O(N * logN) (평균)

O(N^2) (최악)

-> 피벗값에 따라 최악의 경우가 생길 수 있음 [ex) 이미 정렬된 배열]

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def quickSort(start, end):
    if start>=end:  # 원소가 1개인 경우 그대로 둠
        return
    pivot = start   # 피벗은 첫번째 원소
    i = start + 1
    j = end
    while i <= j:   # 엇갈릴 때까지 반복
        while(i <= end and list[i] <= list[pivot]):     #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복
            i = i + 1
        while(j > start and list[j] >= list[pivot]):    #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복
            j = j - 1
        if(i > j):  # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환)
            list[pivot], list[j] = swap(list[pivot], list[j])
        else:       # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환)
            list[i], list[j] = swap(list[i], list[j])
    quickSort(start, j - 1); # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
    quickSort(j + 1, end);     # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
# 정렬할 리스트 입력
list = list(map(int, input("퀵 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 퀵 정렬
quickSort(0, n-1)
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

병합 (Merge)

퀵 정렬과 같은 분할 정복 알고리즘을 사용하는 정렬 알고리즘. 일단 반으로 나누고 나중에 정렬하는 방식

• 퀵 정렬과 다르게 피벗 값에 상관없이 정확히 반을 나누어 정렬하므로 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장.

[방법]

다 쪼개진 원소들을 합치면서 정렬을 수행

합쳐진 배열은 정렬이 됨

최종적으로 합쳐지면 정렬이된 전체 배열을 얻음

시간 복잡도 : O(N * logN)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def mergeSort(start, end):
    if end == start:
        return start
    else:
        half = (end - start) // 2
        l = mergeSort(start, half)
        r = mergeSort(half+1, end)
    
        

# 정렬할 리스트 입력
list = list(map(int, input("병합 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 병합 정렬
print()
mergeSort(list)
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

힙 (Heap)

• 힙 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

셸

삽입정렬을 보완한 알고리즘