분류 전체보기

[백준 1234] 크리스마스 트리 (C++)

1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 레벨이 최대 10이므로 1 + ... + 10 = 55 이다. 따라서 한가지 색을 최대 55개까지만 사용할 수 있다. -> 배열의 크기가 [11][60][60][60]인 이유 cache 배열은 [현재 층][빨간색을 사용한 횟수][초록색을 사용한 횟수][파랑색을 사용한 횟수] = 경우의 수 기저조건은 재귀를 돌면서 현재 층이 N을 넘기면 해당 경우가 있다는 뜻으로 1을 반환하도록 했다. 각 층마다 사용된 색의 개수가 모두 같아야 하고, 각 층마다 색깔에 따라서 순열이..

[Network] 네트워크 계층 : 라우터(Router)

라우터 내부에는 무엇이 있을까? 입력 포트 : 입력 포트의 맨 왼쪽 상자와 출력 포트의 맨 오른쪽 상자로서, 라우터로 들어오는 입력 링크의 물리 계층 기능을 수행한다. 가장 중요한 검색기능은 입력 포트의 가장 오른쪽 상자에서 수행한다. 여기서 포워딩 테이블을 참조하여 도착된 패킷이, 스위칭 구조를 통해 전달되는 라우터 출력 포트를 결정한다. '포트'라는 의미는 물리적인 입출력 라우터 인터페이스(전선)를 의미한다. 애플리케이션과 트랜스포트 계층 사이에서의 소켓과 관련된 포트와는 완전히 다른 의미이다. 스위치 구조 : 라우터의 입력 포트와 출력 포트를 연결한다. 출력 포트 : 스위칭 구조로부터 수신한 패킷을 저장하고 필요한 링크 계층(헤더 확인) 및 물리적 계층 기능(패킷 전송)을 수행해서 출력 링크로 패킷..

[Network] 네트워크 계층 : 개요와 서비스 모델

위 그림은 H1 호스트와 H2 사이를 이루는 간단한 네트워크를 보여 준다. H1에서 H2로 정보를 보낸다고 가정하고, 호스트와 중계 라우터에서 네트워크 계층의 역할을 생각해 보자. H1 네트워크 계층은 H1의 트랜스포트 계층으로부터 세그먼트를 받아 각 세그먼트를 데이터그램으로 캡슐화하고, 인접한 라우터 R1에게 데이터그램을 보낸다. 수신 호스트 H2의 네트워크 계층은, 세그먼트를 추출하여 H2의 트랜스포트 계층으로 전달한다. 각 라우터의 데이터 평면 역할은 입력 링크에서 출력 링크로 데이터그램을 전달하는 것이다. 네트워크 제어 평면의 근본적 역할은 데이터그램이 송신 호스트에서 목적지 호스트까지 잘 전달되게끔 로컬과 퍼 라우터 포워딩을 조정하는 것이다. 포워딩과 라우팅 개념 아래는 네트워크 계층의 중요한 ..

[Database] 개념적 데이터 모델

개념적 데이터 모델은 개체와 속성 그리고 개체간의 관계를 이용하여 현실세계에 존재하는 데이터를 추상화하여 개념적 구조로 표현하는 방법이다. 대표적으로 ER 모델(Entity-Relationship model, ER model)이 있다. 개체(Entity) '사람과 사물 같이 유형의 정보를 가지고 현실세계에 물리적으로 존재하는 실체' 혹은 '개념, 사건 등과 같이 무형의 정보를 가지고 추상적/개념적으로 존재하는 실체' 를 말한다. 예를 들어 서점을 운영하는데 필요한 회원과 도서는 물리적으로 존재하는 개체에 해당되며, 대학 운영에 중요 데이터를 가지고 있는 강의, 과목, 수강 등은 추상적으로 존재하는 개체라고 할 수 있다. 개체는 발생시점에 따라 기본 개체, 중심 개체, 행위 개체로 구분할 수 있다. 기본 ..

[백준 2479] 경로찾기 (C++)

2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 해밍 거리가 1인 경우만 서로 이동이 가능하다. 따라서 모든 정점을 서로 1:1로 보면서(N^2) 해밍거리를 확인하고 1인 경우에 정점을 연결시켜주는 작업을 가장 먼저 한다. 두 번째로 가장 짧은 해밍 경로를 찾아야 하므로 A부터 B까지 최단경로를 구하는 다익스트라 알고리즘을 수행해 준다. 다익스트라 도중 우선순위 큐에 원소를 넣을 때, 큐에 들어가는 정점에 도달하기 직전의 정점이 현재 정점이므로 parent[next] = now 를 통해 이전 정점을 기록해..

