걸음마코딩기

🚦 이번 포스팅에서는 〰️ ▶️ 백트래킹(Backtracking)이란? ▶️ 백트래킹(Backtracking)문제 풀어보면서 익히기 📌 백트래킹(Backtracking)이란? : 해를 찾는 도중 해가 아니라서 막힌다면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. --> 반복문의 횟수까지 줄일 수 있음 일명 가지치기(pruning)로, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 그러나, 문제가 N!의 경우의 수를 가질때 최악의 경우로 O(지수함수) 필요할 수 있다. 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될만한지 판단하고, 그렇지 않으면 가지치지한다. 주로, DFS 등 모든 경우의 수를 탐색하는 과정에서 조건문 등을 ..

🚦 이번 포스팅에서는 〰️ ▶️ 동적 계획법(Dynamic Programming)이란? ▶️ 동적 계획법(Dynamic Programming) 문제 풀어보기 📌 동적 계획법(Dynamic Programming)이란? : 하나의 문제는 단 한번만 풀도록 매번 저장하는 알고리즘 동일한 문제를 요구하는 경우 기존에 이미 저장해 두었던 것을 가져온다. 불필요한 반복 계산을 줄이고 효율적으로 최적해를 찾는다. 계산한 값들은 하나의 보관용 테이블(배열)에 순서대로 저장한다. 분할 정복법과 같이 여러개의 하위 문제들로 나누어 먼저 처리해야 할 때 사용한다. 대표적인 문제 : 피보나치 수열 DP 구현의 두가지 방법 재귀 함수 이용 (Top - Down) : 큰 문제를 쪼개나간다. 재귀 함수를 이용한 피보나치 수열 구현..

🚦 이번 포스팅에서는 〰️ ▶️ Greedy(탐욕) 알고리즘이란? ▶️ Greedy(탐욕) 알고리즘 문제 풀어보기 📌 Greedy(탐욕) 알고리즘이란? : 각 단계에서 가장 최선의 선택을 하는 기법이다. 현재의 선택이 나중에 미칠 영향을 고려하지 않는다. 그렇기 때문에, 그 정당성 분석이 중요하다. ▶️ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요! 동적(dynamic) 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위한 개념이다. 대표적인 문제로 거스름돈 문제, 활동 선택 문제 등이 있다. 📌 Greedy(탐욕) 알고리즘 문제 풀어보기 1️⃣ 백준 14916 거스름돈 동전의 개수가 최소가 되도록 거슬러줘야 하기 때문에 되도록 큰 단위의 동전을 많이..

🚦 이번 포스팅에서는 〰️ ▶️ DFS(깊이 우선 탐색)이란? ▶️ DFS 구현방법 ▶️ BFS(너비 우선 탐색)이란? ▶️ BFS 구현방법 ▶️ DFS vs BFS 📌 DFS(깊이 우선 탐색) 이란? : Depth First Search의 줄인말로, 그래프를 탐색하는 방법 중 하나이다. 루트 노드 (혹은 다른 임의의 노드)에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법이다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택하며, BFS(너비 우선 탐색)보다 좀 더 간단하다. 단순 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느리다. 전위순회(Pre-Order Traversal)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. DFS는 재..

A* 알고리즘이란? Dijkstra 알고리즘의 확장판으로 Best-First 검색을 이용해 시작점->도착점 까지의 가장 적은 비용을 사용하는 경로를 찾음 - 조사하지 않은 node중 가장 효율적이라 판단되는 node를 찾음 - 찾은 node가 도착점이면 종료, 아니면 인접 node들 중 다시 찾음 - 조사한 node들은 close list에 저장, 조사하지 않은 node들은 open list에 저장 ** Dijkstra 알고리즘은 시작노드만 지정하고 다른 모든 노드에 대한 최단 경로를 파악, A* 알고리즘은 시작노드와 목적지 노드를 분명하게 지정하여 이 두 노드간의 최단 경로를 파악한다는 것이 다르다! - 각 정점은 목적함수값 g(x)를 가지고있으며 best-first 검색을 통해 g(x)값이 가장 좋은..

KMP 알고리즘이란 ? 최대 접두부를 구현하여 불일치를 감지할 때마다 이전의 일치 문자열로 돌아가 점프하는 방식으로 시간 복잡도는 최악의 경우 O(N) : 문자열 길이 * 패턴 길이 [ 구성 요소 ] lps[] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대길이 저장 pattern[] : 패턴 문자열 text[] : 주어진 문자열 KMP 알고리즘 함수 구현하기 예시 문자열 ) ABAABAB i 문자열 lps[i] 0 A 0 1 AB 0 2 ABA 1 3 ABAA 1 4 ABAAB 2 5 ABAABA 3 6 ABAABAB 2 => lps에 최대길이인 3이 들어감 lps 구현 코드​ void lps_array(string pattern, int M, int lps[]) { int len = 0; //접두..

원리 퀵정렬은 Divide & Conquer algorithm중 하나로 "pivot"이라는 기준값을 지정하여 pivot을 기점으로 배열을 partitioning하여 정렬하는 알고리즘이다. 보통 pivot은 배열의 맨 앞 원소를 지정하는데 두번째 원소부터 오른쪽으로 pivot보다 큰값을 찾고, 맨 마지막 원소부터 왼쪽으로 pivot보다 작은 값을 찾아나간다. 만약 왼쪽으로 훑던 것이 오른쪽을 추월한다면 pivot과 오른쪽 기준을 swap하고 그렇지 않다면 왼쪽 오른쪽 값을 swap한다. Complexity 모든 원소를 한번씩 훑기때문에 O(n), 배열을 반으로 계속 divide하기 때문에 O(log2n)으로 총 O(nlogn)이라는 빠른 속도를 가진다. 주의사항 - Worst Case ! 배열이 이미 정렬..