기록방

👉 문제링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🔸 문제 분석 🔸 N * 3 보드판을 내려가며 최대,최소값을 구하는 문제이다. 내려갈 수 있는 방법이 3가지가 있는데, 브루트포스로 그래프 탐색하면 시간초과가 난다. 내려가는 방법이 아닌, 역으로 이전 줄을 보고 최대/최소값을 고르는 DP 방식으로 풀이할 수 있다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io...

👉 문제링크 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🔸 문제 분석 🔸 n개의 수로 이루어진 수열에서 연속된 k개를 골랐을 때 그 합의 최대값을 출력한다. 전형적인 두 포인터, 슬라이딩 윈도우 문제이다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.StringTokeniz..

👉 문제링크 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 🔸 문제 분석 🔸 입력된 문자열 S에서 P 길이의 부분 문자열을 만들었을때, 입력된 DNA 문자열 최소 개수를 충족하는 경우의 수를 출력한다. 슬라이딩 윈도우 알고리즘을 이용해서 P길이의 부분 문자열을 문자열 S의 시작점부터 오른쪽으로 밀어간다. 윈도우에서 벗어나는 인덱스는 현재 상태에서 빼기 윈도우에 새로 들어오는 인덱스는 현재 상테에 더하기 조건에 충족 하는지 확인해서 카운트 🔸 코드 🔸 import java.io.Buffe..