본문 바로가기

알고리즘57

반드시 알아야하는 알고리즘 top 8 - 7. 최단거리 알고리즘 반드시 알아야 하는 알고리즘 top 8 재귀 알고리즘 이진 탐색 순차 탐색버블 정렬삽입 정렬탐욕 알고리즘최단거리 알고리즘몬테 카를로 알고리즘 최단거리 알고리즘 최단거리 알고리즘은 한 지점에서 다른 지점까지의 최단거리를 구할때 사용하는 알고리즘 입니다. 이 알고리즘은 가장 적은 비용으로 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용될 수 있습니다. 때문에 실생활에도 깊게 녹아있습니다. 예들 들면 네비게이션이나, 큐브를 푸는 문제, 미로탐색 등 실용성이 매우 높은 알고리즘 이라고 할 수 있습니다. 영상을 보며 기본적인 알고리즘을 살펴보겠습니다. 최단거리 알고리즘 예제 문제 : 집에서 학교까지 최단 거리는 얼마 일까요?각 실선에 있는 숫자는 연결되어 있는 곳 간의 거리를 의미합니다.거리 참고['0.집'.. 2017. 12. 30.
반드시 알아야하는 알고리즘 top 8 - 5. 삽입 정렬 반드시 알아야 하는 알고리즘 top 8 재귀 알고리즘 이진 탐색 순차 탐색버블 정렬삽입 정렬탐욕 알고리즘최단거리 알고리즘몬테 카를로 알고리즘 삽입 정렬 삽입 정렬이란 앞의 숫자들을 정렬된 상태라고 가정한 뒤 정렬되지 않은 숫자들을 하나씩 빼서 정렬되어 있는 숫자 사이의 올바른 위치에 삽입하는 정렬 방법을 의미 합니다. 다음 영상을 통해 자세히 살펴보겠습니다. 2:36 부터 삽입정렬 관련 시작입니다. 삽입 정렬 코드 01 : Python a = [4,1,5,2,3] for i in range(1,len(a)): for j in range(i): if a[i] < a[j]: a.insert(j,a.pop(i)) 삽입정렬을 구현한 코드 입니다. i = 1 j = 0 a = [1, 4, 5, 2, 3]i = 2.. 2017. 12. 28.
반드시 알아야하는 알고리즘 top 8 - 4. 버블 정렬 반드시 알아야 하는 알고리즘 top 8 재귀 알고리즘 이진 탐색 순차 탐색버블 정렬삽입 정렬탐욕 알고리즘최단거리 알고리즘몬테 카를로 알고리즘 버블 정렬 버블 정렬은 두 인접한 값들을 검사하여 정렬하는 방법입니다. 시간이 매우 오래 걸리는 알고리즘 중 하나지만 코드가 단순하기 때문에 자주 사용되는 방법입니다. 값들이 정렬되는 과정이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름 입니다. 다음 동영상을 통해 세부 과정을 살펴보겠습니다. 버블 정렬 코드 01 : Python a = [3,2,4,1]for i in range(len(a)): for j in range(len(a)-1-i): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] 버블 정렬을 간단히 구.. 2017. 12. 27.
반드시 알아야하는 알고리즘 top 8 - 3. 순차 탐색 반드시 알아야 하는 알고리즘 top 8 재귀 알고리즘 이진 탐색 순차 탐색버블 정렬삽입 정렬탐욕 알고리즘최단거리 알고리즘몬테 카를로 알고리즘 순차 탐색 순차 탐색은 가장 간단하며 누구나 사용하는 탐색 방법입니다. 데이터 배열에서 찾고자하는 값이 있으면 배열의 첫 번째부터 하나하나 탐색해가는 방법입니다. 데이터를 조작할 필요가 없지만 비효율적이라는 단점이 있습니다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색이라고 부르기도 합니다. 순차 탐색 코드 : Python data = [1,2,3,4,5]a = 3chk = Falsefor i in data: if a == i: chk = True break print(chk) data 라는 배열에서 a 값을 순차 탐색으로 찾는 코드 입니다. 배.. 2017. 12. 27.