알고리즘
-
Binary Serach알고리즘 2020. 3. 16. 20:57
Binary Search 이진탐색순차 탐색 : 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 방법.이진 탐색 : 탐색 범위를 절반씩 줄어가며 값을 찾는 방법. 탐색 전, 배열이 미리 정렬되어 있어야한다. 배열의 크기가 N이라고 할때, 순차탐색 이진탐색 시간복잡도 O(N) O(log N) 탐색 방법 크기가 N인 배열 arr에서, target을 찾는다고 가정 시start = 0, end = N-1 로 초기화 한다.mid = (start + end) / 2 로 초기화 한다.target과 arr[mid]의 값을 비교한다. 값이 같을 시, 탐색을 종료 같지 않을시, target data[mid] 이면 star..
-
DP알고리즘 2020. 3. 16. 19:34
DP (Dynamic Programming) 동적계획법 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다. Memoization? 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해, 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 → 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다. 구현 방식 : Bottom-up 방식과 Top-down 방식 Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식 Top-down 방식 : 큰 문제를 풀 ..
-
DFS & BFS알고리즘 2020. 3. 16. 16:50
들어가기 전, 그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것 깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다. 1. DFS (Depth First Search) 깊이 우선 탐색 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다. 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.* (ex) 2. BFS (Breadth Frist S..