Doby's Lab

(이번 문제는 첫 골드 문제이다 (울컥)) 이번 문제의 유형이 'Monotonic Stack'이라고 하는데 이 유형의 문제를 처음 접한 것은 아니다. 예전 SCPC 준비를 할 때, 같이 준비하던 친구들과 영어 문제를 풀면서 접했었던 경험이 있다. 많은 시간을 썼었지만 풀리지 않았었고, 해답을 찾다가 Monotonic Stack에 대한 자료가 많이 없어서 나중에 또 이런 유형을 만나게 되면 정리를 해둬야겠다고 생각했었다. (해당 영어문제 링크) https://www.acmicpc.net/problem/6105 6105번: Look Up Farmer John's N (1 a; arr.push_back(a); } vector answer(n, 0); stack s; for (int i = arr.size() ..

(추가 내용 2021.11.15) https://draw-code-boy.tistory.com/96 [알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째! https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램 draw-code-boy.tistory.com 비슷한 문제가 나와서 정리해두었다. 백트래킹의 코드 구조를 익히면서 [N과 M 시리즈]를 풀고 있었다. 이번 문제에서 막히게 되었는데 해당 문제에서 이런 걸 요구했기 때문이다. 'N이 4이고, M이 2일 때, 9 7 9 1의 수들로 부분 수..

(N과 M (1) 문제를 중심으로 설명하려 했으나 Backtracking과 DFS의 차이를 설명하기 위해 N과 M (2) 문제가 적합하다는 생각이 들었다.) 개념 백트래킹은 DFS를 응용하여 나온 알고리즘 같았다. DFS에 대해서는 그래프 이론에 대한 문제를 풀기 시작할 때 제대로 다시 다루겠지만 간단히 정리하면 어떠한 그래프가 주어졌을 때, 시작 노드로부터 연결돼있는 모든 노드를 탐색해나가는 완전 탐색 알고리즘이다. 또한 노드끼리 연결되었는가도 따져보아야 하는데 다음에 다시 다루겠다. 이러한 그래프가 있다고 가정하자. 시작 노드가 1일 때, DFS는 모든 노드들을 다음과 같이 탐색해나간다. 백트래킹은 DFS에 어떠한 조건을 주어서 (조건이라고 해서 무조건 if문을 사용하지 않는다.) 원하는 부분만 탐색..

이 문제는 논리를 짤 수 없어서 다른 사람들의 답을 참고했다. 그래도 이분 탐색을 사용해서 풀어보고자 했던 마음이 있었기에 논리만 참고했다. 논리는 이랬다. 어떠한 거리가 주어지면 '그 거리와 같거나 그 이상의 거리를 가질 때'의 공유기가 설치될 수 있는 개수가 주어진 C보다 많으면 거리를 더 늘려서 탐색해나가고, 그와 반대로 어떠한 거리가 공유기가 설치될 수 있는 개수보다 작으면 거리를 좁혀서 탐색해나가는 논리였다. 논리를 알기 전까지는 어디에 포커스를 두어야 할지도 몰랐다. 구하는 것이 거리이기에 거리에 초점을 두어야 했을까 코드 탐색 내가 짠 코드를 토대로 나름의 해설을 해두어야 할 거 같다. #include #include #include using namespace std; int main() ..

이분 탐색 개념을 알고서도 이분 탐색 문제를 보면 '이게 왜 이분 탐색을 써야 되지?'라는 생각에 빠졌었다. 아무래도 '알고리즘 분류'에 들어가서 이분 탐색을 찾아 풀다 보니 '일단 이분 탐색을 써야 해'하는 전제를 두고서 들어갔기 때문에 쉽사리 문제에 접근할 수 없었다. 이분 탐색을 전제에 두지 않았다면 더 쉽게 접근할 수 있었을까 그랬다면 접근 방법은 이랬을 거다. 제일 큰 나무 위에서 한 칸씩 줄여가며 자른 나무 개수 count count가 >= M이 되는 시점에서 자른 높이 측정 생각보다 쉬운 접근이다. 이분 탐색이 필요했던 이유 문제를 보면 한 나무가 가질 수 있는 최대 높이가 1,000,000,000(10억)이라고 한다. 만약에 모든 나무를 끝까지 다 베어야 한다면 count는 10억 이상이 ..

이 문제를 보았을 때, 너무 쉬운 문제인데 CLASS 2에 왜 있을까라는 생각을 했다. 어떤 수 N이 있다고 가정하자. 'N이 카드 패에 있는지 없는지는 그냥 for문 돌려서 확인하면 끝나는 거 아닐까?'라고 생각할 수 있었다. 하지만, 문제에서의 N과 M의 주어진 범위를 보고, 시간제한을 보면 떠올랐던 생각으로 풀었을 때 '시간 초과'라는 오류를 초래할 수 있다. 왜냐하면 N의 범위가 1~500,000 M의 범위가 1~500,000이면 for문을 돌렸을 때 시간 복잡도가 O(N*M) 일 것이고, 최댓값이 250,000,000,000 즉, 2500억을 넘어가기 때문이다. 시간제한은 1초로 약 1억번 안에 끝내라는 암묵적인 조건을 주기 때문에 for문으로는 처리할 수가 없었다. 해결법 어떠한 배열 안에 특..

알고리즘 문제에서 소수에 관한 문제를 보면 1차적으로 에라토스테네스의 체를 떠올리게 된다. 허나, 에라토스테네스의 체를 잘못 알고 있었기 때문에 블로그의 정리를 해두려한다. (이름 외우는게 젤 어려워.. 아리토스테네스 아레스토테네스...) 기존에 잘못 알고있었던 건 어떤 정수 N이 있을 때 2부터 N까지 소수를 구하려면 2부터 N의 제곱근까지 범위를 주면된다. 이까지만 알고 범위 안에서 뭘 하는지 생각하지 않고 있었다. 물론 소수를 구할 때 N의 제곱근까지만 범위를 준다는게 시간을 조금이라도 줄여주는 것은 존재하는 내용이다. 에라토스테네스의 체 2~정수 N까지의 소수를 구한다고 했을 때 에라토스테네스의 체를 몰랐다면 2~N 사이의 값 i를 i 이하 수들로 나누어보며 소수인지 아닌지 판별했을 것이다. 이런..

다음 문제를 풀 때 부호가 나올 수 있는 경우는 구현을 했지만 "NO"가 출력되어야 하는 부분을 처리하지 못했다. 내가 짰던 코드는 다음과 같다. #include #include #include using namespace std; int main() { int n; cin >> n; stack idx; vector sample; vector chart; for (int i = 0; i > a; sample.push_back(a); } int max = sample[0]; for (int i = 1; i max) { while (1) { if (idx.top() == sample[i]) { popNum.push_back(idx.top()); idx.pop(); ..