알고리즘공부
-
너비 우선 탐색알고리즘공부 2018. 5. 28. 17:44
너비 우선 탐색 Breath-First Search두 항목 간의 최단 경로를 찾는다.너비 우선 탐색은 두 가지 질문에 대답할 수 있다. 질문 1. 정점 A에서 정점 B로 가는 경로가 존재하는가?질문 2. 정점 A에서 정점 B로 가는 최단 경로는 무엇인가? 망고 판매상 찾기 문제 (질문 1. 나의 네트워크에 망고 판매상이 있는가?)나는 망고 농장의 주인이다.망고를 팔기 위해 페이스북 친구 목록 중 망고 판매상을 찾으려고 한다.먼저, 페이스북 친구 목록을 살펴보았다. 그런데, 친구 중에 망고 판매상이 없다.이제 친구의 친구를 찾아볼 차례이다. 만약 앨리스가 망고 판매상이 아니면 앨리스의 친구를 목록에 올린다.앨리스의 친구, 앨리스의 친구의 친구, 이런식으로 망고 판매상을 찾을 때까지 전체 네트워크를 탐색하게..
-
해시 테이블알고리즘공부 2018. 4. 11. 14:56
해시 함수 문자열을 받아서 숫자를 반환하는 함수문자열에 대해 숫자를 할당(mapping) 한다조건 1 일관성이 있어야한다. 예를 들어, "apple"을 넣었을 때 "4"를 반환한다면 "apple"을 넣을 때마다 반환되는 값은 항상 "4"이어야 함=같은 이름에 대해서는 항상 같은 인덱스를 할당한다조건 2 다른 단어가 들어가면 다른 숫자가 나와야 함. 예를들어 어떤 단어를 넣어도 "1"만 나온다면 좋은 해시 함수가 아님=다른 문자열에 대해서는 다른 인덱스를 할당한다. 해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 한다. 해시 테이블(=해시 맵 =맵 =딕셔너리 =연관 배열) 해시 테이블 = 해시 함수 + 배열 book = dict() book["apple"] = 0.6book["..
-
퀵정렬알고리즘공부 2018. 4. 5. 15:01
범용기술 : 다양한 기술을 통해 해결 방법을 알아내는것 분할정복 ( 범용기술 중 하나 )문제를 더 작은 조각으로 나누어 푼다. '기본단계'까지 퀵정렬 ( 분할정복전략사용 )def quicksort(array): if len(array) < 2: #기본단계 return array else: #재귀단계 pivot = array[0] #기준 원소 less = [i for i in array[1:] if ipivot] return quicksort(less) + [pivot] + quicksort(greater) 기준 원소를 무작위로 선택한다. 평균 실행시간은 O(n log n), 최악의 경우 O(n²) 리스트에서 가장 큰 수를 찾기def max (list): if len(list) == 2: return li..
-
배열, 연결리스트, 선택정렬알고리즘공부 2018. 4. 4. 20:12
배열 리스트 읽기 O(1) O(n) 삽입 O(n) O(1) 삭제 O(n) O(1) 접근 방식임의 접근 random access순차 접근 sequential access O(n) 실행시간이 걸리는 연산을 n번 해야 함 => O(n²) 배열의 모든 원소는 같은 자료형이어야 함def findSmallest(arr): smallest = arr[0] smallest_index = 0 for i in range(1, len(arr)): if arr[i] < smallest: smallest = arr[i] smallest_index = i return smallest_index def selectionSort(arr): newArr = [] for i in range(len(arr)): smallest = fin..
-
binary search, 빅오표기법알고리즘공부 2018. 4. 4. 19:52
단순탐색 O(n) (선형시간) 이진탐색 O(logn) (로그시간) list는 정렬된 배열 # -*- coding: cp949 -*-def binary_search(list, item): low = 0 high = len(list)-1 while low item: high = mid - 1 else: low = mid + 1 return None my_list = [1, 3, 5, 7, 9] print binary_search(my_list, 3) #1print binary_search(my_list, 7) #3print binary_search(my_list, -1) #None 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정 O(log n) < O(n) < O(n*log n) < O..
-
알고리즘 : recursion 1알고리즘공부 2017. 10. 10. 04:13
Recursion이 무한 루프에 빠지지 않기 위해서는 Base caseRecursive case 가 존재해야 한다 Recursive case에서 recursion을 반복 -> Base case로 수렴해야 함. 그렇지 않은 경우가 있기 때문에 Base case가 '존재'한다고 무한 루프가 발생하지 않는 것은 아니다. 최대공약수 구하기 : 유클리드 호제법 m>=인 두 양수 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,,n)=n이고, 그렇지 않으면 gcd(m,n)=gcd(n,m%n)이다. int gcd(int a,int b){ //반복문을 이용한 방법 int mod = a % b; while(mod > 0) { a = b; b = mod; mod = a % b; } return b;} int gcd2..