반응형 memoization13 Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다. 제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다. PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver Indexed Priority Queue, Heap - updat.. 2022. 1. 13. BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14. BOJ 2096 : 내려가기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2096 메모리가 4MB로 매우 작은 상태에서 다이나믹 프로그래밍으로 문제를 풀어야 한다. 아래의 4개의 배열로 문제를 풀 수 있다. int A[4]; /* 작은 값 저장 */ int B[4]; /* 큰 값 저장 */ int C[4]; /* 입력 값 */ int D[4]; /* temp 값 */ N번째 내려가기를 했을 때 얻을 수 있는 최소값은 3가지 경우로 나뉜다. 세 개의 수 중 첫 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수를 선택한 경우. 두 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수/세 번째 수를 선택한 경우. 세 번째 수를 선택한 경우 - 이전 값에서 두 번째 수/세 번째.. 2021. 6. 26. BOJ 1212, 1373 : 8진수 2진수, 2진수 8진수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1212 https://www.acmicpc.net/problem/1373 8진수 0 ~ 7를 2진수로 변경하면 아래와 같다. 0 → 000 1 → 001 2 → 010 3 → 011 4 → 100 5 → 101 6 → 110 7 → 111 따라서 str8['8진수 문자열 0 ~ 7']이 000 ~ 111이 되도록 memo 해서 출력만 하면 된다. 단, 가장 처음에 나오는 8진수 0 ~ 3의 경우, 앞의 0은 출력하지 않기 때문에 예외 처리를 한다. #include char str[1001000]; int main(void) { char str8['9' + 1][5] = { 0 }; str8['0'][0] = '0'; st.. 2021. 6. 21. BOJ 18139 : Rush Hour Puzzle (map) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/18139 Hash, 2차원 배열 탐색을 이용하였던 Rush Hour Puzzle을 map으로 풀어보자. 문제의 핵심은 2차원 배열 탐색을 이용하여 hash한 값이 너무 커서, 다시 hash를 한 것이었다. map을 이용하면 기존의 int hashMap[PRIME];으로 hash할 필요 없이 그대로 hash값을 저장할 수 있다. typedef unsigned long long int ull; map hashMap; /* key : 2차원 배열 hash 값, value : Level */ main에서 hashMap을 큰 값으로 초기화해줬으나, 이 코드는 더 이상 필요가 없다. //for (int i = 0; i < PRIME; .. 2021. 6. 19. BOJ 1016 : 제곱 ㄴㄴ 수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1016 에라토스테네스의 체와 같은 방법으로 구할 수 있다. 소수의 배수를 모두 지우고 남은 수가 소수가 되는 것처럼 제곱수의 배수를 모두 지우면 제곱 ㄴㄴ 수가 남게 된다. 1,000,000,000,000의 수에 대해 모든 제곱 ㄴㄴ 수를 구할 수 없으므로, MIN ~ MAX (최대 1,000,000 차이)까지만 구하면 된다. 따라서 100만개의 수 중 제곱 ㄴㄴ수를 구분하기 위해 배열을 100만개 잡는다. check[number] = 0 인 경우가 제곱 ㄴㄴ수이다. 이때, MIN번 째 수가 제곱 ㄴㄴ 수 인지 여부는 check 배열의 0번째 index를 본다. int check[1000100]; /* 0 = 제곱 ㄴㄴ .. 2021. 6. 18. BOJ 1644 : 소수의 연속합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1644 N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다. 따라서, 소수의 판단은 에라토스테네스의 체를 이용한다. int N; int prime[4000000 + 50000]; int primeSet[4000000 + 50000]; int pcnt; void eratos() { prime[1] = 1; for (int i = 2; i * i 2021. 4. 2. BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19. BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18. 이전 1 2 다음 반응형
