본문 바로가기
반응형

binary search5

BOJ 7453 : 합이 0인 네 정수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/7453 참고 - 머지 소트 Merge Sort 합이 0이 되는지 확인하기 위해 4000 x 4000 x 4000 x 4000의 경우의 수를 모두 확인하는 것은 비용이 너무 많이 든다. 따라서 A와 B의 합인 AB 배열 (16,000,000)과 C와 D의 합인 CD 배열(16,000,000)을 만든다. 그리고 AB 배열의 값이 x라면 CD에서 -x가 되는 경우를 찾으면 된다. 이 경우 이분 탐색으로 log(16,000,000) ≒ 24번 만에 답을 찾을 수 있게 된다. 물론 이분 탐색을 위해 배열을 머지 소트로 정렬하였다. 구현 입력을 받은 후, AB, CD 배열을 만든다. idx = 0; for (int i = 0; i .. 2023. 4. 7.
BOJ 5465 : 곰돌이 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5465 queue에는 좌표 (r, c)와 depth(곰이 움직인 거리)를 담을 수 있도록 구조체를 아래와 같이 선언한다. typedef struct st { int r; int c; int depth; }QUEUE; QUEUE queue[MAX * MAX]; int wp, rp; 주어지는 input의 알파벳은 숫자로 변경한다. 그리고 곰돌이의 최초 위치와 도착해야하는 집의 좌표는 따로 (sr, sc), (er, ec)에 저장한다. void input() { int change['Z' + 1] = { 0 }; change['T'] = -1; /* 나무 */ change['G'] = 0; /* 빈 칸 */ change['H'.. 2021. 6. 12.
BOJ 2805 : 나무 자르기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2805 정답을 X라고 가정하자. 즉, X 만큼 자를 때, 적어도 M 미터의 나무를 집에 가져간다. 그러면 X - 1 만큼 나무를 자르면 M 미터 보다 더 많은 나무를 가져가게 되고, X + 1 만큼 나무를 자르면 M 미터 미만의 나무를 집에 가져가게 된다. 따라서 BOJ 1939 : 중량제한처럼 이분 탐색을 이용하여 X를 찾을 수 있다. 먼저 적당한 값 m으로 나무를 잘라보고, 이 값이 M보다 크면 m 보다 큰 값에서 다시 적당한 값을 정한다. 이 값이 M보다 작으면 m보다 작은 값에서 다시 적당한 값을 정한다. 주어지는 나무들의 길이가 1,000,000,000이고 N이 최대 1,000,000이므로, long long t.. 2021. 6. 5.
BOJ 1939 : 중량제한 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1939 문제의 답이 되는 최대 중량을 X라고 하자. 그리고 두 섬이 연결되어 있는 것은 DFS를 이용하자. 섬 1과 섬 2가 중량 X로 다리를 건널 수 있다면, DFS(X, 섬 1)은 섬 2로 연결된다. 그러면 DFS(X, 섬 1)은 true다. DFS(X + 1, 섬 1)은 반드시 false가 된다. 이유는 문제의 답이 되는 최대 중량이 X이므로, X + 1의 중량을 견딜 다리가 없기 때문이다. 반대로 DFS(X - 1, 섬 1)은 반드시 true가 된다. 중량 X를 견디는 다리는 최대 중량 X보다 작은 값도 견딜 수 있기 때문이다. 따라서 정답 X에 대해 X보다 작거나 같은 값은 섬을 연결할 수 있고, X보다 큰 값은.. 2021. 5. 22.
삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 참고 - 삼성 C형 샘플 문제 : 블록 부품 맞추기 최적화 swexpertacademy.com/main/sst/intro.do SW Expert Academy에서 C형 샘플 문제 블록 부품 맞추기를 풀어보자. 블록 부품 맞추기는 C형 샘플 문제지만 B형 유형으로 풀 수 있다. 여기서 필요한 개념은 2차원 배열의 해싱과 정렬(merge sort), 그리고 이분 탐색이다. 보통 어떤 데이터를 빠르게 찾고 싶은 경우, 정렬을 한 후에 이분 탐색을 하는 경우가 많다. 문제의 예시를 보자. 오른쪽의 블럭을 뒤집어서 맞춰 끼우면 모두 높이가 8인 완벽한 육면체가 된다. 총 30,000개의 블럭 중에 완성품의 합이 최대가 되도록 블럭을 맞춰야한다. 먼저 블럭 배열에 번호를 .. 2021. 3. 30.
반응형

티스토리툴바