개발일지

문제 설명 제한 사항 및 입출력 예제 개념 대괄호가 올바르게 짝지어졌는지 확인하는 문제다. 스택을 사용하는 대표적인 문제로서 특정 조건을 만족할 때 스택에서 문자를 뽑아서 스택이 비었는지 여부를 체크하면 쉽게 해결할 수 있다. 풀이 #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..

최소 신장 트리 문제그리디 알고리즘 요구 조건　앞 절에서 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니라고 했다. 즉, 최적 부분 구조(optimal substructure)와 그리디 선택(greedy choice)이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.  　최적 부분 구조는 큰 문제의 최적해가 부분 문제의 최적의 해답들로 구성될 수 있는 구조를 의미한다. 그리디 선택 속성은 현재의 선택이 미래의 선택에 영향을 미치지 않고, 각 단계에서 최적의 선택을 하면 전체적으로 최적의 해답을 얻을 수 있는 것을 의미한다. 　이러한 특성에 대해 이해하기 위해 크루스칼 최소 신장 트리 알고리즘에 대해 알아보도록 하자.개요　최소 신장 트리(Minimum Spa..

문제 설명 제한 사항 및 입출력 예제 개념 첫 문자를 대문자로 처리하고 나머지 알파벳을 소문자로 처리하는 문자열 처리 문제다. 입력 문자열에서 각 단어의 첫 문자를 대문자로, 그 외의 알파벳을 소문자로 바꾸는 작업이 필요하다. 여기서 '단어'는 공백 문자로 구분되므로, 문자열을 순회하며 공백 문자를 만났을 때 그 다음 문자를 대문자로 바꿔주면 된다. 풀이 #include #include using namespace std; string solution(string s) { string answer; bool isTrue = false; answer += toupper(s[0]); s = s.substr(1); 공백 문자를 만났는지 여부를 체크할 플래그 변수 isTrue를 false로 초기화해준다. 그리고..

문제 설명 제한 사항 및 입출력 예제 개념 최댓값과 최솟값 모두 처리할 수 있는 이중 우선순위 큐를 구현하는 문제다. 최소힙과 최대힙을 나눠서 처리하는 방법과, 동일한 요소를 여러 번 저장하는 multiset 자료구조를 이용하는 방법 두 가지가 있다. 풀이 (1) 최소힙, 최대힙 #include #include #include #include using namespace std; vector solution(vector operations) { vector temp, answer; for (const auto& str : operations) { string tmp = str.substr(2); if (str[0] == 'I') temp.push_back(stoi(tmp)); else { if (tmp ..

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

배낭 문제개요　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.본문 　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다.   　반면, 분할 가능 배낭 문제..

문제설명 입출력 예제 개념 우선순위 큐의 정렬 순서를 직접 지정하면 풀 수 있는 문제다. 구조체를 이용하여 연산자를 오버로딩하여도 되고, 단순히 비교 함수를 인자로 추가해도 된다. 풀이 #include #include #include using namespace std; bool abs_operator(int a, int b) { return abs(a) == abs(b) ? a > b : abs(a) > abs(b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq(abs_operator); cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.e..

그리디 알고리즘개요　그리디(greedy) 알고리즘은 매 시점에서 가장 이상적인 선택을 지향하는 알고리즘이다. 이 방법론은 지역(local)적으로 최적화된 해답들을 도출하면서, 그 해답들로부터 전역(global)적인 최적해를 구축하는 전략을 채택한다. 그리디 알고리즘은 각 선택의 순간마다 최적의 결정을 내리지만, 이 일련의 결정들이 꼭 최적의 결과를 보장하는 것은 아니다. 그러나 특정 문제에 대해서는 이 알고리즘이 실제로 최적의 결과를 보장하기도 하고, 복잡하고 시간 소모적인 문제를 효과적으로 근사해결하는 데에 종종 활용되기 때문에 그 가치는 높다고 할 수 있다. 　이러한 그리디 알고리즘의 단순하고 직관적인 접근법은 그것의 한계를 동시에 내포하고 있다. 즉, 그리디 특성을 지닌 문제에 대해서만 그리디 알고..

문제설명 입출력 예제 개념 지난 게시글인 최대 힙 문제처럼 우선순위 큐를 이용하여 풀면 쉽게 해결할 수 있다. 즉, 우선순위 큐를 최소 힙으로 정렬하면 된다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } }

문제설명 입출력 예제 개념 주어진 문제는 우선순위 큐의 기본적인 연산을 이해하고 있는지 묻는 문제다. 따라서 우선순위 큐를 최대 힙으로 정렬한 후, 문제의 요구 사항에 맞게 입출력을 조절하면 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } } 특이 사항..