백준 1446번: 지름길

🤔생각의 흐름

1. N의 최대값이 12이므로 완전탐색, 백트랙킹도 가능하겠다.
2. 선택하는 것에 따라서 이후의 값들이 영향을 받는 것 같은데, 패턴을 한 번 찾아볼까?
3. 도착 위치가 D보다 크거나 지름길을 이용했을 때 더 오래걸리는 입력들은 무시하고 생각해보자.
4. 출발위치와 도착위치가 같은 입력들은 그 중에서 지름길의 길이가 짧은 입력만 받아들이자.
5. 정리된 입력값들을 쭉 나열해보니, 이전 인덱스의 값을 이용하여서 이후 인덱스의 값을 결정하네? DP로 접근해야겠다.

🧻풀이

백준 1446번: 지름길 풀이 코드

1. 딕셔너리를 이용하여 (출발점, 도착점)을 key로 하고 지름길 길이를 value로 입력받기.
2. 1 도착위치 - 출발위치 <= 지름길 입력 제외
3. 2 도착위치 > D 입력 제외
4. 3 딕셔너리에 값을 넣을 때 같은 key가 존재한다면, 지름길 길이가 작은 값으로 업데이트
5. 딕셔너리에서 출발점과 도착점을 추출하여 중복없는 리스트로 만들기
6. 1 출발점인 0과 도착점인 D는 항상 존재해야 하므로, 리스트에 추가
7. 위에서 만든 리스트와 같은 크기의 리스트를 하나 생성
8. 지점이 저장된 리스트의 값을 차례대로 읽으며, 생성한 리스트의 값을 업데이트한다.
9. 1 이전 지점의 값 + (현재 지점 위치 - 이전 지점 위치)와 현재 지점을 도착지점으로 하는 값들을 딕셔너리에서 찾아서 모두 비교 한 후 가장 작은 값을 리스트에 업데이트 한다.

말이 어려우니, 예제 입력 3번을 기준으로 설명해보겠다. N = 8, D = 900 (0, 10) : 9 (80, 190): 100 (50, 70): 15 (160, 180): 14 (140, 160): 14 (450, 900): 0 이 값들만 입력으로 받게 된다.

그리고, 출발점과 도착점으로 리스트를 만든다. [0, 10, 50, 70, 80, 140, 160, 180, 190, 450, 900] 그리고, 새로 리스트를 하나 생성하여 지점까지의 최소 값을 담는다.

예를 들어, 70까지 가기 위해서 얼마만큼의 거리를 이동해야 하는가를 보자. (0, 70) + 0, (10, 70) + 10에 해당하는 값, (50, 70) + 50에 해당하는 값, 70-50 + 50에 해당하는 값 이 값들을 비교하여 가장 작은 값을 새로운 리스트의 70에 해당하는 3번째 index에 값을 업데이트 한다. (딕셔너리에 (0, 70), (10, 70), (50, 70) 값 중 존재하지 않는 것들은 계산하지 않는다. 70-50 + 50에 해당하는 값은 무조건 존재하기 때문에, 딕셔너리에 모두다 없다면, 50이 가지고 있는 값에서 70-50을 더해준 값이 업데이트 된다.)

이렇게 값을 끝까지 업데이트하면 [0, 9, 49, 64, 74, 134, 148, 162, 172, 432, 432]가 된다. 리스트의 마지막 값이 정답이 된다.

📔후기

문제 이름부터 지름길이었고, 최단 거리를 찾는 문제여서 다익스트라나 BFS를 썼으면 쉽게 풀었을 것 같다. 그래프로 생각하지 못하여서 DP를 이용해서 풀었는데, 괜히 어렵게 생각 한 것 같다. 최단 거리를 찾는 문제에 익숙해질 필요를 느꼈다.

자바를 다시 공부하면서 새롭게 알게된 것들과 자세히 알지 못했던 지식들을 기록을 남겨보려고 합니다.

IDE란?

IDE란 통합 개발 환경(Integrated Development Environment)으로 코딩, 디버그, 컴파일, 배포 등을 하나의 프로그램에서 처리 할 수 있도록 하는 소프트웨어이다.

