개인적으로 공부한 내용을 정리중입니다.

1517번 각 숫자 보다 오른쪽에 큰 숫자가 몇개있는지 구해서 다 더하면 될거 같다. 생각 나는 방법1. 그냥 오른쪽으로 쭉 가면서 갯수를 다 세어본다. -> 이건 시간초과; 문제 카테고리상 세그먼트 트리이다. 세그먼트 트리는 분할 정복의 느낌이 조금 있는거 같다. 음 모르겠다. 노드 두개를 병합해서 새로운 노드를 만들때 어떠한 정보를 저장해야 답을 구할 수 있을 텐데 그것을 모르겠다. 12015번 : LIS 방법 6 10 20 10 30 20 15 1 2 1 2 1 1 1 2 1 3 2 2 dp[n] : n번째까지 가장 긴 부분 수열의 길이. dp[n] = (이전에 가장 긴 부분 수열의 연장됨(가장 긴 수열의 마지막 위치와 수를 저장하자) , 현재의 n번째가 처음 시작 수열로 한다) dp에 도대체 무슨..

4358번 생태학 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; map m; //종의 갯수를 빠르게 세기위한 트라이 struct Trie { bool finish; int cnt = 0; Trie* next[200]; Trie() : finish(false) { memset(next, 0, sizeof next); } ~Trie() { for (int i = 0; i < 200; i++) { if (next[i]) delete next[i]; } } void insert(const char* key) { if (*key == '\0') { fin..

가장 먼 노드. #include #include #include #include #include #define N 20001 using namespace std; bool visit[N] = { 0 }; vector adj[N]; //stack st; int maxv = 0; vector ans; queue q; queue dep; void dfs(int cur,int depth) { if (depth == maxv) { ans.push_back(cur); } if (depth > maxv) { maxv = depth; ans.clear(); ans.push_back(cur); } for (int i = 0; i < adj[cur].size(); i++) { if (visit[i] == 0) { visi..

백준 9934번 음 알고리즘 분류가 트라이라서 트라이 문제일 줄 알았는데 그냥 완전 이진 트리 같다. 음 근데 문제는 전위 순회 결과에서 트리를 재구성하라는거 같다. 반대는 몇번 해봤는데 ;; 일단 K에 따라서 트리의 깊이는 미리 알 수 있는데 10으로 깊지 않다. 음 내 생각에 풀이는 임의로 트리를 만들고 순서대로 순회 하면서 도착 지점에 도달하면 주어진 인풋의 맨 앞부터 순서대로 해당 트리 노드에 넣어주면 될거 같다.... 구현했는데 예제는 맞는데 틀렸다 함....음 ㅋㅋ 음 완전 이진트리라는 조건에 뭔가 안맞게 설계한거 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std;..

체육복 음 이 문제를 모든 경우를 생각한다 해보면, 앞뒤로 학생이 빌려주는지 확인한다. 그러면 30명이니까 2^30이 된다 .....그러니까 아님 그래서 탐욕법을 사용하나 보다. 그냥 쉽게 생각해보면 빌려주려는 애가 앞뒤로 옷이 없으면 누굴 줘야 되는 지가 문제다, 자기 뒤에 친구가 옷이 있는지 보고 없으면 그 뒤에 친구가 여분이 있는지 확인하면 될듯?뒤에 친구가 여분이 있으면 앞에 친구 옷 빌려주면 되고, 뒤에 애들도 옷이 없으면 앞에 친구 빌려주면 되지 않을까?? 아니 그냥 앞에사람 빌려주면 되는듯 앞에 사람이 있으면 뒤에사람 맞았다. #include #include using namespace std; int student[31] = { 1 }; int solution(int n, vector lo..

음 비형 대비 내가 일단 다 구현해 보는데 벡터 값은 정렬을 어떻게 하지? 콜 바이 레퍼런스로 넘기면 될듯?? 일단 정렬 코드를 작성했다. 파티션 부분에서 while문 종료되고 마지막에 피벗이랑 i 위치랑 스왑하는걸 빼먹어서 안됬었다. left budgets[j]) { swap(&budgets[i], &budgets[j]); i++; } j++; } swap(&budgets[pivot], &budgets[i]); return i; } void qsort(int left,int right,vector&budgets) { if (left < right) { int pivot = partition(left, right, budgets); qsort(left, pivot - 1, budgets); qsort(p..

K번째 수 음 구현했는데 퀵소트로 틀렸다. 시간 초과임... 아마도 pivot을 맨 오른쪽으로 잡아서 그런거 같다. 그래서 가운데로 잡았는데 이번에는 틀렸다. 코드가 문제인걸까? ㅠ 사실 의 sort를 사용하니까 맞았다.ㅠ 내가 틀린거긴 한데 일단 힙 소트를 구현해보자. 이건 최악의 시간 복잡도가 O(nlogn)이니까. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; } int partition(int left, int right, int arr[]) { int pivot = a..

모의고사 이건 그냥 하면된다. ㅋㅋ 소수찾기 음 이게 좀 문젠데, 소수를 조합하는거랑 소수인지 확인하는 두가지 과정이 필요해 보인다. 음 이런 문제에서 항상 궁금했었다. 갯수 별로 잘라서 그걸 순열로 해야되는건가?!?!? 만들고 그게 소수인지 아닌지 확인하고, 중복인건 배열로 체크해서 제외하도록? 순열 알고리즘 구현을 찾았다. https://gorakgarak.tistory.com/522 순열(Permutation) 알고리즘 1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4.. gorakgarak.tistor..

두 부품의 기둥 면을 마주하여 조립하면, 완벽히 일치(기둥 사이에 틈새가 존재하지 않는)하는 육면체 완성품을 얻을 수 있다. 이렇게 조립한 육면체의 높이는 8이 된다. 이때 이 육면체 완성품은 재사용될 수 있으므로, 절약되는 비용은 육면체의 높이 8만큼이다. 밑면의 [가로 x 세로] 넓이가 각각 [4 x 4]인 블록 부품이 30,000개 주어질 때, 절약되는 완성품들의 총 합이 최대가 되도록 하자. ※ 한개의 완성품은 항상 두개의 블럭으로 구성된다. ▶ 절약되는 완성품들의 총 합의 최대값을 반환하는 makeBlock() 함수를 작성하라. 일일이 두개씩 골라서 다 비교하면 4x4 x 30000 x 29999 = 16*9*10^8 절약되는 값이 최대가 되게 하려면 음 기둥 높이가 2,3,5,8 가 있으면 어..

https://hongku.tistory.com/149 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현) 퀵 정렬 (Quick sort) 특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하자 '분할 정복' 알고리즘으로 평균속도가 O(N * logN) 이다. 퀵정렬에는 기준이 되는 값이 존재한다. 이때, 기준값을 피봇(pivot).. hongku.tistory.com 정렬 코드 수정할때 참고 했다. K번째 수 #include #include #include using namespace std; void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void sort(int st, int dt, int*arr) { if (st..