개발일지

문제설명 입출력 예제 개념 이 문제는 64cm 막대기를 이용하여 길이가 Xcm인 막대기를 만드는 문제다. 이때, 우리가 사용할 수 있는 도구는 막대기를 정확히 절반으로 자르는 것뿐이다. 따라서, 가능한 막대기의 길이는 64, 32, 16, 8, 4, 2, 1cm 등 2의 거듭제곱 형태다. 이는 우리가 풀려고 하는 문제를 이진수 표현으로 해석하는 키가 된다. 각 이진수의 자리는 2의 거듭제곱을 나타내며, 우리가 필요한 막대의 개수는 이진수 표현에서 1의 개수와 같다. 이는 막대기를 사용하느냐, 사용하지 않느냐를 이진수의 1과 0으로 표현한 것과 같다. 이런 점에서 볼 때, 이 문제는 그리디 알고리즘을 사용하여도 풀 수 있다. 그리디 알고리즘을 사용하는 경우, 가장 큰 막대부터 시작하여 목표 길이를 초과하지..

문제 설명 제한 사항 및 입출력 예제 개념 연속된 문자를 제거한다는 측면에서 스택을 활용하면 쉽게 해결할 수 있다. 풀이 #include #include using namespace std; int solution(string s) { stack st; for (int i = 0; i < s.size(); ++i) { if (st.empty()) st.push(s[i]); else if (st.top() == s[i]) st.pop(); else st.push(s[i]); } return st.empty(); }

문제 설명 제한 사항 및 입출력 예제 개념 대괄호가 올바르게 짝지어졌는지 확인하는 문제다. 스택을 사용하는 대표적인 문제로서 특정 조건을 만족할 때 스택에서 문자를 뽑아서 스택이 비었는지 여부를 체크하면 쉽게 해결할 수 있다. 풀이 #include #include #include using namespace std; bool solution(string s) { stack st; bool answer = true; for (const auto& ch : s) { if (st.empty()) st.push(ch); else if (st.top() == '(' && ch == ')') st.pop(); else st.push(ch); } if (!st.empty()) answer = false; return..

문제설명 입출력 예제 개념 문제의 목표는 주어진 문자열에서 특정 '폭발' 문자열을 제외하고 출력하는 것이다. 이를 해결하기 위해 입력 문자열에서 특정 문자열을 식별하고 삭제하는 과정이 필요하다. 이러한 과정은 문자열을 찾는 작업에서 O(n)의 시간 복잡도와 특정 문자열을 삭제한 후 남은 요소들을 이동시키는 작업에서 O(n)의 시간 복잡도를 갖게 된다. 따라서 두 연산을 합치면 전체 알고리즘의 최악의 경우 시간 복잡도가 O(n^2)이 되므로, 큰 입력에 대해 비효율적이라는 결론을 내릴 수 있다. 이를 해결하는 가장 효과적인 방법은 스택을 사용하는 것이다. 폭발 문자열의 마지막 문자와 현재 입력받은 문자를 비교하여, 완전히 일치할 경우 해당 문자열을 제거하는 방식으로 진행하면 된다. 풀이(1) 스택 활용 #..

문제설명 입출력 예제 개념 주어진 문자열에서 괄호만 추출해서 소괄호와 중괄호가 알맞게 짝을 이루고 있는지 확인하는 문제다. 괄호는 스택으로 처리하면 편하게 해결할 수 있지만, 문자열의 종료 시점을 정하는 게 까다로웠다. 필자는 문자열에서 온점을 찾고, 그 문자열의 크기가 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

문제설명 입출력 예제 개념 잘못 부른 수를 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

컨테이너 어댑터(Container Adapter)개요　앞서 살펴본 컨테이너들은 완전 바닥부터 직접 만들었다. 하지만 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업, 즉, 래핑(wrapping)하여 새로운 인터페이스를 만드는 것이 더욱 효율적일 때가 있다. 이것이 바로 컨테이너 어댑터다. C++ 표준 라이브러리에서 제공하는 대표적인 컨테이너 어댑터를 간략하게 설명하고 구현하는 시간을 가져보자.std::stack 　스택(stack)은 데이터의 처리와 저장을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된..

문제설명 입출력 예제 개념 주어진 문자열에서 문자를 하나씩 확인하며 이전 문자와 비교를 하여 좋은 단어인지 확인하는 문제다. 입출력 예제를 분석해보면 다음과 같다. 풀이 #include #include using namespace std; int main() { int num; cin >> num; int cnt = 0; 입력 받을 단어의 개수를 num으로 초기화하고, 좋은 단어의 개수를 초기화할 변수 cnt를 선언한다. for (int i = 0; i > str; stack input; 좋은 단어인지 확인할 문자열을 str로 초기화한다. 그리고 이 문제의 핵심인데, 문자를 하나씩 확인하며 이전 문자와 비교하여 최종적으로 좋은 단어인지 확인할 때 사..