민듀의 일상

class Queue{ constructor(){ this.items = {}; this.front = 0; this.rear = 0; } push(item){ this.items[this.rear] = item; this.rear++; } pop(){ const item = this.items[this.front]; delete this.items[this.front]; this.front++; return item; } front(){ return this.items[this.front]; } size(){ retur..

3열 N행의 가중치가 있는 배열 arr이 주어지고, 다음 규칙을 준수하면서 조약돌을 놓을 때 최대 가중치의 합을 반환하는 함수를 구현하라.각 열에 조약돌은 적어도 하나는 놓아야 한다.각 조약돌에 바로 인접한 위치(상하좌우)에 조약돌을 놓을 수 없다.이 문제에서 i열에 조약돌을 놓는 패턴은 총 4가지가 있을 수 있다.이러한 배치 패턴을 이용하면 아래와 같이 DP를 사용해서 문제를 풀 수 있다.#include #include using namespace std;// 조약돌 배치 패턴에 대해 최대 가중치를 계산하는 함수int solution(vector> arr) { // ❶ 입력 벡터의 열의 개수 int n = arr[0].size(); // ❷ dp 벡터 초기화 vector> dp(4..

최장 증가 부분 수열(longest increasing subsequence)를  LIS라고 한다.수열 1, 4, 2, 3, 1, 5, 7, 3이 있으면, LIS는 1, 2, 3, 5, 7로, 길이는 5이다. LIS의 이해는 아래 글을 참고했다.https://4legs-study.tistory.com/106 최장 증가 수열 (LIS, Longest Increasing Subsequence)최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는4legs-study.tistory.com 이를 구현하면 아래와 같다.#include #in..

최장 공통 부분 수열을 LCS(longest common subsequence)라고 부른다.최장 공통 부분 수열이란 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열을 의미한다.즉, ABCDEFGH와 ADDICTEF 두 개의 수열이 있다면,LCS 는 ADEF, 혹은 ACEF가 된다. (공통으로 찾을 수 있는 가장 긴 부분 수열의 길이는 4이다.) LCS를 구하는 점화식을 생각해보자. 나는 아래 글을 참고했다.https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8..

#include using namespace std;vector> solution(int n) { //❶ N*N 2차원 벡터를 선언하고 초깃값을 0으로 함 vector> snail_array(n, vector(n, 0)); int num = 1; // 행과 열의 시작과 끝 인덱스를 설정 int start_row = 0, end_row = n - 1; int start_col = 0, end_col = n - 1; //❷ 제일 외각부터 달팽이 수열 규칙대로 채움 while (start_row = start_col; --i) { snail_array[end_row][i] = num++; } --end..

#include using namespace std;vector> multiply(vector> matrix1, vector> matrix2) { vector> result(3, vector(3, 0)); for (int i = 0; i > transpose(vector> matrix) { vector> result(3, vector(3, 0)); for (int i = 0; i > solution(vector> matrix1, vector>matrix2) { vector> multiplied = multiply(matrix1, matrix2); vector> transposed = transpose(multiplied); return transposed;}

시계 방향으로 90도씩 n번 회전#include using namespace std;vector> rotate90(vector> arr) { int n = arr.size(); int m = arr[0].size(); vector> rotated(m, vector(n, 0)); for (int i = 0; i > solution(vector> arr, int n) { vector> rotatedArr = arr; for (int i = 0; i  반시계방향으로 90도씩 n번 회전#include using namespace std;vector> rotate90(vector> arr) { int n = arr.size(); int m = arr[0].size(); ..

#include #include #include using namespace std;const int INF = numeric_limits::max();vector solution(int num_vertices, vector> edges, int source) { vector>> graph(num_vertices); //❶ 간선정보를 활용해서 인접리스트를 생성 for (auto& edge : edges) { int from, to, weight; tie(from, to, weight) = edge; graph[from].emplace_back(to, weight); } //❷ 현재까지 구한 최소비용을 INF로 설정(시작노드는 제외) v..

#include #include using namespace std;struct Edge { int cost; int to;};int cntNode, cntEdge;vector v[10];int dist[10]; // DAT, index: 점 번호, value: 지금까지 계산한 거리void dijkstra_1(int start) { int isvalid[10] = { 0 }; // DAT, index: 점 번호, value: 해당 점은 거리가 확정인가? for (int i = 0; i dist[node]) { // 확정이 안된 상태로 거리가 최소면 minDist = dist[node]; minNode = node; } } // 가장 짧은 거리인 점 1개 찾음 isvalid[m..

https://github.com/dremdeveloper/codingtest_cpp/blob/main/solution/33.cpp codingtest_cpp/solution/33.cpp at main · dremdeveloper/codingtest_cppContribute to dremdeveloper/codingtest_cpp development by creating an account on GitHub.github.com #include using namespace std;vector parents;vector rankData;// 문자를 숫자로 변환int charToInt(char c) { return c - '0';}int find(int x) { // x의 부모가 자신인 경우 루트노드..