정의백트래킹은 DFS로 모든 경우를 탐색해되, 탐색 중간에 정답이 될 가능성이 없는 경로를 기준 함수(promising function)로 판별해서 그 가지를 더 이상 확장하지 않는(가지치기) 탐색 기법이다. 푸는 방식백트래킹 문제는 3요소를 먼저 고정시키고 풀면 편리하다. 상태(state)정의재귀 함수 파라미터로 "현재까지 무엇을 결정했는지"를 표현한다.ex) 부분집합/조합/순열 -> idx, sum, depth, used[], path 등으로 표현 선택(choice)정의상태를 정의한 다음, 현재 상태에서 다음으로 갈 수 있는 선택지를 나열한다.ex) i번째 원소를 선택/미선택, 다음 숫자 후보 넣기, 다음 칸에 넣을 값 1~9등 가지치기하는 함수 정의상태가 갈 수 있는 선택지에서 절대 정답이 ..

백트래킹이전에 포스팅했던 DFS, BFS는 완전탐색방법으로 주어진 데이터를 모두 순회하여 탐색하는 방법이다.이는 상당히 비효율적이며, 시간복잡도도 높게 측정된다. 그럼 어떤 방법이 효율적일까?바로 완전탐색을 하지 않고 완전탐색을 하다가 해당 루트가 탐색 가능성이 없다고 판단되었을 때이전 분기점으로 되돌아가는 방법을 말한다. 말 그대로 다시 돌아온다는 의미다. 깊이우선탐색은 가능성의 유무를 확인하지 않고 모든 경로를 탐색하는 방면백트래킹은 해당 경로를 탐색 중 더이상 가능성이 없다고 판단되면 해당 경로를 더 이상 탐색하지않고가능성이 있는 다른 경로를 우선적으로 탐색하는 차이점이 있다. 보통 백트래킹보다는 N-Queen이라는 문제로 더 잘 알려져있고, 예를 들면서 설명해보겠다.백트래킹의 핵심은 상태값..

LIS(Longest Increasing Subsequence)최장 증가 부분 수열로 부분 수열의 원소가 오름차순을 유지하면서 길이가 가장 큰 부분 수열을 말한다.이를 이해 하기 위해서는 부분 수열에 대해 먼저 알 필요가 있다. 부분수열주어진 수열 중 일부를 뽑아서 새로 만든 수열을 뜻하고, 이때 각각의 원소는 전후 관계를 유지해야 된다.예를 들어 {1, 7, 5, 10, 8} 이라는 수열이 있다고 하자.여기서 원소 1, 5, 8을 뽑았을 때 {1, 5, 8} 이렇게 뽑을 경우 원래의 순서를 유지한 채 뽑았기에 부분수열이고{1, 8, 5} 이렇게 뽑았을 경우 원래 수열은 5다음 8이 와야하는데 현재의 수열은 8다음 5가 나왔기 때문에원래의 순서를 유지하지 않았으므로 부분수열이 아니다.여기서 부분..

MST(Minimum-spanning tree)최소 신장 트리(MST)란 그래프이론에서 모든 정점을 가장 효율적으로 찾는 개념을 뜻한다. - 그래프 :여러 정점(노드)과 이들을 잇는 간선(선)으로 이루어진 구조로 간선에 가중치가 부여된다. - 신장 트리 : 그래프의 모든 정점으 포함하면서 사이클(순환)이 없는 부분 그래프를 의미한다. 즉, 모든 정점을 연걸하는 최소한의 간선으로 이루어진 트리를 뜻한다. - 최소 : 간선들의 가중치 합이 가장 작은 신장 트리를 말한다. 신장트리신장트리란 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프를 말한다. 왼쪽 그래프의 경우 정점의 개수 6개, 간선의 개수 5개, 싸이클이 없기 때문에 신장트리..