완전탐색(exhaustive search)① 완전탐색이란?▷ 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다. '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드 완전 탐색 방법1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법2. 순열 : 순열의 시간 복잡도는 O(N!)3. 재귀호출4. 비트마스크5.  BF..

완전탐색 : 브루트포스 알고리즘 Brute Force AlgorithmBrute : 무식한Force : 힘직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 가능한 모든 경우의 수를 모두 탐색하면서 결과를 도출한다.전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.브루트포스 알고리즘은 대부분은 반복문과 조건문을 통하여 답을 도출한다.완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.브루트포스의 장점알고리즘을 설계하고 구현하기 쉽다모든 경우의 수를 탐색하기 때문에 100% 정확성을 보장한다.브루트포스의 단점메모리 효율면에서 매우 비효율적이다.알고리즘의 실행 시간이 매우 오래걸린다. (시간복잡도가 높다)

키워드: 최단경로다익스트라 알고리즘 = 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.다익스트라 알고리즘 과정1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.다익스트라 알고리즘의 탐색과정우선순위 큐 방식우선순위 큐를 이용한 다익스트라 알고리즘우선순위 큐에 (0, 시작점)을 추가우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리..

1. PriorityQueue 란?일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조입니다.반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있습니다. ( 또한 다른 자료구조를 통해서 구현될 수 있음 )2. PriorityQueue 선언 방법// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)PriorityQueue pQ = new PriorityQueue();// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)PriorityQueue pQ = new PriorityQueue(Collections.reverseOrder());3. 기본적인 메소드3. 기본적인 메소..

투 포인터배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘 리스트에 순차적으로 접근하여 두 개의 위치를 기록하며 처리부분 연속 수열 문제에 사용시간 복잡도 O(N)으로 처리 가능 ( 시간 복잡도를 O(n^2) 에서 최대 O(n) 까지 줄일 수 있습니다.)순서투 포인터에서, 2. 둘 다 첫 번째 원소에서 시작하는 경우를 사용하였습니다.start = 0, end = 0 으로 시작합니다. 투 포인터는 start start 구간 합(sum)이 M을 초과하거나, end가 배열의 범위를 넘으면sum-arr[start] , start 오른쪽 한칸 이동을 해줍니다.구간 합(sum)이 M과 같거나 이하일때, end가 배열의 범위를 넘지 않을 때sum+ar..

이분 탐색(Binary Search)이란?‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘을 의미합니다.이진탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형탐색에 비해 빠른 속도를 보장합니다. 하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요합니다.이진탐색 과정배열의 ‘중간 값’을 선택하여 찾고자 하는 값과 비교합니다.만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분'에서 탐색을 진행하고, 값보다 작으면 ‘배열 오른쪽 부분'에서 탐색을 진행합니다.이 과정에서 찾고자 하는 값이 나올 때까지 반복합니다.Start = 0End = 배열의 길이 -1Mid = (Strat + End) / 2 또한, 대표적으로 3가지 아이디어를 기억하시면 됩니..

그리디(Greedy) 알고리즘Greedy(탐욕법)= 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘= 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.구현해서 문제를 통과한다.예) 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶다.최댓값: 5 -> 7 -> 9 로 거쳐가면 21이란 최댓값이 나온다.그리디 알고리즘 풀이는?루트 노드 5에서 시작하여 7, 10, 8 중 가장 큰 10을 선택하고, 4, 3 중에 4를 선택한다.

Dynamic Programming , DP: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘데이블 정의하기점화식 찾기초기값 설정DP (동적 계획법) 조건재귀(Recursion)란?자기 자신을 호출하는 함수로 반복적으로 호출을 함으로써 원하는 결과를 도출 할 수 있습니다.메모이제이션(Memoization)이란?‘중복 계산'을 피하기 위한 기법입니다. 이를 이용하여 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복 계산을 피함으로써 성능을 향상 시킬 수 있습니다.재귀동적계획법의 등장은 피보나치 수열이라고 한다. 피보나치 수열은 대표적인 재귀함수로, 아래와 같이 표현할 수 있다.public class Fibonacci { ..

백트래킹(backtracking)이란?모든 후보군을 따라 들어가며 탐색하는 알고리즘솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다. DFS와 BacktrackingDFS : 완전..

그래프 탐색이란?하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지깊이 우선 탐색이란루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.깊이 우선 탐색(DFS)이 너비 우선 탐색..