RAINBOW-LAB

- 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. - 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. Participant completion return ["leo","kiki",..

DB의 관계 스키마가 잘못 설계되어 데이터가 불필요하게 중복되게 된다면 어떠한 문제가 있을까? 1) 삭제 이상 한 튜플을 삭제함으로써 유지해야 될 정보까지도 삭제되는 연쇄 삭제 현상이 일어나게 되어 정보 손실이 발생한 것 2) 삽입 이상 불필요하고 원하지 않는 데이터도 함께 삽입해야되고 그렇지 않으면 삽입이 되지 않는 현상 3) 갱신 이상 중복된 튜플 중에서 일부 튜플만 애트리뷰트 값을 갱신시킴으로써 정보의 모순성(inconsistency)가 생기는 현상 이와 같은 이상들이 생기는 근본적인 이유는 무엇인가? 그것은 여러 가지 상이한 종류의 정보를 하나의 릴레이션으로 표현하려 하기 때문이다. 즉, 애트리뷰트 간에 존재하는 여러 가지 데이터 종속 관계를 무리하게 하나의 릴레이션으로 표현하려는데서 이러한 이상..

초기의 데이터 처리 시스템에서는 각 응용 프로그램이 개별적으로 자기의 데이터를 "File" 로 관리 유지하였다. 데이터를 공용할 수 없는 이러한 파일 시스템에서의 가장 큰 문제점은 크게 데이터 종속성(Data dependency)과 데이터 중복성(Data redundancy)으로 집약시킬 수 있다. 1. 데이터 종속성 데이터 종속성이란 응용 프로그램과 데이터 간의 상호 의존 관계를 말한다. 데이터 파일이 보조 기억장치에 구성되는 방법이나 저장된 데이터의 접근 방법이 각 응용 프로그램 속에 명세되어야 하는 상황에서 자연히 응용 프로그램은 접근하려는 데이터의 구성 방법이나 접근 방법에 맞게 작성되어야 한다. 따라서 데이터의 구성 방법이나 접근 방법을 변경 시킬 때는 자연히 이것을 기초로 한 응용 프로그램도 ..

◎ Greedy Algorithm 이란? 탐욕 알고리즘(Greedy Algorithm) 이란, 최적해를 구하는데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다. '순간' 이라고 정의하는 선택은 Local 하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그것이 최적이라는 어떠한 보장도 없다. 탐욕 알고리즘에는 대표적으로 '분할 가능 배낭문제' 가 있는데, 다음과 같은 예시를 들어보자. 한 은행의 화폐 단위가 7원/5원/1원 이라고 하자. 한 사람이 14원의 돈을 들고 화폐를 교환하려고 은행에 들렀다. 은행은 Greedy Algorithm을 사용하여 ..

오일러 경로(Eulerian trail) 란 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때 시작점과 도착점이 같으면 오일러 회로(Circuit) 가 됩니다. 가장 대표적으로 별 모양 그래프가 있는데 어느 점에서 시작하더라도 모두 출발점으로 되돌아 올 수 있습니다. 즉, 위 그래프는 오일러 회로가 존재합니다. 위 그래프를 다시 보면 모든 정점의 차수가 2(짝수)인데 시작점과 끝점을 제외하고서는 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 마련되어 있어야 하기 때문입니다. 그렇기에 항상 차수가 2의 배수꼴로 붙게 됩니다. 오일러 경로의 존재여부를 판단하는 방법은, 무향 그래프(non-directed graph)일 경우 Degree가 홀수 인 정점(Vertex)가..

