알고리즘
[BOJ] 16287 Parcel
문제 링크 https://www.acmicpc.net/problem/16287 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제를 풀기 위해서는 주어진 배열에서 서로 다른 원소 2개를 뽑아 더한 값을 구한 뒤, 이를 목표값 w에서 뺀 값을 또다른 두 개의 원소의 합으로 만들 수 있는지를 확인해야 한다. 처음에는 이를 확인하기 위해 서로 다른 원소 2개를 뽑아 더한 값을 전부 저장한 sum 배열을 만들어 이를 정렬한 뒤 이분 탐색을 통해 구하는 방법을 생각했지만, sum 배열의 최대 길이가 5,000*5,000 = 25,000,000이므로 정렬이 불가능했다. 따라서 정렬을 사용하지 않는 다른 방법이 필요했고, 다음과 같은 방법을 사용하기로 했다. 더보기 1. 서로 다른 두 개의 원소 합을 저장하는..
[BOJ] 2759 팬케익 뒤집기
문제 링크 https://www.acmicpc.net/problem/2759 모든 알고리즘 문제는 C++로 구현되어 있습니다. 팬케이크의 갯수가 최대 30개, 그리고 뒤집을 수 있는 최대 횟수가 2n-3번, 즉 57번이므로 완전탐색으로는 답을 구할 수 없었다. 대신 팬케이크를 차례대로 맞춰가는 방법을 생각했다. 위에서부터 k번째까지 뒤집을 수 있으므로, 아래쪽부터 맞춰가기로 했다. 더보기 1. i를 팬케이크의 갯수 num부터 2까지 1씩 줄여간다. 2. 팬케이크가 순서대로 쌓여있는지 확인한다. 순서대로 쌓여있으면 loop 종료 3. 현재 제일 위에 있는 팬케익이 i가 아닐 경우 i가 있는 곳까지 뒤집기 -> 맨 위의 팬케익이 i가 된다. 4. 위에서부터 i까지 뒤집기 -> 위에서부터 i번째에 i번째 팬케..
[BOJ] 1637 날카로운 눈
문제 링크 https://www.acmicpc.net/problem/1637 모든 알고리즘 문제는 C++로 구현되어 있습니다. f(x) =정수더미에서 x이하의 정수 갯수라고 생각하고, 전체 정수 범위를 [1, end]라고 하자. end는 입력으로 들어오는 값 C들의 최댓값으로 설정한다. f(x)는 N개의 입력값 A, C, B에서 x가 A 이상인 경우에 (x - A) / B + 1을 구한 뒤, 이를 전부 더하면 얻을수 있다. for (i = 0; i n; ll maxa = MIN; for (i = 0; i > arr[i][j]; maxa = max(maxa, arr[i][1]); } ..