'이것이 코딩테스트다' 정리하기 👑(2)

💎 개요

---

저번 이코테 정리에 이어서 이번에도 이코테 정리를 해보고자 한다!! 저번 강의들을 통해서 이번에는 그 다음 강의들을 마저 좀더 정리해보고자 한다!! 강의 내용이 조금 분량이 있어서 나눠서 3,4개 정도로 게시글을 작성할 예정이다.

마찬가지로 정리한 내용을 바탕으로 앞으로 파이썬을 잘 사용할 수 있도록 하구 적용해볼 수 있도록 문제를 다양하게 풀어볼 예정이다!!

참고 강의 링크! 👉 https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

💎 알고리즘

---

🍫 정렬 알고리즘

정렬

: 데이터를 특정한 기준에 따라 순서대로 나열

선택 정렬 : 이중 반복문을 이용하여 가장 작은 원소를 찾아 앞쪽으로 자리를 바꾸면서 정렬

for i in range(len(array)):
	min_index = i
	for j in range(i + 1, len(array)):
		if array[min_index] > array[j]:
			min_index = j
	array[i], array[min_index] = array[min_index], array[i]

→ 시간 복잡도는 N번만큼 가장 작은 수를 찾아서 맨앞으로 보내야 함.

이는 빅오 표기법에 따라서 O(N^2)으로 작성함

삽입 정렬 : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입함.

for i in range(len(array)):
	for j in range(i, 0, -1):
		if array[j] > array[j - 1]:
			array[j], array[j - 1] = array[j - 1], array[j]
		else :
			break

→ 시간복잡도는 선택 정렬처럼 반복문이 두 번 중첩되서 O(N^2) 중첩됨

데이터가 거의 정렬되어 있는 경우면 매우 빠르게 동작 → 거의 O(N)임

퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

• 첫 번째 데이터를 기준 데이터(피봇)으로 설정함.
• 피봇을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 함.
• 재귀적으로 수행됨.

→ 시상적인 경우 분할이 절반씩 이루어지면 전체 연산 횟수가 O(NlogN)을 기대 가능(너비 * 높이)

시간복잡도가 평균의 경우 O(NlogN) 으로 가지나 최악의 경우는 O(N^2) 의 시간 복잡도
→ 모두 이미 정렬된 배열을 퀵 정렬로 실행하려고 할 때 최악의 경우

def quick_sort(array, start, end):
	if start >= end:
		return
	pivot = start
	left = start + 1
	right = end
	while left <= right :
		while(left < end and array[left] <= array[pivot]):
			left += 1
		while(right > start and array[right] >= array[pivot]):
			right += 1
		if(left > right):
			array[right], array[pivot] = array[pviot], array[right]
		else :
			array[left], array[right] = array[right], array[left]
	
	quick_sort(array, start, right - 1)
	quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)

계수 정렬 : 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬알고리즘

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터의 개수가 N, 데이터 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)보장

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8 , 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array)):
	count[array[i]] += 1

for i in range(len(count)):
	for j in range(count[i]):
		print(i, end=' ')

시간 복잡도 : O(N + K)

• 계수 정렬은 데이터 범위가 클 때 굉장히 비효율적
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있음!!

🍫 이진 탐색

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

이진 탐색 : 정렬 되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

• 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정
• 시간 복잡도 : O(logN) 탐색 범위를 절반씩 줄임

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
		else:
			start = mid + 1
	return None

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환
• 파라메트릭 서치 : 최적화 문제를 결정 문제(yes, no)로 바꾸어 해결하는 기법

문제

1. 떡볶이 떡 만들기

   start = 0
   end = max(array)
   
   result = 0
   while start <= end:
   	total = 0
   	mid = (start + end) // 2
   	for x in array :
   		if x > mid:
   			total += x - mid
   	if total < m:
   		end = mid - 1
   	else:
   		result = mid
   		start = mid + 1

2. 정렬된 배열에서 특정 수의 개수 구하기

   from bisect import bisect_left, bisect_right
   
   def count_by_range(array, left_value, right_value):
   	right_index = bisect_right(array, right_value)
   	left_index = bisect_left(array, left_value)
   	return right_index - lef_index
   
   n, x = map(int, input().split())
   array = list(map(int, input().split()))
   
   count = count_by_range(array, x, x)
   
   if count == 0:
   	print(-1)
   else: 
   	print(count)

