CSE 전공노트

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 난이도: 실버 1 사용 언어: JAVA 토마토를 담는 큰 상자가 있고, 이 상자는 M x N의 크기를 가집니다. 이 상자에 토마토를 보관하게 되는데, 토마토 중에는 익은 토마토도 있고, 안 익은 토마토도 있습니다. 익은 토마토는 1, 안 익은 토마토는 0, 그리고 아무것도 들어있지 않은 칸은 -1로 표시됩니다. 안 익은 토마토..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 난이도: 실버 1 사용 언어: JAVA 아래의 그림 1과 2와 같이 한 변의 길이가 N인 정사각형 모양의 지도가 있고, 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타냅니다. 집이 연결되어 있으면, 이를 단지라고 정의하고, 단지에 번호를 붙입니다. 여기서 연결되어 있다는 말은 어떤 집의 좌우 또는 아래위로 다른 집이 위치해있는 경우를 뜻합니다..

다이나믹 프로그래밍(Dynamic Programming)은, 핵심부터 설명하자면, 한 번 수행한 연산을 저장시켜두어, 다음에 해당 연산을 또 해야 할 때 기존의 연산 결과를 이용함으로써, 연산의 중복 수행을 막는 알고리즘입니다. 수행한 연산의 결과를 메모리에 저장시켜 둠으로써, 메모리를 조금 더 사용하긴 하지만 그로 인해 연산 속도를 비약적으로 증가시킬 수 있습니다. 다이나믹 프로그래밍 사용의 가장 대표적인 예시가 바로 피보나치 수열 문제입니다. 피보나치 수열이란, 이전 두 항의 합을 현재의 합으로 사용하는 특징을 가지는 수열입니다. 아래의 예시가 바로 피보나치 수열입니다. 우선 수학적으로 접근하여 재귀함수로 피보나치 함수를 구현하면, 간단하게 구현이 가능합니다. 1 2 3 4 5 6 7 8 9 10 1..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 난이도: 실버 2 사용 언어: JAVA 밭에 유기농 배추를 심어두었는데, 배추흰지렁이를 이용해 해충을 예방할 수 있습니다. 여기서 배추흰지렁이는 인접해있는 배추로는 이동할 수 있기 때문에, 여러 인접해있는 배추들의 경우에는 지렁이가 한 마리만 있어도 해충으로부터 보호될 수 있습니다. 여기서 인접해있다는 것은 한 배추의 상하좌우 네 방향 중에 다른 배추가 ..

그리디 알고리즘(Greedy Algorithms)은 이름 그대로 번역하면 '탐욕법'이라고 해석됩니다. 이 이름 그대로, 어떤 문제에 대해서 탐욕적으로 문제를 푸는 방법이 바로 이 그리디 알고리즘입니다. 탐욕적이라는 말을 조금 더 듣기 좋게 풀어보자면, '현재 상황에서 최선의 선택을 하는 방법'이라고 할 수 있습니다. 즉, 매 순간 여러 선택지 중 가장 좋아 보이는 선택지를 고르고, 이 선택이 추후에 미칠 영향은 고려하지 않습니다. 추후에 미칠 영향을 고려하지 않는다는 말은, 결과적으로는 최적의 해가 아닐 수도 있다는 것을 뜻합니다. 그래서 항상 어떤 문제와 마주치면, 이 문제를 그리디를 이용해 풀어도 되는 것인지에 대해 생각을 해 보아야 합니다. 하지만 만일 그리디로 접근해도 되는 문제라면, 그리디를 사..

1. ICMP 네트워크 계층과 라우팅에 대해 지금껏 공부하면서 알아본 내용은 어떻게 패킷을 출발지로부터 목적지까지 안전하게 운반을 하는가에 대한 내용이었습니다. 그리고 패킷이 실제로 안전하게 운반이 된다면 통신이 제대로 성공한 것이므로 문제가 생기지 않습니다. 하지만 어떠한 문제로 인해 목적지에 패킷을 전달하는 것에 실패한다면 문제가 발생합니다. 인터넷 프로토콜(IP)에는 이러한 에러에 대한 처리 방법이 존재하지 않기 때문입니다. 그래서 IP의 이런 문제점을 보강하기 위해 IP와 함께 사용되는 것이 바로 ICMP(Internet Control Message Protocol)입니다. TTL이 0이 되었거나 목적지에 도착했는데 명시된 포트 번호가 존재하지 않거나, 또 해당하는 호스트가 없거나 하는 다양한 경..

