알고리즘 정리

[백트래킹] 백트래킹의 설명과 간단한 예제풀이

백트래킹(Backtracking) 1. 백트래킹이란? 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 가장 중요한 점은 제한조건을 위배한다면 그 노드를 제외한다는 점이다. 백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. 여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다. 따라서 한마디로 정의하면 DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요..

[BFS] BFS의 설명과 간단한 예제풀이

BFS(너비 우선 탐색 , Breadth First Search) 1. 특징 1. BFS는 재귀적으로 동작하지 않는다. 2. 이 알고리즘도 DFS와 마찬가지로 그래프 탐색의 경우 방문한 노드에 대해 기존에 방문했었는지의 여부를 검사를 해야 무한루프에 빠지지 않는다. 3. BFS는 방문한 노드들을 차례대로 저장한 후 먼저 방문한 노드부터 먼저 꺼낼 수 있는 자료구조인 큐를 사용합니다. (선입선출이 원칙!!) 4. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다. ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A사람과 B사람에 존재하는 관계 경로를 찾을려면 DFS는 모든 친구 관계를 다 살펴봐야 할수도있는데 BFS는 A와 가까운 관계부터 먼저 탐색함에 따라 ..

[DFS] DFS의 설명과 간단한 예제풀이

DFS(깊이 우선 탐색 , Depth-First Search) 1. 특징 1. 자기 자식을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택) 2. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다. (이것을 검사하지 않으면 무한루프에 빠지게 된다. ex) visited[idx] = true;) 3. 우리가 미로의 길을 계속 가다가 더 이상 갈 수 없게 되면 우리는 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 탐색을 진행하는 것과 비슷한 양식이다. 4. 모든 노드를 방문하려고 할때 이 방식을 사용한다. 5. BFS(너비 우선 탐색)보다 더 간단하다. 6. 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 ..

[그리디 알고리즘] 그리디 알고리즘의 설명과 간단한 코테 예제풀이

그리디알고리즘(Greedy Algorithm) 그리디(Greedy)란 '탐욕스러운, 욕심 많은' 이란 뜻이다. 그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방식이다. 하지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장이 없다. 따라서 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들일때 그리디 알고리즘을 적용할 수 있다. 여기서 가장 중요한 점은 그리디 알고리즘을 이용하면 최적해를 찾지 못할 수 도 있다는 것을 항상 명심해야한다. 그렇다면 그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 어떤 조건을 만족할까? 1. greedy choice property : 현재 선택이 이 후의..

[브루트 포스] 브루트 포스의 설명과 간단한 코테 예제풀이

브루트 포스(Brute Force) 브루트 포스는 모든 경우의 수를 무식하게 탐색하면서 요구조건을 충족한 결과만 가져오는 것을 말한다. 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색 한다는 점이다. 전체를 탐색하는 방법에서 1. 선형 구조를 전체적으로 탐색하는 순차 탐색 2. 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS) , 너비 우선 탐색(BFS)가 기본적인 도구이다. 실제로 알고리즘을 풀때는, 이 문제가 브루트포스로 해결이 가능한지 확인 후 불가능하다면 어떤 알고리즘을 적용해서 시간복잡도를 줄이며 간단하게 짤 것인지 고민해야한다. (DP, 누적합 , 이분탐색 등등) 브루트 포스에 가장 대표적인 예제로 백준 블랙잭 문제가 있다. 2798번 블랙잭 문제 카지노에서 제일 인기 있는 게임..