가장 작은 데이터를 맨 앞의 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복
선택 정렬 과정
array = [7,5,9,0,3,1,6,2,4,8]
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] // 두 개의 순서를 바꿈
print(array)
//선택정렬의 코드
선택 정렬은 N-1번 만큼 가장 작은 수를 찾기 위해 비교 연산을 진행하기 때문에,
N+(N-1)+(N-2)+...+2 ~= N(N+1)/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)
//삽입 정렬의 코드
삽입 정렬도 앞선 선택 정렬과 같이 반복문을 두개 연달아 사용했기 때문에
시간 복잡도는 O(N^2)형태라고 볼 수 있다.
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
'피벗'이라는 기준을 설정해 보통 정렬을 진행하는데, 가장 대표적인 '호어 분할' 방식에서는
리스트의 첫 번째 데이터를 피벗으로 설정해 정렬을 진행한다.
퀵 소트의 진행 과정
앞에서부터 피벗보다 큰 데이터와 작은 데이터의 위치를 변경하며 정렬을 진행한다.
만약 두 데이터의 위치가 서로 엇갈리면(큰 데이터가 뒤쪽, 작은 데이터가 앞쪽)
작은 데이터와 피벗의 위치를 변경하여 분할을 수행한다.
만약 분할된 리스트의 길이가 1인 경우에는 해당 리스트에 대해서 정렬을 중지한다.
피벗의 위치가 변경되면 이후 분할된 리스트에 대해 동일한 작업을 반복하여 정렬을 진행한다.
//가장 대표적으로 사용되는 직관적인 퀵 정렬 소스코드
def quick_sort(li, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and li[left] <= li[pivot]:
left += 1
while right > start and li[right] >= li[pivot]:
right -= 1
if left > right:
li[right], li[pivot] = li[pivot], li[right]
else:
li[left], li[right] = li[right], li[left]
quick_sort(li, start, right - 1)
quick_sort(li, right + 1, end)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
quick_sort(array, 0, len(array) - 1)
print(array)
퀵 정렬은 N개의 데이터를 절반씩 나눈다고 도식화 시
O(Nlog(N))의 시간 복잡도를 지닌다.
계수 정렬
가장 큰 데이터와 가장 작은 데이터의 범위가 담기도록 리스트를 생성하고
데이터의 갯수만큼 해당 인덱스에 1을 더해 개수를 저장하고 이후 개수가 저장된 리스트의 앞에서부터 개수만큼 출력
따라서
"데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때"만 사용 가능하다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(li) + 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 = ' ')
//계수 정렬 소스코드
가장 대표적인 예시인 팩토리얼을 재귀로 구현한 방식과 재귀를 이용하지 않은 방식으로 표현하면
//재귀를 이용한 방식
int factorial(int n) {
if (n === 1) {
return 1;
}
return n * factorial(n-1);
}
//재귀를 이용하지 않은 방식
int factorial_nonrecursive(int n) {
result = 1
for i in range(1,n+1):
result *=i
return result
}
재귀를 이용한 방식이 코드가 짧고 간편하다.
따라서, 재귀함수는 변수를 여럿 만들 필요가 없고 반복문을 사용하지 않아도 되기에 간결한 코드가 된다는 장점이 있으나연속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값을 stack에 저장하며 지연이 생긴다는 단점도 있다.
장점
가독성: 코드가 더 직관적이고 읽기 쉬우며 변수를 여러개 만들 필요가 없다.
문제 해결이 편함: 재귀식을 그대로 가져오면 되기 때문에 문제 해결에 대한 접근을 손쉽게 얻을 수 있다.
단점
성능: 지속적인 함수 호출로 호출 스택에 작업이 지속적으로 추가되어 성능 저하가 발생할 수 있다.
이런 식으로 반복되는 값에 대한 예외 처리가 없는 경우도 성능 저하 발생 가능
4. 그래프
노드와 간선으로 이루어진 자료구조를 말한다.
노드(Node) : 데이터를 저장하는 위치, 정점(Vertex)라고도 함.
간선(Edge) : 노드와 노드, 정점과 정점을 연결하는 선
보통 그래프를 표현하는 방식은 인접 행렬 방식과 인접 리스트 방식으로 나뉨
인접 행렬(Adjacency Matrix) 방식
2차원 배열로 그래프의 연결 관계를 표현하는 방식
연결이 되어있지 않은 노드끼리는 무한의 비용/0으로 가정함.
모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리가 낭비됨
인접 리스트(Adjacency List) 방식
'연결 리스트'라는 자료구조를 이용해 구현(C++/Java), 파이썬은 기본 리스트 라이브러리 사용 가능
리스트로 그래프의 연결 관계를 표현하는 방식
두 개의 노드가 연결되어있는지 확인하는 과정이 필요해 정보를 얻는 속도가 느림
인접 행렬과 인접 리스트 방식
DFS(Depth-First-Search)
말 그대로 깊이 우선 탐색 방식을 의미한다.
구현 시 대부분 재귀함수를 이용한다.
아래 그림과 동작 과정,코드를 통해 이를 이해해보자
일반적으로 DFS의 동작 과정은 다음과 같다.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
DFS 동작 방식 GIF
보통 코딩테스트/문제에서는 관행적으로 번호가 낮은 순으로 처리하기에 정렬의 필요성 존재.
def dfs(graph,v,visited):
visited[v] = True
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
dfs(graph,1,visited)
dfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.
보통 DFS는 다음과 같은 상황에 사용한다.
모든 경우를 하나하나 전부 탐색하는 완전탐색 문제(조합, 순열)
단순히 두 지점 간의 경로가 존재하는지 여부를 찾는 문제(조건문 넣으면 중간에 종료 가능) => 백트래킹
BFS(Breadth-First-Search)
말 그대로 너비 우선 탐색 방식을 의미한다.
보통 선입선출 방식인 큐 자료구조를 이용해서 구현한다.
아래 그림과 동작 과정,코드를 통해 이를 이해해보자
일반적으로 BFS의 동작 과정은 다음과 같다.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
BFS 동작 방식 GIF
from collections import deque
def bfs(graph,start,visited):
queue = deque([start])
visited[start]=True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
bfs(graph,1,visited)
bfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.
a_list=list(map(int,input()))
is_three=0
is_zero=True
result=0
iterat=0
for num in a_list:
if num==0:
is_zero = False
result+=num
if (is_zero) or ((result%3)!=0):
print(-1)
else:
a_list.sort(reverse=True)
for nums in a_list:
print(nums,end="")
