본문 바로가기
반응형

알고리즘312

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.
BOJ 14889 : 스타트와 링크 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14889  N개의 팀 중, N / 2를 선택해야 하는 조합 문제이다.조합 문제에서는 list에 경우의 수를 저장했지만, 여기에서는 visit 배열을 이용해 선택한 팀을 1로 체크하자.그러면 visit = 0인 팀은 저절로 다른 팀이 된다. 마지막으로 선택된 팀(start), 선택되지 않은 팀(link)에 대해 입력받은 표를 보고 점수를 계산해주면 된다.start 팀은 team 배열의 앞에, link 팀은 team[halfN] 부터 저장하자.#include #define MAX (20 + 5)int .. 2021. 2. 19.
BOJ 14888 : 연산자 끼워넣기 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14888 숫자가 N개 연산자가 N-1개가 있다.연산자는 4종류고, 중복으로 사용이 가능한 경우다.보통 DFS에서 visit(check, used)으로 현재의 값(여기에서는 연산자)을 사용 중인지 확인하고,DFS를 다음 단계로 보낸다.void DFS(int L){ if (/* return 조건 */) return; for (int i = 0; i  visit을 최대 possible까지 허용한다면?아래와 같이 코드를 수정하면 된다.void DFS(int L){ if (/* return 조건 */) re.. 2021. 2. 19.
B형 필수 : 우선순위 큐 Priority Queue A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 B형에서 Merge Sort는 마지막에 이분 탐색을 위해 필요한 경우가 많다. 그리고 '무언가'를 push해주고, 그 중 가장 우선순위가 높은 '무언가'를 pop하면서,순서를 유지하고 싶을 때는 우선순위 큐를 이용해야된다. 요즘 B형에서는 HashTable + 우선순위 큐 모두 사용해야하는 경우가 많으므로, 우선순위 큐에 대해서 익혀.. 2021. 2. 19.
BOJ 7785 : 회사에 있는 사람 (Hash Table + Merge Sort) 삼성 B형 전체 링크 www.acmicpc.net/problem/7785 이름을 입력받으면, 아래의 DB 배열에 저장하고 in = 1로 두자. typedef struct st { char name[6]; int in; }DB; DB에 저장하고 이름을 hashing하여 HashTable에 저장하는데, 이때, DB를 포인터로 가르키도록 하자. typedef struct st2 { DB *db; struct st2 *next; }HASH; 즉, Hash에서 db를 보고 있으므로, 포인터로 접근하여 in = 0으로 바꿀 수 있게 된다. DB 자체는 배열로 유지하되, in을 Hash를 통해 포인터로 값을 바꾼다. input = 'enter'면 Hash 저장 및 in = 1, input = 'leave'면 Hash.. 2021. 2. 18.
반응형

티스토리툴바