오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Address Mapping host 또는 router에 packet을 전달하려면 logical 및 physical 두 가지 수준의 주소가 필요하다. logical address를 해당 physical address에 mapping 할 수 있어야 하며, 그 반대의 경우도 마찬가지이다. 이러한 작업은 static 또는 dynamic mapping을 사용하여 수행할 수 있다. host나 router가 다른 host나 router에 보낼 IP datagram을 가질 때마다, 수신기의 logical(IP) address를 갖는다. 그..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Introduction Internet Protocol(IP)은 네트워크 layer에서 TCP/IP procotol에 의해 사용되는 전송 메커니즘이다. ▶Datagrams 네트워크(인터넷) layer의 packet을 'datagrams'이라고 한다. Datagram은 header와 data의 두 부분으로 구성된 가변 길이 packet으로 구성된다. header의 길이는 20 ~ 60 Byte이며 routing 및 전송에 필수적인 정보를 포함한다. TCP/IP에서는 header를 4Byte 섹션으로 표시하는 것이 일반적이다. H..

▶1398 - 동전 문제 ▶문제 구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000... 즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25 × 100K인 동전이 있는 것이다. 구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다. ▶입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Delivery 네트워크 layer은 기본 physical 네트워크(하위의 레이어)에 의한 packet의 handling을 감독하는데, 이를 패킷 전달 (packet delivery)이라고 한다. packet을 최종 destination으로 delivery 하는 것은 direct와 indirect의 두 가지 다른 delivery 방법을 사용한다. direct delivery는 같은 네트워크 상에서 패킷을 전달하는 것을 의미한다. 외부 router를 거치다가 마지막에 해당 네트워크의 router(R)에서 host(H)로 가는 R..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Introduction TCP/IP protocol suite의 IP layer에서 인터넷에 연결된 각 장치를 식별하는 데 사용되는 식별자를 Internet addrss 또는 IP address라고 한다. IPv4 address는 인터넷으로의 host나 router의 연결을 독특하고 보편적으로 정의하는 32bit 주소이다. IPv4 address는 32bit이다. IPv4 address는 고유하고 보편적이다. IPv4의 address 공간은 2^32 또는 4,294,967,296이다. (43억 개 - 이론적으로는 부족해 v6를..

▶1563 - 개근상 ▶문제 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다. 출결사항이 기록되는 출결은 출석, 지각, 결석이다. 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다. 한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결 정보는 OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA AOAL AOLO ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Introduction 글로벌 인터넷은 전 세계 수백만 대의 컴퓨터를 하나로 연결하는 블랙박스 네트워크라고 생각할 수 있다. 한 컴퓨터의 응용 프로그램 layer에서 보낸 게 다른 컴퓨터의 응용 프로그램 layer에 도달하는 것만 걱정한다. Device A에서 Device B로 가는 과정이다. 인캡슐레이션 후 Link 타고 가서 디캡슐레이션 (header 떼는 작업) 한다. ▶Switching (switch는 L2) 이전에, source에서 destination으로 메시지를 전달하는 것은 많은 결정을 수반한다는 것이 명백하다...

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 이번 chapter는 Data 통신, Layer 1, 2에 관한 chapter다. ▶Wired Local Area Networks LAN(Local Area Network)은 건물이나 캠퍼스와 같은 제한된 지리적 영역을 위해 설계된 컴퓨터 네트워크다. LAN은 리소스를 공유하는 유일한 목적으로 조직의 컴퓨터를 연결하는 고립된 네트워크로 사용한다. 오늘날 대부분의 LAN은 WAN 또는 인터넷에 연결되어있다. LAN 시장은 이더넷, 토큰 링, 토큰 버스, FDDI, ATM LAN과 같은 여러 기술이 있다. 그중에서 Ethernet을..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Protocol Layers 두 개의 실체가 통신해야 할 때 Protoccol이 필요하다. 단순하지 않을 때, 우리는 communitcation이라는 복잡한 작업을 여러 Layer로 나눌 수 있다. 이 경우 각 Layer에 하나씩 여러 개의 Protocol이 필요할 수 있다. Example 1 통신은 매우 간단하여 한 Layer에서만 발생할 수 있다. ▶The OSI Model International Standards Organization 국제표준기구(ISO)는 국제표준에 관한 세계적 합의를 전담하는 다국적 기구이다. 세계..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶A Brief History Network 컴퓨터 및 프린터와 같은 연결된 통신 장치의 그룹 Internet 서로 통신할 수 있는 둘 이상의 네트워크 상호 연결된 수십만 개의 네트워크로 구성 100여 개국의 정부기관, 학교, 연구시설, 기업 등 다양한 단체는 물론 개인들도 인터넷을 사용 ▶Internet Today ISP : Internet Service Provide (접속 서비스) ▶Protocols and Standards Protocol rule (통신 규약) - Communication Protocol Standard ..

▶1915 - 가장 큰 정사각형 ▶문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. ▶입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. ▶출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. ▶예제 ▶풀이 가로세로 길이가 1인 부분은 1 이렇게 될 것이고, 가로세로 길이가 2인 부분은 1 1 1 1 이 형식이 된다. 그럼 이것을 dp로 바꾸면 되는데, (0,0)에서 (n-1, m-1)까지 비교해준다. 이때 i, j 중 하나가 0이면 그냥 a..

▶2133 - 타일 채우기 ▶문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. ▶입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. ▶출력 첫째 줄에 경우의 수를 출력한다. ▶예제 ▶힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. ▶풀이 dp를 이용해서 푸는 문제이다. N이 홀수일 때는 짝이 맞지 않기 때문에 항상 0이 된다. 그럼 N이 짝수일 때만 생각해주면 된다. 2, 4, 6일 때 규칙이 어떻게 되는지 가장 먼저 생각해주었다. n = int(input()) dp = [0 for _ in range(31)] dp[2] = 3 for i in range(4, n+1, 2): dp[i] = dp[2] * dp[i - 2] for j in range(4, i, ..

▶11402 - 이항 계수 4 ▶문제 자연수 n과 정수 k가 주어졌을 때 이항 계수 nCk를 m으로 나눈 나머지를 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 n, k와 m이 주어진다. (1 ≤ n ≤ 10^18, 0 ≤ k ≤ n, 2 ≤ m ≤ 2,000, m은 소수) ▶출력 nCk를 m으로 나눈 나머지를 출력한다. ▶예제 ▶풀이 dp문제라고 해서 풀었는데 왜 dp인지는 잘 모르겠다. 이것도 dp에 포함되는 문제인가 보다. 아님 내가 dp를 쓰지 않고 풀었나 보다. 아무튼 어떻게 풀지 고민하면서 구글에 검색을 해보았는데 이항 계수를 구해서 m으로 나누는 문제는 '뤼카의 정리'를 사용하면 된다고 보았다. 그래서 뤼카의 정리가 뭔지 찾아보았다. https://ko.wikipedia.org/wiki/%..

▶1520 - 내리막 길 ▶문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로..

▶2655 - 가장높은탑쌓기 ▶문제 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. 벽돌들의 높이는 같을 수도 있다. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ▶입력 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이,..

▶1328 - 고층 빌딩 ▶문제 상근이가 살고 있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다. 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어, N = 5, L = 3, R = 2인 경우에 가능한..

▶1256 - 사전 ▶문제 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다. 규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다. N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 세..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Schematic Overview of Computer System 초록색 원 : process unit 파란색 사각형 : memory (+ local buffer) 빨간색 사각형 : register ▶Remind: Von Neumann Machine 모든 현대 컴퓨터 시스템의 프로토타입(Prototype) Stored-program computer processing unit은 오직 main memory와 통신할 수 있다. 산술논리 unit과 processer register를 포함한 처리장치 instruction regist..

▶2293 - 동전 1 ▶문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ▶입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. ▶출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. ▶풀이 2, 3, 4번째 행은 각각 1, 2, 5에 해당하는 money를 나타낸 것이다. dp[1] dp[2] dp[3] dp[4] d..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶운영체제(OS)란? 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층을 말한다. 좁은 의미의 운영체제 : 운영체제의 핵심 부분으로 메모리에 상주하는 부분, 흔히 커널(kernel)이라고 부른다. 넓은 의미의 운영체제 : 커널뿐 아니라 각종 주변 시스템 유틸리티를 포함하는 개념이다. 항상 메모리에 올려져 있는 것이 아닌 필요할 때 올라가는 별도의 프로그램이다. ▶Three Main Features of Operating Systems 1. Virtualization CPU Virt..