gmlwlsl 님의 블로그

문제 풀이노드 간의 최소 간선 갯수를 구해야 하므로BFS 알고리즘을 이용한다. 문제를 풀면서 헷갈렸던 부분은 c++에서 그래프를 만들 때아래의 두 가지 방식이 있다. 1. graph[x][y] = 1; - 인접 행렬 (Adjacency Matrix)- 1이면 x에서 y로 간선이 있다는 의미- 간선 존재 여부 탐색에는 빠른데, 정점 수가 많으면 메모리가 심각하게 낭비됨- 행렬에 정점 연결 여부가 모두 정리되어있기 때문에, 두 정점을 모두 연결하는 간선을 조회할 때 빠르다. O(1) 2. graph[x].push_back(y);- 인접 리스트 (Adjacency List)- graph[x]는 정점 x와 연결된 모든 정점을 담은 리스트- 필요한 간선만 저장해서 메모리 효율이 좋음 답안#include #incl..

문제 풀이그리디 알고리즘, multiset 자료구조를 사용한다. 세종이의 돈과 가장 가깝고 큰돈을 줘야 하기 때문에 multiset 알고리즘을 사용한다.multiset 자료구조는 중복을 허용하고 자동 정렬되는 자료구조이다.내부적으로는 이진 탐색 트리로 되어있기 때문에, O(log N)으로 삽입/탐색/삭제가 가능하다. [중요 함수]lower_bound(x): x 이상인 첫 번째 값의 iterator를 반환해 줌iterator는 컨테이너 내부 요소에 접근하기 위한 포인터처럼 동작하는 객체다.  답안#include #include #include using namespace std;int main() { cin.tie(NULL); ios::sync_with_stdio(false); int n;..

