해바

문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 백준 게시판에 올라온 풀이 Tip Quick Sort로 풀고 보나 마나 맞겠지 했다가 시간 초과가 떠서 당황했다. 시간 초과의 원인은, 최악의 경우(ex. 정렬 혹은 역정렬) $O(n^2)$의 시간 복잡도를 가지기 때문이었다. Quick Sort 아래 define으로 정의된 SWAP 함수를 매크로 함수라고 한다. 처음에 그냥 void swap(int* x, int* y) 꼴..

문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 시간복잡도가 O($n^2$)인 정렬 알고리즘 중에 아무거나 쓰면 된다. Bubble Sort와 Insert Sort 둘 다 짜봤다(기본 개념은 여기를 참고함). 5 2 3 4 1 이란 숫자를 정렬하는 방법을 설명하는 건 아날로그적 방식으론 바로 설명할 수 있는데, 코드로 구현하는 과정은 전혀 다른 문제다. 다음에 풀어볼 Merge Sort나 Quick Sort는 특히나.. C++이라면 #in..

문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 해결 방법은 입력된 수열 값과 일치할 때까지 값을 비교하며 스택에 넣다가, 일치하면 일치하지 않을 때까지 스택에서 빼는 것이다. 처음에는 값을 8번 입력하는 범위 안에서 임의로 넣어도 작동해야 하는 줄 알고 입력받은 값을 sort함수로 정렬시켜서 비교하려고 난리쳤는데 나중에 다시 보니 1부터 n까지 순서대..

문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다. 모든 왼쪽 대괄호("[")는 오른쪽 대 www.acmicpc.net 풀이 문제 설명이 구체적이지 않아 어디가 문제인지 모르겠는 문제. '균형'이란 것의 정의가 모호해서 나의 경우 처음에는 ( )..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net 풀이 벡터도 써봤다, 동적 배열도 써봤다, 50짜리 고정 배열도 써봤다, 아예 스택 구조를 안 쓰는 등 삽질을 많이 했다. 문제를 보고..

문제 https://www.acmicpc.net/problem/10773 불러오는 중입니다... 풀이 1. Linked List Stack 구조를 사용하는 방법 #include "cstdio" class NODE { friend class Stack; private: int m_data; NODE* prev, *next; public: NODE(); NODE(int); }; NODE::NODE() : m_data(0), prev(NULL), next(NULL) {} NODE::NODE(int data) : m_data(data), prev(NULL), next(NULL) {} class Stack { friend NODE; private: int count; NODE* head, *tail; public..

문제 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 풀이 풀고 나서 다른 사람 풀이를 봤더니 대체로 그냥 통짜 배열로 처리해서 허탈했던 문제. 난 왜 Linked List까지 쓰면서 구현했는가.. 사실 C코드이기 때문에 구조체를 써서 만들면 되지만 클래스 형태로 짜면 어떻게 만들어야 할까 궁금해서 이렇게 해봤다. 문제에서 요구하는 push X, pop, top, size, empty 명령어..

문제 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 처음 실행했을 때 또는 처음 입력하는 단어의 경우 이상하게 세는 경우가 있었지만, 코드만 봐선 이상이 없어 보여 대수롭지 않게 넘겼다. 이게 굉장히 잘못된 판단이었다. 원래는 scanf(..