본문 바로가기

알고리즘&자료구조

 (12)
이진검색트리 변형 : 트립 #include #include #include using namespace std; typedef int KeyType; struct Node { KeyType key; int priority, size; Node* left; Node* right; Node(const KeyType& _key): key(_key), priority(rand()), size(1), left(NULL), right(NULL) {} void setLeft(Node* newLeft) { left = newLeft; calcSize(); } void setRight(Node* newRight) { right = newRight; calcSize(); } void calcSize() { size = 1; if (left) siz..
[종만북] 울타리 - 스위핑 알고리즘 1.문제 문제요약 : 서로 높이가 다른 나무판자들로 이루어진 울타리가 있다. 이때 울타리에 포함되는 사각형 중 가장 넓이가 큰 사각형의 넓이를. 출력한다. (단, 사각형의 밑변은 지면과 수평이다.) 입출력 : 시간복잡도: 기존의 분할정복 방법을 통해 O(NlgN)으로 문제해결하였다. 오늘은 스위핑알고리즘을 통해 O(N)으로 이 문제를 해결하고자 한다. 분할정복을 통한 문제 해결 알고리즘은 아래 링크를 참고. [백준6549] 히스토그램에서 가장 큰 직사각형 - 분할정복 분할정복 (Devide and Conquer) 분할-정복 방법은 말 그대로 하나의 문제를 둘로 분할하여 생각하여 해결하는 방법론이다. 병합정렬(merge sort)이 대표적이다. 분할-정복 문제는 문제를 둘로 분할하는 ohreallystor..
[종만북] 양자화 1. 문제 문제요약: 양자화란 주어준 수열에서 각 수를 몇개의 수만으로 변환한다. 이때 원래의 수와 변환한 수의 차이의 제곱의 합이 최소가 되도록 해야한다. 길이가 N인 수열을 최대 S개의 수로 양자화할때 원래의 수와 양자화한 수의 오차의 제곱의 합을 구하여라. 제한범위: 수열의 길이(N) : 1 ~ 100 양자화에 사용할 숫자의 수(S) : 1~10 각 수는 모두 100이하의 자연수 2. 접근 : 단순화 무작위로 정렬된 수열에서 각 수의 양자화 수를 구한다는것은 거의 불가능한 일이다. 각 수마다 양자화할 수 있는 수는 1부터 100까지 존재하고, 양자화 수의 개수 S도 고려해야 한다. 일단 문제를 단순화할 필요가 있다. 비슷한 크기의 수들은 같은 수로 양자화된다. 양자화를 하기 위해서는 오차를 최소화해..
[종만북] 팬미팅 (feat. 카라츠바 곱셈) 1. 문제 문제요약: 일렬로 선 팬들이 차례대로 멤버들과 악수 또는 포옹을 한다. 이때 남-남의 경우 악수를 하고, 그 외의 경우는 포옹을 한다. 이때 모든 멤버가 동시에 포옹을 하는 경우의 횟수를 구하라. 제한범위: 멤버의 수
[백준1208] 부분수열의 개수2 어떤 집합의 부분집합 중 그 원소의 합이 S인 부분집합의 개수를 구하는 문제이다. 문제상에는 수열, 부분수열이라 나와있지만 명칭의 직관성을 위해 집합, 부분집합이라고 하겠음 Idea1. Brute Force #include using namespace std; int n, s; int arr[40]; int solution(int curr, int start, int end) { if (start > end) { if (curr == s) return 1; else return 0; } else { int ret = 0; ret += solution(curr + arr[start], start+1, end, isFront); ret += solution(curr, start+1, end, isFront)..
[백준1525] 퍼즐 주어진 한칸이 비어있는 숫자 옮기기 퍼즐을 풀어 최종 상태를 만들때 까지 필요한 최소 이동횟수를 구하는 문제이다. 123 456 78* 최종 상태 step1 . Brute Force 가장 단순하게 재귀적으로 생각해보자. 현재 상태의 최소 이동 횟수는 한칸을 이동 후 최소 이동 횟수에 1을 더한 값이다. (최소 이동 횟수) = 1 + (한칸 이동후 최소 이동횟수) 간단한 DFS 알고리즘이다! 하지만 이렇게 풀면 무한루프에 빠지게된다. 만약 최종상태를 만들 수 없는 입력값이 주어질 경우 재귀를 멈출 기저조건이 없기 때문에 무한루프를 돈다. 또한 만약 가능한 입력값이 입력돼도 한번 이동할때마다 최대 4번의 연산이 필요하므로 시간복잡도가 4의 지수배로 커진다. 즉, 15번이상만 이동해도 4^15이 되어 시간초과..
[백준6549] 히스토그램에서 가장 큰 직사각형 - 분할정복 분할정복 (Devide and Conquer) 분할-정복 방법은 말 그대로 하나의 문제를 둘로 분할하여 생각하여 해결하는 방법론이다. 병합정렬(merge sort)이 대표적이다. 분할-정복 문제는 문제를 둘로 분할하는 파트와, 분할 하여 구한 값을 통해 주워진 원래의 문제의 답을 도출하는 과정으로 나뉜다. 이때 어려운 문제는 보통 후자에서 높은 난이도를 자랑한다. 오늘 알아볼 **“히스토그램에서 가장 큰 직사각형”**문제도 분할하여 얻은 결과를 통해 어떻게 답을 도출할지에 대해 깊이 고민해야 하는 문제이다. [백준6549] 히스토그램에서 가장 큰 직사각형 히스토그램 내애 직사각형을 그렸을 때, 가장 큰 직사각형의 넓이를 구하는 문제이다. 직사각형의 밑변은 수평축에 포함된다. 일단 위 문제를 분할해보자. ..
[백준1517] 버블소트 정렬되지 않은 수열을 버블정렬 하는 과정에서 스왑이 몇번 일어나는지 출력하는 간단한 문제이다. O(N^2) Solution ll bubbleSort(int n) { ll ret = 0; for (int i=0; i

티스토리툴바