개발일지

문제설명 입출력 예제 개념 이 문제는 주어진 문자열 내에서 특정 문자가 등장하는 빈도를 특정 구간에서 확인하는 것을 요구한다. 일반적으로, 구간 l에서 r까지 특정 문자 비교를 직접 수행하는 경우, 문자열의 길이가 매우 긴 경우엔 계산 시간이 지나치게 오래 걸릴 수 있으므로 시간 초과 문제에 직면하게 된다. 이러한 문제를 극복하기 위해 '특정 구간'이라는 핵심 키워드에 주목하고, 누적합의 개념을 적용하면 이 문제를 보다 효율적으로 해결할 수 있다. 또한 문자의 등장 횟수를 벡터에 초기화하여 이진 탐색을 통해 구현할 수도 있다. 풀이 (1) 이진 탐색 #include #include #include using namespace std; vector v[26]; string str; int T, l, r; ..

문제설명 입출력 예제 개념 정수 배열을 AC 언어를 이용해 연산하는 문제다. 이때 입력이 대괄호와 쉼표가 포함되는 것에 유의해야 한다. 그 후 정수들을 뒤집거나 지우는 과정이 필요한데, 전체 배열을 뒤집는 연산을 효율적으로 처리하기 위해 deque 자료구조를 이용하면 된다. 풀이 #include #include #include #include #include using namespace std; int main() { int T, n; string p, str; cin >> T; 테스트 케이스의 개수 T, 배열에 들어있는 수의 개수 n, 명령을 수행할 함수 문자열 p, 배열을 저장할 문자열 str를 초기화한다. while (T--) { cin >> p >> n >> str; deque dq; string..

문제설명 입출력 예제 개념 1부터 N까지의 수열 중에서 특정 위치의 수를 최소한으로 회전하며 뽑아내는 문제다. 따라서 왼쪽으로 갈지 오른쪽으로 갈지 판단한 후, 값을 뽑아내면 된다. 이때 양방향으로 선입선출하는 구조이므로 dequeue를 사용하면 편하다. 풀이 #include #include #include using namespace std; int main() { int N, M, n, cnt = 0; cin >> N >> M; deque dq; for (int i = 1; i > n; auto it = find(dq.begin(), dq.end(), n); int distance = it - dq.begin(); bool isLeft = distance N >> M; deque dq; for (in..

문제설명 입출력 예제 개념 문자열을 입력받아 덱의 기본 동작을 확인하는 간단한 문제다. dequeue의 기본적인 원리를 이해하고 있다면 쉽게 해결할 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; cin >> N; deque dq; string str; while (N--) { cin >> str; if (str == "push_back") { cin >> n; dq.push_back(n); } if (str == "push_front") { cin >> n; dq.push_front(n); } if (str == "front") { if (d..

문제설명 입출력 예제 개념 문서의 개수와 중요도가 주어졌을 때, 큐에서 M번째에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제다. 프린터 대기열은 큐 자료 구조를 사용한다는 점과, 문서의 중요도가 필요하다는 점에서 문서의 이름과 중요도를 자료형 pair로 받아 처리해야 한다는 점을 유의하자. 풀이 #include #include #include using namespace std; int main() { int T, N, M, n; cin >> T; 테스트 케이스의 수 T, 문서의 개수 N, 출력 순서가 궁금한 정수 M, 중요도 n을 초기화한다. while (T--) { int index = 0; cin >> N >> M; queue q; pair ans; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 예제 (7,3) 요세푸스 순열이 생성되는 과정은 다음과 같다. 따라서 K번 만큼 수를 뒤로 보낸 후 수를 뽑으면 요세푸스 순열이 생성된다. 즉, 선입선출의 구조를 갖고 있으므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; queue q; for (int i = 1; i

문제설명 입출력 예제 개념 큐의 기본적인 구조를 잘 이해하고 있는지 묻는 문제다. 기존의 스택(10828) 문제처럼 입력받은 문자열에 맞게 큐의 동작을 수행하게끔 작성하면 해결할 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; cin >> N; queue q; while (N--) { string str; cin >> str; if (str == "push") { cin >> n; q.push(n); } else if (str == "front") { if (q.empty()) cout

문제설명 입출력 예제 개념 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..

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