https://www.acmicpc.net/problem/2618 질문게시판에서 힌트 하나를 얻고 푼 문제..처음에는 스티커 문제처럼 어떤 사건을 경찰차 1이 해결한 경우, 경찰차 2가 해결한 경우로 나누어서 테이블을 구성하고,dp[w][1] = 사건 w를 경찰차 1이 해결했을 때, 그때까지 두 경찰차의 최소 이동거리 합 =min( dp[w-1][1] + dist(w-1, w) , dp[w-1][2] + dist(w-1을 경찰차 2가 해결한 최적해에서의 경찰차 1의 위치, w) ) 로 두고 dp[w][1], dp[w][2] 로 이루어진 2차원 배열로 풀려고 했다. 이렇게 말로만 적어도 벌써부터 점화식이 복잡한데, 이 점화식은 안타깝게도 틀렸다.비교하고 있는 두 값이 '같은' 경우 어떤 값을 취할 지 정할..
https://www.acmicpc.net/problem/1450 문제 풀이 주어진 물건들을 가방 안에 담을 수 있는 모든 경우의 수를 출력하는 문제나이브하게 접근하면 물건이 최대 30개 있으므로, 2^30 조합을 모두 시도해보면 된다.하지만 이렇게 접근하면 최악의 경우 1,073,741,824 가지의 경우의 수가 나오기 때문에 시간초과가 발생한다.따라서 meet in the middle 테크닉을 이용하여 시간을 줄이는 것이 이 문제의 핵심이다. '중간에서 만나기' 라는 이름으로도 불리는 이 테크닉은, 사이즈가 큰 전체 대상을 처음부터 끝까지 직접 탐색하는 것보다,전체 영역을 반으로 나눈 뒤, 반씩 쪼개서 탐색한 결과를 조합하여 해답을 구하는 기법이다. 이 문제의 경우, 2^30의 조합을 모두 구하는 것..
https://www.acmicpc.net/problem/2179 가장 긴 prefix를 구하는 건 쉬운데, 입력된 순서상 앞선 조합을 골라내는 것이 까다로운 문제가장 긴 prefix를 구할 때는 단어를 정렬해서 한번 순회하면 O(n log n) 시간에 구할 수 있다. 이때 같은 길이의 prefix에 대해서 입력이 먼저된 단어를 출력해야 한다.그래서 단어를 저장할 때, 입력된 순번도 같이 저장했다. n = int(input())l = []for i in range(n): s = input().rstrip() l.append((s, i)) 단어를 정렬하고 순회하면서 prefix를 체크할 때는 별도 함수를 사용했다.이때 같은 prefix 를 갖는 단어들을 모두 저장하기위해 딕셔너리와 셋을 이용했다..
[ '돈의 시나리오 - 김종봉, 제갈현열' 을 읽고 생각을 정리한 글입니다. ] 이 책은 제목 그대로 자신만의 '돈의 시나리오'를 만들고 이를 기반으로 돈을 벌 수 있는 방향을 제시하는 책이다.그런데 돈과 관련된 내용보다 이 책에서 제일 기억에 남는 구문은 다음 구문이었다. 자신에게 온전히 시간을 쏟는 사람은 불행하지 않다.그 사람의 시간에 타인의 시선, 타인의 감정이 들어설 틈이 없기 때문이다....그리고 투자자에게 이 사실은 아주 중요하다.투자는 돈이 아닌 시간을 쏟는 행위이며투자자는 자신을 위해 시간을 쏟는 행위이다.나는 당신이 투자자가 되어야 한다고 주장할 참이지만많은 돈을 버는 사람이 되길 바라는 마음보다는스스로 만족하는 의미있는 삶을 살아갔으면 하는 마음이 더 크다.당신이 흔들리지 않고 자신의..
https://www.acmicpc.net/problem/30804 탕후루 꼬치에서 앞 뒤로 몇개의 과일을 빼 2가지 종류 이내로 구성된 가장 긴 길이의 탕후루 꼬치를 만드는 문제다.처음에는 단순 구현을 해야하나 싶어서 한참 고민했는데, 앞 뒤로 과일을 뺀다는 것은 남은 과일이 연속적이라는 점에서 힌트를 얻어 투 포인터를 생각해낼 수 있었다. 앞에서부터 과일을 하나씩 살펴보면서 2가지 종류가 되지 않았다면 연속된 길이에 포함하고, 2가지가 넘는 종류가 나오는 순간 그때까지 담은 길이를 정답 후보로 체크한다.그리고 그 이전에 담았던 과일 중, 제일 마지막에 나왔던 종류가 아닌 과일을 2가지 종류에서 제외하고, 새로 나온 종류를 2가지 종류에 추가한 뒤 위 과정을 반복한다. n = int(input())fr..
벌써 2024년 1학기가 끝났다.3월 개강한 이후부터 정말 정신없이 시간이 흘러간 것 같다.이제 1~4월 회고에 썼던 내용을 돌아보며, 1학기 종강을 되돌아보고, 여름방학 계획을 세워보려고 한다. 2024년 목표 2차 점검개발과 관련된 목표 1. 전공 과목 모두 A+ 맞을 수 있도록 공부하기아직 성적이 나오진 않앗지만 우선 시험을 다 보고난 이후 느낌으로 생각하기에 이 목표는 달성하지 못했다.알골은 수학이니 그렇다고 해도 컴네는 정말 열심히 공부했는데, 기말에 시험을 망치는 바람에 A+은 힘들 것 같다.정말 열심히 공부했던 과목인데 많이 아쉽다.. (수정) 오늘 성적이 나왔는데 다행히 모두 A+이 나왔다! A+이 안나올 거라고 생각했는데 다행이다..! 그래도 성적보다 중요한 건 실제로 내가 잘 이해하고..
https://www.acmicpc.net/problem/17472구현 + MST 섬의 위치가 격자판 모양으로 주어질 때, 격자판 모양으로부터 그래프를 직접 정의하고, 그 그래프에 대해 MST를 찾으면 됩니다.이런 복잡한 문제는 어떤 것들을 구현해야 하는지 잘 나눠서 생각하면 구현하기 좋습니다.(그래도 이 문제는 구현이 엄청 복잡한 편까지는 아닙니다.) 먼저 섬부터 찾아보겠습니다.섬을 찾는다는 것은 격자판을 그대로 그래프로 보았을 때, 컴포넌트를 찾는 것과 같습니다.# 섬 찾기island_number = 2island_tiles = []for i in range(N): for j in range(M): if board[i][j] == 1: # BFS ..
ICMPInternet Control Message Protocol 의 줄임말이다.trace route를 하는 과정을 통해 ICMP 동작을 살펴본다. 원래 ICMP의 목적은 호스트나 라우터에서 error reporting 목적으로 사용되는 프로토콜이다.(호스트나 라우터에 도달할 수 없다든가, 프로토콜이 존재하지 않는다거나) 또는 ping 프로그램에서 요청/응답을 echo 하는데 사용한다. 이 프로토콜은 3계층 프로토콜이지만, 마치 TCP 처럼 IP 위에 존재하는 프로토콜이라, ICMP 메세지는 IP 데이터그램의 데이터로 들어간다. 그래서 이때는 IP 헤더에 프로토콜을 가리키는 부분에 ICMP 정보가 들어간다. ICMP 메세지는 다음과 같은 구조를 가진다. Type, Code 로 구성된다.(0, 0) 이면..
이전에 정리한 SDN은 data plane 관점에서의 SDN 이었다.이번엔 control plane 관점에서 SDN을 정리해보자.즉, 어떤 OpenFlow 기반의 라우팅 테이블이 어떻게 만들어지는지, 누가 만드는지를 살펴보자. SDN인터넷 네트워크 계층인 기본적으로 분산 라우터 기반의 control approach를 쓰고 있다.라우터끼리 라우팅 도메인(AS, 정확히는 area) 내에서 정보를 교환해서 각 라우터가 스스로 라우팅 알고리즘도 결정해서 포워딩 테이블을 만들었다. 이 방식은 최초의 라우터를 만든 CISCO 사에서 시작했다.그때는 라우터를 만들면서 당연히 장치에 필요한 소프트웨어를 다 넣어서 같이 팔았다.온전한 일체형 제품을 판 것이다. (이를 가리켜 monolithic router 라고 한다.)..
BGPBGP (Border Gateway Protocol) 는 ISP 사이의 통신 표준이다.이 프로토콜을 따르지 않으면 다른 AS하고 통신할 방법이 없기 때문에, 모든 라우터 벤더들이 이 프로토콜을 따른다.이 프로토콜은 인터넷을 연결시켜주는 접착제 역할을 한다. intra-AS routing protocol 은 심지어 프로토콜 자체를 안써도 상관없다.우리는 그냥 라우팅 프로토콜 없이 어떤 목적지로 갈 때는 static 하게 무조건 이 길로 간다라고 해도 상관이 없다.하지만 그런 AS도 다른 AS와 연결되고 싶다면 이 프로토콜을 써야 한다. 가령 위 그림과 같이 네트워크가 구성되어 있다고 해보자.AS X 에 속한 A 컴퓨터에서 트래픽을 발생시켰는데, 목적지를 가는 길에 AS Y 를 거쳐야 한다고 하면, ..
