문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ ..
문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이..
문제 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니..
I/O 입출력 I/O는 input, output의 약자로 입출력 통칭하는 용어로 I/O라고 부르며 읽을때는 Input, 파일쓰거나 외부전송은 Output이다(JVM기준) 한마디로 프로그램간의 데이터를 주고 받는것을 말한다 키보드로부터 데이터를 입력받는것 print문을 이용해 화면에 출력하는것 스트림(Stream)/ 버퍼(Buffer)/ 채널(Channel) 기반의 I/O Stream Stream 데이터를 운반하는데 사용되는 연결통로 자료의 입출력을 도와주는 중간 매개체 역할을 한다. 응용 프로그램과 입출력 장치를 연결하는 소프트웨어 모듈 단방향: 입력, 출력 다안하고 하나만 가능하다(따라서 동시에 수행할려면 스트림이 2개 필요하다), 추가로 도달하는것은 큐를 생각하면 됨(선입선출) Buffer 데이터를 ..
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬..
빌더패턴 집을 생각해보면 각각의 집들은 다른 요소들이 있을 수 있다.(주차장, 창문, 수영장, 정원) 근데 이런 집을 다 따로 만들자니 종류가 너무 많아지고 이거를 파라미터값으로 다 넣어주자니 메서드 하나에 파라미터값이 많아진다. 해결법: 빌더 패턴은 복잡한 객체들을 단계별로 생성할 수 있다. 그리고 빌더는 제품이 생성되는 동안 다른 객체들이 제품에 접근 하는 것을 허용하지 않는다. 자세한 내용은 아래 실습 예제를 보여주면서 설명하겠다. 실습 예제 Builder패턴 적용 이전 객체에 값을 할당하는 방법 생성자 생성 Setter 생성 Task클래스와 Client 클래스 코드 Task import java.util.Date; public class Task{ //항상 외부에서 사용못하게 하는 변수는 priv..
문제N개의 수 A1, A2, ..., AN과 L이 주어진다.Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)출력첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. 풀이처음에는 힙을 생각했었다. 최솟값을 O(log N)만에 찾을 수 있기때문이다.그래서 이제 힙에 값을 넣고 추후에 i-L 위치가 되면 그 값을 찾아내서 힙에서 제외시킬려고 했다.문제는 여기서 발생한다. 힙의 최솟값 접근은 O(log N)이지만 특정 값 찾는 시간복잡도는 무려 O..
어노테이션 어노테이션이란? 어노테이션은 자바 1.5부터 추가된 요소로 사전적 의미로는 주석을 의미한다. 하지만 자바에서는 단순 주석이 아닌 클래스에 특수한 의미를 부여하거나 기능을 주입하기 위한 메타데이터라고 볼 수 있다. 어노테이션은 인터페이스 일종으로 @를 사용하여 선언한다. 전에 JUNIT 테스트시 사용하는 @Test도 어노테이션이다. 단지 이게 테스트해야한다는 것을 프로그램에게 알리는 역할을 할 뿐, 메서드가 포함된 프로그램에는 아무런 영향을 미치지 않는다. 어노테이션의 용도 컴파일러에게 코드 문법 에러를 체크하도록 정보를 제공 인텔리제이 같은 소프트웨어 개발 툴이 빌드나 배치 시 코드를 자동으로 생성할 수 있도록 정보를 제공 런타임 시 특정기능을 실행하도록 정보를 제공 어노테이션의 종류 Buil..
문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마..
싱글톤 싱글톤 개념 싱글톤은 하나의 클래스 인스턴스를 전역적으로 공유하기 위한 디자인 패턴으로, 해당 클래스의 인스턴스가 오직 하나만 생성되고 어디서든 접근 가능하도록 보장한다. 클래스 내부에서 생성자를 private으로 선언하고, 유일한 인스턴스를 반환하는 정적 메서드를 제공한다. 다수의 객체 생성을 피하고 공유 리소스를 효율적으로 활용하는 패턴이다. ※디자인 패턴: 소프트웨어를 보다 모듈화하고 확장가능하며 유지보수가 쉽도록 만드는 해결책을 정리한 것이다 싱글톤 생성 예제 -> 문제점 -> 새로운 예시를 드는 방식으로 설명하겠다 public class Singleton { private static Singleton uniqueInstance; //하나뿐인 정젹 변수로 객체 선언 private Sing..
