오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶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..

학부과정에서 배운 내용들을 이곳에다가 쓸 것입니다. 제가 복습하기 위해서 그리고 제가 쓴 글이 다른 사람들에게 도움이 되었으면 해서 앞으로 꾸준히 써 내려갈 것입니다. 하지만, 저는 아직 학부생이고 복습 차원에서 쓰는 거라서, 그리고 석사, 박사, 교수님 등 전문가가 아니기 때문에 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶17106 - 빙고 ▶문제 최근에 구더기 컵 공식 트위터 계정은 구더기 컵 빙고를 공개했다. 원본 트윗은 이 링크에서 볼 수 있다. 마침 이번 대회의 첫 문제이므로 간단한 몸 풀기를 해 보자. 빙고판을 하나 주면 답안을 작성해서 제출하기만 하면 되는 간단한 문제다. 위에 있는 빙고판 말고 새로운 빙고판을 줄 예정이다. 시작하기 전에, 몇 가지 내용을 덧붙이고자 한다. 문제를 이해하기 쉽게 하기 위해 각 칸에 번호를 붙여 놓았다. 열 번호는 왼쪽에서 오른쪽으로 A, B, C, D, E이고, 행 번호는 위에서 아래로 1, 2, 3, 4, 5이다. 칸의 번호는 열 번호와 행 번호를 이어 붙여서 만들어진다. 예를 들어 위 빙고판의 "Is it rated?"가 적힌 칸의 번호는 C5이다. 빙고를 하려면 각 칸에..

▶1854 - K번째 최단경로 찾기 ▶문제 봄 캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자. ▶입력 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 ..

▶2887 - 행성 터널 ▶문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표 위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌..

▶1238 - 파티 ▶문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N) 번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. ▶입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으..

▶1937 - 욕심쟁이 판다 ▶문제 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어놓아야 하는데, 어떤 지점에 처음에 풀어놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을..