본문 바로가기

알고리즘7

이진 탐색(Binary Search) 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. By 위키백과 간단히 요약하자면, 1. 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 방식이다. 2. 배열 중간에 있는 임의의 값을 선택해 찾고자 하는 값과 대소를 비교한다. 3. 처.. 2023. 2. 22.
투 포인터(Two Pointer) 투 포인터(Two Pointer)란? 두 개의 포인터를 활용해 문자열 / 배열 / 리스트 등 연속적인 데이터셋에서 원하는 값을 탐색하는 방식이다. 일반적인 반복탐색이 가지는 O(N^2) 정도의 시간복잡도를 O(N)으로 줄일 수 있다. 간단히 요약하자면, 1. 문자열 / 배열 / 리스트 등 연속적인 데이터셋이 주어지고 특정값을 찾아야 할 때 사용된다. 2. 포인터 배치는 두 가지로 할 수 있다. 2 - 1) 맨 앞 시작 - 맨 뒤 시작 2 - 2) 선행 포인터 - 후행 포인터 투 포인터는 어떻게, 왜 사용하는 것인가? 아래 크기 10짜리 배열 array가 존재한다. 여기서 두 배열 요소의 합이 11이 나오는 경우의 수를 구하라는 문제가 주어질 때 어떻게 풀이할 것인가? array[10] = { 1, 2, .. 2023. 2. 8.
누적합(Prefix Sum) 누적합(Prefix Sum)이란? 말그대로 나열된 수의 누적된 합을 말한다. 배열의 일부 구간에 대한 합을 빠르게 구할 수 있게 해주는 알고리즘이다. 누적합은 어떻게, 왜 사용하는 것인가? 아래 크기 6짜리 배열 array가 존재한다. 여기서 구간 [2, 5]의 합을 구하라는 문제가 주어질 때 어떻게 풀이할 것인가? array = {1, 2, 3, 4, 5, 6} for(int i = 0; i = 2) { sum += array[i]; } } 일반적인 풀이로는 구간 [2, 5]의 합 3 + 4 + 5 + 6 = 18로, 배열을 반복문으로 순회하며 값을 더하는 방식으로 간단하게 구현할 수 있다. 그러나 수열의 개수 'N'이 매우 커졌을 때 구간 [100000, 231311].. 2023. 2. 8.
BFS & DFS BFS & DFS? BFS(너비 우선 탐색) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. DFS(깊이 우선 탐색) 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노.. 2023. 2. 6.

티스토리툴바