[알고리즘] 코딩 테스트를 위해 알아야 하는 문제들

작성 중 완벽하지 않습니다. 재미로 봐주세요

먼저 이 글은 복수 전공자 및 비전공자 분들을 위한 글입니다. (물론 전공자 분들이 보셔도 됩니다)
저는 복수 전공자로서 코딩 테스트가 막막함이 있어 이것을 해결하고자 적어보는 글입니다. 

알고리즘 목록

• 완전검색 - 브루트포스
  • 순열 (next_permutation) > stl
  • 조합 (재귀)
  • 비트 마스크

비트 마스크

#include <iostream>
#include <vector>

using namespace std;

vector<int> a;

int main(){
	int n, m;
    cin>>n>>m;
    a.resize(n);
    
    for(int i=0; i<n; i++) cin>>a[i];
    
    int answer = 0;
    
    for(int i=1; i<(1<<n); i++){
    	for(int k=0; k<5; k++){
        	if(i&(1<<l)) sum+=a[k];
        }
        if(sum==m) answer+=1;
    }
    cout<<answer<<'\n';
    return 0;
}

최대 공약수
c++17 에서는 #include <numeric> 에서 stl 로 제공을 해줍니다. 
c++ 17 을 사용할 수 있다면 참고하시기 바랍니다.

int gcd(int a, int b){
	 return b ? Euclidean(b, a%b) : a;
}

최소 공배수 

int gcd(int a, int b){
	return b? gcd(b, a%b) : a;
}

int lcm(int a, int b){
	return a*b/gcd(a, b);
}

진법 변환 (2진법으로 변환을 하는 방법)

#include <string>

using namespace std;

int main(){
	int n = 10;
    string s;
    while(n>0){
    	if(n%2==0) s = '0' + s;
        else s = '1' + s
    	n/=2;
    } //2진법 변환

	return 0;
}

 

• 그리디:  부분적인 최적해가 전체적인 최적해가 되는 방법 (반드시 최적해의 보장은 안된다.) 그리디 알고리즘으로 풀 수 있으면 다이나믹으로 해결이 가능하다. 하지만 그 역은 가능하지 않는다.
  • 회의실 배정: 제일 많은 회의를 잡는 방법은 무엇인가? :끝 시간을 기준으로 정렬한다.
  • 거스름돈 문제: 그리디로 풀수는 있지만 보장은 해주지 않는다. 다이나믹을 활용해 최적해를 만들 수 있다. 
  • 최소 신장 트리: 주어진 가중치 중 사이클 없이 모든 점들은 연결시킨 트리 중 가중치 합이 최소인 트리      
    크루스칼 알고리즘(유니온 파인드)과 프림 알고리즘(우선순위 큐)이 있다. 
    외판원 문제(TSP) 를 풀 수 있게 해준다.
  • 배낭 문제 (0-1), 부분 배낭 문제가 있다.
  • 작업 스케줄링 문제: 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 시작하는 시간을 우선으로 배정
• Divide and Conquer 
  • 퀵 정렬
  • 합병 정렬
• 그래프 (DFS, BFS, 다익스트라, 플로이드 - 와샬, 크루스칼, 프림)
  • 다익스트라 - 한 정점에서 최단거리를 구하는 방법 (우선 순위 큐를 이용)
  • 플로이드 와샬 - 모든 정점에서 최단거리를 구하는 방법 (다이나믹 방식을 이용)
  • 크루스칼 알고리즘 - 유니온 파인드를 이용하여 사이클 없는 것에서 MST 구하는 방법
  • 프림 알고리즘 - 우선순위 큐를 이용하여 MST 구하는 방법
  • 애정하는 조합은 다익스트라 + 프림

•  문자열 탐색
  • '(', ')' 문제가 나오는 경우는 웬만하면 stack 을 사용하였습니다. 
  • KMP 알고리즘
• 다이나믹: 부분의 해들을 사용하여 다음 해를 구하는 것이다. 
  • 플로이드 와샬 (모든 정점에서 최단거리를 구하는 알고리즘) 이 해당한다. 여기서 신기한 점은 플로이드 와샬 알고리즘은 시간 복잡도 O(n^3) 이고 비슷하지만 한 정점에서 최단거리를 구하는 다익스트라 알고리즘은 시간 복잡도가 O(n^2) 라는 것이다. 여기서 다익스트라를 모든 정점에서 적용을 하면 O(n^3)이 된다. 하지만 플로이드가 더 간단할 수 있다. 음수가 있는 경우 다익스트라를 사용할 수 없고 플로이드를 사용해야 한다. ^^
  • 연속 행렬의 곱 문제: 행렬을 연속으로 곱하 때 중복되는 부분이 있을 수 있다. 이를 해결을 하는 방법
  • 편집거리 문제: 하나의 문자를 삽입, 삭제, 대체를 활용하여 최소한의 연산을 구하는 문제, LCS 문제와 동일하다.
  • 배낭 문제를 해결할 수 있다. 
  • 동전 문제를 해결할 수 있다.