꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/5430 생각보다 구현하기 까다로운 문제였습니다.'R' 명령어가 올 때 직접 뒤집지 않고 boolean 변수 left를 통해 해당 덱이 뒤집어져있는지의 여부를 확인합니다.뒤집어져있을 때 'D' 명령어가 들어오면 pop_back, 뒤집어져있지 않을 때 'D' 명령어가 들어오면 pop_front를 해줍니다.물론, 덱이 비어있을 때는 "error"를 출력해줍니다. #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int test_case; cin >> test_case; for (..

문제 링크입니다: https://www.acmicpc.net/problem/10866 STL 덱 활용을 연습하는 문제였습니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; deque dq; for (int i = 0; i > temp; int num; if (temp == "push_back") { cin >> num; dq.push_back(num); } else if (temp == "push_front") { cin >> num; dq.push_front(num); } e..

문제 링크입니다: https://www.acmicpc.net/problem/15368 다단계의 현실을 간접적으로 보여주는 재미있는 문제였습니다.DFS(Depth First Search) 알고리즘을 이용하여 푸는 문제였습니다.처음에는 문제를 그대로 구현하여 DFS를 20만번이나 하는 어마무시한 코드를 작성해서 메모리 초과가 발생했습니다.이후에는 세진님(http://sejinik.tistory.com/96#comment12977181) 코드를 참고하여 풀었습니다. 알고리즘은 아래와 같습니다.1. 양방향 그래프처럼 입력받고 i의 상사가 누군지 표시합니다.2. DFS를 이용하여 트리를 형성하고 미리 num의 자식의 수를 employee 배열에 표시합니다.3. 이후에는 또 다시 DFS를 이용하여 급여를 계산합니다..

문제 링크입니다: https://www.acmicpc.net/problem/1188 평론가들은 일인당 소시지 N/M 개의 소시지를 가져갑니다.즉, 소시지를 N개 이어붙일 경우 (M - 1)번의 칼질이 필요합니다.하지만, N이 M으로 나누어 떨어질 경우에는 칼질이 전혀 필요없습니다.따라서, M - GCD(N, M)번의 칼질이 필요합니다.(최악의 경우 GCD(N, M) = 1이기 때문에 (M - 1)번의 칼질) #include using namespace std; //최대 공약수 int GCD(int a, int b) { if (a%b == 0) return b; return GCD(b, a%b); } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); ..

문제 링크입니다: https://www.acmicpc.net/problem/4179 백준 5427번 불(http://jaimemin.tistory.com/657)과 동일한 문제였습니다. #include #include #include #include using namespace std; const int MAX = 1000; typedef struct { int y, x; }Dir; Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int R, C; string maze[MAX]; bool visited[MAX][MAX]; pair start; vector fire; int BFS(void) { queue q; q.push(start); queue flam..

문제 링크입니다: https://www.acmicpc.net/problem/2905 monotone priority queue(https://en.wikipedia.org/wiki/Monotone_priority_queue)을 이용해 푸는 문제였습니다.간단히 설명하자면, 우선순위 큐를 이용하여 최소힙을 구현하는데 최소힙 내 요소들이 감소하지 않고 증가해야한다는 것입니다. 그래도 설명이 모호하다면 슬라이딩 윈도우 기법인데 슬라이드 내 최소값을 찾는 문제라고 생각하면 될 것 같습니다.코드는 http://codersbrunch.blogspot.com/2016/02/2905.html를 참고했습니다. 알고리즘은 아래와 같습니다.1. 우선 높이를 다 입력받고 높이의 누적합을 저장합니다.2. 인덱스와 높이를 저장하는..

문제 링크입니다: https://www.acmicpc.net/problem/3015 시간복잡도를 O(N)으로 줄여야했기 때문에 어려웠던 문제였습니다. 알고리즘은 아래와 같습니다. 1. 을 저장하는 스택을 선언합니다. 2. 핵심은 스택 제일 아래 저장되어 있는 키부터 top까지 내림차순을 유지하는 것입니다. -> 따라서, 현재 키가 스택의 top보다 클 경우 스택의 top이 현재 키와 같거나 클 때까지 pop을 해줍니다. 3. 스택이 비어 있다면 스택에 push 해줍니다. 4. 스택이 비어 있지 않을 경우 i) 현재 키와 스택의 top이 같을 경우 pop을 해준 뒤 second(연속 몇 명)를 수정해줍니다. -> 이 때, 스택이 비어있지 않다면 스택 내 제일 큰 사람과 쌍을 이루므로 결과에 1 증가 ii)..

문제 링크입니다: https://www.acmicpc.net/problem/2841 스택 배열을 이용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 줄이 1 ~ 6까지 6개이므로 크기가 7인 int형 스택을 선언합니다.2. N번 동안 줄과 프랫을 입력받습니다.i) 해당 줄의 스택이 비어있다면 무조건 추가합니다.ii) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫이 기존에 입력받은 프랫보다 높을 경우 추가해줍니다.iii) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫과 기존에 입력받은 프랫과 동일하다면 다음 줄과 프랫을 입력받습니다.iv) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫이 기존에 입력받은 프랫보다 낮다면 현재 입력 받은 프랫이 스택의 top보다 높거나 같을 때까..

문제 링크입니다: https://www.acmicpc.net/problem/1935 자료구조 시간에 후위표기식을 이용한 계산기를 만들어 봤기 때문에 쉽게 접근할 수 있었습니다. 알고리즘은 아래와 같습니다.1. 해당 인덱스가 연산자일 경우 스택에서 숫자 두 개를 꺼냅니다.-> 두 번째로 꺼낸 숫자가 사실 먼저 나온 숫자이기 때문에 연산을 두 번째 숫자를 기준으로 합니다.2. 해당 인덱스가 피연산자일 경우 스택에 추가합니다.3. 반복문을 통해 1 혹은 2를 수행하면 결과는 스택의 top에 저장되어있습니다. 따라서 스택의 top을 출력해주면 됩니다. #include #include #include #include using namespace std; const int MAX = 26; int alphabet[..

문제 링크입니다: https://www.acmicpc.net/problem/1918 자료구조 시간에 후위표기식을 이미 배워놓은 상태이기 때문에 쉽게 접근할 수 있었습니다. 알고리즘은 아래와 같습니다.1. 피연산자 즉, 대문자 알파벳은 무조건 결과 문자열에 즉시 추가해줍니다.2. 연산자일 경우는 아래와 같이 3가지 경우가 있습니다.i) 괄호 안에 있는 연산을 제일 먼저 실행하기 때문에 현재 인덱스에 있는 연산자가 '('라면 바로 스택에 넣어줍니다.ii) '+', '-', '*', '/' 연산자가 등장할 경우 스택에 현재 연산자보다 우선순위가 높거나 같은 기호들은 전부 결과 문자열에 추가해줍니다.a) '*'와 '/'가 '+'와 '-'보다 우선순위가 높습니다.b) 따라서, '*'와 '/'가 등장할 경우, 스택..