반응형 알고리즘303 BOJ 15656 : N과 M (7) - 중복 순열 permutations with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15656 N과 M (5)와 마찬가지로 input에 대해서 N과 M (3)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0); return 0;} 2021. 2. 22. BOJ 15655 : N과 M (6) - 조합 combination 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15655 N과 M (5)와 마찬가지로 input에 대해서 N과 M (2)의 코드를 조금만 수정하면 된다. #include int N, M; int list[10]; int input[10]; void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } for (int i = start; i 2021. 2. 22. BOJ 15654 : N과 M (5) - 순열 permutation 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15654 N과 M (1)은 1~N으로 순열을 출력했다면, 이번엔 특정 input에 대해서 순열을 출력하면 된다. 사전 순으로 증가하는 순서로 출력해야 하므로, input을 입력받고 정렬하자. N이 작기 때문에 단순한 O(N2) 정렬로 해도 큰 무리가 없다. #include int N, M; int list[10]; int visit[10]; int input[10]; /* input 저장 */ void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L) { if (L == M) { outputList(); ret.. 2021. 2. 22. BOJ 14891 : 톱니바퀴 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14891 시뮬레이션 문제는 시키는대로 구현하면 된다.이 문제는 연속으로 회전이 발생하므로, DFS로 연속 회전 시켜보자. 먼저 rotate를 구현해보자.톱니의 번호와 방향을 입력받으면 회전하는 함수는 아래와 같이 구현할 수 있다.톱니바퀴 4개와 12시 방향 = 1 부터 8까지(순서대로 시계방향)의 톱니를 넣을 수 있는 2차원 배열을 선언하자.int wheel[5][10]; /* wheel[번호 1~4][각 톱니 1~8] */void rotate(int number, int dir){ int temp; if (dir == -1) /* 반시계 방향 */ { t.. 2021. 2. 21. BOJ 1655 : 가운데를 말해요 with 우선순위 큐 삼성 B형 전체 링크 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1655 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 가운데라는 값은 우선순위로 두기 굉장히 애매하다. 이유는 가장 높은 우선순위의 가운데와 최악의 가운데를 정의할 수 없기 때문이다. 만약 어떤 값들 중, 가운데 값을 pop한다고 하자. 그러면 heap[hn--] 에서 최악의 가운데 값을 넣어야 하는데, 이.. 2021. 2. 21. BOJ 15652 : N과 M (4) - 중복 조합 combinations with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15652 중복 순열에서 순서가 의미가 없다면, 중복 조합이 된다. 중복으로 선택은 가능하되, 다음으로 선택해야할 숫자가 작아서는 안되므로, DFS에 현재 선택한 값을 그대로 넘겨주면, 다음 Level에서는 작은 값을 선택할 수 없게 된다.#include int N, M;int list[10];void outputList(){ for (int i = 0; i 2021. 2. 21. BOJ 15651 : N과 M (3) - 중복 순열 permutations with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15651 중복으로 숫자를 선택 가능하고, 순서도 의미가 있는 중복 순열 문제이다.즉, visit배열로 숫자를 현재 선택했는지 관리할 필요가 없다. 따라서 다음 Level에서도 모든 숫자를 선택할 수 있도록 i = 1 ~ N으로 하면 된다.#include int N, M;int list[10];void outputList(){ for (int i = 0; i 2021. 2. 21. BOJ 10825 : 국영수 삼성 B형 전체 링크 www.acmicpc.net/problem/10825 정렬의 방법은 다양하지만 우선순위 큐 응용을 위해 힙으로 풀어보자. 우선순위가 높은 순은 다음과 같다.1) 국어 점수가 높다.2) 국어 점수가 같으면 영어 점수는 낮은 순.3) 영어 점수까지 같으면 수학 점수가 높은 순.4) 모두 같은 점수면 이름의 사전 순. 따라서 pop을 할 때, 최악의 input은 아래와 같다.heap[hn].kr = 0; /* 낮은 국어 점수 */heap[hn].en = 0x7fff0000; /* 높은 영어 점수 */heap[hn--].math = 0; /* 낮은 수학 점수 */mystrcpy(hea.. 2021. 2. 21. BOJ 11286 : 절댓값 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/11286 우선순위가 최소 힙, 최대 힙보다 조금 더 까다롭다. 1) 절댓값이 가장 작으면 우선순위가 높다. 2) 같은 절댓값인 경우는 음수가 우선순위가 높다. 따라서, 최악의 값은 양수 중에 가장 큰 값이 된다. if / else if의 비교를 함수로 만들면 편하다. heap[hn--] = 0x7fff0000; /* 최악의 값은 양수 중 가장 큰 값 */ int abs(int x) { return (x > 0) ? x : -x; } int isMin(int a, int b) { if (abs(a) < abs(b)) return 1; /* 절댓값 중 작으면 우선순위가 크다 */ if (abs(a) == abs(b) && a < b) retu.. 2021. 2. 21. 이전 1 ··· 26 27 28 29 30 31 32 ··· 34 다음 반응형
