알고리즘5 정렬 정렬이란 지난 글에서 배웠던 이진 탐색이라는 강력한 탐색 방법을 사용하기 위한 준비과정이라고 할 수 있다. 정렬 알고리즘은 종류에 따라서 시간 복잡도의 형태가 다르다. O(n²)인 버블 정렬, 삽입 정렬, 선택 정렬, O(n log n)인 병합 정렬, 퀵 정렬 등이 있고 이 외에도 다양한 정렬 종류가 존재한다. 버블 정렬이란 n번의 라운드로 이루어져 매 라운드마다 원소의 값을 모두 살펴본다. 연달아 있는 두 원소의 값을 비교하여 정렬 순서에 맞지 않을 경우 두 원소의 위치를 바꾼다. 매번 n만큼을 확인하기 때문에 시간 복잡도는 O(n²)으로 비효율적이라고 할 수 있다. 버블 정렬 수도코드 begin BubbleSort(list) for all elements of list if list[i] > list.. 2022. 11. 23. 이진 탐색 이진 탐색 전에 정렬 알고리즘에 대해서 공부하고 난 다음에 이진 탐색에 대해서 정리하고 싶었는데, dreambooth 문제 해결하느라 정리해서 올리지 못했다. 이진탐색(Binary Search)란 정렬되어 있는 상태의 array에서 target을 찾는 알고리즘 문제이다. 처음과 끝 점을 설정하고, 예를 들어 start, end = 0, len(nums)-1 로 설정한 다음에 중간 위치의 index를 mid로 설정한다. target과 binary_search[mid] 값을 비교하여 start나 end 값을 이동하는 방식이다. # 수도코드 function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := floor((L + R) / 2) if .. 2022. 11. 16. DFS와 BFS DFS(Depth-first search)와 BFS(Breadth-first search) 그래프나 트리 구조의 탐색방법으로 dfs는 한 노드를 깊숙하게 탐색한 다음 다시 돌아가서 다음 노드를 탐색하는 방식, bfs는 자식 노드를 stack 에 저장한 다음 차례대로 탐색하는 방식이다. dfs를 활용할 때는 재귀함수에 대한 이해가 있어야 하고 bfs를 활용할 때는 queue에 대한 이해가 필요하다. # Using a Python dictionary to act as an adjacency list graph = { '5' : ['3','7'], '3' : ['2', '4'], '7' : ['8'], '2' : [], '4' : ['8'], '8' : [] } visited = set() # Set to k.. 2022. 11. 1. Greedy algorithm Greedy algorithm (그리디 알고리즘) 이란 여러 경우 중 하나를 선택해야 할 때 그 순간 최적값을 고르는 방식을 말한다. 그리디 알고리즘은 순간순간 최적의 선택을 하지만 결과값인 최종적 해답이 최적이라는 보장을 하지는 않는다. 따라서 그리디 알고리즘을 적용할 수 있는 문제인지 아닌지 생각해야한다. greedy choice property와 optimal substructure 두가지 조건을 만족해야한다. Greedy choice property는 그 순간 가장 좋아보이는 선택을 한다. 하지만 이후에 상황이나 선택에는 영향을 받지 않는다. 탐욕적 선택 조건은 계속해서 순간의 최적해만 찾는 선택을 하게되고, 이전의 선택이나 이후의 선택에 대해서는 고민하지 않는다. Optimal substruct.. 2022. 10. 26. 이전 1 2 다음