Intellij vs Eclipse

인텔리제이와 이클립스는 자바의 IDE로 대표되는 것들인데, 이 둘을 비교한 자료를 정리해보았습니다.

• 인텔리제이는 유료, 이클립스는 무료
• 인텔리제이가 이클립스에 비해 빠르다
• 사용자 경험에서 인텔리제이가 앞선다.
• 전자정부 프레임워크는 이클립스 개발 환경을 공식 지원한다.
• 인텔리제이가 자바, 스프링 부트 버전 향상에 대한 업데이트가 빠르다.
• 이클립스는 한 화면에 여러 프로젝트를 띄울 수 있지만, 인텔리제이는 한 화면에 하나의 프로젝트만 띄울 수 있다.

JDK, JRE, JVM?

JDK란?

JDK란 Java Development Kit로 자바소스 파일을 만들고 javac 명령어로 소스 파일을 바이트 코드로 컴파일 할 수 있게 해준다. JRE를 포함하고 있다.

JRE란?

JRE란 Java Runtime Environment의 약자로 자바로 만들어진 프로그램을 실행시키는데 필요한 라이브러리, API, JVM이 포함되어 있다.

JVM이란?

JVM은 Java Virtual Machine으로 바이트 코드 파일을 완전한 기계어로 번역하고 실행시킨다. 그리고, Garbage Collection(GC)이 여기에 포함되는데 이로 인해 더 이상 필요하지 않은 객체를 식별하고 메모리에서 해제하여 프로그램의 메모리 사용을 최적화하는 역할을 자동으로 하게 해준다. 자바 가상 머신은 운영체제별로 다르게 설치된다.

JAR?

JAR란 Java Archive로 .jar 확장자를 가지는 파일이다. 자바 클래스 파일과 관련 리소스들을 하나의 파일로 모아서 배포하기 위한 아카이브.

자바 폴더들의 의미

src (Source)

이 디렉토리는 소스 코드 파일을 포함하는 곳입니다. 주로 자바 소스 코드 파일들이 여기에 저장됩니다.

bin (Binary)

컴파일된 자바 클래스 파일들이 저장되는 디렉토리입니다. 소스 코드 파일을 컴파일하면 이 디렉토리에 클래스 파일들이 생성됩니다.

lib (Library)

외부 라이브러리 또는 JAR(Java Archive) 파일들을 포함하는 디렉토리입니다. 이 라이브러리들은 프로젝트에서 사용될 수 있고, 클래스 패스(classpath)에 추가하여 프로젝트에서 접근할 수 있습니다.

build

프로젝트를 빌드한 결과물, 즉 실행 가능한 JAR 파일이나 WAR 파일 등이 저장되는 디렉토리입니다.

resources

소스 코드 이외의 자원 파일들을 저장하는 곳입니다. 예를 들어, 이미지, 설정 파일, 텍스트 파일 등이 여기에 포함될 수 있습니다

자바 프로그램 실행방법

1. Java 개발 환경 설치 확인: 먼저 리눅스 시스템에 Java 개발 환경(JDK - Java Development Kit)이 설치되어 있는지 확인해야 합니다. 터미널을 열고 다음 명령어를 실행하여 JDK 버전을 확인합니다:

   java -version

2. 소스 코드 컴파일: 자바 소스 코드를 실행하기 전에 먼저 컴파일해야 합니다.

   javac hello.java

   이 명령은 컴파일된 클래스 파일(hello.class)을 생성합니다.

3. 자바 클래스 실행: 컴파일된 클래스 파일을 실행하려면 다음 명령어를 사용합니다.

   java hello

GenerationType.IDENTITY는 기본 키 생성을 데이터베이스에 위임하여 DB에서 PK를 AUTO_INCREMENT 한다. AUTO_INCREMENT를 할 때 PK가 1부터 시작하여 1씩 올라가는데, PK에 직접 0을 INSERT 하니 AUTO_INCREMENT와 꼬인 것이다. PK에 0을 입력한 첫 번째 줄을 지우면 Duplicate error가 해결된다.