걸음마코딩기

문제를 풀다보면 종종 순열, 조합, 중복순열, 중복조합을 이용하는 경우가 있다. 이번 포스팅에서는 각각의 정의와 c++로 구현하는 방법에 대해 정리해보았다. 1. 순열 : 순서를 따지고, 중복을 허용하지 않는다. 중복을 허용하지 않기 때문에, 중복을 검사하는 visitied 처리가 필요하다. depth로 r만큼의 길이를 출력해준다. 그렇지 않다면 중복을 검사한 후, 재귀로 함수를 부른다. depth가 r이 될때, 순열이 완성된 것이므로, 순열을 출력해주고 backtracking해준다. backtracking을 수행한 뒤, check[i] = false로 다음 루프에서 해당 숫자를 사용할 수 있게 한다. 그렇지 않으면, 한번 사용된 숫자는 계속 사용중으로 표시가 되어, 그 숫자가 다른 가능한 순열 위치에서..

그리디 문제이다. 2+1으로 3개중 가장 작은 값을 무료로 해주기 때문에 가능한 큰 숫자들끼리 묶어서 가장 작더라도 전체에서는 큰 숫자를 무료로 받도록 코드를 짰다. 내림차순으로 정렬 3개씩 묶어서 마지막 값은 sum에 포함 안해준다. (인덱스가 0부터 시작하므로 i%3이 2가 아니면 다 더해줌) #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; vector c; cin >> N; for(int i=0; i> t; c.push_back(t); } sort(c.begin(), c.end(), greater ()); long..

공통된 숫자를 이용하여 가장 큰 수를 만들어주는 문제이다. string solution(string X, string Y) { string answer = ""; vector num(10,0); vector result; for(int i=0; i

풀이과정 괄호 문제는 스택의 대표적 문제이다. 짝맞추는 문제이므로 '('가 들어왔을때만 스택에 넣어준다. ')'가 들어왔을 때 스택이 비어있다면 잘못된 괄호이므로 "NO"를 출력해주고 아니라면 짝이 맞았으므로 스택을 pop해준다. 문자열 길이만큼 진행한 뒤 스택이 비어있지 않다면 짝이 안맞았음을 의미하므로 "NO"를 출력한다. 스택이 비어있다면 짝이 다 맞았다는 것을 의미하므로 "YES"를 출력한다. #include #include using namespace std; void VPS(string inp) { stack s; for (int i = 0; i < inp.length(); i++) { if (inp[i] == '(') s.push('('); else { if (!s.empty()) s.pop..

간단하게 스택을 구현하면 되는 문제로, 배열을 써서 풀었고 STL stack을 사용한 간단한 버전도 올려놨다. [1차원 배열 이용] #include using namespace std; void push(int value); void pop(); void size(); void empty(); void top(); int N; int top_v = -1; int myStack[100000]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string com; cin >> N; for(int i=0; i> com; if(com == "push") { int x; cin >> x; push(x); } else if(c..

단순한 sorting 문제로, 직접 구현해도 되지만 나는 간단하게 STL의 sort 함수를 이용했다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int arr[N]; for(int i=0; i> arr[i]; sort(arr, arr+N); for(auto x : arr) cout a; arr.push_back(a); } sort(arr.begin(), arr.end()); arr.erase(std::unique(arr.begin(), arr.end()), arr.end()); for(auto x : arr) c..

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; //접두..

[ 구현 방법 ] [ vector 이용 ] void Array() { int n, m; cin >> n >> m; vector array; for(int i=0; i> input; array.push_back(input); } for(int i=0; i> input; array.push_back(input); } sort(array.begin(), array.end()); for(auto a : array) cout n >> m; int arr_a[n], arr_b[m], arr[n+m]; for(int i=0; i> arr_a[i]; for(int i=0; i> arr_b[i]; while(check_n + check_m < n + m) { if(check_n == n) cout

[ 구현 방법 ] [ 코드 ] #include #define sync ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; void func() { int n; long binary[90]; binary[0] = 1; binary[1] = 1; cin >> n; for(int i=2; i