[백준 16437] 양 구출 작전 (C++)

16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 각 마을에 있는 늑대와 양의 수를 island 배열에 저장한다. 이때 늑대의 수는 음수로 저장하도록 했다. 양이 1번 섬으로 들어오는 최대 수를 알아야 한다. 따라서 1번 섬에서 시작해서 양을 데려온다는 생각으로 dfs를 수행했다. 1. 만약 현재 섬이 리프 노드이고 양이 살고 있다면 양을 데리고 올 수 있다. return 양의 수 만약 현재 섬이 리프 노드이고 늑대가 살고 있다면 0을 리턴한다. 2. 현재 섬에 살고있는 양 또는 늑대(음수)를 ..

[백준 15591] MooTube(Silver) (C++)

15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net N과 Q가 각각 최대 5000이므로 주어지는 쿼리마다 매번 bfs를 수행해도 시간에 늦지 않을 것이라고 생각했다. 시작점에서 bfs를 수행하면서 다음 영상과의 유사도(USADO)가 K보다 작은 경우 다음 영상은 추천되지 않는다고 생각하면 편하다. K보다 큰 경우에만 다음 영상의 번호를 큐에 넣으면서 bfs를 수행하고 그 수를 카운팅을 해준다면 매 쿼리마다 답을 구할 수 있게 된다. 1 2 3 4 5 6 7 8 9..

[Network] 트랜스포트 계층 : 흐름제어, TCP 연결

흐름제어 수신 호스트는 여러 작업을 하기 때문에 자신에게 들어오는 메시지를 바로바로 읽지 못한다. 이 점을 인지하지 못하고 송신 호스트가 계속해서 메시지를 보내게 된다면 수신 버퍼가 가득차게 되어 오버플로우가 일어나게 된다. TCP는 수신 버퍼의 오버플로우를 방지하기 위해서 수신호스트가 메시지를 읽는 속도와 송신 호스트가 메시지를 보내는 속도를 일치시키는 작업을 하게 된다. 이를 '흐름제어'라고 한다. TCP는 송신 호스트가 수신 윈도우 라는 세그먼트 변수를 유지하여 흐름제어를 제공한다. 파일 전송 환경에서 수신 윈도우를 알아보자. TCP 연결 상에서 A호스트가 B호스트에서 큰 파일을 전송한다고 가정해보자. B호스트는 이 TCP 연결에 수신 버퍼를 할당한다. 이를 RcvBuffer 라고 한다. B호스트는..

[Network] 트랜트포트 계층 : TCP 연결 (연결 지향형)

TCP 연결 TCP의 특징 TCP는 애플리케이션 프로세스가 데이터를 다른 프로세스에게 보내기 전에, 두 프로세스가 서로 "핸드셰이크"를 먼저 해서 연결을 시키는 사전 작업이 필요하다. 따라서 TCP는 연결을 성공시킨 뒤 데이터를 확실하게 주고 받는 연결 지향형이다. 즉, 데이터 전송을 보장하는 파라미터들을 각자 설정하기 위한 사전 세그먼트들을 보내야 한다. 파라미터로는 송수신 포트번호 등이 있다. TCP 프로토콜은 오직 종단 시스템에서만 동작하고 중간의 네트워크 계층의 요소들(라우터, 스위치) 에서는 동작하지 않는다. 따라서 중간의 네트워크 계층의 요소들은 TCP 연결상태를 유지하지 않고, 현재 전송되는 데이터가 TCP 방식인지도 알 수 없다. TCP 연결은 전이중(full-duplex)서비스를 제공한다..

[Network] 트랜스포트 계층 : 다중화와 역다중화

트랜스포트 계층의 다중화와 역다중화에 대해서 알아보자 다중화와 역다중화 애플리케이션의 한 부분으로서 프로세스는 소켓을 가지고 있다. 소켓을 통해서 프로세스와 프로세스가 네트워크를 통해 데이터를 주고받을 수 있다. 위 그림을 보면 트랜스포트와 애플리케이션 계층 사이에 소켓(초록 네모 박스)이 있고 소켓과 프로세스가 연결되어 있음을 볼 수 있다. 따라서 트랜스포트 계층은 메시지를 직접 프로세스로 전달하지 않고 중간 매개자인 소켓에게 전달한다. 이때 애플리케이션이 메시지를 받을 다양한 소켓을 가지고 있을 수 있으므로 각 소켓은 TCP 소켓인지 UDP 소켓인지를 구분하는 식별자를 가지게 된다. 역다중화 트랜트포트 계층에 상대 프로세스로부터 수신된 세그먼트 필드 집합이 있다. 이들은 사전에 설정된 트랜스포트 프로..