algorithm (34) 썸네일형 리스트형 백준 6198번 옥상 정원 꾸미기 - 모노톤 스택 https://www.acmicpc.net/problem/6198 https://www.acmicpc.net/problem/17298의 하위호환 아이디어:1. 모노톤 스택 사용스택에는 2가지 문제 유형이 있는데, 첫번째는 괄호 지우는 것처럼 자연스러운 패턴을 찾는 것2번째는 6198번과 모노톤 스택처럼 스택 내부의 정렬(?)이다.https://www.youtube.com/watch?v=Z4R582bn7B82. 목표는 빌딩을 볼 수 있는 횟수의 총합3. 스택의 입력은 빌딩의 높이인데, 이걸 내림차순으로 정렬해서 더 낮은 값이 있으면 pop하는 로직이 필요하다.4. 첫 빌딩 높이는 그냥 push5. 다음 들어오는 빌딩부터만약, 스택 top이 입력 빌딩보다 작으면 pop하고 크거나 같으면 정답에 더한 뒤, 스.. 백준 1874번 스택 수열 https://www.acmicpc.net/problem/1874 아이디어:1. 스택 사용2. 입력한 수열과 현재 자연수 (1~n)을 비교3. 결과를 배열에 저장해서 마지막에 출력4. 현재 수열 값이 현재 자연수보다 크거나 같으면 값이 같아질 때 까지 계속 push하고 마지막에만 pop(ex. 백준 예제 입력의 경우, 수열이 4로 시작한다. 자연수는 1이므로, 4에 도달할 때 까지 계속 push후, 마지막에 pop해서 4를 결과 배열에 저장)5. 현재 수열 값이 현재 자연수보다 작을 때, pop해서 나온 값이 수열 값과 다르면 후입선출의 원리에 의해 수열 만들기가 불가능하다. > NO 출력, flag를 false로 만들고 종료6. 불가능하지 않다면 pop만 실행(ex. 백준 예제 입력의 경우에서 4를 p.. 백준 11003번 최솟값 찾기 https://www.acmicpc.net/problem/11003 아이디어:1. 슬라이딩 윈도우 사용2. 범위가 i - L + 1 부터 1까지 => 슬라이딩 윈도우의 사이즈가 L3. 덱을 사용해서 덱 내부 정렬하듯이 구현4. (값, 인덱스)로 구성된 Node 사용5. 새 노드가 추가될 때, 덱에서 새 노드의 숫자보다 큰 숫자의 노드는 전부 삭제6. 새 값 추가7. 덱 안에 있는 노드의 인덱스 범위가 슬라이딩 윈도우의 크기를 벗어나면 (ex. L = 4인데, 덱에 있는 인덱스는 2~6인 경우) 덱의 앞에서부터 노드 제거 // 11003#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); c.. 백준 12891번 DNA 비밀번호 https://www.acmicpc.net/problem/12891 아이디어:1. 슬라이딩 윈도우 사용2. 현재 부분문자열의 검사 결과를 저장하고 윈도우가 이동할 때마다 검사 결과를 업데이트 // 12891#include using namespace std;int S, P, checkAnswer, answer = 0;string str;int myArr[4] = { 0 };int checkArr[4] = { 0 };void Add(char c);void Remove(char c);void check();int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> S >> P; cin >> str; for (int i = 0.. 백준 1253번 좋다 https://www.acmicpc.net/problem/1253 아이디어:1. vector, 정렬, 투 포인터 사용2. 정수 범위이므로 음수 고려 > 끝 인덱스가 N - 1에서 시작3. 자기자신을 더할 때는 제외한다. // 1253#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long N, answer = 0; cin >> N; vector A(N, 0); long start = 0; long end = 0; for (int i = 0; i > A[i]; } sort(A.begin(), A.end()); for (int i = 0; i.. 이전 1 2 3 4 ··· 7 다음
