[알고리즘] 1. 배열과 정렬

1. 배열 Array : 일정한 자료형의 변수들을 하나의 이름으로 열거해 사용하는 자료구조.

• 프로그램 내에서 여러개의 변수가 필요할 때
• 하나의 선언을 통해 둘 이상의 변수를 선언
• 다수의 변수로는 하기 힘든 일을 배열을 통해 할 수도 있다.
• ex: 6개의 변수를 사용해야 하는 경우

 num0 = 0
 num1 = 1
 num2 = 2
 num3 = 3
 ...
 -> num = [0,1,2,3,4,5]

 

2. 1차원 배열

• append() ⇒ 쓸 때마다 해당 배열을 복사하는 만큼의 시간이 듦. pop()도 해당
• 배열을 배울 때는 그림을 많이 그려보자. → 복잡한 문제가 나올 때도 그릴 수 있다.
• 알고리즘을 배울 때, 조건문/반복문/이중 조건-반복문을 배우는 것도 도움이 된다.

arr = list()
arr = []
arr = [0] * 10
arr = [1,2,3]

• 배열 원소의 합 계산하기

s = 0
for i in range(N):  # for x in arr :
	s += arr[i]       # s += x

• 배열 원소 중 최댓값 max_v 찾기

max_v = arr[0]         # 첫 원소를 최대로 가정
for i in range(1,N):
	if max_v < arr[i]:
		max_v = arr[i]     # arr[i]가 더 크면 max_v 갱신

• 배열 원소 중 최댓값의 인덱스 max_idx 찾기

max_idx = 0
for i in range(1, N):
	if arr[max_idx] < arr[i]:
		max_idx = i

• 최댓값이 여러 개인 경우 max_idx 찾기

max_idx = 0
for i in range(1, N):
	if arr[max_idx] <= arr[i]:
		max_idx = i

• 찾는 값이 있으면 해당 원소의 인덱스, 없으면 -1을 idx에 넣기

N, V = map(int, input().split())
arr = list(map(int, input().split()))

idx = -1
for i in range(N):
	if arr[i] == V:
		idx = i
		break

3. 정렬 Sort

• 2개 이상의 자료를 키에 의해 작은 값부터 큰 값, 혹은 그 반대 순으로 재배열하는 알고리즘.
• 정렬 종류: 버블 정렬, 퀵 정렬, 카운팅 정렬, 삽입 정렬, 선택 정렬, 병합 정렬

4. 버블 정렬 Bubble Sort

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 시간 복잡도 On제곱

1. 첫번째 원소부터 인접한 원소끼리 자리 교환 → 마지막 원소까지 이동
2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
3. 교환하며 자리를 이동하는 모습이 거품과 비슷하다 하여 버블 정렬이라고 한다.

BubbleSort(a, N):
	for i : N-1 -> 1
		for j : 0 -> j-1
			if a[j] > a[j+1]
				a[j] <-> a[j+1]

def bubble_sort(a, N):        # 정렬할 List, N 원소 
	for i in range(N-1, 0, -1): # 범위의 끝 위치
		for j in range(i):        # 비교할 왼쪽 원소 인덱스 j
			if a[j] > a[j+1]:
				a[j], a[j+1] = a[j+1], a[j]