문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 ..
문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 전형적인 특정값에 최소로 도달하는 DP문제이다. 반대로 생각해서 1부터 N까지 도달하는 최소의 과정을 구하면 된다고 생각했다. +1, *2, *3의 방법이 있고 그걸 이용해서 코드를 짜게되면 아래와 같다.그리고 추가로 시간제한은 0.15초로 1500만번, 즉 O(n)..
문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을..
열거형 열거형이란 서로 관련된 상수를 편리하게 선언하기 위한 것으로 여러 상수를 정의할 때 사용하면 유용하다. 자바 1.5전에는 C언어와 달리 별도의 열거형이라는 것이 존재하지 않았으나 1.5부터 새로 추가되었다. enum은 여러 상수를 정의한 후, 정의된 것 이외의 값은 허용하지 않는다. 아래는 Enum이 컴파일러에 의해 정의되는것부터 Enum의 상수들이 바이트코드로 포함되고 이후 런타임때 클래스 로더에 의해 로드되는 과정을 아래 그림으로 표현했다 사용 이유와 장점 코드 가독성 향상: Enum은 관련된 상수들을 그룹화하고 이름을 부여하여 코드의 가독성을 향상시킵니다. 이 경우, 각 단위(Unit)는 Enum 상수로 정의되어 있으며, 코드에서 해당 상수를 사용하면 의미가 명확하게 전달됩니다. 타입 안정성..
Thread 클래스와 Runnable 인터페이스 먼저 프로세스와 쓰레드가 뭔지 알아보자 Process 독립적인 실행 단위로, 운영체제에서 자원과 메모리를 할당받아 실행되는 프로그램의 인스턴스를 나타낸다 각 프로세스는 자체 메모리 공간을 가지며, 서로 간섭하지 않고 독립적으로 실행된다. Thread 프로세스 내에서 실제로 작업을 수행하는 주체를 의미한다 모든 프로세스에는 1개 이상의 쓰레드가 존재하여 작업을 수행한다 두 개 이상의 쓰레드를 가지는 프로세스를 멀티 쓰레드 프로세스 라고한다 Thread 클래스와 Runnalbe 인터페이스 쓰레드 생성 방법 2가지 Runnable 인터페이스 사용 Thread 클래스 이용 아래는 자바내에 정의된 Thread클래스의 코드다(Thread관련 메서드와 변수를 java...
공부기간 및 공부법, 잡담 시험은 9/9(토요일) 10시에 치뤘다.(10분전 이렇게 도착하지말고 가능하면 25~30분전에 도착하자, 은근 뭐가있다) 신청 이후에 시험장에 갈때는 검정볼펜, 컴싸, 신분증, 수험표(선택, 어차피 번호 알려주신다)챙겨가야한다 다른 블로그 보고 수험번호 물어보면 시간걸린다길래 외워갔는데 시험전에 알려주시는거라 큰 상관없다. 그리고 화이트 못씀, 추가로 가채점 불가능하다. 혹시라도 작성자 본인처럼 번호 객관식 번호 외워도 네이버 데이터 전문가 포럼에서 복원하는거보면 번호가 대부분 문제답으로 하기때문에 의미없다. 공부는 7월 중순부터 학교 학술 동아리 사람들과 매주 스터디하는씩으로 진행했고 노랭이 문제집으로 진행했다. 보통 1주에 5시간공부+블로그정리2시간으로 진행한거같고 막판 5..
자바에서 예외 처리 방법 try, catch, finally try-catch 프로그램 실행 도중 발생된 에러는 어쩔 수 없지만 이외엔 대비처리를 해야한다. 이럴때 이제 대비 처리하는 try-catch문을 작성해줘야한다. try{ //예외 발생 가능성이 있는 코드 } catch(Exception1 e1){ //Exception1 이를 처리하기 위한 코드 } catch(Exception2 e2) { //Exception2가 발생시 이를처리하기 위한 코드 } 예시로 문자열을 정수형으로 변환하는 과정중에 발생하는 NumberFormatException 예외를 생각했지만 자바 문서 찾아보니 RuntimeException클래스의 자식이라 try~catch문 예시로 안좋을것같다. 그래서 RuntimeExceptio..
문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 풀이 처음에 생각했던 방식은 DP(다이나믹 프로그래밍)이었다. 하지만 메모리를 생각했을때 10억이란 숫자는 512MB(1MB당 약 25만개의 정수 담을수있음)이상이 필요하고 그러면 제한조건에 걸리게 된다. 따라서 방법을 변경해야하는데 생각해낸게 BFS이다. 주어진 수가 1만개이고 BFS는 시간복잡도가 O(log n)이기 때문에 제한시간안에 ..
인터페이스 정의 인터페이스 자바 인터페이스는 자바 프로그래밍 언어의 초기 버전부터 존재한다.(Java 1.0, 1996년) 인터페이스는 추상화의 한 형태로, 메서드의 선언만 있고 구현 내용이 없는 추상 메서드들로 이루어져있다. 클래스가 이 모든 메서드들을 구체적으로 구현해야한다. 선언 모든 기능을 추상화로 정의한 상태로 선언만 해야한다 접근 제어자로는 public 또는 default를 사용한다 interface MyInterface { void myMethod(); } 내장 인터페이스 이미 자바에서는 다양한 내장 인터페이스가 있다. 아래 그림과 예시를 보면 인터페이스와 클래스간의 관계, 필요성이 더 잘 느껴지지않을까 싶다. 아래는 내장되어있는 Collection의 구조이다. 그마저도 일부분이고 실제로 자..
문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 풀이 이문제의 핵심은 부모가 표시되지않은 2개의 연결 노드를 어떻게 표현할 것인가 다. 처음에 arr[N][N] 도 생각해서 표시를 해볼까 했지만 N의 최대값이 10만이기에 메모리 초과가 난다. 따라서 이중 배열리스트를 이용하여 두개의 값 연결을 표현해봤다. 이후 BFS를 통해 자식 노드를 찾고 찾은 자식노드의 부모를 앞선 값으로 입력하도록 ..
