개발일지

문제설명 입출력 예제 개념 1부터 N까지 정렬되어 있는 시퀀스에서 맨 앞에 수를 뽑고, 앞 뒤를 바꿔갔을 때, 마지막에 남는 카드가 무엇일지 구하는 문제다. 먼저 들어간 요소가 뽑힌다는 관점에서 queue를 적절히 활용하면 해결할 수 있는 문제다. 풀이 #include #include using namespace std; int main() { int N, n; cin >> N; queue q; for (int i = 1; i

문제설명 입출력 예제 개념 먼저 예제 1에 대해 스택 수열이 어떻게 형성되는지 그림으로 확인해 보자. 그림에서 알 수 있듯이, 입력받은 수 n이 기존의 max보다 크다면 max + 1부터 n까지 스택에 수를 푸시한다. 그렇지 않다면, 입력받은 수가 스택에서 뽑을 때까지 pop을 해주면 된다. 반대로 스택 수열을 형성할 수 없는 경우인 예제 2를 보자. 3을 입력받는 순간 3을 뽑기 위해서 4를 뽑아야 하는데, 4를 빼면 주어진 수열을 만들 수 없으므로 에러가 뜬다. 즉, 입력받은 수가 num보다 작거나 같은데, 그 수가 스택의 top과 다르다면 주어진 수열을 만들 수 없다. 풀이 #include #include #include using namespace std; int main() { ios::sync..

분할 정복개요　분할 정복(divide-and-conquer)은 복잡하고 해결하기 어려운 문제를 작은 부분 문제로 나눠서 해결하는 방법론이다. 이 접근법의 핵심은 큰 문제를 둘 이상의 하위 문제로 분할하고, 이러한 각각의 하위 문제를 독립적으로 해결한 후, 그 결과를 결합하여 원래 문제의 해법을 도출하는 것이다. 이 기법은 복잡한 문제를 간소화함으로써 알고리즘의 효율성을 증대시키는 데에 중요한 역할을 한다. 　주어진 문제를 분할 정복 방식으로 해결하려면 다음과 같은 세 단계가 필요하다.분할(divide): 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 서브 문제로 나눔정복(conquer): 각 서브 문제에 대한 해답을 구함결합(combine): 각 서브 문제의 해답을 결합하여 전체 문제에 대한 해답을..

문제설명 입출력 예제 개념 주어진 문자열에서 괄호만 추출해서 소괄호와 중괄호가 알맞게 짝을 이루고 있는지 확인하는 문제다. 괄호는 스택으로 처리하면 편하게 해결할 수 있지만, 문자열의 종료 시점을 정하는 게 까다로웠다. 필자는 문자열에서 온점을 찾고, 그 문자열의 크기가 1일 때를 종료 시점으로 정했다. 풀이 #include #include #include using namespace std; int main() { while (true) { string str; stack st; getline(cin, str); if (str.find(".") != string::npos && str.size() == 1) break; 문자열 str을 공백을 포함하여 입력받고, 종료 시점인지 판단한다. else if ..

문제설명 입출력 예제 개념 괄호 검사는 스택을 활용하는 대표적인 문제다. 입력받는 문자가 소괄호이기 때문에 스택에서 하나씩 꺼내어 괄호 문자열이 맞는지 확인하면 된다. 풀이 #include #include using namespace std; int main() { int N; cin >> N; string str; while (N--) { stack st; cin >> str; if (str.size() % 2 == 1) cout

알고리즘 및 이진 탐색알고리즘　알고리즘(Algorithm)이란 주어진 문제를 해결하기 위한 일련의 명령들의 순서와 절차를 의미한다. 다시 말해, 문제를 정의하는 데 필요한 입력을 받아, 일련의 변환 과정을 거쳐 결과를 출력한다는 점에서 함수와 유사한 개념이다. 이러한 알고리즘은 문제를 효율적으로 해결하기 위해 설계되며, 이를 위해 다양한 최적화 기법이 사용된다. 　알고리즘의 효율성은 해당 알고리즘의 동작과 수행에 필요한 명령 수에 따라 결정된다. 예를 들어 소수를 판별하는 알고리즘을 짰다고 가정하자.  // 소수 판별 알고리즘1bool isPrime1(int n){ for (int i = 2; i 　두 개의 소수 판별 알고리즘 중 어떤 게 효율적일까? 먼저 첫 번째 함수는 2부터 n까지 모든 수를 ..

문제설명 입출력 예제 개념 잘못 부른 수를 0으로 지우고, 마지막의 수의 합을 출력하므로 스택의 개념을 이용하면 쉽게 풀 수 있다. 즉, 0을 입력받는 순간 스택에서 하나를 뽑으면 된다. 풀이 #include #include int main() { int K, n, sum = 0; std::cin >> K; std::stack st; while (K--) { std::cin >> n; if (n == 0) st.pop(); else st.push(n); } while (!st.empty()) { sum += st.top(); st.pop(); } std::cout

문제설명 입출력 예제 개념 기본적인 스택을 잘 이해하고 있는지 확인하는 문제다. 입력받은 문자열에 맞게 스택의 동작을 수행하게끔 작성하면 쉽게 해결할 수 있다. 풀이 #include #include int main() { std::stack st; int N, n; std::cin >> N; while (N--) { std::string str; std::cin >> str; if (str == "push") { std::cin >> n; st.push(n); } else if (str == "top") { if (!st.empty()) std::cout

문제설명 입출력 예제 개념 경우의 수를 계산하는 문제다. 이때 순서에 상관없이 N개의 다리와 M개의 다리를 이으면 되므로, 조합의 개념을 이용하면 쉽게 해결할 수 있다. 풀이 #include #include int main() { int T, N, M; std::cin >> T; while (T--) { std::cin >> N >> M; std::cout M; std::cout T; while (T--) { result = 1; tmp = 1; cin >> M >> N; for (int i = N; i > N - M; --i) { result *= i; result /= tmp++; } cout

문제설명 입출력 예제 개념 주어진 문자열을 빈도수 → 길이순 → 알파벳 순으로 정렬하는 문제다. 자료구조 맵을 이용해 특정 길이 이상의 문자열을 빈도수와 함께 컨테이너에 저장한 후, 주어진 조건에 맞게 정렬하면 문제를 해결할 수 있다. 풀이 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; string str; map m; cin >> N >> M; 영단어의 개수 N, 외울 단어의 길이 기준 M, 영단어 문자열 str, 단어를 저장할 컨테이너 m을 초기화한다. while (N--) { cin >> str; if (str.size(..