반응형 전체 글1066 BOJ 15651 : N과 M (3) - 중복 순열 permutations with repetition A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 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. BOJ 11279 : 최대 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/11279 우선순위 큐 설명은 링크를 참고하자. 링크를 보면, pop과 push에서 변경해야 할 곳은 총 4군데 이다. int pop(int* heap, int& hn) { ... heap[hn--] = 0x7fff0000; for (register int i = 1; i * 2 1; i /= 2) { if (heap[i / 2] heap[i * 2 + 1]) break; else if (heap[i * 2] > heap[i * 2 + 1]) { tmp = heap[i * 2]; heap[i * 2] = heap[i]; heap[i] = tmp; i = i * 2; } else { tmp = heap[i * 2 + 1]; heap[i * 2.. 2021. 2. 21. BOJ 1927 : 최소 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/1927 우선순위 큐 설명은 링크를 참고하자. #include int N; int heap[100100]; int hn; int pop(int* heap, int& hn) { register int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[hn--] = 0x7fff0000; for (register int i = 1; i * 2 1; i /= 2) { if (heap[i / 2] = 1; i /= 2) 최소 힙이지만, x가 자연수라는 조건에 의해서 얼떨결에 통과하게 되는 것이므로, i > 1이란 것을 잘 기억해두자. i = 1인 경우 부모 node가 없으므로, i > 1까지만 갱신하면 된다. 2021. 2. 21. BOJ 15650 : N과 M (2) - 조합 combination SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15650 N과 M(1) - 순열이 줄 세우기 문제라면, 이번 문제는 조합문제이다. 1 2 3 4 = 1 2 4 3 = ... = 4 3 2 1 이 모두 중복으로 취급된다.즉, 순서가 상관이 없다. 그리고 사전 순으로 증가하도록 출력해야하므로,DFS Level에서 start를 기억해두고, start에서 N까지만 list를 작성하도록 만들면 된다. list에서 선택한 번호를 저장하고, 선택한 번호 + 1을 다음 DFS에 넘겨주면 된다.이렇게 되면, 선택한 번호는 다음 DFS Level에서 선택할 수 없으므로, visit 배열이 필요가 없다.#include int N, M;i.. 2021. 2. 20. BOJ 15649 : N과 M (1) - 순열 permutation A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15649 순열을 구하는 문제이다.서로 다른 N개중에 M을 선택하는 경우의 수를 의미하고 순서가 상관이 있다.그리고 중복이 없어야 한다. N = M이면 팩토리얼이 된다.(서로 다른 N개를 모두 나열하는 경우의 수) 예제 입력 2를 예로 4개 중 2개를 선택해서 줄을 세운다면, 아래의 출력이 나온다.1 21 31 42 12 32 43 13 23 44 14 24 3순서에 의미가 있으므로 1 2 와 2 1이 다르다. 경우의 수 문제는 대부분 재귀 호출로 해결한다. 먼저 첫번째를 선택하면 다음 재귀에서는 선택하지 못하도록 해야한다.따라서 숫자들이 현재 선택된 상태인지 확인하는 .. 2021. 2. 20. BOJ 14890 : 경사로 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14890 먼저 경사로가 설치 가능한지, 1차원 배열에 대해서만 check함수를 만들고, for문을 이용해서 N번 check하자.이때, 가로 배열, 세로 배열에 대해서 따로 check를 만들 필요 없이, MAP을 회전 시킨 후 check 하면 된다.sum = 0;for (int i = 0; i 이제 경사로가 설치 가능한지 check해보자. 먼저 arr에 대해 inverse한 배열이 필요하다.for (int i = 0; i arr는 →로 가면서 낮아지는 구간이 있는지만 check한다.inverse.. 2021. 2. 20. JavaScript test setting 자바스크립트 전체 링크 index.html index.js console.log("hello"); 2021. 2. 19. 이전 1 ··· 111 112 113 114 115 116 117 ··· 119 다음 반응형
