늘 겸손하게

그리디 알고리즘 문제 회의실 배정 문제로 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는 문제 문제 풀이 그리디 알고리즘의 정의를 다시 생각해보면 현 상황에서 가장 최적의 선택을 하는 알고리즘이 그리디 알고리즘. 이 점을 이용할 수 있도록 주어진 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 % ..

백트래킹 문제 한번 선택한 정수는 다시 선택할 수 없으므로 visited 배열을 이용하여 promising 한지 promising 하지 않은지 판별할 수 있습니다. 재귀적으로 깊이 들어가다가 M 개의 수를 선택하면 결과를 출력합니다 코드 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 34 35 36 37 38 39 40 #include using namespace std; const int MAX = 9; int N, M; int arr[MAX] = {0,}; bool visited[MAX] = {0,}; void dfs(int cnt) { if (cnt == M ) { for (int i ..

brute force method 으로 해결하는 문제 코드 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 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; int main(void) { set s; int N , M; cin >> N >> M; int * arr = (int*)malloc( sizeof(int) * N ); for (int i = 0; i > arr[i]; } for (int i = 0; i