2022-07-22 TIL

 

☝ 알고리즘

• 반복문을 돌려서 반복문의 결과로 나오는 값 중 최댓값이나 최솟값을 구해야 하는 경우,
  반복문 내에서 반복문의 결과를 받을 변수를 선언하고,
  반복문 밖에서는 반복문의 결과를 받아온 변수와 비교하여 최종 값을 저장할 변수를 설정한다.
• 예시

# 1부터 10까지 반복문을 돌려 최댓값을 찾는 경우

#최종값을 받을 변수 선언
result = 0

for i in range(1, 11) :

	#반복문의 리턴값을 받을 변수 선언
    count = 0
    
	for x in range(n) :
    	for y in range(m) :
        	#로직 실행 생략
			count += 1
    
    #반복문 실행 결과값과 외부의 result(처음은 0)과 max 비교
    result = max(count, result)
    
    #실행 결과 외부의 result 값 변경

 

 

☝ 재귀 함수를 사용해 벽 세우기 코드

• 랜덤한 3곳의 좌표에 벽을 세워야 한다고 가정할 때 재귀 함수를 사용해 모든 좌표를 얻을 수 있다.
• 예시

def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)
        result = max(result,score())
        return

    #빈공간에 울타리 설치 
    #DFS 이용해 울타리 설치 가능한 모든경우의 수 탐색
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                count+=1
                dfs(count)
                graph[i][j] = 0
                count-=1
                #맵의 상태가  count값이 3이 된 이전과 이후가 계속해서 바뀌기 때문에 
                #모든 울타리 설치 경우의 수를 구할 수 있다.

 

 

☝ 정렬

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 정렬 알고리즘은 이진 탐색(Binary Search)의 전처리 과정
• 대표적인 정렬 알고리즘 '선택 정렬', '삽입 정렬', '퀵 정렬', '계수 정렬'

 

☝ 선택 정렬

• 두 개의 데이터 중 작은 것을 선택해서 정렬하는 방식
• 선택 정렬 예시

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

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

print(array)

• array[i], array[min_idx] = array[min_idx], array[i] => 스와프(Swap) 코드
• O(N*2)의 시간 복잡도

 

☝ 삽입 정렬

• 특정 데이터를 특정 위치에 삽입하는 정렬 방식
• 선택 정렬에 비해 구현 난도가 높지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적
• 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 정렬되어 있을수록 효율적
• O(N*2)의 시간 복잡도
• 삽입 정렬 예시

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

for i in range(1, 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

print(array)

 

☝ 퀵 정렬

• 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식
• 퀵 정렬에서는 큰 수와 작은 수를 교환하기 위한 기준으로 '피벗(Pivot)'이 사용됨
• 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 구분됨
• O(NlogN)의 시간 복잡도

 

☝ 호어 분할(Hoare Partition)

• 리스트에서 첫 번째 데이터를 피벗으로 설정
• 리스트의 첫 번째 데이터를 피벗으로 설정하고
  왼쪽에서부터 피벗보다 큰 수를 선택, 오른쪽에서부터 피벗보다 작은 수를 선택
• 이후 두 데이터의 위치를 변경
• 위 과정을 반복 후에 왼쪽에서 찾는 값과 오른쪽에서 찾는 값이 엇갈리는 경우
  작은 데이터와 피벗을 변경
• 이렇게 피벗이 이동한 상태에서 피벗을 기준으로 왼쪽은 피벗보다 작고,
  오른쪽은 피벗보다 크게 데이터가 정렬되는데 이것을 분할 혹은 파티션이라고 함
• 각 파티션에 대해 다시 해당 과정을 반복
• 같은 과정을 파티션 내에서 반복하기 때문에 재귀 함수로 구현할 수 있다.
• 퀵 정렬 재귀 함수의 종료 조건은 리스트의 개수가 1개일 때
• 퀵 정렬 예시

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

def quick_sort(array) :
  #원소가 1개인 경우 종료
  if len(array) <= 1 :
    return array

  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x <= pivot]
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

☝ 계수 정렬

• 특정한 조건이 부합할 때 사용하는 매우 빠른 정렬 알고리즘
• 모든 데이터가 양의 정수이고 데이터의 개수가 N개, 데이터 중 최댓값이 K일 때,
  계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 10**6을 넘지 않아야 효과적
• 계수 정렬은 별도의 리스트를 선언하고 리스트에 정렬 정보를 담는 방식
• 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리
• 계수 정렬의 공간 복잡도는 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=' ')

 

 

☝ 튜플 데이터 정렬

• 튜플 데이터를 입력받고 정렬하여 출력하기 예시

n = int(input())
graph=[]
for i in range(n) :
  input_data = input().split()
  graph.append((input_data[0], int(input_data[1])))

graph = sorted(graph, key=lambda student: student[1])

for student in graph :
  print(student[0], end=' ')

 

 

☝ 이진 탐색

• 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있다.
• 이진 탐색은 위치를 나타내는 변수 3개를 사용 👉 탐색하고자 하는 범위의 시작점, 끝점, 중간점
• 중간 인덱스가 소수점이 붙는 경우 소수점 이하를 버린 인덱스를 중간점으로 설정한다.
• 이진 탐색의 시간 복잡도는 O(longN)
• 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색을 고려해보는 것이 좋음
• 이진 탐색 재귀 함수로 구현 예시

def binary_search(array, target, start, end) :
  if start > end :
    return None
    
  mid = (start+end) // 2

  if array[mid] == target :
    return mid
  elif array[mid] > target :
    return binary_search(array, target, start, mid - 1)
  else :
    return binary_search(array, target, mid + 1, end)


n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None :
  print("원소가 존재하지 않습니다.")
else :
  print(result+1)

 

 

☝ 트리 구조

• 트리는 부모 노드와 자식 노드의 관계로 표현
• 트리의 최상단 노드를 루트 노드라 함
• 트리의 최하단 노드를 단말 노드라 함
• 트리의 일부도 트리 구조이며, 이를 서브 트리라 함

 

 

☝ 이진 탐색 트리

• 트리 자료구조 중에서 가장 간단한 형태의 이진 탐색 트리
• 이진 탐색 트리의 부모 노드는 왼쪽 자식 노드보다 크다
• 이진 탐색 트리의 부모 노드는 오른쪽 자식 노드보다 작다
• 이진 탐색 트리에서