Algorithm
[알고리즘] Base
by orioncsy
2022. 9. 28.
Greedy Algorithm
개념
- 당장 눈앞에 보이는 선택에서 최적해를 선택하여 해답을 구하는 알고리즘
절차
- 선택 절차 : 최적해를 선택
- 적절성 검사 : 해당 최적해가 문제 조건 부합하는지 확인
- 해답 검사 : 기존 문제가 해결되었는지 확인
조건
- 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는 경우
- 최적 부분 구조 : 부분 문제에 대한 최적 문제 해결로 구성
예시
- 거스름 돈을 최소한의 개수의 동전으로 받기
- Knapsack problem
Implementation - 구현
개념
- 로직을 코드로 구현하는 문제
- 일반적으로 문제가 길거나 자세하고 까다롭게 출제
- 대표적으로 brute force 나 simulation이 존재
Simulation
- 모든 과정과 조건을 제시하고 결과가 무엇인지 확인하는 문제
Brute Force - 완전 탐색
개념
- 가능한 경우의 수를 모두 탐색하여 해답을 찾는다
- 무차별 대입 방법
특징
- 최적의 해를 구하진 않지만 최악의 복잡도를 감수하고 해를 구하는 것
- 적절한 알고리즘이 없을 때 사용
한계
- 프로젝트 규모가 커진다면 자원 소모가 커짐
- 정확도를 희생하더라도 다른 알고리즘 사용하는 경우 발생
사용 예시
- 순차 검색 (sequential search) - 순차적으로 특정 데이터 탐색
- 문열 매칭 (brute-force string matching) - 문자열 내 패턴 일치 확인
- 선택 정렬 (selection sort) - 가장 큰 값을 비교해서 끝으로 보내기를 반복
- 버블 정렬(bubble sort) - 두 개씩 연속적으로 비교해서 n번 반복
- Tree 완전 탐색 - exhausive search(BFS, DFS)
Binary Search - 이진 탐색
종류
- Linear Search - 선형 탐색
- Binary Search - 이진 탐색
- Hash Search - 해시 탐색
Binary Search 특징
- 중간 값을 선택하고 작거나 큰 영역을 분리해서 반복해 찾아가는 알고리즘
- 정렬된 배열에서 값을 찾고 데이터 양이 많을수록 효율적이다
사용 예시
- 사전 검색, 도서관 도서 검색
- 시스템 리소스 파악
- 반도체 테스트에서 디지털, 아날로그 레벨 측정
DP VS Divide-and-conquer
DP(Dynamic Programming)
- 작은 문제들을 쪼개서 작은 문제들을 해결해서 큰 문제를 해결하는 방식
- 데이터를 따로 저장해서 이를 활용하여 문제 해결
- 작은 문제를 해결하며 올라가는 Bottom-up 방식
- Coin changing
dp[해당 금액+1];
dp[0]=0; (0원을 만드는 데 필요한 동전은 0);
for(dp[1-]) - (idx 1부터 INF로 설정)
for(코인의 종류){
for(코인의 금액부터 해당 금액까지 순차 접근)
dp[j]= min(dp[j], dp[j-코인 금액])기존값과 코인값을 뺀 인덱스의 최솟값
}
return dp[금액]
- 0-1 knapsack problem
dp[물건의 수 + 1][최대 용량];
for(i는 1부터 물건의 수까지){
w=물건 무게, v=물건 가치
for(j는 1부터 최대 용량까지){
if(j>=w) dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v);
else dp[i][j]=dp[i-1][j];
}
}
return dp[물건수][최대용량];
Divide-and-conquer
- 큰 문제를 작은 문제들로 나눠가면서 문제 해결
- 재귀를 사용하여 해결
- 큰 문제를 나눠가며 해결하는 Top-down 방식
Algorithm with Math
GCD & LCM
int GCD(int a, int b){
return b==0? a : GCD(b, a%b);
}
LCM = A*B/GCD;
Permutation(순열) & Combination
- nPr= n개 중에 r개를 순서를 상관있게 뽑는 경우의 수
- nCr= n개 중에 r개를 순서 상관없이 뽑는 경우의 수
- nCr=n-1Cr-1 + n-1Cr
소수 찾기 - 에라토스테네스의 체
bool prime[num+1]; //false인 경우 소수
prime[1]=true;
for(int i=2; i*i<=num; i++){
if(prime[i]) continue;
for(int j=i*i; j<=num; j++){
prime[j]=true;
}
}
#include <string>
#include <vector>
#include <set>
using namespace std;
set<int> setnum;
bool isPrime(int num){
if(num==1 || num==0) return false;
for(int i=2; i*i<=num; i++){
if(num%i==0) return false;
}
return true;
}
void Permutation(string front,string s){
if(front.length()!=0) setnum.insert(stoi(front));
for(int i=0; i<s.length(); i++){
Permutation(front+s[i],s.substr(0,i)+s.substr(i+1));
}
}
int solution(string numbers) {
int answer = 0;
Permutation("", numbers);
for(int val : setnum){
if(isPrime(val)) answer++;
}
return answer;
}
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> list;
int temp;
int sum = -100;
int r1 = 0;
int r2 = 0;
for (int i = 0; i < 9; i++) {
cin >> temp;
list.push_back(temp);
}
sort(list. begin(), list.end());
for (auto val : list) sum += val;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if (list[i] + list[j] == sum) {
r1 = i;
r2 = j;
break;
}
}
}
for (int i = 0; i < list.size(); i++) {
if (i != r1 && i != r2) cout << list[i] << "\\n";
}
return 0;
}
DFS
전형적인 템플릿
public [결과값의 리스트] DFS([대상이 되는 후보리스트], [횟수], [임시저장],[결과값리스트]){
if([탈출조건: ex횟수가 0인경우]){
[결과값리스트]에 [임시저장] 값을 넣기
return [결과값리스트]
}
for([대상 후보리스트]){
[임시저장]에 [대상 후보값 중 하나 선택] 넣기
[대상후보리스트]에서 선택한 대상 제거한 [남아있는 후보리스트] 생성
[결과값리스트]=dfs([남아있는 후보리스트], [횟수]-1, [임시저장], [결과값리스트]
}
return [결과값리스트]
}
BFS
전형적인 템플릿
Queue 선언
[queue].add([첫번째 값])
while(!queue.isEmpty()){
[queue에서 가져온값]=queue.peek();
queue.poll();
[가져온 값]을 처리
for([대상 후보값]){
queue.add([대상 후보값])
}
}
return;