본문 바로가기

전체 글36

[Algorithm] Quick Sort 소스코드 #include #include using namespace std; const int MX = 50001; int partition(int* a, int left, int right) { int pivot_idx = (left + right) / 2; int pivot_val = a[pivot_idx]; swap(a[right], a[pivot_idx]); int cnt = left; for (int i = left; i < right; ++i) { if (a[i] 2020. 10. 24.
[Algorithm] Quick Selection 소스코드 #include #include using namespace std; const int MX = 5000001; int partition(int* a, int left, int right) { int pivot_idx = right; int pivot_val = a[pivot_idx]; swap(a[pivot_idx], a[right]); int cnt = left; for (int i = left; i < right; ++i) { if (a[i] 2020. 10. 23.
[Algorithm] Master Theorem (feat. Quick Selection) 마스터 정리는 알고리즘을 재귀적인 점화식으로 표현하여 알고리즘의 동작시간을 점근적으로 계산할 수 있다는 정리입니다. 정해져있는 일종의 템플릿에 값만 넣으면 되기 때문에 계산하는 것이 어렵지 않지만 마스터 정리는 만능이 아니라 모든 재귀식에 대한 시간복잡도를 구할 수는 없습니다. # Master Theorem 마스터 정리를 간단한 형태로 나타낸 것입니다. 여기서 a, b는 1보다 큰 양수이고, f(n)은 충분히 큰 n에 대해서 양의 함수값을 가져야 합니다. 자신의 알고리즘으로 위와 같은 점화식을 세웠다면, 점화식은 다음의 세 가지 중 한 가지를 반드시 만족하며 각각의 시간복잡도 T(n)은 아래와 같이 계산할 수 있습니다. # Time Complexity of Quick Selection 이렇게만 보면 복잡.. 2020. 10. 23.
[BOJ] 20056 마법사 상어와 파이어볼 문제 링크 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치� www.acmicpc.net 2020년 하반기 새로운 상어 시리즈가 등장했습니다...! 마법까지 쓰게 될 줄이야... 모든 시뮬레이션 문제가 그렇지만 정말 위의 내용을 착실하게 구현하면 됩니다. 다른 상어 시리즈에 비해서 구현 난이도가 어렵지 않았습니다. 현재 위치(x,y), 질량(m), 방향(d), 속력(s)을 속성으로 갖는 파이어볼 구조체를 정의합니다. 파이어볼은 두 개.. 2020. 10. 19.
[C++] Cat *cat = new Cat; 를 이해해보자 C++을 통해 과제를 작성하는데 객체를 생성할 때 습관처럼 작성하는 한 줄이 있었습니다. C++을 사용해서 PS 뿐만 아니라 객체지향 패러다임의 프로그래밍을 해보셨다면 누구나 작성했을 코드인 이 글의 제목에 해당하는 코드입니다. 간단한 코드이지만 저 한 줄을 제대로 이해하고 있는가에 대한 의문을 시작으로 관련된 내용을 간단히 정리를 해보려 합니다. C와 C++ 두 언어는 많은 부분이 비슷하지만 다른 언어입니다. C++는 기존의 C의 문법을 따르며 객체지향 패러다임을 지원하는 언어로 등장했고 C++의 컴파일러로 C언어로 작성한 코드를 컴파일 할 수 있어 초기 C언어에 익숙한 사용자들의 유입을 끌어낼 수 있었습니다. 그렇다면 C언어와 비교해서 가장 큰 차이점은 객체지향 프로그래밍 패러다임을 따르는 것인데 객.. 2020. 10. 8.
[Android] Android Threads 자바로 작성한 프로그램은 JVM(안드로이드의 경우 ART)이 프로그램의 시작점에 해당하는 메인함수를 찾아 실행합니다. 그래서 일반적으로 자바로 프로그램을 작성해야 한다면 main( ) 함수를 구현해야 합니다. 하지만 안드로이드의 경우 메인함수가 안드로이드 프레임워크의 "android.app.ActivityThread" 클래스에 구현되어 있기 때문에 개발자가 직접 메인함수를 작성하지 않고 Manifest 파일에서 액티비티 중 하나를 Launcher로 지정함으로써 해당 액티비티를 어플리케이션의 진입점(Entry Point) 으로 만들 수 있습니다. 메인 스레드(Main Thread) 안드로이드의 진입점(Entry Point)을 통해서 어플리케이션이 실행되면, 안드로이드 시스템은 처음에 하나의 스레드로 애플리.. 2020. 10. 2.