백준: 문제 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 오늘 아예 작정하고 슬라이딩 윈도우 문제를 풀고 있다. 이전 두 문제는 별도의 배열을 사용해 조금 어렵게 접근했어야 했던 문제라면 이번 문제는 풀이 방식은 쉬우나 배열 처리가 어려운 문제였다. 왜냐하면 우선 전체 배열 크기를 문제에서 제시하지 않고 주어진 수의 범위를 통해 계산해야했기 때문이다. 여기서 K의 범위가 0이상 2,000,000이므로 전체 배열의 크기는 2,000,000 * 2 + 1이다. 이제 주어진 양동이를 알맞게 위치시키고, 앨버트를 한칸씩 옮기면서 2 * ..

백준: 문제 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 처음에 보면 매우 간단한 문제로 보이나, 생각보다 메모리와 제한 시간이 빡빡해서 알고리즘을 여러 번 바꾸어가며 코드를 작성해야 했다. 1. 반복문 첫 번째로 시도한 방법은 정말 단순한 방식으로 시간복잡도가 최악의 경우 O(N^2)가 되는 반복문을 사용하였다. 쉬운 만큼 디버깅도 필요없이 단번에 작성해냈으나, 바로 시간 초과를 당했다. #include #include using namespace std; vector students..

백준: 문제 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 평소 투 포인터, 슬라이딩 윈도우 알고리즘 문제를 많이 풀어보지 않아서 직접 찾아서 풀어보았다. 기본적으로 너비가 고정된 투포인터가 슬라이딩 윈도우 문제이기 때문에 포인터를 2개로 잡아도 되고, 1개로 잡아도 된다. 하지만 2개로 잡으면 그만큼 신경 쓸 게 많아지기 때문에 여기서는 구간의 오른쪽 끝 포인터만 잡고, 나머지 하나는 그 포인터에서 주어진 너비를 감소함으로써 왼쪽 끝 포인터로 설정하였다. 회전 무엇보..

백준: 문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 단순한 DP 문제인줄 알았는데, 메모리를 줄이는 게 관건인 문제였다. N의 최대 크기는 100,000으로 배열 크기를 그만큼 잡아야한다고 생각했다. 하지만 잘 생각해보면 직전 줄의 값만 필요하고 그보다 이전 줄의 값은 필요하지 않다. 따라서 이전 줄과 현재 줄의 값만 저장하면 되므로 long long dp[2][3]만 있으면 된다. 경우의 수 dp 배열의 크기를 줄여도 여전히 메모리를 줄이라는 경고 문자가 뜬다. 즉 주어진 입력값을 저장하는 배열조차도 줄..