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

백준 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..

N은 4자리로 고정되어 있다. query 함수를 호출해 보면 스트라이크와 볼의 갯수를 알 수 있다. 예시인 플레이어1은 '1234' 플레이어2는 '4139'면 첫번째 경우 1 스트라이크, 2 볼일 수 있다. 그러면 음 뭘 해야 될까. 1. 스트라이크를 찾는다. -> '1234'중 한 자리씩 아예 새로운 숫자로 바꿔 본다. (2,5,6,7,8,) 중에 가능하다. 4139 -> 2139 : 1스트라이크 2볼 여전하다. 4139 -> 4239 : 2스트라이크 0볼, 스트라이크가 하나 늘었다. 확실한거는 꼭 저장하자. 어떻게?? (1,5,6,7,8) //즉 스트라이크 + 볼 4231 : 1 스트라이크 3볼 // 스트라이크와 볼의 갯수가 4개니까 여기서 부터는 숫자..

b형 코테 보려고 푼다. 음 막상 풀어보니까 쉽지 않다. iostream만 쓴다는건 더 정확하게 설계해야 한다. 난 중간에 하다가 뒤집어서 시간이 오래걸린다.!!! 9088. 다이아몬드 음 배열이 주어지면 서로 차이가 K이하인 것들을 모았을때 최대가 되도록 하는 갯수를 구해야 한다. 다이아몬드 갯수는 1000개 이하라 n^2도 가능하다. 이중 for문으로 각 다이아에 대해 다른 다이아들이 K이하인지 확인하면 될듯? -> 안된다. 이런식으로 넣으면 확인하는 대상 두개 말고 넣어진 애들끼리 K 이상일 수 도 있다. 아니면 오름 차순으로 정렬하고 앞에서 부터 차례로 K 이하인 놈들끼리만 넣어보는거다. 근데 이때 틀리고 알게된건데 가장 작은 놈이랑 새로 넣으려는 놈의 K만 비교하면 된다. 즉 그냥 우선순위 qu..

이 파트에 되게 취약하다..... 전에 전공 복습에서 힙을 공부 했었다. 이번에는 c++로 객체 지향으로 구현해 보자. 문제는 최소 힙을 구현하면 된다. 그리고 최소힙 팝, 푸쉬를 구현하면 된다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) scoville의 길이는 1 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. scoville의 원소는 각각 0 이상 1,000,000 이하입니다. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 길이가 100만이다. 음 힙을 구현하느라 애를 많이 먹었다. 버블 다운 방식, 바텀 업 방식. #include #inc..