문제 풀이LCS은 Longest Common Subsequence, 최장 공통 부분 수열이다.주어진 두 수열 중에서 모두의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이다. 해당 문제 유형은 DP(Dynamic Programming)으로 해결할 수 있었다. 2차원 배열을 이용해서 i열과 j열에 문자열을 매칭한다. ex) "ACCDE" -> 배열[0] = "A", 배열[1] = "C", 배열[2] = "C", 배열[3] = "D", 배열[4] = "E" 점화식은 아래와 같다. if (text1[i] == text2[i]) { lcs[i][j] = lcs[i-1][j-1] + 1 // 현재 기준 왼쪽 대각선 위의 lcs 길이에 + 1} else { lcs[i][j] = max(lcs[i-1][j], ..

문제 풀이입력 값이 1인 경우: 1 (최소 횟수 0번)입력 값이 2인 경우: 2 > 1 (최소 횟수 1번)입력 값이 3인 경우: 3 > 1 (최소 횟수 1번)입력 값이 4인 경우: 4 > 2 > 1 or 4 > 3 > 1 (최소 횟수 2번)입력 값이 5인 경우: 5 > 4 > 2 > 1 (최소 횟수 3번)입력 값이 6인 경우: 6 > 3 > 1 or 6 > 2 > 1 or 6 > 5 > 4 > 2 > 1 (최소 횟수 2번)입력 값이 7인 경우: 7 > 6 > 3 > 1 or 7 > 6 > 2 > 1 or 7 > 6 > 5 > 4 > 2 > 1 (최소 횟수 3번)입력 값이 8인 경우: 8 > 4 > 2 > 1 or 8 > 7 > ~~ (최소 횟수 3번) => 입력값-1의 횟수 + 1 or 입력 값이 2나 ..

문제 풀이아래 그림처럼 생각해서 재귀로 풀면 된다.n=3, r=7, c=7인 경우의 그림이다. (빨간 체크가 내가 가야 하는 곳)재귀 함수를 z(int n, int r, int c)라고 가정,재귀가 돌아가는 과정을 식으로 나타내면 아래와 같다. z(3, 7, 7)= 3*4*4 + z(2, 3, 3)= 48 + (3*2*2 + z(1, 1, 1))= 48 + (12 + (3*1*1 + z(0, 0, 0)))= 48 + 12 + 3= 63 답안#include using namespace std;int z(int n, int r, int c) { if (n == 0) { return 0; } int half = 1 = half) { return half*half + z..

문제 풀이탑의 인덱스와 높이를 함께 관리하기 위해서 stack >를 사용한다. + 모노톤 스택새로 입력받은 탑의 높이가 이전에 있던 탑의 높이보다 높으면 이전에 있던 거 pop -> 이전 탑 높이가 더 높을 때까지 반복반복문 끝나고 남은 탑은 어차피 맨 앞이 가장 높은 탑임. 따라서 top.top().first로 해당 탑의 인덱스 출력 답안#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; stack> top; for (int i = 0; i > height; wh..

문제 풀이문제에서 오큰수란, 예를 들어 [3, 5, 2, 7]이면 3 오른쪽에 5, 2, 7 중에서, 3보다 큰 5, 7 중에서, 왼쪽에 있는 5를 뜻하는 것이다. A 배열에 숫자 배열 입력받기, result 배열에는 오큰수 배열 저장, st 스택에는 인덱스 저장 1. for문과 while문을 이용해서 result와 st를 채움1-1. st가 비어있으면(오큰수가 아무것도 없으면) 그냥 첫 번째 숫자의 인덱스를 추가1-2. st가 비어있지 않고 && 현재 st top에 저장된 오큰수     - A[st.top()]  2. st에 남아있는 인덱스는 오큰수가 존재하지 않는 인덱스임. 따라서 result[st.top()]에 -1을 저장해 줌 답안#include #include #include using name..

문제 풀이줄 선 사람을 스택으로 정리할 것임. 그런데 키가 같은 (중복된) 사람이 있을 수 있으니까 pair를 사용해서 키와 중복되는 수를 저장해야 함사람의 키도 int형의 범위를 초과하기 때문에 long long을 사용해야 함총 존재하는 쌍 변수는 count라고 하였음 1. 아무도 줄을 서지 않은 경우- 그냥 people stack에 추가하면 됨- 이때 해당 키의 사람은 처음 카운트 되는 거니까 second 값은 1로 하면 됨 2. 줄이 있고, 맨 뒷 사람의 키 - 방금 줄 선 사람보다 키가 큰 사람이 나올 때까지 stack을 pop 하면서 찾으면 됨- 팝되는 사람들의 중복되는 수를 count에 추가하면서 while문 돌면 됨 3. 줄이 있고, 맨 뒷사람의 키 == 방금 줄 선 사람의 키- 맨 뒷 사람..

문제 풀이Deque, Slidiing Window를 사용  슬라이딩 윈도우 기능을 할 deque를 만들고, 입력받은 문자열 배열 내에서 for문을 통해 deque를 돌림위 문제는 슬라이딩 윈도우 내에서 최솟값을 구하는 문제이므로deque에서 현재 문자열 배열에 있는 값보다 큰 값을 보고 있으면 걔는 deque에서 빼면 됨그 과정에서 슬라이딩 윈도우 내의 존재하는 최솟값을 저장하는 vector에 최솟값을 저장함답안#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, L; cin >> N >> L; vector A(N); for (i..

문제 풀이벌집의 가운데부터 바깥까지 한줄씩 숫자 범위를 분류1 / 2~7 / 8~19 / 20 ~37 / ...각 범위의 끝 숫자는 6, 12, 18 즉 6의 배수로 증가함을 알 수 있음따라서 입력받은 숫자가 각 범위의 끝 숫자보다 작거나 같은지 (==해당 범위 내에 있는지) 확인 후count를 늘려가는 방식을 적용 답안#define _CRT_SECURE_NO_WARNINGS#include int main() { int n; int e = 1; int add = 6; int cnt = 1; scanf("%d", &n); while (1) { if (n