본문 바로가기
반응형

memoization14

[코드트리] 코드트리 메신저 (삼성 SW 역량테스트 2023 하반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. https://www.codetree.ai/training-field/frequent-problems/problems/codetree-messenger Define을 다음과 같이 정의한다.ALARM_OFF는 알람 설정이 OFF일 때, 모든 알림을 더 이상 위로 올려 보내지 않는 경우에 사용한다.#define MAX (100000 + 5000)#define DEPTH (20 + 3)#define READY (100)#define ALARM_ON_OFF (200)#define SET_AUTH.. 2024. 8. 8.
Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다.제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다.   PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver  Inde.. 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.
반응형

티스토리툴바