어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이 동적계획법(Dynamic Programming) 이다. Divide-and-conquer 와 비슷해 보이지만 DC는 문제를 큰 부분에서 작은 부분으로 나누는 Top-Down approach인데 반해, DP는 작은 문제부터 큰 문제로 풀어가는 Bottom-Up approach이다. 또한 DC는 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만 DP는 이전 단계의 답에 의존적이다. 그래서 한 번 푼적 있는 문제는 다시 풀지 않도록 테이블에 저장해둔다. 정리하면, 1. 문제를 작은 부분 문제로 나눈다. 2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다. (Mem..

1. P 문제 현실적으로 쓸만한 알고리즘이라면, 그 비용이 견딜만큼 현실적인 알고리즘이라는 것이다. 알고리즘의 Time complexity가 입력 크기 n에 대해 상수 k승을 가진다면 '현실적' 이라고 본다. 예를 들어 $$O(n^2)$$ 혹은 $$O(n^3)$$등이 있다. 입력 크기가 커지면 다항으로 증가하는 비용(Polynomial Complexity)이다. 즉, 현실적인 비용으로 풀 수 있는 문제들, 다항(Polynomial) 알고리즘이 있는 문제들을 'P 클래스 문제' 라고 한다. 2. NP 문제 어려운 문제의 경계에 가까이 있는 문제들의 집합을 'NP클래스 문제' 라고 한다. 운에 기대면 현실적인 비용으로 해결할 수 있는(Non-Deterministic polynomimal) 문제들이다. 운에 ..

Network 에서 패킷의 오류를 검출하기 위해 CheckSum이라는 헤더의 Field를 사용한다. CheckSum방법은 상대적으로 패킷 오버헤드가 적은데, 예를 들어 TCP와 UDP는 16bit만 사용한다. (TCP의 헤더크기는 20byte, UDP는 8byte) Checksum은 보안 관점에서 사용되는 Hash Function보다는 취약한 무결성 검증 방법이다. Transport 계층은 일반적으로 호스트의 OS의 일부로서 Software로 구현된다. 즉, Transport계층의 오류 검출이 Software로 구현되므로 CheckSum처럼 간단하고 빠른 오류 검출 기법이 필요하다. 반면에 Data Integrity를 위한 보안 관점의 Hash는 예로, 대표적인 Hash 알고리즘인 MD5는 길이로만 봐도..

◎ 신뢰적인 데이터 전달 프로토콜의 구축 완전히 신뢰적인 데이터 전송 프로토콜에 도달하기 위해 조금씩 복잡해지는 일련의 프로토콜을 소개한다. 1. 완벽하게 신뢰적인 채널 상에서의 신뢰적인 데이터 전송 : rdt 1.0 먼저, 하위 채널이 완전히 신뢰적인 가장 간단한 경우를 고려한다. 프로토콜 자체는 단순하며, rdt(reliable data transfer) 1.0이라 부르겠다. rdt 1.0은 송신자와 수신자에 대한 유한상태 머신(Finite-State Machine, FSM) 이다. 위의 Figure 3.9(a) 는 송신자의 동작을 정의하고, 3.9(b) 는 수신자의 동작을 정의한다. 송신자에 대해 그리고 수신자에 대해 분리된 FSM이 있다는 것에 유의해야한다. 변화를 일으키는 Event에 대해서는 ..

프로토콜 rdt3.0 은 기능적으로 정확한 프로토콜이다. 오늘날의 고속 네트워크에서 누구나 이것의 성능에 만족하지는 않는다. rdt 3.0 의 핵심적인 성능 문제는 stop-and-wait방식이라는 것이다. 이러한 특별한 성능 문제에 대한 간단한 해결책으로, Stop-and-Wait 동작하는것 대신에 송신자에게 확인 응답을 기다리지 않고 여러패킷을 전송하도록 허용하는 것이다. 이러한 신뢰적 데이터 전송 프로토콜 기술을 "파이프라이닝(Pipelining)" 이라고 한다. 파이프라이닝 방식은 데이터 전송 프로토콜에서 다음과 같은 중요성을 가지고 있다. 1) 순서번호의 범위는 증가되어야 한다. 각각의 전송중인 패킷은 유일한 순서번호를 가져야하고, 거기에 전송 중이고 확인 응답이 안 된 여러 패킷이 있을지도 모..