kark's

브루트 : 무식한명칭처럼 무식하게 탐색하는 알고리즘이다. 문제를 해결하기 위해 모든 경우의 수를 확인해본다 라고 생각하면된다.그럼 완전탐색 알고리즘과 백트레킹 알고리즘과 거의 유사해 보이지만, 브루트포스는 그냥 완전히 확인하는 것이라 생각하면 된다. 모든 경우의 수를 확인하는 점은 최적의 결과를 반환시켜 주지만, 반대로 시간이 오래걸린다는 점이 단점이 된다. 브루트포스 : 모든 탐색을 진행완전탐색 : 모든 탐색을 진행하지만 가능하다면 조건을 활용해 불필요한 탐색을 제거백트레킹 : 명확한 조건을 두어, 불필요한 탐색을 제거하는 가지치기 방식 예시 문제https://www.acmicpc.net/problem/2798주어지는 카드들로 3장의 카드를 골라서 주어지는 값에 가장 근접하게 만들어 내야한다.대신 반드..

이진트리란 하나의 노드가 있을때, 자식노드가 2개 이하인 트리를 말한다. 자식노드가 3개라면 이진트리라 부를수 없다. 트리를 사용하는 이유는 데이터를 계층적으로 구성하며 효율적으로 관리하기 위해 사용된다. 계층적 구조를 이룸으로써 빠른 검색, 삽입, 삭제가 가능하다. 이러한 트리구조에서 모든 노드를 빠르게 확인하거나, 처리를 하기위해선 순회 방법을 알아야한다. 순회 방법으로는 전위순회 중위순회 후위순회가 있다. 전위순회 Preorder , 중위순회 Inorder , 후위순회 , Postorder 각 접두사를 확인해보면 Pre, In, Post 로 앞에 , 안에 , 뒤에 로 유추할수 있다. 단어의 각 위치는 트리의 Root의 위치를 의미한다. 위와 같은 간단한 트리가 있을때, Root는 A 로 Left는 ..

백트레킹은 시도와 오류 방식을 기반으로 모든 방법을 시도하되, 현재의 경로가 해결책으로 이어질 가능성이 없다고 판단될때 이전의 분기점으로 되돌아가 다른경로를 시도하는 방식이다. 최적화 문제, 조합문제를 해결하는데 유용할수 있다. 예시의 경우를 살펴보자 위와같은 노드가 있고 노드의 리프에 도착했을때 모든 노드의 합이 6 이 되는 경로를 찾아야된다고 할경우를 가정해보자. DFS 방식으로 탐색을 진행할경우 왼쪽방향으로 먼저 탐색하게 될것이다. 위처럼 리프에 도달했을때 노드의 총합은 21이라는 틀린값이 나오게된다. 하지만 이때 백트레킹 기법을 활용하게 된다면 노드 중간에 이미 찾아야하는 값이 먼저 나와버렸고, 해당 정점이 리프가아니므로 더이상 탐색은 의미가 없게되어버린다. 이때 다시 부모 분기점으로 되돌아가 다..

데이터가 정렬된 상태에서 데이터의 크기를 절반씩 줄이면서 대상을 찾는 알고리즘 중앙값을 비교하여 절반씩 줄여가므로 시간복잡도는 O(logN) 이 필요하다. 위와 같은 배열이 있을때 35를 찾아야한다고 가정해보자 앞에서부터 순차적으로 탐색하게될시 6번의 탐색 과정이 필요하다. 이진탐색 과정을 살펴보자 ① 중간값 15 보다 크므로 오른쪽을 다음 탐색범위로 지정 ② 중간값 23 보다 크므로 오른쪽을 다음 탐색범위로 지정 ③ 중간값 35 로 탐색대상 확인 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤..