전체 글

인접 행렬이나 인접 리스트를 사용하여 그래프를 저장하는 방식이 일반적이다.`암시적 그래프 (Implicit Graph)`는 명시적인 저장 방식 없이, 문제의 조건을 통해 그래프의 구조를 유추하며 탐색하는 방식이다.미로 탐색, 퍼즐 문제, 최단 거리 문제 등에서 자주 출제되며, 이를 효과적으로 해결하기 위해 반드시 이해해야 한다.암시적 그래프 개념암시적 그래프는 명시적으로 노드와 간선을 저장하지 않고, 탐색하면서 그래프 구조를 동적으로 유추즉, 탐색 과정에서 이동 가능한 정점과 간선을 문제의 조건을 기반으로 판별함예시)아래와 같은 미로가 있다고 가정`1`: 이동 가능`0`: 이동 불가능상하좌우로 이동겉보기에는 그래프로 보이지 않지만, 값이 1인 곳이 이동 가능(노드) 하다는 점과 상하좌우로 이동(간선)할 ..

그리디 알고리즘 (Greedy Algorithm)눈앞의 이익만 우선 추구하는 알고리즘을 총칭하여 `그리디 알고리즘`이라 한다.그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.📌 그리디 알고리즘은 최적화 문제를 대상으로 한다.최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 한다.do{ 가장 좋아보이는 선택을 한다; (매번 최선의 선택)} until(해 구성 완료)그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아 보이는 선택을 반복한다.그리디 알고리즘으로 최적해가 보장되는 예1) 최소 신장 트리 (MST)최소 신장 트리를 위한 프림 알고리즘, 크루스칼 ..

그래프에서는 모든 정점을 방문해야 할 때가 자주 있다.모든 정점을 방문하는 방법은 다양하지만, 대표적으로 BFS와 DFS 방법을 사용할 수 있다.두 방법은 매우 간단하나, 그래프 알고리즘에서 핵심적인 위치를 차지한다.∴ 두 탐색 방법에 대해 아주 깊은 직관을 가져야 할 필요가 있다.트리에 대해 BFS, DFS 수행루트를 시작으로 탐색을 한다면 `BFS`는 먼저 루트의 자식을 차례로 방문함,다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문= 루트에서 가까운 거리 순으로 방문`DFS`는 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려감더 이상 내려갈 수가 없으면 위로 되돌아 오다가 내려갈 곳이 있으면 즉각 내려감 일반적인 그래프 G =(V..

흐름 제어 (Flow Control)파이프라이닝 기반 전송으로 한 번에 무한히 많은 데이터를 주고 받을 수 있는가? 👉 No!수신 측이 송신 측보다 데이터 처리 속도가 빠르면 문제 없지만, 송신 측의 속도가 더 빠를 경우 문제가 생김수신 호스트가 한 번에 받아서 처리할 수 있는 세그먼트의 양에는 한계가 있기 때문에,한계를 초과한 이후 도착하는 패킷은 손실될 수 있고 만일 손실된 경우 불필요한 추가 패킷 전송 발생📌 TCP의 흐름 제어송신 호스트가 수신 호스트의 처리 속도를 고려하여 송수신 속도를 균일하게 유지하는 기능Stop-and-Wait ARQ를 사용하면, 흐름 제어 필요 없음파이프 라이닝 기반 ARQ를 사용하면 흐름 제어 필요!ACK 응답 마다 윈도우 크기를 포함하여, 수신자가 이후 허용 가능한..

전송 계층네트워크 계층과 응용 계층 사이에 위치IP한계 보완: `신뢰`할 수 있는 통신과 `연결`형 통신 기능 제공응용 계층의 프로세스 식별: 포트 번호 활용IP 한계신뢰할 수 없는 통신패킷이 수신지까지 제대로 전송되었다는 보장X통신 과정에서 패킷이 잘못 전송되어도 확인X, 재전송X, 순서대로 도착 보장X비연결형 통신송수신 호스트 간에 사전 연결 수립 작업X그저 수신지를 향해 패킷을 보내기만 함∴ IP 패킷의 전달 = 신뢰성이 없는 통신 + 비연결형 통신IP는 왜 신뢰할 수 없는, 비연결형 통신을 하는가 ?비연결형 통신이 나쁜 게 아님👉 신뢰할 수 있는 연결형 통신 = `성능`에 악영향신뢰성 있는 전송이 모든 경우에 필요한 게 아님간단함연결 유지 & 상태 저장X = 라우터가 가볍고 빠르게 작동확장성수십..

TreeSet이나 TreeMap 같은 컬렉션에 저장되는 객체는 저장과 동시에 오름차순으로 정렬이때, 어떤 객체든 정렬될 수 있는 것이 아닌, 객체가 `Comparable` 인터페이스를 구현하고 있어야 가능함Integer, Double, String 타입은 Comparable을 구현하고 있으므로 상관 없음📌 사용자 정의 객체를 저장할 땐 반드시 Comparable을 구현해야 함Comparablecomparable 인터페이스에는 `compareTo()` 메소드가 정의돼 있음∴ 사용자 정의 클래스에서 이 메소드를 재정의하여 비교 결과를 정수 값으로 반환해야 함리턴 타입메소드설명intcompareTo(T o)주어진 객체와 같으면 0,주어진 객체보다 적으면 음수,주어진 객체보다 크면 양수 리턴Comparator..

자바는 널리 알려진 자료구조를 바탕으로, 객체들을 효율적으로 추가, 삭제, 검색할 수 있도록 관련된 인터페이스와 클래스들을 `java.util` 패키지에 포함시켜 놓음👉 이를 총칭하여 컬렉션 프레임워크라고 부름List와 Set은 객체를 추가, 삭제, 검색하는 방법에 있어서 공통점이 있기에 공통된 메소드만 따로 모아 Collection 인터페이스로 정의 & 상속Map은 키와 값을 하나의 쌍으로 묶어서 관리하는 구조로 List와 Set 과는 사용방법이 다름❓ 인터페이스로 구현한 이유처음에는 공유 코드가 없어서 인터페이스로 설계 했으나, 시간이 흐르며 공통 기능이 필요해졌고 이를 해결하기 위해 `default` 메서드가 도입 됨인터페이스 분류특징구현 클래스CollectionList순서를 유지하고 저장중복 저..

그래프(Graph)는 객체 간의 연결 관계를 표현하는 자료구조노드(Node) 또는 정점(Vertex)과 이를 연결하는 간선(Edge)으로 구성됨.그래프의 활용그래프는 연결 관계를 표현하는 자료구조로, 현실 세계의 다양한 개체와 관계를 모델링할 수 있음SNS 분석사용자 간의 팔로우 관계교통망 & 지도 데이터도시, 도로정거장, 정거장 연결 선컴퓨터 네트워크라우터와 그 연결 관계종류무방향 그래프 (Undirected Graph)간선에 방향성이 없는 그래프, 두 노드는 `양방향`으로 연결됨A → B로 갈 수 있고, B → A로 갈 수 있음 = 서로 연결된 상태방향 그래프 (Directed Graph)간선에 방향성이 있는 그래프, A → B로 향하면, A에서 B로만 이동 가능들어오는 간선과 나가는 간선으로 구분 ..