알고리즘

문제 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 먼저 용액을 두 포인터를 위해 정렬한다. 배열에서 세 용액 중 하나를 0에서부터 N - 1까지 선택한다. 선택한 용액 뒤의 배열에서 두 포인터를 실시하여, 선택한 용액과 start, end에서의 용액의 합의 절대값이 0과 가장 가까운 용액을 답으로 한다. 시간 복잡도는 O(N * N)으로 N은 5000이하이므로 시간초과는 발생하지 않는다. 코드 #include #include #include #incl..

문제 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 두 포인터, 슬라이딩 윈도우 문제이다. 라이언의 인덱스를 따로 벡터에 저장한다. 벡터의 길이가 K보다 작은 경우 집합을 만들 수 없다. 크기가 K로 고정된 슬라이딩 윈도우 방식으로 벡터를 순회하면서 집합의 최소 크기를 탐색한다. i에서 부터 i + K - 1까지의 원소의 수는 K개이다. lion[i + K - 1] - lion[i] + 1이 lion[i]를 첫 요소로하며 크기가 K인 집합의 크기이다. 코드 #include #include #incl..

문제 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 풀이 수학, 두 포인터 문제이다. 몸무게는 0에서 시작할 수 없고, 현재 몸무게는 기억한 몸무게보다 커야 한다. 기억한 몸무게와 현재 몸무게를 두 포인터, start = 1, end = 2로 설정한다. 현재 start와 end일 때의 G를 current라고 할 때, current가 G 이하일 경우 end를 증가시켜 현재 몸무게를 더 늘려야 한다. 코드 #include #include using namespace std; int main() { ios_base::sync_..

문제 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 수학, 정수론, 누적 합 문제이다. for (int i = 1; i T; // 먼저 약수들의 합을 구해야 한다. // 약수들의 합을 O(N * log(N))의 시간복잡도로 구한다. for (int i = 1; i

문제 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 입력받은 수열을 정렬한다. start와 end를 0에서부터 시작한다. start와 end에서의 수의 차이가 M이상이라면 답을 갱신한다. 차이를 더 줄이기 위해 start를 증가시킨다. 미만이라면 차이를 더 늘리기 위해 end를 증가시킨다. 코드 #include #include #include using namespace std; int nums[100000]; int main() { ios_base::s..

문제 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 브루트포스 알고리즘, 두 포인터, 슬라이딩 윈도우 문제이다. 두 포인터는 구간의 넓이가 유동적으로 변하고, 슬라이딩 윈도우는 구간의 넓이가 고정적이다. 현재 문제에서 회전 초밥은 연속으로 k개 집어야 하므로 구간이 고정적이기 때문에 슬라이딩 윈도우로 풀어야 한다. 슬라이딩 윈도우 방식에서 구간을 한칸 옮겼을 때, 모든 구간을 다시 검사하는 것 보다 변한 구간. 즉, 맨 왼쪽과 맨 오른쪽만 계산하는게 더 빠르다. ..

문제 풀이 두 포인터 문제이다. start와 end를 0에서부터 시작하여, end의 수는 수열에 추가하고, start의 수는 수열을 추가할 수 없을 때 수열에서 제거하는 방식으로 start와 end를 증가하거나 감소시킨다. 원본 수열을 nums라고 하면, nums[end]는 현재 부분 수열에 추가하려는 수이다. nums[start]는 수를 추가할 수 없을 때, 부분 수열에서 제거하는 수이다. 코드 #include #include using namespace std; int nums[200'000]; int num_count[100'001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int N, K; cin >> N..

문제 풀이 누적 합 문제이다. 보드가 격자로 칠해져 있기 때문에, 칠해야 하는 칸을 누적 합으로 구해야 한다는 것을 생각하기 힘들었다. 보드판의 첫 칸이 검정색인 보드와, 하얀색인 보드로 나눠서 생각한다. (i, j)칸 까지, 각 보드칸에서 칠해야 하는 칸의 수를 누적 합으로 구해놓는다. i + j 가 짝수라면, 첫 칸의 색과 같은 색상이어야 한다. 홀수라면, 다른 색상이어야 한다. 이런 식으로 (i, j)칸을 탐색하며 누적 합을 구한다. 구한 2차원 누적 합에 K X K칸을 잘라냈을 때의 누적 합의 최솟값을 찾는다. 코드 #include #include #include using namespace std; char board[2001][2001]; int sum_black[2001][2001]; int..

문제 풀이 누적 합 문제이다. https://kantatatam.tistory.com/143 [백준][C++] 30508: 고인물이싫어 문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 kantatatam.tistory.com 2차원 배열의 누적 합을 구하는 문제로 위 문제와 풀이가 같다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; c..

문제 풀이 다이나믹 프로그래밍 문제이다. https://kantatatam.tistory.com/155 [백준][C++] 27210: 신을 모시는 사당 문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 kantatatam.tistory.com 위의 문제와 유사하다. 선택한 수의 배열의 총합을 current로 생각한다. 배열을 탐색하면서 current에 현재 요소의 값(nums[i])을 더한다. current가 현재 요소의 값보다 작다면, 기존의 배열을 버리고, 현재 요소를 첫 요소로 하는 새로운 배열을 생성한다. current의 최댓값이 답이다. 코드 #in..