TIL
- 알고리즘 1문제 : 등산 경로 (다익스트라)
- 자바의 신 1권 남은 정리문제 풀이
- 프로토콜과 TCP/IP
1. 등산 경로 정하기
100만년 만에 풀어보는 다익스트라 알고리즘!
다익스트라 알고리즘이란?
그래프에서, 기준으로 잡는 시작 노드로부터 연결된 모든 노드까지 거리의 최솟값을 구하는 알고리즘. 시작 노드와 연결된 최소 비용의 노드들을 모두 방문 처리할 때까지 업데이트 하는 방식으로 구현한다.
이 문제가 특별한 이유는, 시작할 수 있는 노드들과 끝날 수 있는 노드들이 여러개 있다는 점이다. 보통은 시작 노드 한 개, 끝나는 노드 한 개가 주어진 후 시작 노드에서 끝나는 노드까지 비용의 최솟값을 구하는게 기본이다. 하지만 이 문제는 시작점과 끝점이 여러개여서, 이를 위한 새로운 논리를 생각하지 않으면 시간초과 크리 맞고 좌절을 하게 된다는 점이 다르다.
gates 리스트에 시작 지점 인덱스들이, summits 리스트에 끝 지점 인덱스들이 들어있다. 목표는 각 시작 지점들에서 끝 지점들까지의 최소 비용 구하기다.
이때 비용 update에도 일반적인 다익스트라와는 다른 점이 있는데, 비용의 최솟값을 담을 리스트에 역대 비용의 누적합이 아닌 역대 엣지 비용의 최댓값을 넣어야 한다는 점이었다. 이 점은 특별히 어려울 것이 없었고..
이 문제에 specific한 풀이를 생각하기 위해 다음을 고려해야 한다.
gates에서 시작해서 다시 돌아오는 상황 조건은 함정이다.gates->summits비용의 최솟값만 구하면 편도 거리를 다시 돌아가면 된다.- 누적합이 아니라 최댓값으로 비용을 판단하므로, "다익스트라 비용 검색을
gates의 어떤 부분에서 시작하는가"는 고려 사항이 아니다! - 업데이트 하고자 하는 새로운 비용이 기존의
intensity값보다 크다면 미련없이 해당 노드를 기준으로 한 검색을 멈춰야 한다.
2,3 번을 빨리 깨달아야 시간 초과에서 벗어날 수 있다. 특히 2번, 나 역시 gates의 모든 시작점에서summits까지의 최소 비용을 계산했는데 곰곰이 생각해보니 누적합이 필요 없는 상황에선 그럴 필요가 없다는걸 깨닫고 코드를 수정했다.
from collections import defaultdict
from heapq import heappop,heappush
def solution(n, paths, gates, summits):
answer = [50_000,10_000_000]
summits,gates,path = set(summits),set(gates),defaultdict(list)
for i,j,w in paths:
path[i].append((w,j)); path[j].append((w,i))
intensities = [10_000_001 for _ in range(n+1)]
heap,visited = [(0,s) for s in gates],[False for _ in range(n+1)]
while heap:
dis,node = heappop(heap)
visited[node] = True
if (dis > answer[1]):
continue
for n_dis,n_node in path[node]:
if visited[n_node] or n_node in gates:
continue
intensity = max(n_dis,dis)
if (intensities[n_node] > intensity):
intensities[n_node] = intensity
if (n_node in summits):
if (intensity < answer[1]):
answer = [n_node,intensity]
elif (intensity==answer[1]):
answer[0] = min(answer[0],n_node)
else:
heappush(heap,(intensity,n_node))
return answer이러한 case specific한 최소 비용 업데이트에 대한 고민은 감을 잃지 않을만큼 항상 생각해야하는 것 같다.
2. 자바의 신 1권 남은 정리문제
13장 : 인터페이스와 추상클래스, enum
1) 인터페이스에 선언되어 있는 메소드는 body(몸통)가 있어도 되나요?
메소드 시그니처 앞에 default가 붙지 않는 한, body가 있어선 안된다.
2) 인터페이스를 구현하는 클래스의 선언시 사용하는 예약어는 무엇인가요?
클래스 선언부의 마지막에 implements {인터페이스명}을 붙인다. extends {클래스명}과는 다르게, 구현할 인터페이스는 여러개가 올 수 있다.
3) 일부만 완성되어 있는 클래스를 무엇이라고 하나요?
abstract class, 즉 추상 클래스라고 한다. body가 없는 메소드가 존재해도 되지만, new를 통한 객체 생성은 불가능하다.
4) 3번의 답에 있는 클래스이 body(몸통)가 없는 메소드를 추가하려면 어떤 예약어를 추가해야 하나요?
abstact 키워드를 반환 타입 앞에 붙여야 한다.
5) 클래스를 final로 선언하면 어떤 제약이 발생하나요?
해당 클래스는 더이상 상속될 수 없다는 제약이 생긴다. immutable 클래스를 만드는 상황에서 쓰일 수 있다.
6) 메소드를 final로 선언하면 어떤 제약이 발생하나요?
하위 클래스에서 해당 메소드를 override할 수 없다.
7) 변수를 final로 선언하면 어떤 제약이 발생하나요?
final 변수엔 새로운 값을 할당할 수 없다. = 연산자의 좌측에 변수가 올 수 없다는 뜻이다.
8) eunm 클래스 안에 정의하는 여러 개의 상수들을 나열하기 위해서 상수 사이에 사용하는 기호는 무엇인가요?
,
public enum Month {
JANUARY(1),
FEBRUARY(2),
MARCH(3),
APRIL(4),
MAY(5),
JUNE(6),
JULY(7),
AUGUST(8),
SEPTEMBER(9),
OCTOVER(10),
NOVEMBER(11),
DECEMBER(12);
private final int month;
Month(int month) {
this.month = month;
}
public int getMonth() {
return month;
}
}각 달과 달 숫자를 기록할 때, 이런 식으로 enum 클래스를 사용할 수 있다.
9) enum으로 선언한 클래스는 어떤 클래스의 상속을 자동으로 받게 되나요?
java.lang.Enum 클래스를 상속받는다. 그리고 컴파일러에 의해 해당 클래스의 생성자가 자동으로 구성/실행된다.
10) enum 클래스에 선언되어 있찌는 않지만 컴파일시 자동으로 추가되는 상수의 목록을 배열로 리턴하는 메소드는 무엇인가요?
values()
14장 : 다 배운 것 같지만, 예외라는 중요한 것이 있어요
1) 예외를 처리하기 위한 세 가지 블록에는 어떤 것이 있나요?
try-catch-finally 블록이다. try는 예외가 던져질 가능성이 있는 코드가, catch는 괄호 안의 예외가 던져졌을 때 실행할 코드가, finally는 어떤 상황에서든지 반드시 실행되는 코드가 위치한다.
2) 1의 답 중에서 "여기에서 예외가 발생할 것이니 조심하세요"라고 선언하는 블록은 어떤 블록인가요?
try
3) 1의 답 중에서 "예외가 발생하든 안하든 얘는 반드시 실행되어야 됩니다."라는 블록은 어떤 블록인가요?
finally
4) 예외의 종류 세 가지는 각각 무엇인가요?
Error, RuntimeException(Checked Exception), 그 외의 Exception들(Unchecked Exception)
5) 프로세스에 치명적인 영향을 주는 문제가 발생한 것을 무엇이라고 하나요?
Error이다. 프로그램 바깥에서 일어나는 오류(하드웨어 관련 문제 등)를 통칭해서 Error로 부른다.
6) try나 catch 블록 내에서 예외를 발생시키는 키워드는 무엇인가요?
throw. 뒤에 던지고자 하는 예외 객체를 만들어 던진다.
7) 메소드 선언시 어떤 예외를 던질 수도 있다고 선언할 때 사용하는 키워드는 무엇인가요?
throws. 메소드 뒤에 해당 키워드와 던질 예외 클래스를 함께 붙인다.
8) 직접 예외를 만들 때 어떤 클래스의 상속을 받아서 만들어야만 하나요?
Exception클래스. 실행 즉 런타임 중에 발생할 확률이 높은 클래스는 RuntimeException을 상속받는 것이 좋다.
16장 : String
1) String 클래스는 final 클래스인가요? 만약 그렇다면, 그 이유는 무엇인가요?
final 클래스가 맞다. 문자열 기능을 하는 String 클래스를 더이상 상속하지 못하고, 있는 그대로 사용하게 하기 위함이다. String은 자바의 대표적인 immutable 클래스인데, thread-safe, 객체의 신뢰성 등을 이유로 그렇게 구현했다.
2) String 클래스가 구현한 인터페이스에는 어떤 것들이 있나요?
CharSequence: 문자열을 다루는 객체임을 명시적으로 표현Comparable:compareTo()메소드를 override하여, 정렬의 대상이 될 수 있는 객체임을 표현Serializable: 파일로 저장되거나, 서버를 통해 보낼 수 있는 객체Constable: 불변하는 constant 객체
3) String 클래스의 생성자 중에서 가장 의미없는 (사용할 필요가 없는) 생성자는 무엇인가요?
매개변수가 없는 기본 생성자 String()
4) String 문자열을 byte 배열로 만드는 메소드의 이름은 무엇인가요?
getBytes()
5) String 문자열의 메소드를 호출하기 전에 반드시 점검해야 하는 사항은 무엇인가요?
null-checking. null이 할당된 객체의 메소드를 호출하면 NullPointerException이 발생한다.
6) String 문자열의 길이를 알아내는 메소드는 무엇인가요?
length()
7) String 클래스의 equals() 메소드와 compareTo() 메소드의 공통점과 차이점은 무엇인가요?
- 공통점 : 둘 다
String객체의 주소가 아닌 내용 문자열을 기준으로 한 연산 결과를 반환한다. - 차이점 :
equals()는 문자열의 내용이 같은지 여부를boolean타입으로 반환하고,compareTo()는 메소드를 호출한 문자열이 인자 문자열보다 얼마나 사전상 앞에 위치해있는지int타입으로 반환한다.
8) 문자열이 "서울시"로 시작하는지를 확인하려면 String의 어떤 메소드를 사용해야 하나요?
String myString = "서울시로 시작하는 문자열";
System.out.println(myString.startsWith("서울시"));9) 문자열에 "한국"이라는 단어의 위치를 찾아내려고 할 때에는 String의 어떤 메소드를 사용해야 하나요?
String myString = "어디 있을까 한국은?";
System.out.println(myString.indexOf("한국"));10) 9번 문제의 답에서 "한국"이 문자열에 없을 때 결과 값은 무엇인가요?
-1
11) 문자열의 1번째부터 10번째 위치까지의 내용을 String으로 추출하려고 합니다. 어떤 메소드를 사용해야 하나요?
String stringSeq = "일이삼사오육칠팔구십아이우에오";
System.out.println(stringSeq.subString(0,10));12) 문자열의 모든 공백을 * 표시로 변환하려고 합니다. 어떤 메소드를 사용하는 것이 좋을까요?
String myString = "이 문자열의 모든 공백은 별로 대체됩니다.";
System.out.println(myString.replace(" ","*"));13) String의 단점을 보완하기 위한 두 개의 클래스는 무엇인가요?
StringBuffer, StringBuilder
14) 13번의 답에서 문자열을 더하기 위한 메소드의 이름은 무엇인가요?
add()
16장 : 클래스 안에 클래스가 들어갈 수도 있구나
1) Nested 클래스에 속하는 3가지 클래스에는 어떤 것들이 있나요?
- static nested class : 내부 클래스 선언을
static class로 한 내부 클래스. 프로그램 시작시 JVM이 클래스를 초기화하며,static변수와 메소드만 사용할 수 있다 - local inner class :
static이 붙지 않은 내부 클래스 - anonymous inner class : 클래스 내부에서 사용하는 인터페이스의 구현 내용을 중괄호로 한꺼번에 처리한 클래스
2) Nested 클래스를 컴파일하면 Nested 클래스 파일의 이름은 어떻게 되나요?
{바깥 클래스}${Nested 클래스}.class 형식
3) Static Nested 클래스는 다른 Nested 클래스와 어떤 차이가 있나요?
프로그램 시작시 JVM이 클래스를 초기화하며, static 변수와 메소드만 사용할 수 있다.
4) StaticNested 클래스의 객체 생성은 어떻게 하나요?
부모 클래스의 객체를 생성할 필요 없이 new {부모 클래스}.{static nested calss}()형식의 생성자를 사용한다.
5) 일반적인 내부 클래스의 객체 생성은 어떻게 하나요?
4)번과 다르게, 부모 클래스의 객체가 생성된 후 객체 내의 생성자를 호출한다.
Outer outer = new Outer();
Outer.Inner inner = outer.new Inner();6) Nested 클래스를 만드는 이유는 무엇인가요?
클래스에서 특별하게 사용되는 내부 클래스가 필요할 때. 같은 Student 객체라도 HighSchool과 University에서 하는 역할이 다를 수 있는데, 이 때 각 클래스의 Nested 클래스를 둘 수 있다.
7) Nested 클래스에서 감싸고 있는 클래스의 private로 선언된 변수에 접근할 수 있나요?
물론 가능하다. private는 클래스 안에서만 접근 가능한 변수이고, Nested 클래느 역시 클래스 안에 존재하기 때문이다.
8) 감싸고 있는 클래스에서 Nested 클래스에 선언된 private로 선언된 변수에 접근할 수 있나요?
역시 가능하다.
17장 : 어노테이션이라는 것도 알아야 한다
1) @Override 어노테이션의 용도는 무엇인가요?
해당 어노테이션이 붙은 메소드는 상위 클래스나 인터페이스의 메소드를 재정의한 것임을 알리기 위함이다.
2) @SupressWarnings 어노테이션의 용도는 무엇인가요?
컴파일러가 내뱉는 기본 경고 문구를 무시하기 위함이다.
3) @Deprecated 어노테이션의 용도는 무엇인가요?
해당 메소드, 클래스, 변수 등은 더이상 지원하지 않으니 사용하지 않길 권할 때 사용한다.
4) 어노테이션을 선언할 때 사용하는 어노테이션을 무엇이라고 부르나요?
메타 어노테이션. @Retention, @Target, @Documented 등이 있다.
5) 4번의 답에 있는 어노테이션들을 사용할 때 import 해야 하는 패키지는 무엇인가요?
Java.lang.annotation
6) @Target 어노테이션의 용도는 무엇인가요?
정의하고자 하는 어노테이션이 프로그램의 어떤 요소에 붙을 수 있는지 정의한다. METHOD, CLASS, FIELD, PARAMETER 등을 지정해줄 수 있다.
7) @Retention 어노테이션의 용도는 무엇인가요?
어노테이션, 그리고 그 어노테이션이 적용되는 기간을 정의한다. RUNTIME일 경우 JVM이 가동되는 런타임동안, CLASS일 경우 javac의 결과인 .class파일에서만 적용된다.
8) @Inhereted 어노테이션의 용도는 무엇인가요?
해당 어노테이션이 붙은 클래스의 자식 클래스까지 같은 어노테이션을 적용할 것을 설정하기 위해 사용한다.
9) 어노테이션을 선언할 때에는 class 대신 어떤 예약어를 사용해야 하나요?
@interface
3. TCP/IP
1) Protocol : 규약
네트워크란, 참여자들 간의 통신으로 원하는 데이터를 주고받기 위해 구성된 연결망이다. 데이터를 주고받는다면, 서로의 데이터가 오류나 손실 없이 원하는 상대방에게 보내지길 기대할 것이다. 이를 달성하기 위해 어떤 포맷, 어떤 길이의 데이터를 어떻게 교환할 것인지 사전에 규칙을 정하는 것이 필요하다. 이 규칙이 바로 네트워크 프로토콜이다.
2) OSI 7계층과 TCP/IP 4계층
과거에는 OS마다 통신 프로토콜이 달랐고, 이를 위한 하드웨어 구현도 달랐다. 따라서 서로 다른 프로토콜을 가진 기기들 사이의 네트워크는 힘든 일이었다.
또한 통신에 사용될 데이터를 구성하고, 설정하고, 가공하고, 보내고, 받고, 다시 읽을 수 있는 형태로 변환하까지 전체 과정을 아우르는 프로토콜을 만드는 것은 상당히 복잡한 일이고 특정 과정중 오류가 발생했을 때 오류를 검출하고 수복하는 과정이 어렵다는 단점이 있었다.
이를 해소하고자, 네트워크 통신에서 이뤄지는 과정을 단계별로 나누고 각 단계 specific한 일을 책임지고 수행할 수 있도록 하는 각각의 프로토콜을 만들었다. 이렇게 나눠진 계층이 OSI 7계층과 TCP/IP 4계층이고, 해당 네트워크 구조들에는 계층 구조에서 정의한 프로토콜이 사용된다.
OSI 7계층은 국제 표준화기구가 편리한 네트워크 통신을 위해 정의한 계층 구조이고, TCP/IP 4계층은 OSI 7계층을 기반으로 만들어져 현재 전세계 인터넷에서 실제로 사용되는 계층 구조이다.
위의 그림과 같이 OSI 7계층의 5~7레이어, 1~2레이어가 TCP/IP의 4레이어, 1레이어로 병합된 구조이다.
위와 같은 계층 구조를 따른 현재 네트워크 참여 기기들은 국가나 OS와는 상관 없이, LAN/WAN을 넘나들며 참여자간 통신이 가능하다.
