프로그래밍/Algorithm3 [백준] 2751번 : 수 정렬하기 2 (C언어 풀이) https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 해당 문제는 수의 개수가 100만까지 있다. N^2로 하면 시간초과가 날게 뻔하다. 정렬 알고리즘 중에서 최대 NlogN까지의 시간복잡도를 갖는 애로 가야한다. 1) 퀵소트로 풀어봤다. #include void quick (int arr[], int start, int end) { if (start>=end) { return; } int key = start; int i = start+.. 2022. 9. 10. [알고리즘] # 1. 그리디 알고리즘 (Greedy Algorithm) 이론과 예제 풀이 풀이에 사용한 언어 : C언어 그리디 알고리즘 - 현재 주어진 Step만을 기준으로 하여, 최적의 해를 구하는 알고리즘이다. 다만, 매 Step마다 최적의 해를 구했다해도 최종 결과는 최적의 해가 아닐 수 있다. 그래서 불완전한 알고리즘이며 특수한 경우에만 그리디 알고리즘을 쓴다. 대표적인 예제가 거스름돈이다. 우리가 맥도날드에서 상하이스파이시버거세트를 산다하자. 한 때, 굉장히 좋아했는데 이사한 집 근처에 맥날이 없어서 가격이 기억안나지만 대충 5500원이였던 것 같다. 10000원을 지불하고 4500원을 거슬러 받는다 하면, 일반적으로 1000원 4장, 500원 1개로 총 5번의 거스름을 받는게 맞다. 화폐는 그 단위가 5000,1000,500,100... 이런 식으로 정해져 있고 내림차순 (혹은 오.. 2022. 7. 11. [알고리즘] # 0. Big-O / 시간 복잡도(Time Complexity)와 거품 정렬 (Bubble Sort) 알고리즘 공부를 시작하다보면 가장 먼저 마주하는 용어가 '시간 복잡도' 입니다. 이 시간복잡도가 어떤 꼴로 나오냐에 따라 알고리즘의 좋고나쁨을 알 수 있기 때문입니다. 우리 모두 수학을 싫어하는건 알지만 그래프를 하나 보도록 하겠습니다. 너무 잘 나와있어서 설명이 필요없는 그래프긴 하나, 살펴보겠습니다. X축은 Example Scale이라 보시면 되겠습니다. 얼마나 많은 양을 처리해야하는지인데요. Y축을 보면 그 양을 처리하는데 걸리는 시간이 나와있습니다. 더보기 어? 그러면 똑같은 문제의 양이 주어졌어도 푸는데 걸리는 시간이 짧을수록 좋겠네? 맞습니다. 위 그래프에 따르면 지수 함수에 가까워질 때 비효율적이고 로그 함수에 가까워질 때 효율적임을 보입니다. 더보기 그러면 어떤 이유에서 각각의 알고리즘의 .. 2022. 2. 18. 이전 1 다음
