파이썬(Python) 선택정렬, 삽입정렬, 퀵정렬

1. 선택정렬

1 2 3 4 5 6 7 8 9 10 11 12 13

def select_sort(array): 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[min_index], array[i] = array[i], array[min_index] return array array = [3, 4, 7, 2, 1, 0, 8] print(select_sort(array))

1 => 선택정렬 구현한 함수: 선택정렬 수행 후 정렬된 배열 반환

3 => 가장 작은 값의 인덱스 초기화

5 => 가장 작은 값의 인덱스 저장

7 => 가장 작은 값이 앞에 오도록 값 교체

9 => 선택정렬이 완료된 배열 반환

2. 삽입정렬

1 2 3 4 5 6 7 8 9 10 11 12 13

def insert_sort(array): 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; return array array = [3, 4, 7, 2, 1, 0, 8] print(insert_sort(array))

1 => 삽입정렬 정의한 함수: 정렬된 배열을 반환

2 => 맨 처음 값은 정렬되었다고 가정

3 => 정렬하려는 요소보다 작은 값을 만날 때까지 값 교환

6 => 정렬하려는 요소보다 작은 값을 만나면 for문 돌지않는다.

6번줄 때문에 삽입정렬은 이미 정렬된 값이 많은 배열에서 효과적이다!

3. 퀵정렬

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

def quick_sort1(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[pivot], array[right] = array[right], array[pivot] else: array[left], array[right] = array[right], array[left] quick_sort1(array, start, right -1) quick_sort1(array, right + 1, end) array = [3, 4, 7, 2, 1, 0, 8] quick_sort1(array, 0, len(array) - 1) print(array)

1 => 퀵정렬을 정의한 함수: 반환값은 없음

4 => pivot은 항상 맨 처음 요소로 시작

8 => left와 right가 교차할 때까지 while문 수행

9 => left가 pivot 값보다 클 때까지 인덱스 증가

11 => right가 pivot 값보다 작을 때까지 인덱스 감소

14 => left와 right가 교차한 상태면 pivot과 right 값 교환

16 => left와 right가 교차한 상태가 아니면 left와 right 값 교환

이번에는 파이썬의 장점을 극대화한 퀵정렬 소스를 살펴보자.

1 2 3 4 5 6 7 8 9 10 11 12 13

def quick_sort(array): #condition for return 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))

1 => 퀵정렬을 정의한 함수: 인덱스가 한개일 때, 배열 반환

2 => 재귀 탈출 조건

5 => 퀵정렬의 첫번째 pivot은 항상 첫번째 요소

6 => 첫번째 요소를 제외한 나머지 값의 배열

8 => pivot보다 작은 값들을 모은 left_side 배열

9 => pivot보다 큰 값들을 모은 right_side 배열

11 => left_side와 right_side에 다시 퀵정렬을 수행하여 pivot과 연결한다.

Share:

파이썬 너비우선탐색(BFS) 알고리즘 소개

 너비우선탐색(BFS) 알고리즘 소개

위와 같은 그래프가 있을 때, 너비 우선 탐색(BFS)을 수행하는 코드를 파이썬으로 작성해보자.

BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 합니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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)

Share:

파이썬 깊이우선탐색(DFS) 알고리즘

 깊이우선탐색(DFS) 알고리즘 with 파이썬

DFS는 깊이 우선 탐색이라고 부른다.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

스택자료구조나 재귀함수를 이용하며 구체적인 동작은 다음과 같다.

• 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다
• 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 2번의 과정을 수행할 수 없을 때까지 반복한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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)

그냥 기본기니까 암기해두자!!

Share:

백준 11047번 문제 파이썬 해설(그리디 알고리즘)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

n, k = map(int, input().split()) coins = [] for _ in range(n): coins.append(int(input())) # coins = list(map(int, input().split('\n'))) # 코인 내림차순 정렬 coins.sort(reverse = True) # print("coins:", coins) count = 0 for coin in coins: # 코인이 k보다 작으면 더한다. if coin <= k: count += k // coin k %= coin # print("count:", count, "k:", k) else: continue if k == 0: break print(count)

정답은 맞췄다.

짚고넘어갈 점은 엔터로 값을 쭉 입력할 때 받는 방법이다.

처음에는 모르고 6번줄 처럼 받을라고했는데 안된다;;

4,5번 줄처럼 간단하게 받을 수 있다!

Share:

 백준 11399번 문제풀이 (그리디 알고리즘)

그리디 알고리즘 문제이다.

각 사람이 돈을 인출하는데 필요한 시간의 최솟값을 구해야한다.

따라서 돈을 인출하는데 걸리는 시간이 작은 사람이 최대한 앞에 몰려 있어야한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
persons = int(input()) 

pList = list(map(int, input().split()))

pList.sort()

result = 0

for i in range(len(pList)): 
    result += pList[i] * (len(pList) - i)

print(result)

몇 번 틀렸는데 2번째 값을 받을 때, 5개를 한정해서 받아버렸다.

항상 일반화된 코드를 작성해야한다는 것에 주의하자!

다른 개발자의 블로그를 보면서 다른 풀이도 참고해보자.

1 2 3 4 5 6 7 8 9 10 11 12 13

n = int(input()) numbers = list(map(int, input().split())) numbers.sort() # 정렬 pre = 0 #이전 까지의 합 result = 0 #총 합계 for i in range(0, n): result += pre + numbers[i] pre += numbers[i] print(result)

비슷한 로직인데 이전까지의 합을 따로 저장한다.

Share: