[Programmers] 1. 기본 자료구조: 배열(리스트), 기초 알고리즘: 정렬, 탐색, 재귀

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

자료구조 (Data Structures)와 알고리즘 (Algorithm)은 왜 알아야 하는가?

문제를 풀 때 문제마다 최적의 해법은 서로 다릅니다. 그리고 같은 문제를 풀어도 어떠한 자료구조와 알고리즘을 사용하느냐에 따라 활용되는 저장공간과 수행되는 시간이 달라집니다.
그러므로 문제의 특성을 이해하여 자원을 효율적으로 활용(저장, 삭제, 검색 등)하면서 효과적인 방법으로 문제를 풀어내야 합니다.

자료구조 1. 배열 (Array, List)

배열은 원소들을 순서대로 늘어놓은 것을 말합니다. 파이썬에서는 List로 구현할 수 있습니다.

>>> L = ['Bob', 'Cat', 'Spam', 'Programmers']
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']

1. Python List의 연산 - 리스트 길이와 무관하게 빠르게 실행되는 연산

• .append(): 현재 List의 끝(마지막)에 원소 x를 덧붙이는 연산입니다.
• .pop(): 현재 List의 끝(마지막) 원소를 반환하고 삭제합니다.
  위의 연산들은 맨 끝에 원소를 하나 추가하거나 삭제하므로 리스트의 길이와 무관하게 빠르게 실행되는 연산입니다.

>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L.append('illstandtall')
>>> L
['Bob', 'Cat', 'Spam', 'Programmers', 'illstandtall']

>>> L.pop()
'illstandtall'
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']

2. Python List의 연산 - 리스트 길이에 비례하여 실행시간이 달라지는 연산

• .insert(n, x): 현재 List의 n번째에 x 원소를 추가하는 연산입니다.
• del(L[n]): 리스트 L의 n번째 원소를 삭제합니다.
• .pop(n): 현재 List의 n번째 원소를 반환하고 삭제합니다.

위의 연산들은 원소를 추가/삭제하는 시간 외에 리스트의 크기를 조정하는 시간이 추가됩니다. 그러므로 리스트가 길면 길수록 시간이 오래 걸립니다.

>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L.insert(2, 'data')
>>> L
['Bob', 'Cat', 'data', 'Spam', 'Programmers']

>>> del(L[3])
>>> L
['Bob', 'Cat', 'data', 'Programmers']

>>> L.pop(0)
'Bob'
>>> L
['Cat', 'data', 'Programmers']

정렬과 탐색 그리고 재귀

정렬 (sort)

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것입니다.
• 오름차순이나 내림차순으로 정렬될 수 있으며,
• 정렬 알고리즘에는 선택 정렬 (Selection Sort), 삽입 정렬 (Insertion sort), 퀵 정렬 (Quick Sort), 계수 정렬 (Counting Sort), 합병 정렬(Merge Sort) 등이 있습니다.

Python List의 정렬 연산

• sorted(L): 리스트 L을 오름차순으로 정렬하여 반환합니다. (문자열은 알파벳순)
• .sort(): 현재 List를 오름차순으로 정렬합니다. (문자열은 알파벳순)
• 정렬 연산의 인자들
  • reverse=: 내림차순으로 정렬하고 싶을 때 사용합니다.
  • key=: 다른 기준으로 정렬할 때 사용합니다.

>>> L1 = [3, 2, 4, 5, 1]
>>> L1
[3, 2, 4, 5, 1]
>>> sorted(L1)
[1, 2, 3, 4, 5]

>>> L2 = [3, 2, 4, 5, 1]
>>> L2.sort()
>>> L2
[1, 2, 3, 4, 5]

>>> L2.sort(reverse=True)
>>> L2
[5, 4, 3, 2, 1]

>>> L3 = ['Bob', 'Cat', 'Spam', 'Programmers']
>>> L3
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L3.sort(key=lambda x: len(x)) # 문자열의 길이를 기준으로 정렬하기
>>> L3
['Bob', 'Cat', 'Spam', 'Programmers']

탐색 (Search)

선형/순차 탐색 (Sequential Search)