🍫 다이나믹 프로그래밍

다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법 → 이미 계산된 결과는 별도의 메모리 영역에 저장

• 두가지 방식 → 탑다운, 보텀 업
• 동적 계획법으로 불리기도 함
• 자료구조에서의 동적 의미 : 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법
• 반면 다이나믹 프로그래밍에서는 별다른 의미없이 사용된 단어

다이나믹 프로그래밍의 사용 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눠 작은 문제의 답 모아서 큰 문제 해결
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결

피보나치 수열 - 1, 1, 2, 3, 5, 8, 13 …
점화식 : 인접한 항들 사이의 관계식 의미

def fibo(x):
	if x == 1 or x == 2:
		return 1
	return fibo(x - 1) + fibo(x - 2)

단순 재귀 함수 코드 (위처럼) 하면 지수 시간 복잡도를 가지게 됨(동일한 호출이 여러 번 호출 되는 것 확인 가능)

빅 오 표기법으로 : O(2^N) 시간 복잡도

메모이제이션(탑다운) : 한번 계산한 결과를 메모리 공간에 메모하는 기법

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
• 값을 기록해 놓는다는 점에서 캐싱이라고도 함

<탑다운 - 하향식, 보텀업 - 상향식>

전형적인 다이나믹 프로그래밍의 전형적인 형태는 보텀업으로 결과 저장용 리스트는 DP 테이블이라고 부름

탑다운 방식

d = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
		return 1
	if d[x] != 0:
		return d[x]
	d[x] = fibo(x - 1) + fibo(x - 2)

	return d[x]

보텀법 방식

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
	d[i] = d[i - 1] + d[i - 2]

메모이제이션을 이용한 피보나치 수열 함수의 시간 복잡도는 O(N)임

다이나믹 프로그래밍 vs 분할 정복

→ 둘다 최적 부분 구조를 가질 때 사용하나 부분문제의 중복에서는 다름 (분할정복은 X)

• 분할이 이루어진 뒤에 그 문제는 다시 처리하지 않음

• 주어진 문제가 DP 유형임을 파악하는 것이 중요함.

• 다른 알고리즘(그리디, 구현, 완전 탐색)으로 안 풀리면 다이나믹 프로그래밍으로 문제 접근하기

• 탑다운 → 보텀업으로 코드 개선하는 방법 사용해보기

문제

1. 개미 전사

   i 번째 식량창고에 대해서 털지 안 털지 여부를 결정하여 문제 해결

   ai = max(ai-1, ai-2 + ki)

   → i-3 번째 이하는 고려 필요 없음

   n = int(intpu()
   array = list(map(int, input().split()))
   
   d = [0] * 100
   
   d[0] = array[0]
   d[1]= max(array[0], array[1])
   for i in range(2, n):
   	d[i] = max(d[i - 1], d[i - 2] + array[i])
   
   print(d[n - 1])

2. 1로 만들기

   정수 x에 사용하는 연산 4가지, 4개를 적절히 사용하여 1로 만들기

   ai = min(ai-1, ai/2, ai/3, ai/5) + 1

   x = int(input()
   
   d = [0] * 30001
   
   for i in range(2, x + 1):
   	d[i - 1] = d[i -1] + 1
   	if i % 2 == 0:
   		d[i] = min(d[i], d[i // 2] + 1)
   	if i % 3 == 0:
   		d[i] = min(d[i], d[i // 3] + 1)
   	if i % 5 == 0:
   		d[i] = min(d[i], d[i // 5] + 1)
   
   print(d[x])

💎 정리

---

이렇게 이번에는 이코테의 정렬 알고리즘, 이진 탐색, DP의 방법들을 살펴 보았다. 다음에는 다른 내용의 알고리즘을 정리하고자 한다!! 인제 OPIC 시험도 봐서 앞으로는 개발공부에 더 집중해볼 예정이다. 또는! 한주만 쉬고 컴활을 공부할 수도 있고 일단 담주에 여행 다녀오기 전에 최대한 디자인과 코테 준비를 진행해보고자 한다.

파이썬을 이용하여 백준의 쉬운 문제를 차근차근히 풀고 있어서 우선 내가 기억하면 좋을 파이썬의 라이브러리나 알고리즘을 사용하였을 때 그 문제를 velog에 정리하고자 한다!!

화이팅~!