반응형 sliding window4 BOJ 8983 : 사냥꾼 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/8983 참고 - 머지 소트 Merge Sort 어떤 동물이 사대에서 잡을 수 있는 동물이라면, 이 동물을 기준으로 가장 가까운 사대만 확인하면 된다. 즉, 동물을 기준으로 왼쪽과 오른쪽 사대에 대해서만 거리를 계산해 L과 비교하면 된다. 왼쪽과 오른쪽 사대가 동물을 사냥할 수 없다면, 다른 사대는 더 멀리 있으므로 검사할 필요가 없다. 사대의 좌표(= x)를 작은 순으로 정렬하고, 동물도 x 좌표를 기준으로 정렬한다. 모두 정렬했으니, 사대의 좌표가 animal보다 가장 가깝게 작은 곳을 찾을 수 있다. while (index != M - 1 && place[index + 1] 2023. 1. 25. BOJ 2531, 15961 : 회전 초밥 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2531 https://www.acmicpc.net/problem/15961 BOJ 2531 : 2 ≤ N ≤ 30,000 BOJ 15961 : 2 ≤ N ≤ 3,000,000 초밥의 종류가 가장 최대가 되도록 모두 구해보면 된다. 이 과정에서 슬라이딩 윈도우를 사용해야 N이 3,000,000인 경우에도 시간 내에 처리할 수 있다. 초밥 벨트에 놓인 접시를 담을 배열 arr와 먹은 초밥을 저장할 table 배열을 선언하자. 초밥의 가짓수가 최대 3000이므로 3000이상으로 잡는다. int arr[3010000]; int table[3100]; 회전 초밥이기 때문에 arr의 N ~ N + k 까지 앞부분의 초밥을 추가한다... 2021. 7. 4. 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 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. 이전 1 다음 반응형
