Programing/Tips
-
[알고리즘] 퀵정렬(QuickSort)Programing/Tips 2016. 11. 19. 14:14
안녕하세요. 꿈꾸는 개발자 몽키준입니다.이번에는 퀵정렬에 대해 알아보려고 하는데요. 아시는 바와 같이 정렬방법은 여러가지가 있지만 그중에서 나름 괜찮은(?) 속도로 구현이 가능한 정렬 방법이 퀵 정렬인 것 같습니다. 가운데를 기준으로 좌우 대칭적인 값을 가지고 있는 데이터의 경우 가장 효과적으로 정렬이 가능(O(n l og n)합니다만 worst case 로는 O(n^2) 의 복잡도를 가집니다. 코드에 들어가기에 앞서 간략하게 동작원리를 설명하자면, 저장된 데이터 중 하나를 피봇으로 잡고 피봇 왼쪽에는 피봇보다 작은 값이 위치하도록 하고 피봇 오른쪽엔 피봇보다 큰값을 채워준다. 이를 무한히(데이터가 1개 인 경우) 반복하여 정렬 하는 방법입니다. [퀵정렬 코드] void printSrc(const cha..
-
[알고리즘] Dijkstra's algorithmPrograming/Tips 2016. 11. 19. 14:13
안녕하세요. 꿈꾸는 개발자 몽키준입니다.이번에는 최단 경로(shortest path) 찾기 알고리즘 중의 하나인 데이크스트라 알고리즘(Dijkstra's algorithm) 에 대해 알아보려고 합니다.네덜란드 컴퓨터 과학자 이름이라는데 발음하기가 어렵네요. 저만 그런가요?일단 위키에서는 다음과 같이 알고리즘에 대해 소개를 하고 있습니다. 해당 알고리즘의 가정은 일단 출발점/도착점이 정해져야 하며 각 경로는 마이너스(-) 값이 없다는 전제로 수행하게 됩니다. 만약 마이너스 값이 존재한다면 테이블의 없는 경로로 우회하는 경우 기존 값들에 영향을 주기 때문입니다. 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 알고리즘에 대한 자세한 설명..
-
[알고리즘] 최대 공약수와 최소 공배수 구하기Programing/Tips 2016. 11. 18. 17:18
안녕하세요. 이번에는 최대 공약수와 최소 공배수 구하기에 대해 알아보려고 합니다. 여기서 최대 공약수란 ? 최대공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor, 약자 GCD)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.(위키피디아 발췌) 그럼 최소 공배수란 무엇일까요? 수론에서, 여러 개의 정수/다항식/환의 원소의 공배수(公倍數, 영어: common multiple)는 그들 모두의 배수가 되는 정수/다항식/환의 원소이다. 최소공배수(最小公倍數, 영어: least common multiple, 약자 LCM)는 음이 아닌 공배수 가운데 가장 작은 하나이다.(위키피디아 발췌) [최대 공약수] /* get_gcd.cpp */ in..
-