문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 설명 다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다. DP만 사용해 문제를 풀면 모든 숫자를 배열로 담고 활용해야 하므로 메모리 제약에 걸린다. 따라서, 슬라이딩 윈도우 알고리즘을 같이 사용하면 dp 배열을 계속해서 초기화하면서 문제를 풀 수 있다. 먼저 처음에 maxDP와 minDP를 첫 줄의 숫자들로 초기화한다. 다음 줄부터 들어갈 m..
문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 설명 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구해야 한다. 일일이 부분합을 구해서 문제를 풀기 보다 시간복잡도를 줄이기 위해 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 sum이 M보다 크거나 ..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 설명 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해야 한다. 일일이 부분합을 다 구해서 문제를 풀면 시간복잡도가 크게 나오기 때문에 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 합이 S보다 작으면 현재 end가 가리키는 값을 더하고 end를 하나 전진시킨다..
문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 설명 이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 형택이의 승률이 절대 변하지 않는다면 -1을 출력한다. 만약 현재 승률이 99% 또는 100%라면 승률이 절대 변할 수 없으므로 -1을 출력한다. 현재 게임을 X번 했으므로 start를 1, end를 X로 하고 이분 탐색을 진행한다. start와 end가 역전되기 전까지 mid를 계속해서 구해서 getPercent 함수를 이용해..
이분 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 원하는 데이터를 탐색하는 방법이다. 리스트의 중간 부분에 찾는 데이터가 있는지 확인하고, 없으면 왼쪽에 있는지 오른쪽에 있는지 판단한다. 이분 탐색은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 이분 탐색의 시간복잡도 원하는 데이터를 찾을 때까지 처음부터 끝까지 계속 탐색하는 순차 탐색은 Worst Case일 때 \(O(N)\) 이라는 시간복잡도를 가지므로 10만개의 데이터가 있을 때 10만번을 탐색해야 한다. 그러나, 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에 Worst Case일 때에도 탐색의 횟수가 \( log_{2} N \)이 되어 \(O(log N)\) 의 시간복잡도를 가지므로 10만개의 데이터가 ..
문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 설명 N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내야 한다. 매번 하나씩 숫자를 비교하면서 탐색할 수 있지만 시간복잡도를 줄이기 위해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이분 탐색을 수행한다. 이분 탐색을 하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있기 때문에 먼저 입력받은 수를 오름차..
문제 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 설명 1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경..
문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 설명 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 알파벳은 총 26개이므로 words 배열의 크기를 26으로 만든다. 주어진 단어에서 해당하는 알파벳 자리에 각 자릿수만큼 10의 거듭제곱을 더해준다. int[] words = new int[26]..
