문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60061 [2020 카카오 블라인드]에서 나왔던 문제. 너무 생각을 복잡하게 하고, 이상하게 해서 오래 걸렸다. 문해력이 부족한 탓일까? 문제 핵심 및 풀이 제한 사항 분석 제한사항을 보면 n은 최대 100이기 때문에, 100x100이 한계이다. 또한 build_frame이라는 구조물의 설치/삭제 커맨드는 최대 1000개까지 들어온다. 100x100x1000 = 10^7 으로 완전탐색을 해도 상관이 없다. 구조물을 어떻게 표현할 것인가? 이것도 나름 생각이 필요했다. 문제에서 기둥은 위로 설치하고, 보는 오른쪽으로 설치한다고 했다. 그래서 이를 설치가 시작된 곳의 좌표로, 구조물을 표현했다..
GBN(Go-Back-N, N부터 반복) 프로토콜 프로토콜 이름은 손실이 있거나 아주 긴 지연된 패킷이 있을 때의 송신자 동작으로부터 유래됨 해당 프로토콜에서 송신자는 확인응답을 기다리지 않고 여러 패킷을 전송할 수 있다. 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크면 안 된다. GBN 프로토콜의 사용으로 송신자는 패킷으로 파이프라인을 채우는 것이 가능해짐 송신자 관점의 순서 번호 범위 base : 확인응답이 안 된 가장 오래된 패킷의 순서 번호 nextseqnum : 사용되지 않은 가장 작은 순서 번호 전송될 다음 패킷의 순서 번호 4가지 순서 번호 범위 간격 [0, base-1] 순서 번호는 이미 전송되고 확인응답된 패킷에 대응된다. 간격 [base, nextseqnum-1] 송신..
rdt3.0 비트 오류와 손실 있는 채널상에서의 신뢰적인 데이터 전송 2가지 부가 내용을 프로토콜로 생각해야 함 어떻게 패킷 손실을 검출할 것인가? 새로운 프로토콜 메커니즘을 추가해야 함 패킷 손실이 발생했을 때, 어떤 행동을 할 것인가? 체크섬, 순서 번호, ACK 패킷, 재전송의 사용 송신자에게 손실된 패킷의 검출과 회복 책임을 부여 송신자의 손실된 패킷의 검출 가정 송신자가 데이터 패킷을 전송하고, 패킷 또는 수신자 패킷에 대한 ACK를 손실 → 송신자에게는 수신자로부터 어떠한 응답도 없음 송신자가 패킷을 잃어버렸다고 확신할 정도로 충분한 시간을 기다릴 수 있다면, 패킷을 재전송 가능 패킷 손실 확신을 위해선 얼마나 기다려야 할까? 적어도 송신자와 수신자 사이의 (왕복 시간 지연 + 수신 측에서 패..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118668?l [2022 KAKAO TECH INTERNSHIP]에 나왔던 문제 현재 프로그래머스에서 정답률은 20%로 Level 3 중에서도 낮은데, 실제 시험에서는 훨씬 더 낮지 않았을까? 다른 사람이 푼걸 보니, 꽤나 풀이법이 다양하게 나오는 문제였다. 그리고 최적화를 아주 깐깐하게 보는 문제였다. 문제 핵심 및 풀이 행동의 선택지 생각하기 어떻게 보면 문제를 그냥 정리하는 것일 수도 있는데, 난 여기서 큰 힌트를 얻었다. 점수는 알고력과 코딩력이라는 2가지의 유형이 존재하므로, 이를 각각 A, B라고 두겠다. 초기 점수가 (A, B)라고 생각해 보자. 최단 시간을 얻기 위해 할 수 ..
rdt 1.0 rdt 1.0 : 완벽하게 신뢰적인 채널상에서의 신뢰적인 데이터 전송 프로토콜 하위 채널이 완전히 신뢰적인 가장 간단한 경우 유한 상태 머신(FSM) 정리 rdt1.0 송신자와 수신자에 대한 유한상태 머신(finite-state machine) (a) : FSM은 송신자의 동작을 정의 (b) : FSM은 수신자의 동작을 정의 송신자와 수신자는 분리된 FSM을 가진다. 해당 그림에서 송신자와 수신자 FSM은 각각 하나의 상태만을 가진다. 하나의 상태를 가지므로, 전이는 그 상태로부터 자신으로 되돌아옴 유한 상태 머신 표기 점선 화살표 : FSM의 초기 상태 액션(action) : 이벤트가 발생했을 때 취해지는 것 가로선 아래에 나타냄 이벤트(event) : 전이를 일으킴 가로선 위에 나타냄 ..
신뢰적인 데이터 전송의 원리 신뢰적인 채널의 서비스 추상화 상위 계층 객체에게 제공에게 제공된다. 데이터가 전송될 수 있는 신뢰적인 채널의 서비스 추상화이다. TCP 인터넷 애플리케이션에게 제공하는 서비스 모델 신뢰적인 채널에서 전송된 데이터는 손상이나 손실되지 않는다. 모든 데이터는 전송된 순서 그대로 전달된다. 신뢰적 데이터 전송 프로토콜의 의무 - 서비스 추상화를 구현 신뢰적인 전송 프로토콜 ‘아래에 있는’ 계층이 신뢰적이지 않을 수 있어서 어려워진다. 예시 TCP → IP의 바로 상위에 구현된 신뢰적인 데이터 프로토콜 비신뢰적인 종단 간의 네트워크 계층(IP) 신뢰적으로 통신하는 두 종단점 바로 아래에 있는 계층의 구성 단일 물리적 링크(링크 레벨 프로토콜) 전 세계 인터넷 네트워크(트랜스포트 레..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49993? [Summer/Winter Coding 2018~]로 태그가 나와있던데 아무튼 그렇다. 직관적이고 단순하게 생각하면 된다. 복잡하게 생각하면 더 어려워지는 문제인 것 같다. 문제 핵심 및 풀이 선행 스킬 관계 만들기 특정 스킬을 익히기 전에 익혀야 할 스킬을 선행 스킬이라고 하겠다. 이건 단순하게 꼬리물기 구조로 만들어주면 된다."BCD"가 규칙일 때, B → C → D라는 뜻인데, 연속적으로 이루어져 있다.. 이걸 부모 자식 관계로 한번 바꿔서 생각해 보자. C를 배우기 위해선 B가 필요하다. 즉, parent [C] = B가 된다. D라는 스킬을 배우기 위해선 B, C 2개를..
UDP - 최소 기능의 트랜스포트 계층 프로토콜 UDP는 트랜스포트 계층 프로토콜이 할 수 있는 최소 기능으로 동작한다. UDP가 제공하는 기능 다중화/역다중화 간단한 오류 검사 기능 → IP에 아무것도 추가하지 않는다. UDP를 사용한다는 것은 거의 IP와 직접 통신하는 것과 같다. 데이터 전달 과정 애플리케이션 프로세스로부터 메시지를 가져와서 세그먼트를 생성하여 네트워크 계층으로 넘김 세그먼트의 구성 다중화/역다중화 서비스에 대한 출발지 포트 번호 필드와 목적지 포트 번호 필드 다른 2개의 필드 네트워크 계층은 세그먼트를 IP 데이터그램으로 캡슐화하고, 수신 호스트에게 전달하기 위해 최선을 다한다. 세그먼트가 수신 호스트에 도착 UDP는 데이터 전달을 위해 목적지 포트 번호를 사용해 애플리케이션 프로..