파게로그

TCP(Transmission Control Protocol) vs UDP(User Datagram Protocol) OSI Model (7 Layers) 물리 계층 기능: 비트 스트림 전송 프로토콜: RS-232 장비: hub, repeater 데이터링크 계층 기능: 데이터 전송 오류 감지, 오류 시 재전송, MAC 주소를 통해 통신 프로토콜: HDLC, PPP, 프레임 릴레이, ATM 장비: 스위치, 브리지 네트워크 계층 기능: 주소(IP) 정하기, 경로(Route) 선택, 패킷 전달. 네트워크 라우팅 프로토콜: IP, ARP, RARP, ICMP, IGMP, ... 장비: 라우터, L3 스위치 전송 계층 기능: 전송 속도 조절. 오류 처리. 헤더에 송,수신지 포트번호를 포함하여 세션 계층에 전달 프..

문제 링크: 3687번 제목 https://www.acmicpc.net/problem/3687 1. 최댓값 만들기 어려운 부분이 없다. 최댓값을 만들고자 한다면 먼저 ①자리수 ②앞자리를 고려해야 한다. 즉 자리수를 무작정 늘린 후 앞자리를 가장 크게 하면 된다. 이를 위해 성냥을 가장 적게 필요로 하는 1을 최대한 만든다. n이 홀수일 때는 3개를 이용해 7을 하나 만들고 맨 앞에 배치하여, 남는 성냥이 없도록 한다. 2. 최솟값 만들기 숫자를 쭉 나열하다보면 뭔가 규칙이 보인다. 성냥의 개수 최솟값(독립적) 최솟값(의존적) 2 1 1 3 7 7 4 4 4 5 2 2 6 6 0 7 8 8 8 10 01 9 18 07 10 22 04 11 20 02 12 28 00 13 68 08 14 88 88 15 1..

문제 링크: 16724번 제목 https://www.acmicpc.net/problem/16724 마치 섬의 개수를 세듯이, 어딘가에서 연결되어 있는 덩어리의 개수만큼만 SAFE ZONE이 있으면 된다. 임의의 점 P를 잡았을 때, 해당 P에 쓰인 화살표부터 끝까지 따라가면 이미 방문했던 어딘가가 나오게 되므로 해당 덩어리를 모두 탐색한 것이다...라고 하면 거짓말이고, P가 해당 덩어리의 '처음'이라는 보장은 없다. 위 그림에서, 하늘색 부분은 임의의 점을 택하더라도 반드시 모든 점을 순회하게 되지만, 연두색이나 연노란색 부분은 그렇지 않다. 특히 연두색의 경우 2행 2열을 먼저 확인하게 되는데, 그러면 2행 2열과 2행 3열은 다른 덩어리로 분류되어버린다. 따라서 이전 노드 또한 함께 확인하여 덩어리..

Java에서는 다음과 같이 구현할 수 있다. 물론 인덱스 값을 주었기에, 완전히 동일한 형식으로 char[]를 사용해도 된다. 워낙 유명한 내용이라 다른 책이나 블로그와 큰 차별점은 없겠지만 조만간 설명 추가할 예정 class Node { Node[] ch; boolean end; Node() { ch = new Node[26]; end = false; } void insert(String s, int idx) { if (idx == s.length()) { end = true; return; } int now = s.charAt(idx) - 'a'; if (ch[now] == null) ch[now] = new Node(); ch[now].insert(s, idx + 1); } boolean find(..

문제 링크: 13334번 제목 https://www.acmicpc.net/problem/13334 개선의 여지가 꽤 남아있는 코드이다. list는 각 사람들의 'home' 주소의 목록이다. 그리고 59라인에서도 알 수 있듯, 탐색은 'home' 기준으로 진행한다. 왜 그럴까? rail 길이 내에 들어가는 최대 경로(home-office 경로)의 개수를 구하는 과정을 잘 생각해보면, rail은 반드시 어떤 경로의 'home'에서부터 시작해야 한다. 그렇지 않다면 일부 경로를 포함하지 못하거나, 또는 기껏해야 같은 경로의 수를 포함할 뿐이다. 한편 hq는, 현재 begin부터 rail 길이를 봤을 때, 여기에 포함되는 경로들이다. 60라인은 hq의 경로 중 home이 begin보다 작은 것들을 제외하는 과정..

문제 링크: 1967번 트리의 지름 https://www.acmicpc.net/problem/1967 풀이 자체는 상당히 직관적인데, 전제에 대한 '직관'만 있는 것에 대한 증명을 누군가 잘 해주셨다(다만 댓글을 꼭 읽어야 한다). https://blog.myungwoo.kr/112 처음에 하나의 정점 u로부터 가장 먼 정점 v를 찾을 건데, 일단 루트를 u로 해서 v를 찾는다. 그 다음, v로부터 가장 먼 정점을 찾는다. 그리고 두 정점 간의 거리를 출력한다. 이렇게 DFS 2번을 사용하는 것이 마치 국룰과 같은 풀이이다. 하나는 아직은 잘 이해되지 않는 DP 풀이이다. 트리 DP는 앞으로도 계속 사용될 것이기에 꼭 살펴보아야 한다. https://suuntree.tistory.com/172 impor..

문제 링크: 프로그래머스 Lv. 3 보석 쇼핑 https://programmers.co.kr/learn/courses/30/lessons/67258 투 포인터를 통해 해결할 수 있는 문제이다. left와 right를 움직여주면서 [left, right] 구간 내에 모든 보석이 1개 이상 포함된다면, 이 때 시작 진열대 번호와 끝 진열대 번호를 갱신한다. 이러한 과정에서 left와 right는 다음과 같이 움직인다. 구간 내에 모든 보석이 포함되어 있다면? 이 때에는 크기를 줄여본다. 즉 left를 1 증가시킨다. 구간 내에 모든 보석이 포함되어 있지 않다면? 이 때에는 더 많은 보석을 보아야 한다. 즉 right를 1 증가시킨다. 한편 구간 내에 모든 보석이 포함되어 있는지의 여부에 대해서는 어떻게 알 ..

문제 링크: 21316번 제목 https://www.acmicpc.net/problem/21316 "반드시 그림과 같은 모습임이 보장된다"에서, 그림을 통해 Spica의 특징(?), 즉 Spica를 변별해낼 수 있는 유일한 성질을 발견해야 한다는 것을 알 수 있다. 점 i와 연결되는 점의 개수를 f(i)라고 하고, 점 i와 연결되는 점을 i[1], i[2], ..., i[n]이라고 하면, Spica만 유일하게 f(i) = 3이면서 f(i[1])+f(i[2])+...+f(i[n]) = 6이다. 이 그림에서, Spica는 7이고, 7과 연결되는 점은 6, 3, 8이다. 그리고 f(6)= 1, f(3) = 3, f(8) = 2이다. 반면 f(i) = 3을 만족하는 다른 점들, 즉 3, 4, 9의 경우 f(i[..