파게로그

헷갈리는 용어들을 간단하게 정리하면 다음과 같다. LCS(Longest Common Substring, 최장 공통 부분문자열) ABCDE, ZBCDZE의 최장 공통 부분문자열은 BCD(연속성이 요구됨) LCS(Longest Common Subsequence, 최장 공통 부분수열) ABCDE, ZBCDZE의 최장 공통 부분수열은 BCDE(연속성이 요구되지 않음) LIS(Longest Increasing Subsequence, 최장 증가 부분수열) 5 2 4 3 7 8 1 9의 최장 증가 부분수열은 2 3 7 8 9(연속성이 요구되지 않음) 다음을 예시로 해서 Longest Common Substring, Longest Common Subsequence의 길이를 구해보자. s1 = "POCKETNIZED" ..

문제 링크: 9935번 제목 https://www.acmicpc.net/problem/9935 s = ABCABCDEDE, p = ABCDE인 경우를 생각해보자. 스택에 C, 2 B, 1 A, 0 를 push한 이후, 다시 A를 만나게 되면, 패턴과 일치하지 않는다. 다만 새로 만나게 된 문자가 A로서 패턴의 첫 번째와 일치하므로(그렇지 않다면 A -1을 넣었을 것) A, 0을 넣어준다. 이렇게 하면, E, 4가 스택에 push된다는 것은 곧 패턴과 일치하는 문자가 스택에 포함되어 있다는 것을 보장한다. 따라서 p의 길이만큼 스택을 pop한다. pop한 이후에는, pi를 스택의 top의 idx 다음 것으로 해서 패턴이 계속해서 연속되는지 확인한다. import java.io.IOException; imp..

방향이 있는 그래프(directed graph)에서 꼭짓점들이 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 대개 많이 언급되는 예시로 대학 강의에서의 선수과목 체계가 제시된다. 너무 질리니까 여기서는 게임 스킬트리의 일종이라고도 할 수 있는, 스타크래프트의 프로토스 테크트리로 대체해서 설명한다. 다음은 모든 건물들을 제시하고 있지는 않지만, 실제 선결 조건들이 제시되어 있다. 위상정렬은 위와 같이 비순환 유향 그래프(DAG, directed acyclic graph)의 건물들을 선후 관계에 따라 정렬하고자 할 때 이용되며, 그 결과는 여러가지일 수 있다. 위상정렬을 수행하기 위해서 비순환 그래프이어야 하는 이유, 즉 사이클이 존재하지 않아야 하는 이유는, 사이클이 있으면 시작점을 어느 정점으로 ..

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보다 작은 것들을 제외하는 과정..