꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1725 Algospot FENCE(http://jaimemin.tistory.com/567)와 동일한 문제였습니다. #include #include #include #include using namespace std; int N; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; vector height(N); for (int i = 0; i > height[i]; //제일 끝 울타리 높이가 i번째 울타리 높이보다 작아야 범위가 설정됨 height.push_back(0); stack remaining; int result = 0;..

문제 링크입니다: https://www.acmicpc.net/problem/3986 문제가 조금 난해하지만 결국 알파벳끼리 쌍을 이룰 때 사이에 다른 알파벳이 없을 경우가 좋은 단어입니다. 알고리즘은 아래와 같습니다.1. 스택이 비어 있지 않은 상태에서 스택의 top과 현재 알파벳이 같을 경우 한 쌍을 이루므로 스택에서 pop합니다.2. 1번이 아닌 경우에는 쌍을 이루지 않기 때문에 스택에 push합니다.3. 해당 문자열을 전부 순회한 뒤 스택이 비어있다면 좋은 단어, 비어 있지 않다면 좋은 단어가 아닙니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int..

문제 링크입니다: https://www.acmicpc.net/problem/12931 B 배열을 전부 0인 배열로 바꾼다는 생각으로 거꾸로 접근하면 수월하게 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다.1. 배열의 모든 요소를 살피면서 모두 2로 나누어 떨어지는지 확인합니다.i) 모두 2로 나누어 떨어진다면 우선 전부 2로 나눕니다.ii) 하나라도 2로 나누어 떨어지지 않는다면 해당 요소를 1 감소시킵니다.2. 전부 0이라면 A 배열이 된 것이기 떄문에 0을 반환합니다.3. 1번과 2번을 반복문 내에서 처리하여 총 연산 횟수를 구합니다. 위와 같이 그리디하게 접근한 이유는 1씩 더하는 것보다 2를 곱하는 것이 더 빠르다는 것이 자명하기 때문입니다. #include #include using na..

문제 링크입니다: https://www.acmicpc.net/problem/5397 스택을 두개 사용하여 푸는 흥미로운 문제였습니다. 알고리즘은 아래와 같습니다.1. 결과를 저장하는 result와 화살표 입력시 필요한 temp 스택을 각각 정의합니다.2. 왼쪽 화살표를 입력하는 경우 result의 top에 있는 문자를 temp에 push하고 result에서 pop합니다.3. 오른쪽 화살표를 입력하는 경우 temp의 top에 있는 문자를 result에 push하고 temp에서 pop합니다.4. 백스페이스를 하는 경우 단순히 result에서 한번 pop합니다.5. 2, 3, 4번 외에는 단순히 result에 push 합니다.6. 반복문을 탈출했을 때, temp에 여전히 문자들이 남아있을 수 있습니다. 따라서..

문제 링크입니다: https://www.acmicpc.net/problem/9935 문자열 처리가 메인이였던 스택 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 입력받은 문자열을 순회하면서 일단 결과 문자열에 추가합니다.2. 폭탄 문자열의 마지막 문자를 발견하면 결과 문자열 끝에 폭탄이 있는지 확인하고 폭탄이 있다면 인덱스를 폭탄 문자열 길이만큼 빼서 폭탄을 제거합니다.3. 2번을 마친 후 인덱스가 0이라면 폭탄문자열로만 구성된 문자열이였으므로 "FRULA"를 출력하고 인덱스가 1 이상이라면 해당 문자열을 출력합니다. #include #include using namespace std; const int MAX = 1000000 + 1; string s, bomb; char result[MAX]..

문제 링크입니다: https://www.acmicpc.net/problem/2493 분류는 스택으로 되어있지만 우선순위 큐를 이용하여 푼 문제였습니다. 알고리즘은 아래와 같습니다.1. 오른쪽에서부터 왼쪽으로 레이저를 발사하기 때문에 오른쪽에서부터 반복문을 시작합니다.2. 우선 minHeap 형태를 띄는 우선순위 큐를 정의하고 N번째 탑의 높이와 인덱스를 넣습니다.3. (N - 1)번째 탑부터 현재 우선순위 큐의 top(cur)에 저장되어있는 탑의 높이와 비교합니다.i) 현재 인덱스에 위치한 탑의 높이가 cur의 높이보다 크거나 같다면 레이저 신호를 수신했으므로 결과 배열 cur번째 탑 인덱스에 현재 인덱스를 저장하고 3번을 반복합니다.ii) 현재 인덱스에 위치한 탑의 높이가 cur의 높이보다 작다면 우선..

문제 링크입니다: https://www.acmicpc.net/problem/11383 string을 이용해 간단히 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 10; string str[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; for (int i = 0; i > temp; for (int j = 0; j < temp.length(); j++) for (int k = 0; k < 2; k++) str[i] += temp[j]; } bool eyfa = tr..

문제 링크입니다: https://www.acmicpc.net/problem/2504 생각보다 구현하기 힘들었던 스택 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 왼쪽 괄호가 나올 때마다 스택에 넣습니다.i) 여기서 핵심은 temp = 1로 선언하여 소괄호일 때는 2를 곱해주고 중괄호일 때는 3을 곱해주는 점입니다.ii) 처음에 접근했을 때는 안에 내용물이 있을 때와 없을 때를 구분했다가 코드만 길어지고 실수를 하여 WA가 여러번 발생했습니다.2. 시간 단축을 위해 불가능한 조합이 나올 경우 미리 반복문에서 탈출합니다.i) 마지막에 impossible 혹은 스택이 비지 않았을 경우에 0을 출력하도록 했는데 간단한 예시를 들겠습니다.(()()() 와 같은 경우 제가 정의한 불가능한 경우를 피해갑니..

문제 링크입니다: https://www.acmicpc.net/problem/1874 스택과 큐를 적절히 이용하여 풀어야했던 문제였습니다. 알고리즘은 아래와 같습니다.1. 큐를 선언하여 원하는 순서를 선언한 큐에 넣습니다.2. 큐의 front에 있는 숫자에 대해 먼저 처리해줍니다.i) num이 해당 숫자가 될 때까지 +ii) 해당 숫자에 대해서 처리했으므로 큐와 스택 pop을 진행하고 -3. 이후에는 반복문 내에서 나머지 숫자들을 아래와 같은 세가지 경우에 대해 처리해줍니다.i) 스택이 비었거나 현재 원하는 숫자 > 스택의 top 일 경우ii) 현재 원하는 숫자 == 스택의 topiii) 현재 원하는 숫자 < 스택의 top4. 3번을 진행한 후 불가능한 경우이면 "NO"를 출력하고 가능한 경우이면 결과 문..

문제 링크입니다: https://www.acmicpc.net/problem/5724 간단한 수학 문제였습니다.cache[N] = cache[N-1] + N * N (N >= 1)과 같이 간단한 점화식을 통해 풀 수 있기 때문에 어렵지 않게 풀 수 있는 문제였습니다. #include using namespace std; const int MAX = 100 + 1; long long cache[MAX]; void preCalculate(void) { cache[1] = 1; for (int i = 2; i > N; if (N == 0) break; cout