알고리즘/[Python] 알고리즘
(Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기
(Python) 순열, 조합 쉽게 만들기¶결론부터 말하자면, 라이브러리에서 불러온 함수와 직접 구현한 함수가 속도차이 10배정도를 보였다. (라이브러리가 훨씬 빠름) 파이썬 documentation에서 어떻게 구현했는지 나중에 차차 확인해봐야 할 것 같다. 1. itertools를 이용하여 순열, 조합 구현하기¶ 1.1 순열(=permutations) 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열한다. 뽑힌 순서대로 나열하기 때문에 순서가 의미가 있다. (즉, 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 취급한다.) permutations(반복 가능한 객체, r) In [1]: from itertools import permutations for i in p..
(Python) 버블 정렬(bubble sort)
(Python) 버블 정렬(bubble sort)¶ 버블 정렬(bubble sort)란? 서로 인접한 두 원소들을 순차적으로 비교하여 정렬하는 알고리즘이다. (인접해 있는 두 원소의 크기가 순서에 맞지 않다면 서로 교환한다.) In [1]: from IPython.display import Image Image("img/bubble_sort.png") Out[1]: 버블 정렬(bubble)의 시간복잡도 비교 횟수 best, average, worst가 모두 일정하다. n-1, n-2, n-3, ... , 2, 1번 비교하므로 총 n(n-1)/2번 비교한다. 교환 횟수 입력 자료가 이미 정렬되어 있는 경우라면, 자료의 이동이 일어나지 않는다. 최악의 경우는 입력 자료가 역순으로 정렬되어 있는 경우이다. 두..
(Python) 리스트의 선형 탐색(linear search)
(Python) 리스트의 선형 탐색 (linear search)¶ 정렬되지 않은 리스트에서 특정 항목을 찾으려면 어떻게 해야 할까? 이미 정렬된 리스트라면 이진 탐색(binary search)처럼 좀 더 효과적인 탐색 방법을 사용해 볼 수 있겠지만 그렇지 않다면 순차적으로 배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아야 할 것이다. 선형 탐색(linear search)는 가장 기본적인 탐색 방법으로, 위에서 언급한 바와 같이 배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아내는 선형 탐색 기법이다. In [1]: # 배열(=array)안에 찾고자 하는 특정 항목(=value)이 있으면 그 index값을 return, 없다면 -1을 return def linear_search(value, arr..
(Python) 이진 탐색(Binary Search) 구현하기
(Python) 이진 탐색(Binary Search)¶ Binary Search : 이진 탐색, 이분 탐색, 또는 이원 탐색 서로 다른 정수들을 원소로 갖고 있는 정렬되어 있는 리스트가 있다고 가정하자. 특정 정수값 searchnum이 리스트에 존재하는지 알고싶다. 만일 searchnum이 리스트에 존재한다면 list[i] = searchnum인 인덱스 i를 반환하고, 그렇지 않다면 -1을 반환한다. 순차적으로 탐색하는 것보다 훨씬 효율적이다 (리스트가 정렬되어 있을 경우에 대해서만) left: 탐색하고자 하는 배열의 왼쪽 right: 탐색하고자 하는 배열의 오른쪽 middle: (left+right)/2 list[middle]과 searchnum을 비교하여 다음의 세가지 경우 중 하나를 선택한다. se..
(Python) 너비 우선 탐색(BFS) 구현하기
(Python) 너비 우선 탐색(BFS) 구현하기¶ In [1]: from IPython.display import Image Image("img/bfs_graph.png") ## code안에서 그림이 나오게 할 떄 #  ## markdown안에서 그림이 나오게 할 때 Out[1]: DFS에서는 반복문(iteration), 재귀(recursive)적인 방법으로 구현했었는데 BFS의 경우 반복문(iteration)을 이용해서 구현을 해야 한다. 반복문(iteration) DFS : stack 이용 DFS 방문 순서 : A B D E F C G H (왼쪽 노드부터 방문한다고 가정할때) BFS : queue 이용 BFS 방문 순서 : A B C D E G H F..
(Python) 깊이 우선 탐색(DFS) 구현하기
깊이 우선 탐색(DFS) 구현하기¶ In [1]: graph = {'A':['B','C'], 'B':['A','D','E'], 'C':['A','G','H'], 'D':['B'], 'E':['B','F'], 'F':['E'], 'G':['C'], 'H':['C']} 반복문(iteration)을 이용해서 DFS 구현하기¶dfs는 stack을 이용해서, bfs는 queue를 이용해서 구현할 수 있는..