올해 휴가를 전부 써 버려 당장 판교로 돌아가야 하는 한별이는 돌아가기 위한 방법을 어떻게든 찾아보기 위해 이세계를 돌아다녀 보려고 한다. 이세계는 $R\times C$의 격자로 되어 있다. 지금은 밤이어서 한별이는 자신이 위치한 칸 및 그 칸에서 위, 아래, 왼쪽 또는 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 설치하면 조금 더 넓은 영역의 시야를 확보할 수 있다. 구체적으로는, 격자의 모든 칸은 각각 어떤 영역 하나에 속해 있는데, 와드를 놓으면 와드가 놓인 칸이 속한 영역에 있는 모든 칸을 볼 수 있게 된다. 한별이의 여행 기록이 주어질 때 한별이가 얼마나 넓은 시야를 확보했을지 계산해 보자. 입력 첫 번째 줄에는 격자의 크기를 나타내는 두 정수 $R$과 $C$가 주어진다. ( $1 \le R..
고려할 사항 재귀는 사용할 수 없음 (문자열의 최대 길이가 1000이므로 재귀 함수로 구현 시 시간 복잡도 증가) 적용 알고리즘 DP (동적 계획법) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Problem9251_LCS { // 최장 공통 부분 수열 문제 static char[] arr1; // 첫번째 문자열의 파싱 static char[] arr2; // 두번째 문자열의 파싱 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..
고려할 사항 1, 2, 3 들의 합이 주어진 정수의 값을 초과할 경우는 카운트 하지 않는다. 1, 2, 3 들의 합이 주어진 정수와 완벽히 같아진 경우에는 카운트를 증가시킨다. 적용 알고리즘 DP (동적 계획법) 이전까지의 연산 결과를 저장해두고 다음 단계로 넘어가는 메모이제이션 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] arr = {1, 2, 3}; // 1, 2, 3의 배열 // static boolean[] check; // 1, 2, 3 각 부분을 사용했는지 체크할 boolean static int cnt; // 나타..
문제 풀이 시 고려할 사항 M 번째 사람을 제거할 때 마다 원의 진행 방향을 반전한다 원의 진행 방향은 2번 이상 바뀔 수 있다 ( ex : 8 3 2 의 경우, 정방향 - 역방향 - 정방향 - 역방향 순) 시간 제한을 맞추기 위해, while 문의 사용은 최소화한다 사용한 자료 구조 덱 (Deque) 을 사용 count < K 일 경우 숫자를 덱에 다시 넣어준다 정방향의 경우 맨 앞의 숫자를 맨 뒤로, 역방향의 경우 맨 뒤의 숫자를 맨 앞으로 넣어준다 count = K 일 경우 숫자를 출력한다 정방향의 경우 맨 앞의 숫자를 출력, 역방향의 경우 맨 뒤의 숫자를 출력 StringBuilder에 넣어서 while문 종료 이후 한번에 출력 boolean 타입으로 정방향과 역방향 구분 import java.i..
문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000)..
