개발일지

ATmega 128 구조 개요 지난 시간에 ATmega 128에 대한 대략적인 개요를 파악했었다. 이번 시간에는 ATmega 128의 CPU와 메모리 구조를 파악해 보는 시간을 가지도록 해보자. 시작하기 앞서 ATmega 128은 프로그램(SRAM)과 데이터(FLASH, EEPROM)가 분리되어 있으므로 Havard 구조를 채택하고 있다는 점 알아두자. 그리고, 해당 구성요소들은 컴퓨터 구조 시간에서 한 번씩 다뤘던 내용이므로, 헷갈린다면 해당 게시글들을 확인해 보자. 본문 CPU 구조 ATmega 128의 CPU 구조다. 여기서 ALU를 포함해 범용 레지스터(General Purpose Register), 상태 제어 레지스터(Status and Control), 프로그램 카운터, 플래시 메모리, 명령 ..

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

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