본문 바로가기
반응형

Computer Science/Algorithm21

이진 검색 binary search의 여러 가지 형태(파이썬 코드) 1. 다음은 가장 잘 알려진 이진 검색 코드다. 찾으려는 값을 target으로 넣어주면 그 값에 해당하는 인덱스를 빠르게 찾아 리턴한다. a= [1,4,5,8,12] def binary_search(target): left = 0 right = len(a)-1 while left target: right = mid -1 else: left = mid + 1 return mid print('target:',4, 'find:',a[binary_search(4)]) print('target:',5, 'find:', a[binary_search(5)]) print('target:',8, 'find:', a[binary_search(8)]) print('target:',12, 'find:', a[binary_se.. 2021. 6. 11.
[알고리즘 algorithm] 플로이드-워셜 Floyd-Warshall 알고리즘 개념과 예제 그래프 알고리즘에는 대표적으로 다익스트라 알고리즘, 플로이드-워셜 알고리즘이 있다. - 다익스트라 vs 플로이드-워셜 이 둘의 차이점은 다익스트라는 한 노드에서 다른 특정 노드까지의 최단 경로를 구할 때 사용되고, 플로이드-워셜은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구할때 사용된다. 우선순위큐를 활용하여 구현한 다익스트라의 시간복잡도는 O(ElogV)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 반면 플로이드-워셜은 시간복잡도가 O(n3)이다. n번의 탐색동안 n2번 값을 비교하여 업데이트해준다. 또한 다익스트라는 그리디 알고리즘인데 플로이드-워셜은 다이나믹 프로그래밍이라는 특징이 존재한다. - 플로이드-워셜 알고리즘의 개념 플로이드- 워셜의 결과는 항상 2차원 배열이다. 모든 노드.. 2021. 4. 21.
[알고리즘 algorithm] 다이나믹 프로그래밍 dynamic programming 방법론, 예제 이 글은 '파이썬 알고리즘 인터뷰'라는 책을 참고하여 작성하였습니다. - 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘. - 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이할 수 있다. - 타뷸레이션(Tabulation): 상향식 접근법 - 메모이제이션(Memoization): 하향식 접근법 ex) 피보나치 수열 코드 작성 예제 ## tabulation def fib(n): dp[0]=0 dp[1]=1 for i in range(2,n+1): dp[i] = dp[i-1]+ dp[i-2] return dp[n] ## memoization def fib(n): i.. 2021. 4. 19.
[알고리즘 algorithm] 분할 정복 divide and conquer 활용 예제 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임이다. - 대표적인 분할정복 알고리즘으로 병합정렬이 있다. - 문제를 재귀로 쪼개 직접 해결할 수 있을 정도로 만든 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다. 분할 정복은 재귀 구조랑 거의 동일하며, 단지 넘겨주는 인자를 점점 분할하여 넘긴다. 이때 윈도우 슬라이싱이 잘 활용된다. - 분할 정렬 : 대표적인 분할 정복 알고리즘 분할 과정) 긴 배열을 정렬해야 한다 => 어렵다. 쪼개자. 두 개의 배열로 쪼갬 => 여전히 어렵다. 더 쪼개자. 각각의 배열이 다시 2개로 쪼개져 총 4개의 배열이 됨. => 계속 쪼개자. 이런 방식으로 계속 진행하다보면 마지막에는 1개의 원소만을 가진 배열로 쪼개짐. 정복 과정).. 2021. 4. 19.
[알고리즘 algorithm] 비트 연산과 비트 조작 출처: 박상길 지음, 정진호 일러스트, 책만, 2020(https://www.onlybook.co.kr/entry/algorithm-interview) - 부울 연산자 >>> True and False False >>> True or False True >>> not True False and, or, not은 기본 부울 연산자로, 이들을 조합하여 다른 보조 연산을 만들어 내는데, XOR 연산이 대표적인 보조 연산에 해당한다. >>> x = y = True >>> (x and not y) or (not x and y) False - 비트 연산자 >>> True & False # and False >>> True | False # or True >>> True ^ True # xor False >>> ~T.. 2021. 4. 15.
[알고리즘 algorithm] 이진 검색 Binary Search 정의와 사용 예제 이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘. 시간복잡도가 O(logN)로 1억개의 데이터에서도 단 27번 안에 원하는 데이터를 찾아낼 수 있는 정말 마법같은 검색 알고리즘이다. 이진탐색트리와 이진검색은 유사한 점이 많은데 이진탐색트리(BST)가 정렬된 구조를 저장하고 탐색하는 자료구조라면, 이진검색은 정렬된 배열에서 값을 찾아내는 알고리즘 자체를 지칭한다. 이진 검색 기본 문제: leetcode.com/problems/binary-search/ Binary Search - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepare.. 2021. 4. 15.
반응형

티스토리툴바