Whatever floats your boat

이 문제는 다이나믹 프로그래밍으로 분류되어있지만 문제의 이해와 원리를 파악하면 풀 수 있는 문제입니다. 이진포화트리는 Perfect binary tree로 불리며 꽉꽉채워진 이진트리 입니다. 자세한 설명은 다음링크로 남겨놓도록 하겠습니다. https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/ Binary Tree 종류 - Heap 구현 사전지식 개요 Heap 구현을 위한 Binary Tree 의 기초적인 개념에 대해 알아본다. yaboong.github.io 풀이 저는 weight와 node 두가지 vector를 int형으로 선언해 사용하였습니다. 먼저 weight에 각 edge들의 가중치를 입력받았고 node는 각 edge들의 we..

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많으며 대부분 c++ 라이브러리를 사용하여 정렬을 하는 경우가 많다. 이번엔 sort함수를 간단하게 알아보고 정렬하기 위해 sort의 세번째 인자로 전달해 주는 함수 사용법을 알아보도록 하겠다. sort() 란 먼저 sort()를 사용하기 위해 algorithm 헤더파일을 include 해야한다. sort 함수는 내부적으로 IntroSort라는 정렬 방법으로 구현되어있다. 이 방법은 QuickSort와 HeapSort와 InsertionSort를 합쳐놓은 방식으로 평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 QuickSort와는 달리, 최악의 경우에도 nlogn을 복잡도를 보장한다. https://en.wikipedia.org/wiki/Intr..

그리디 알고리즘 그리디 알고리즘은 탐욕 알고리즘이라고도 불리며 어떤 순간에 가장 최선의 선택을 하는것을 말한다. 특징은 local하게 최적의 선택을 하는것이 결국 global하게 최적의 해를 도출해준다. Activity-selection-problem이란? 그리디 알고리즘을 보여주는 한 예시이며 문제는 다음과 같다. 한개의 강의실에 n개의 수업들이 있다. 이때 각 수업은 시작시간 끝나는 시간이 주어진다. 이때, 한개의 강의실에서 수업이 최대 개수가 될 수 있도록 하는 수업 수를 찾으시오. 이때 문제를 해결하기 위해서는 끝나는 시간을 기준으로 오름차순 정렬한다. 그리고 겹치지 않는 선에서 수업을 선택하여준다. 다음은 위의 문제풀이 방식의 증명이다. 1 < x < y 이면서 수업의 최대 개수 집합이 A = ..