늘 겸손하게

ATM 문제 그리디 알고리즘으로 푸는 문제이다. 그리디 알고리즘을 정의를 다시 생각해보자. 현 상황에서 최적의 선택을 하는 과정을 정답이 나올때까지 반복하는알고 리즘이 그리디 알고리즘이다. 이 알고리즘을 문제에 적용해보자. 문제를 보면 N 명의 사람이 있고, 각 사람이 돈을 인출하는데 걸리는 시간이 Pi 라고 한다. 이 문제에 그리디 알고리즘을 적용하면 현재 가장 돈을 인출하는데 걸리는 시간이 적은 사람을 선택하고, 선택한 사람을 제외한 사람들중에서 가장 돈 을 인출하는데 걸리는 시간이 적은 사람을 선택하는 과정을 N번 반복하면 된다. 이를 코드로 구현하기 위해서는 N개의 Pi를 배열에 저장하고, 배열을 오름차순으로 정렬시킨 다음 적은 숫자부터 선형으 로 골라주면 된다. 코드 1 2 3 4 5 6 7 8..

그리디 알고리즘 문제 회의실 배정 문제로 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는 문제 문제 풀이 그리디 알고리즘의 정의를 다시 생각해보면 현 상황에서 가장 최적의 선택을 하는 알고리즘이 그리디 알고리즘. 이 점을 이용할 수 있도록 주어진 N 개의 시작시간, 종료시간 쌍을 정렬하자. algorithm 라이브러리를 include 하여 sort 함수를 이용하면 쉽게 정렬이 가능하다. sort(v.begin(), v.end(), cmp); v 는 N개의 회의시간 정보를 담고 있는 벡터이다. cmp는 어떤 방식으로 정렬할지 sort 함수에 알려주는 함수이다. typedef struct pair { int start; int end; } Pair; bool cmp(Pair f,..

그리디 알고리즘 문제 가장 큰 숫자부터 K를 나누고 그 몫을 계속 누적하여 더하면서 그 나머지를 K에 다시 저장하는것을 K가 0이 될때까지 반복하면 풀리는 문제 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include using namespace std; int main(void) { int N , K; cin >> N >> K; int * arr = (int*)malloc( sizeof(int) * N ); for (int i = 0 ; i > arr[i]; } int count = 0; while ( K != 0 ) { count += K / arr[N-1] ; K = K % ..

안녕하세요 이번 글에는 정렬 알고리즘들의 정렬 속도 차이를 비교해볼까 합니다. 비교할 정렬 알고리즘은 1. 버블 정렬 (bubble sort) 2. 단순 삽입 정렬(straight insertion sort) 3. 퀵 정렬(quick sort) 입니다. 정렬 알고리즘 구현 코드는 글 하단에 있습니다 :) - 기본 지식 버블 정렬과 단순 삽입 정렬의 시간 복잡도는 O(n^2), 퀵 정렬의 시간 복잡도는 O(n logn)입니다. 정렬 알고리즘들의 실제 정렬 속도 차이를 알기 위해 라이브러리 의 함수인 clock()을 이용해 정렬 전 시간과, 정렬 후 시간을 비교할 것입니다. 또한 무작위 숫자가 저장된 배열을 만들기 위해 라이브러리 의 rand() 함수도 사용할 것입니다. 또한 정렬할 원소 수가 적을 경우와 ..