분류 전체보기 (12) 썸네일형 리스트형 [알고리즘] 백트래킹(Back Tracking) 이해하기 [ 목차 ]1. 정의2. 한정조건(예시) 3. 코드 구현 4. 정리▶ 백트래킹(Back Tracking) : 퇴각 검색한정조건에서의 모든 경우의 수를 탐색하는 알고리즘전체 조건에서 모든 경우의수를 탐색하는 완전탐색 (≒ 브루트 포스) 알고리즘보다 빠른 탐색이 가능하다.어떤 지점이 한정조건에 부합하지 않음이 명백할 경우, 이전 지점으로 돌아가며 다른 지점을 다시 탐색하는 방식으로 작동.위 작동 방식 때문에 이전에 알아본 DFS를 이용한 탐색이 선호됨 (깊이 우선 탐색) ◈ 한정조건 (예시)백트래킹과 한정조건에 대한 이해를 돕기 위해 백준 9663번 N-Queen 문제를 들고왔다. 문제 힌트에 있는 Queen - The show must go on을 들으며 풀어보자(...) 우선, 이 문제의 한정조건은 N.. [알고리즘] 브루트 포스(Brute Force) 이해하기 [ 목차 ]1. 정의 2. 예시 3. 정리▶ 브루트포스(Brute Force) : 무식한 힘영어 단어 그대로 무식하게 모든 경우를 탐색하는 완전탐색 알고리즘 (브루트포스 ≒ 완전탐색)완전탐색은 보통 반복문과 조건문을 이용하여 진행무식하게 하나씩 다 찾으니까 당연히 시간복잡도가 매우 큼이전에 알아본 DFS, BFS 및 순차탐색을 이용하여 브루트포스 알고리즘을 구현할 수 있다. ◈ 순차탐색을 이용한 브루트포스 (예시)순차탐색을 이용하기 위해서는 데이터가 선형구조를 이루어야한다. 선형구조로 이루어진 데이터를 순차탐색하며 계산을 수행하고 결과값을 도출한다.예시로 백준의 1198번 : 삼각형으로 자르기 문제를 가지고 와보았다. 2차원 좌표평면에서 다각형의 점의 좌표들을 입력받아, 도형을 잘랐을때 제일 커다란 .. [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 이해하기 [ 목차 ]1. 정의 2.재귀와의 차이점 3. DP를 사용할 수 있는 문제인지에 대한 판별 4. DP 사용 예시 5. 정리▶ 다이나믹 프로그래밍 (Dynamic Programming)동적 계획법이라고도 한다. (줄여서 DP)복잡한 문제를 더 작은 하위 문제로 나누어 해결알고리즘 자체가 아닌 알고리즘 설계기법 (그래서 동적 "계획법") ◈ 재귀(Recursion)와의 차이점재귀는 대개 Top-Down 방식 DP는 대개 Bottom-Up 방식 (작은 문제들을 해결하며 큰 문제들로 다가감)DP는 Memoization 방식을 사용※ Memoization -중복되는 계산 결과를 저장하는 메모리 기법 ex) 피보나치 수열 f(n) = f(n-1) + f(n-2)를 계산할때 메모이제이션을 사용하면 f(n-.. [알고리즘] DFS(깊이 우선 탐색)와 BFS(넓이 우선 탐색) 이해하기 [ 목차 ]1.정의 1-1.DFS (Depth-First Search) 1-2.BFS (Breadth-First Serch)2.구현 2-1.DFS의 구현 방법 2-2.BFS의 구현 방법3.DFS의 재귀4.코드 구현(전체 코드 미리보기) 4-1.Stack으로 구현한 DFS 4-2.Queue로 구현한 BFS 4-3.재귀로 구현한 DFS 4-4.출력 결과 5.정리▶ DFS (Depth-First Search)그래프 검색에 사용된다.이진트리에서 사용했던 PreOrder, InOrder, PostOrder 순회방법Stack 자료구조를 이용하여 구현한다. ▶ BFS (Breadth-First Search)마찬가지로 그래프 검색에 사용.이진트리에서 사용했던 LevelOrder 순회 방.. 이전 1 2 다음