• 데이터를 차례대로 하나씩 확인하며 원하는 값을 찾아내는 탐색 방법입니다.
• 최적의 경우에는 찾는 원소가 첫 번째에 있어서 O(1)의 시간에 바로 찾을 수 있지만,
• 최악의 경우에는 원소가 마지막에 있어서 $O(N)$ (N=리스트의 길이)의 시간이 걸려서 찾거나 $O(N)$의 시간이 걸렸는데도 리스트에 찾고자 하는 원소가 없을 수 있습니다.

이진 탐색 (Binary Search)

• 이진 탐색은 리스트의 원소가 정렬되어 있는 경우에만 사용할 수 있습니다.
• 탐색 범위를 절반씩 좁혀가며 데이터를 찾아내는 탐색방법입니다.
• 한 번 비교가 일어날 때마다 리스트를 반씩 줄일 수 있습니다. (Divide & conquer)
• 그렇기 때문에 이진 탐색을 이용하여 데이터를 찾을 때 항상 $O(logn)$ 안에 찾을 수 있다는 장점이 있습니다.

# binary search algorithm

while left <= right:
	mid = (left + right) // 2
    if L[mid] == x:
    	answer = mid
    	break
    elif x < L[mid]:
        right = mid - 1
    else:
        left = mid + 1

재귀 (Recursion)

• 문제의 특성이 주어진 문제를 같은 종류의 보다 쉬운 문제(혹은 작은 문제)의 답을 이용하여 풀 수 있을 때 사용할 수 있는 성질입니다.

예: 1부터 N까지 자연수의 합

• 1부터 50까지의 합을 구할 때, 1부터 49까지의 합에 50을 더해 문제를 풀 수 있습니다.
  • 1부터 49까지의 합을 구할 때, 1부터 48까지의 합에 49를 더해 문제를 풀 수 있습니다.
    • 1부터 48까지의 합을 구할 때, 1에 부터 47까지의 합에 48을 더해 문제를 풀 수 있습니다.
      - 1부터 47까지의 합을 구할 때, 1에 부터 46까지의 합에 47을 더해 문제를 풀 수 있습니다.
      중략...

• 위와 같은 성질이 재귀입니다. 1부터 N까지의 자연수의 합을 구하는 코드를 Python 코드로 나타내면 아래와 같습니다.

# recursion

def sum(n):
	return sum(n-1) + n

• 그러나, 위의 방법으로는 답을 구할 수 없습니다. 재귀에는 종료 조건이 매우 중요하기 때문입니다. 종료조건이 없다면 n은 한없이 작아지다가 컴퓨터에 설정된 Recusion depth를 초과하게 되면 오류로 종료될 것입니다.

# recursion

def sum(n):
	if n == 1:		# Base case / trivial case
    	return 1
    else:
    	return sum(n-1) + n

• 재귀 함수는 보통 반복문을 이용한 반복적인(iterative) 접근으로도 풀 수 있습니다.
• 다음은 반복문을 이용한 1부터 N까지 자연수의 합을 구하는 코드입니다.

# recursive -> iterative

def sum(n):
	res = 0
	for i in range(n):
		res += i  
    return res

• 재귀적인 접근과 반복적인 접근 모두 시간 복잡도는 $O(n)$으로 동일합니다.
• 그렇지만 재귀 함수는 함수를 계속 호출하고, 반복적인 접근은 변수를 사용합니다.
• 이는 반복적인 접근이 공간(메모리) 효율성이 좋다고 말할 수 있습니다.

재귀 알고리즘의 응용: 이진 탐색

• 재귀적인 접근이 좋은 이유는 사람이 생각하는 방식으로 프로그래밍을 할 수 있다는 점입니다.
• 위의 이진 탐색 예제에서는 반복적인 접근으로 이진탐색 알고리즘을 나타냈습니다.
• 아래는 재귀적으로 나타낸 코드입니다.

# recursive

def binary_search(L, x, left, right):
	if right > left:
    	return -1
    else:
    	mid = (left + right) // 2
    	if x == L[mid]:
       		return mid
       	elif x < L[mid]:
        	return binary_search(L, x, left, mid-1)
        else:
        	return binary_search(L, x, mid+1, right)

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.