개인공부용123 프로그래밍 블로그

FixHeapFast를 사용해서 HeapSort를 구현해봤습니다. 각 함수별 기능 설명 swap함수 : 두 배열의 원소를 바꿔주는 함수입니다. parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.) FixHeapFast 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. 단 이떄 FixHeapFast함수는 promote함수를 이용해서 높이의 절반 만큼씩 내려가게 됩니다. 그리고 vacant가 잘못 내려갔을경우 BubbleUpHeap함수를 이용해서 있어야할 위치로 올려줍니다. Promote 함수 : vacant를 높이의 절반만큼 내리는 함수입니다. (한칸..

백준 9426문제는 N개의 원소중에서 K개의 부분집합원소의 중앙값들의 합을 구하는 문제입니다. 이 문제는 세그먼트 트리를 이용해서 풀었습니다. 세그먼트 트리의 각노드에는 노드들의 갯수를 저장하고있습니다. (리프 노드에는 해당 노드가 세그먼트 트리에있는지 없는지를 표시) 업데이트시 1, -1로 원소를 추가 삭제 가능합니다. 쿼리함수를 이용해서 서브트리에 대한 중간값에 해당하는 값을 찾을수있습니다. 세그먼트 트리는 보통 포화 이진트리이므로 값이 N개일 떄 높이는 O(logN)입니다. 즉 하나의 중간값을 찾는데 걸리는시간은 O(logN)이 걸립니다. 그러므로 세그먼트 트리를 이용한 최악의 경우 시간 복잡도는 약 O(NlogN)입니다. Worst Case time Complexity = O(NlogN) incl..

MergeSort를 구현했습니다. 각 함수별 기능 설명 Merge : 분할된 두 부분을 합쳐주는 기능을합니다. MergeSort : 분할 정복을 이용해서 각각 Sort를 실행하는 함수입니다. 위 사진과 같이 분할 정복을 통해서 머지소트가 실행됩니다. Worst Case time Complexity 머지소트의 최악수행시간의 점화식은 W(n) = W(n/2) + W(n/2) + W(merge)(n)입니다. 이를 Master theorem을 이용해서 점화식을 풀면 O(nlogn)이라는 최악수행시간이 나옵니다. 즉 MergeSort의 최악수행시간 = O(nlogn) #include #include using namespace std; void Merge(vector& arr,int start, int mid, ..

퀵소트를 인플레이스로 구현해봤습니다. 퀵소트란 비교연산 기반의 Sorting으로서 Randomized Sorting알고리즘이고 또한 분할 정복이기도합니다. 퀵소트에는 주요한 원소가있는데 Pivot이라는 원소입니다.이 원소는 퀵소트를 수행시 소팅의 기준이 된다고 할수있는 원소입니다. 퀵소트를 정렬시 피벗의 왼쪽에는 피벗보다 작은값 오른쪽에는 피벗보다 크거나 같은값들로 정렬합니다. L은 피벗의 왼쪽 리스트 : 피벗보다 작은 원소들의 집합P는 피벗(원소)R은 피벗의 오른쪽 리스트 : 피벗보다 크거나 같은 원소들의 집합 InplacePartion을 실행하면 L P R 이런식으로 정렬이 되게됩니다. 제 코드에서 Inplace_Partion의 수행방식은1. 먼저 임의의 피벗을 잡고 맨오른쪽 위치로 보냄 (저는 중간..

백준 2751번 문제도 풀고 HeapSort도 구현해보기위해서 HeapSort를 구현해서 백준 2751 문제를 풀었습니다. 각 함수별 기능 설명 swap함수 : 두 배열의 원소를 바꿔주는 함수입니다. parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.) FixHeap 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. consturctHeap 함수 : 이 함수는 주어진 배열을 Heap으로 만들어주는 함수입니다. (아래 코드의경우엔 MaxHeap입니다.) HeapSort 함수 : Heap의 Root에 있는 노드를 배열 끝에 넣고 FixHeap시키는 함수..

구현방식 * 배열이 sorting되있지 않을시 sort를 시켜야함 (sorting된 data structure를 대상으로 하는 알고리즘)1. 시작 인덱스와 마지막 인덱스의 중간지점( (시작 인덱스 + 마지막 인덱스) / 2 ) 을 잡는다.2. 찾으려는 Key값과 비교해서 탐색범위를 1/2로 줄인다.3. 위와 같은 방법을 찾으려는 키값을 찾을때까지 재귀적으로 반복한다. #include using namespace std; // Edited by Survivalking 2017 03 25 int binarySearch(int e[], int first, int last, int K) { int index = 0; if (last < first) { cout K; cout

아래와 같은 알림메세지 창을 띄우는 코드 및 설명입니다. 가운데 있는 버튼을 클릭시 위와 같은 다이얼로그 창을 띄워줍니다. 아래는 소스코드입니다. public class MainActivity extends Activity { final Context context = this; private Button button; public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.main); button = (Button) findViewById(R.id.buttonAlert); // 버튼 리스너 추가 button.setOnClickListener(new OnClickL..

위 그림과 같이 버튼으로 PopupMenu를 실행하는 간단한 예제입니다. public class MainActivity extends AppCompatActivity { @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_main); Button btn = (Button) findViewById(R.id.btn); btn.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { PopupMenu popup= new Popup..

문제 : https://algospot.com/judge/problem/read/GRADUATION 졸업하기위해 전공과목을 수강해야하는데 전공과목을 듣기위해서는 선행과목이 필요할수있다. 이런 제한조건을 가지고 최소학기에 졸업할수있는 학기를 출력하거나 불가능할경우 불가능을 출력하는 문제입니다. 이 문제는 비트마스크와 DP를 이용해서 문제를 풀었습니다. 비트연산을 이용해서 메모리 사용량을 줄이고 dp를 이용해서 탐색 시간을 줄였습니다. 처음에 입력부분에서 or 비트연산을 이용하지않고 (int)pow(2,n)연산을 이용해서 각과목에대한 선행과목 정보등을 더해가면서 표시했더니 테스트케이스는 정확히 나왔지만 사이트에서 답안 제출을 할때 오답이 나왔습니다. 그리고 cache배열은 이진연산을 이용한 정보를 담을수있게..

문제 : https://algospot.com/judge/problem/read/PASS486 주어진 범위내에서 정해진 약수의 갯수를 가지는 수를 찾는 문제입니다. 이를 해결하기위해서 주어진 범위내에서 수의 약수를 배열에 미리 저장해두고 찾는 방식을 사용했습니다. 가장작은수인 2부터 10,000,000까지 차례대로 약수의 갯수를 미리 구해서 문제를 해결했습니다. 이를 위해 에라토스테네스의 체를 이용해서 소인수분해한 수 중 최소의 수를 찾은후 그것을이용해서 각 수의 약수의 갯수를 구했습니다. #include #include using namespace std; const int MAX = 10000000; int MinPrime[MAX + 1]; // 최소 소수 int MinPrimeNum[MAX + 1]..