1. 완전 탐색 가능 여부 확인 : 주어진 시간안에 모든 경우의 수 확인이 가능한지 체크. 2. 조각 내기 : 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔. (각 선택은 답의 후보를 만드는 과정의 한 조각.) 3. 부분 문제 해결 : 이 선택 중 한 조각을 선택해 답의 일부를 만들고, 나머지를 재귀 호출을 통해 완성. 4. 기저 사례 작성 : 조각이 하나 또는 하나도 남지 않은 경우를 기저 사례로 선택해 처리. ex) 보글 게임 문제 (https://algospot.com/judge/problem/read/BOGGLE) 1. 주어진 시간안에 모든 경우의 수 탐색 가능한가? 2. 조각 내기 & 답만들기, 재귀 호출 : 각 글자를 하나의 조각으로 만들기. 즉, 현재 글자 == 단어의 글자 ? 재..

다음 순열 : https://www.acmicpc.net/problem/10972 이전 순열 : https://www.acmicpc.net/problem/10973 모든 순열 : https://www.acmicpc.net/problem/10974 다음 순열과 이전 순열에선 우선 input으로 어떤 수열이 주어진다.그러면 결과로 그 수열 이후/이전에 오는 순열(permutation)을 프린트한다. 모든 순열에선 n이 주어지며, 1 ~ n 까지 모든 permutation을 구하면 된다. 1. 반복문으로 해결하기 - 다음 순열 next_permutation이 치트키이지만... 안쓰고 반복문으로 도전해보았다. #include #include #include using namespace std; int N, k;..

N과 M (2) : https://www.acmicpc.net/problem/15650 N과 M (4) : https://www.acmicpc.net/problem/15652 N과 M (6) : https://www.acmicpc.net/problem/15655 N과 M (8) : https://www.acmicpc.net/problem/15657 N과 M (10) : https://www.acmicpc.net/problem/15664 N과 M (12) : https://www.acmicpc.net/problem/15666 2번은 n개의 자연수 중 m개를 고르는 조합(nCm) 문제이고, 4번은 중복 조합을 구하는 문제이다. 6번은 2번과 똑같이 nCm을 구하는 문제인데, n개의 자연수가 크기에 상관없이 ..

N과 M (1) : https://www.acmicpc.net/problem/15649 N과 M (3) : https://www.acmicpc.net/problem/15651 N과 M (5) : https://www.acmicpc.net/problem/15654 N과 M (7) : https://www.acmicpc.net/problem/15656 N과 M (9) : https://www.acmicpc.net/problem/15663 N과 M (11) : https://www.acmicpc.net/problem/15665 1번은 n개의 자연수 중 m개를 고르는 순열(nPm)을 구하는 문제이고, 3번은 중복 순열을 구하는 문제이다. 5번은 1번과 똑같이 nPm을 구하는 문제인데, n개의 자연수가 크기에 상..

https://www.acmicpc.net/problem/9095 1. 문제 이해 => 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 1, 2, 3을 사용해서, 1, 2, 3의 합으로 n을 나타내는 방법의 수를 구하는 것. 2. 재정의 & 추상화 => 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. == 1, 2, 3을 사용하여 n을 나타내는 모든 경우의 수를 구하여라. == 완전 탐색 문제 == 재귀, 분할 정복등을 사용 3. 설계 재귀적 접근 : 함수 내부에서 for 문으로 1, 2, 3을 돌면서 n - 1, n - 2, n - 3한 값을 다시 함수에 인자로 넣음. 기저 사례는 n이 0..

1. 괄호 쌍이나 문자 확인 유형 (기본 유형) 2. 오큰수 유형 (심화 유형) 3. 커서 이동 유형 4. 후위 표현식 유형 1. 기본 유형 : 괄호 쌍이나 문자 확인 유형 괄호 (실버 4) : https://www.acmicpc.net/problem/9012 좋은 단어 (실버 4): https://www.acmicpc.net/problem/3986 문자열 폭발 (골드 4) : https://www.acmicpc.net/problem/9935 => 괄호 혹은 문자의 순서, 규칙이 조건을 만족하는지 확인하는 유형. => 보통은 input을 스택안에 넣어두고, 들어오는 input에 따라 규칙이 맞으면 true 혹은 pop, 규칙이 틀리면 false 혹은 전부 pop. => 괄호쌍 : 스택을 하나 생성하고, ..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 랭크 : 골드 3 17298 오큰수와 세트인 문제다. 접근법도 거의 흡사하다. 1. 문제 이해 => 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 랭크 : 골드 4 1. 문제 이해 => 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) =..