앞의 글들에서도 여러 번 언급했지만, 전통적으로 네트워크 장비들은 데이터 평면(Data Plane)과 컨트롤 평면(Control Plane)으로 구성되어 있습니다. 그래서 데이터 평면과 컨트롤 평면이 동등한 위치에서 역할을 수행해왔습니다. 하지만 이러한 구조의 여러 문제점으로 인하여 새로운 방법이 등장하게 됩니다. 이 방법은 바로 컨트롤 평면을 떼내어 더 상위 레벨에 위치시키는 것입니다. 즉, 중앙 집중형으로 설계된 하나의 컨트롤 평면이 네트워크의 라우팅을 담당하는 것입니다. 이러한 방법을 SDN (Software Designed Networking)이라고 합니다. 이러한 네트워크 형태는 중앙 컨트롤 타워 하나에서 여러 라우터들의 관리와 제어가 가능하기 때문에, 라우터 하나하나마다 컨트롤 평면을 위한 네..

과연 전 세계의 네트워크를 하나의 시스템으로 통일시킬 수 있을까요? 또는 전 세계의 수많은 라우터들을 라우팅 테이블에 모두 집어넣을 수 있을까요? 당연히 불가능합니다. 결국 네트워크는 작은 네트워크들을 서로 연결한 형태이고, 이 작은 네트워크들은 그 내부의 저마다 다른 프로토콜로 작동하게 됩니다. 이렇게 동일한 프로토콜을 사용하는 한 네트워크, 또는 네트워크 그룹을 자율 시스템 (Autonomous System, AS)라고 합니다. 그리고 이 AS는 종종 라우팅 도메인(Routing Domain)으로 불리기도 합니다. 이 AS는 전 세계적으로 고유한 번호인 ASN(Autonomous System Number)을 부여받아야 합니다. 1. 게이트웨이 AS 내부에서는 자신들의 프로토콜을 이용해 네트워크를 운용..

네트워크 계층을 공부할 때, 네트워크 계층은 컨트롤 평면(Control Plain)과 데이터 평면(Data Plain), 이렇게 둘로 나누어진다고 공부했습니다. 컨트롤 평면은 출발지로부터 도착지까지 어떤 라우터를 통해 어떤 길로 가야 하는 지를 결정하고, 라우팅 테이블(Routing Table)을 만들어줍니다. 그러면 데이터 평면에서 패킷의 헤더를 확인하고, 라우팅 테이블을 참조하여 어느 인터페이스로 보내주어야 하는지를 실제로 포워딩해주게 됩니다. 이렇게 라우팅 테이블을 만들고 경로를 찾아주는, 컨트롤 평면이 하는 일들을 규약으로 만들어 둔 것을 라우팅 프로토콜(Routing Protocol)이라고 합니다. 라우팅 프로토콜의 목적은 당연히 네트워크 내에서 출발지로부터 도착지까지 가장 좋은 경로를 만드는 ..

IP 주소 부족 문제를 해결하기 위한 방법들 중 마지막으로 알아볼 것은 IPv6입니다. 32비트의 IPv4를 가지고는 최대 2^32개(약 42억 개)의 기기에만 주소를 할당해줄 수 있는데, IoT나 모바일 기기들의 발전으로 인해 주소를 할당받는 기기가 기하급수적으로 늘어나며 주소가 부족해질 수밖에 없습니다. IPv6는 128비트로 이루어진 주소 체계입니다. 따라서 2^128개의 IP 주소를 할당해 줄 수 있습니다. 따라서 총 1조 개 이상의 기기에 IP주소를 할당해 줄 수 있습니다. 최종적으로는 IPv4를 대체하기 위해 등장한 IPv6이지만, 현재는 둘 모두 사용되고 있습니다. 그리고 IP주소의 길이가 바뀌기 때문에 IPv6를 탑재한 데이터그램은 헤더의 구성요소와 모양도 IPv4와는 달라지게 됩니다. 1..