0. Stack (스택)이란? 스택(Stack)은 후입선출(Last In First Out)의 형태를 갖고있는 자료구조이다. 나중에 들어간 것이 먼저 나온다는 의미인데 큐(Queue)의 선입선출과 반대라고 보면 된다. 그래프의 깊이 우선 탐색(DFS)에서 사용되고, 재귀적(Recursion) 함수를 호출 할 때도 사용된다. 기본 함수로 push, pop, empty, top, swap 등이 대표적으로 자주 쓰인다. 1. 기본 사용법 1.1 헤더 스택 STL은 헤더를 통해 stack을 include하여 사용할 수 있다. #include stack stk1;// int형 스택 stack stk2;// char형 스택 1.2 멤버 함수 push(data) : stack에 data를 추가한다. pop() : s..
- 문제 설명 - 문제 풀이 DFS를 사용해야 하는 문제이다. 그러나 단순히 DFS만 사용해서 풀면 탐색의 양이 무수히 많아지기 때문에 시간초과가 발생한다. 때문에 DFS + DP 메모제이션을 추가로 활용해줘야 하는 문제이다. 우선 상하좌우를 검색할때 현재 노드보다 값이 작은 곳만 향할 수 있어야 하기 때문에 배열의 크기를 arr[502][502]로 해주고, 최대값이 10000이므로 10001로 초기화 해주었다. 예제로 예시를 든다면 아래 표와 같이 나타낼 수 있다. 10001 10001 10001 10001 10001 10001 10001 10001 50 45 37 32 30 10001 10001 35 50 40 20 25 10001 10001 30 30 25 17 28 10001 10001 27 24..
우선순위 큐를 사용해야 하는 문제가 나올 때 사용법을 자주 검색해왔어서 개인 기록 겸 공부를 위해 정리해 보았다. 특히나 구조체나 클래스의 객체 타입을 우선순위 큐에 저장하거나, 비교 함수를 재정의, 연산자 오버 로딩도 알아보려고 한다. 0. Priority_queue(우선순위 큐) 란? 기본적으로 큐(queue)는 선입선출 FIFO(First In First Out)을 뜻한다. 때문에 우선순위 큐는 일반적인 큐와 비슷한 연산을 갖고있지만 내부 구조는 완전히 다르다. 선입선출인 큐는 pop을 하면 가장 먼저 들어왔던 원소를 반환하지만 우선순위 큐에서는 제일 우선순위가 높은 원소를 반환한다. 우선순위 큐는 들어간 순서에 상관없에 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐의 속성 모든 항목에는 우선..
- 문제 설명 - 문제 풀이 N의 수가 2 > N >> C; for (int i = 0; i > arr[i]; sort(arr, arr + N); s = 1; // 최소 거리 e = arr[N - 1] - arr[0]; // 최대 거리 while (s = mid) { router++; // mid만큼 인접거리가 늘어나면 공유기 설치 spot = arr[i]; // 인접거리 갱신을 위해 } } if (router >= C) { ans = max(ans, mid); s = mid + 1; } else { e = mid - 1; } } cout
- 문제 설명 - 문제 풀이 이분 탐색을 활용해야 하는 문제다. 예제 1과 같이 4개의 나무, 7의 길이 만큼 가져가야 할 때를 예로 들어보자. 이분 탐색을 위해 최소 잘라내는 수 1 = s, 최대 자를 수 있는 길이를 나무중에 제일 큰 나무(20 = e)라고 해보자. 그럼 그 중간값 mid = (s + e) / 2 를 기준으로 잘라낸다. 잘라낸 길이의 합이 가져가야 할 길이 7보다 크다면 mid값을 높여아 하기 때문에 s = mid + 1로 , ans = mid 갱신 (마지막은 항상 7만큼 혹은 그보다 더 가져가야 할 것이므로 정답을 mid로 갱신) 잘라낸 길이의 합이 가져가야 할 길이 7보다 작다면 mid값을 낮춰야 하기 때문에 e = mid - 1 s 가 e보다 커질때 까지 반복한 후 그 순간 mi..
- 문제 설명 - 문제 풀이 분할 정복을 이용한 거듭제곱을 활용해야 하는 문제이다. 우선 기본적으로 행렬의 곱셈을 어떻게 하는지를 이해하자면 그림과 같이 A행렬과 B행렬이 있다면 1.A행렬의 크기 (m x k) 2. B행렬의 크기 (k x n) 즉 A의 열의 갯수(k)와 B의 행의 갯수(k)가 같아야 곱셈이 성립된다. 그러면 새로운 행렬의 크기 (m x n)가 생기게 되고 이 행렬이 결과값이라고 할 수 있다. 즉 행렬의 거듭제곱은 하나의 행렬을 곱하는 것이므로 행과 열의 크기가 같아야 한다. 이 때 단순히 거듭제곱 수(B) 만큼 곱셈을 반복하게 되면, B의 범위는 1 > N >> B; for (int i = 0; i > A[..
- 문제 설명 - 문제 풀이 분할 정복을 활용해야하는 문제이다. 1. 검사하고자 하는 모든 영상(배열의 원소)들이 0만 있거나 1만 있으면 그 값만 출력하면 된다. 2. 만약 0과 1이 하나라도 섞여있으면 괄호 '(' 를 넣어 준 뒤 4개의 영역으로 재귀를 통해 분할하고, 그 뒤에 괄호 ')' 를 넣어준다. 3. 1, 2번을 반복한다. ex1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 예를 들면 이런 배열의 경우 1번 과정에서 끝이 나므로 답은 1이다. ex2 이런 경우 1번 과정이 안되므로 2번 과정을 거쳐야 하므로 괄..
- 문제 설명 - 문제 풀이 대표적인 그리디 알고리즘의 예시 문제이다. 그리디 알고리즘(greedy algorithm)이란 탐욕 알고리즘이라고도 불리는데 그리디 알고리즘의 모토는 "지금 당장 최적인 답" 을 이용하자는 것이다. 단 이 알고리즘은 지금 당장에 대해선 최적이지만 전체를 봤을 때 최적이라는 보장이 없다는게 특징이다. 이번 문제와 같은 거스름돈 문제는 무조건 최대한 가치가 높은 동전부터 나눠야하므로 그리디 알고리즘에 적합하다. 심지어 정렬이 된 상태로 주어지므로 역순으로 값이 나눠지는지를 보며 검사하기만 하면 된다. - 코드 #include using namespace std; int N, K, result = 0; int cnt[10]; int main() { ios_base::sync_wit..
- 문제 설명 - 문제 풀이 서브테스크가 있는 문제이다. 본래 문제에서는 문자열의 길이가 200,000자 이하, 질문의 수는 200,000개 이하를 조건으로 되어있는데 만약 문자열의 길이가 2,000개 이하, 질문의 수가 2,000개 이하에서만 만족하는 시간복잡도를 갖는다면 50점만 맞는다. 때문에 시간복잡도를 잘 고려해야 하는 문제이고 주의할 점은 O(n^2)을 넘지 않는 것이다. 문자열의 문자가 알파벳 소문자만 있다는 것을 이용해서 범위가 2차원이지만 arr[26][문자열의 길이]를 사용한다. 문자열의 길이만큼인 이유는 최악의 경우 문자열이 모두 같은 알파벳일 수도 있기 때문이다. 반복문을 통해 순차적으로 문자열의 문자들을 검색하고 아스키 코드 값을 이용해 arr[문자 - 97] 인 곳들을 누적합을 ..
- 문제 설명 - 문제 풀이 문제가 간단해 보이는듯 하면서도 배열을 적어보지 않으면 규칙을 찾기가 꽤 까다로웠다. 이 문제는 2차원 배열을 이용하여 풀어낼 수 있다. 이를 DP로 한다 하고 크기를 첫째 줄의 문자열의 길이 x 둘째 줄의 문자열의 길이로 해 선언해 준다. 이를 DP[i][j]라 했을때 0부터 i번째 문자열과 0부터 j번째 문자열 까지의 공통 부분 수열의 갯수를 넣어준다. 예제와 같이 ACAYKP, CAPCAK를 예로 든다면 아래 표와 같다. 행열의 첫째 줄은 0으로 한다고 가정하자. 형광칠 된 곳은 i번째 문자와 j번째 문자가 같은 지점이다. 표를 보면 규칙을 찾을 수 있는데 1. i번째 문자와 j번째 문자가 같다면 DP[i-1][j-1] + 1 을 한 것과 같다는 규칙 (대각선 위의 DP..
