해바

문제 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://marell.tistory.com/1 입력버퍼 비우기 [Visual Studio 2015버전] 숫자를 입력한 뒤 Enter키를 누르게 되면, 다음에 입력받는 단계를 건너뛰는 경우가 발생한다. #include"stdio.h" #pragma warning(disable : 4996) void main(){ int num1, n.. marell.tistory.com 변수에 값이 저장되기 전에 입력 버퍼에 값이 씌여짐.

문제 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..

결론부터 말하자면 C의 입출력 함수들은 C++의 입출력 함수들보다 빠르다. getchar > scanf > std::cin 백준 온라인 저지의 속도 비교 자료 입력속도 비교 출력속도 비교 중간에 C++이 끼어있는 것에 대해선 여기를 읽어보면 되고, 더 자세한 것은 sync with stdio 로 구글링하면 나온다. 이걸 적용한 것이든 하지 않은 것이든 C++ 입출력 함수의 문제는 여기에서 설명하듯, C의 I/O method보다 느린 속도 멀티쓰레드 사용 불가 scanf, printf 등 C 입출력 함수와의 혼용시 문제 발생 가능성 엄밀히 따지면 일종의 편법인 방식 등이 있다. 그러니까 불편하고 cin >> 하고 입력하는 것에 비해 %d, %c, %lf ... 까다롭게 느껴지더라도 C 스타일에 적응하자. ..