목록분류 전체보기 (155)
Rootable의 개발일기
사이클 없는 양수 가중치 그래프에서 최단 거리를 구하는 알고리즘 시간 복잡도 : O(ElogV) (V : 노드 수, E : 에지 수) 📌 핵심 이론 🔎 인접 리스트 다익스트라 알고리즘은 인접 행렬보다 시각 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋다. 🔎 최단 거리 배열 초기화 최단 거리 값을 저장하기 위한 배열을 만든다. 출발 노드는 0, 나머지 노드는 매우 큰 값으로 초기화한다. 🔎 값이 가장 작은 노드 고르기 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 따라서, 출발 노드에서 시작하면 된다. 🔎 최단 거리 배열 업데이트 인접 리스트와 최단 거리 배열 값을 비교하여 둘 중 작은 값으로 최단 거리 배열을 갱신한다. Min(출발 노드의 최단 거리 배열의 값 +..
📌 정의 시작점을 지정하지 않고 그래프에서 모든 노드와 관련된 최단 거리를 구하는 알고리즘 📌 주요 특징 기능 특징 시간 복잡도(노드 수: V) 모든 노드 간에 최단 경로 탐색 - 음수 가중치 Edge가 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근 O(V^3) 📌 핵심 이론 최단 경로를 구했다고 가정했을 때, 그것을 이루는 부분 경로 역시 최단 경로이다. 예를 들어, A에서 B까지 최단 경로를 구했다고 가정한다. 이때, 해당 경로 위에 K 노드가 존재한다면 A에서 K 노드를 거쳐 B에 도착하는 경로 역시 최단 경로라는 것이다. 따라서 점화식은 다음과 같이 도출된다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 📌 접근 방법 🔎 초기 배열 D[S..
📌 입출력이란 컴퓨터 내부 또는 외부의 장치와 프로그램 간의 데이터를 주고받는 것 📌 스트림(Stream) 데이터를 운반하는데 사용되는 연결통로 두 대상 사이에서 데이터를 전달하려면 이들을 연결하는 매개체가 필요하다. 이러한 역할을 수행하는 것이 '스트림'이다. 스트림은 연속적인 데이터의 흐름을 물에 비유해서 붙여진 이름으로, 단방향 통신만 가능하다. 즉, 입력과 출력을 동시에 처리할 수 없다. 이를 해결하려면 서로 반대 방향의 스트림 2개(입력, 출력)가 필요하다. 이를 '입력 스트림(input stream)', '출력 스트림(output stream)'이라 한다. 스트림은 큐와 같은 FIFO(First In First Out) 구조로 되어 있으며, 중간에 건너뜀 없이 연속적으로 데이터를 주고받는..
📌 Wrapper class란 자바의 기본 자료형을 객체로 다루기 위해 사용하는 클래스를 wrapper class라 한다. 자바의 모든 기본 자료형마다 래퍼 클래스가 존재한다. 이러한 클래스를 포장 객체라고 하는데, 그 이유는 기본 타입의 값을 내부에 두고 포장하기 때문이다. 래퍼 클래스로 포장하고 있는 기본 타입 값은 외부에서 변경할 수 없다. 만약 값을 변경하고 싶다면 새로운 포장 객체를 만들어야 한다. 📌 종류 기본 타입(primitive type) 래퍼 클래스(wrapper class) byte Byte char Charater int Integer float Float double Double boolean Boolean long Long short Short 래퍼 클래스는 java.lang 패..