백트래킹으로 접근하고자 생각했다.주어진 단어들을 무제한 사용할 수 있음으로, 문자열을 해석하는 각 순간에 같은 단어를 여러번 사용할 수 있다.알고리즘주어진 인덱스부터 적용가능한 모든 단어들을 탐색한다.해석가능한 단어를 찾는다.2-1. dp테이블에 현재까지의 비용을 계산 후, 최솟값으로 업데이트 한다.2-2. 업데이트 시, 2 부터 다시 시작한다.2-3. 업데이트가 안될 시, 이를 무시한다.(2) 과정을 통해 특정 인덱스에서 실행 가능한 최소비용으로만 프로그램을 실행할 수 있도록 한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import j..

OS가 Tcp Connection을 어떻게 적절한 Socket으로 넘기는지 탐구한다.1. 문제 인식이전까지, TCP 패킷들은 포트번호를 통해 프로세스로 통한다고 이해하고 있었다. 이에 따라, ServerSocket이 TCP Connection을 받을때 새로 생성되는 소켓은 항상 새로운 포트를 점유하고, 클라이언트는 이 소켓과 통신한다고 이해했었다. 결론부터 말하자면, 틀렸다. OS는 TCP 패킷을 수신하면 이를 Socket Pair를 확인하여 적절한 Socket으로 매핑한다. 2. 이론출처 1: 컴퓨터 네트워킹 하향식 접근 55p출처 2: UNIX Network Programming : The Sockets Networking API https://books.google.co.kr/books?id=ptS..

1. 과제 소개 Scanner 는 입력 Character Stream 을 Token Stream 으로 변환하는 역할을 컴파일러 내에서 수행합니다. 각각의 토큰들을 식별하기 위한 Recognizer 들을 내부적으로 가지며, 각각의 Recognizer 는 Scanner Generator 가 RE(Regular Expression)을 바탕으로 생성한 DFA 를 통해 각각의 토큰을 식별합니다. Scanner Generator 가 RE 를 바탕으로 한 DFA 의 생성은 다음과 같은 과정으로 이루어집니다. RE to NFA w/ε-move NFA w/ε-moves to DFA DFA → Minimized DFA DFA→RE 이번 과제는 위 네가지 과정 중 첫번째 단계, RE to NFA w/ε-move 과정에 집중..

다익스트라 알고리즘은 어떤 그래프 내에서 출발노드를 지정하여, 출발 노드에서 모든 노드로의 최소비용을 구하는 알고리즘이다. 다익스트라 알고리즘은 다음과 같은 순서로 진행된다. 출발 노드를 정한다. 출발 노드로부터 갈 수 있는 모든 노드들에 대해 최소비용을 갱신한다. 방문하지 않은 노드중 최소비용의 노드를 선택한다. 선택된 노드로 부터 갈 수 있는 노드들에 대해 최소비용을 갱신한다. 3 ~ 4를 반복한다. 이 루틴을 구현해 보면 정상적으로 실행된다는 결과는 얻을 수 있었지만, 3번, 왜 방문하지 않은 노드 중 최소값을 선택하는지 개념적으로 이해하지 못했다. 이를 이해하기 위해 먼저 아래 그림에서 1번노드를 출발노드로 실행되는 과정을 살펴 보았다. 아래 그림에서 출발노드인 1번 노드에서 갈 수 있는 노드는 ..