Algorithm

그리디 알고리즘이란❓ 그리디 알고리즘이란 greedy라는 이름의 뜻에서 알 수 있듯이 탐욕스러운, 욕심스러운 알고리즘입니다. 탐욕이라는 뜻처럼 그리디 알고리즘(탐욕 알고리즘)은 각 단계에서 가장 최선의 선택을 하는 방법을 말합니다.  다음 그림을 보면 한눈에 알 수 있습니다. 위 그림을 보면 가장 큰 수를 탐색하는 과정을 greedy 알고리즘과 일반적으로 탐색하는 과정을 보여줍니다. 가장 큰 수를 찾기 위해 앞으로 간다면 제일 큰 수가 있는 "99"과 연결되어 있는 3 ➡️ 99 을 생각할 것입니다. 하지만 Greedy 알고리즘은 시작부터 3과 12 두 수중 가장 큰 수인 "12"을 탐색하고 그다음 큰 수인 "6"을 탐색합니다. 이 처럼 그리드는 최종결과에서의 최적의 해가 아닌 "현재상황에서 최적의 해"..

동적 계획법 DP란❓  동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.  주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다. 위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장동일 결과 재사용 DP 문제 성립 조건동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다. 최적 부분 구조(Optimal Substructure)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..

한 사람이 단어를 생각하고 다른 사람이 그 단어를 추측하는 만약 "단어 맞추기" 게임을 한다면 추측하는 사람은 가능한 모든 단어를 시도하여 맞출 때까지 계속합니다. 예를 들어 추측하는 사람이 "축구"라는 단어를 맞춰야 할 때, 가능한 모든 단어를 시도하여 "축구"를 찾을 때까지 계속합니다. 이는 이번 포스팅에서 알아볼 브루트 포스 알고리즘의 아이디어와 비슷합니다. 완전 탐색  : 브루트 포스 알고리즘 (Brute Force Algorithm)Brute : 무식한Force : 힘 직역하면, 무식한 힘을 갖는 알고리즘입니다. 단어에서 알 수 있듯이 브루트 포스(Brute Force) 알고리즘은 문제 해결을 위해 가능한 모든 경우의 수를 시도하는 가장 단순하지만 강력한 방법입니다.   완전탐색(Exhausti..

1. 유클리드 호제법이란? 유클리드 호제법(- 互除法, Euclidean Algorithm) 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘 중 하나이며, 두 개의 정수 or 다수의 자연수에서 최대공약수(gcd)를 구하는 방법입니다. 이때 호제법이라는 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 의미합니다. 2. 유클리드 호제법으로 최대공약수 구하기 나머지가 0이 될때까지 계속 재귀적으로 구해줘야합니다. 1. a, b (a> b) 두 수를 큰 수를 작은 수로 나눠 나머지(R1)를 구합니다. R1 = (a % b), R1!= 0 2. b % R1을 나눠서 나머지(R2)를 구합니다. R2!= 0 3. R1 % R2을 나눠 나머지(R3)를 구합니다. R3..