https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 이 문제는 DP를 이용하여 해결할 수 있다. 벼의 최대 개수는 2000개이다. 또한 벼를 수확할 수 있는 방법은 2000 * 2000개의 방법이 있다. 따라서 DP 배열을 2000 x 2000의 크기를 할당해야한다. 벼의 가치를 입력받았다면, 0번째 인덱스 부터 N - 1번째 인덱스까지의 합 중에 최대 값을 알아봐야한다. 이는 아래 점화식을 사용하면 해결할 수 있다. DP[start][end] = MAX(start를 선택한 경우, ..
분류 전체보기
https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 이 문제는 투 포인터를 사용한 DP 문제이다. 문제에서 각 먹이의 만족도의 최대값이 100000000이고, 먹이의 최대수가 100000이다. 따라서 각 먹이의 만족도의 합의 최대 값은 10^8 * 10^5 = 10^13이 된다. 이는 int의 범위인 10^9를 벗어나기 때문에 DP는 long long 형을 사용해야한다. 문제에서 투 포인터를 사용한 이유는 호석 애벌레가 미래를..
UDP 프로토콜이란? User Datagram Protocol의 약자로 데이터를 데이터그램 단위로 처리하는 프로토콜이다. 비연결형, 신뢰성 없는 전송 프로토콜이다. 데이터그램 단위로 쪼개면서 전송을 해야하기 때문에 전송 계층이다. Transport layer에서 사용하는 프로토콜 UDP와 TCP? UDP와 TCP가 나오게된 이유 IP의 역할은 Host to Host (장치 to 장치)만을 지원한다. 장치에서 장치로 이동은 IP로 해결되지만, 하나의 장비안에서 수많은 프로그램들이 통신을 할 경우에는 IP만으로는 한계가 있다. IP에서 오류가 발생한다면 ICMP에서 알려준다. 하지만 ICMP는 알려주기만 할 뿐 대처를 못하기 때문에 IP보다 위에서 처리를 해줘야 한다. 1번을 해결하기 위하여 포트 번호가 나..
TCP/IP 프로토콜이란? 네트워크 통신에서 사용하는 신뢰성있는 연결 방식 TCP는 기본적으로 unreliable network(비신뢰성 네트워크)에서 reliable network(신뢰성 네트워크)를 보장할 수 있도록 도와주는 프로토콜 TCP는 network congestion avoidance algorithm(네트워크 혼잡 방지 알고리즘)을 사용 TCP/IP는 하나의 프로토콜이 아닌 TCP와 IP를 합쳐서 부르는 프로토콜 TCP/IP를 사용하는 것은 IP 주소 체계를 따르고 IP Routing을 이용해 목적지에 도달한 후 TCP 특성을 활용해 송수신자간의 논리적 연결을 생성하고 신뢰성을 유지할 수 있도록 하겠다는 것을 의미 TCP/IP는 송신자가 수신자에게 IP 주소를 사용하여 데이터를 전달하고 그..
OSI 7계층이란? 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것을 의미한다. 7계층으로 나눈 이유 계층을 나눠 통신이 일어나는 과정을 단계별로 파악할 수 있다. 통신의 흐름을 한눈에 알아보기 쉬우며, 사람들이 이해하기 쉽다. 7단계 중 특정 단계가 손상된다면 다른 단계의 소프트웨어나 하드웨어를 건들지 않고 이상이 생긴 단계만 고칠 수 있다. OSI 계층 단계 1계층 - 물리 계층 (Physical Layer) 데이터를 전기적인 신호로 변환해서 주고 받는 기능을 수행하는 계층 데이터를 전송하는 역할만 진행 데이터가 무엇인지 어떤 에러가 있는지 신경쓰지 않는다. 주로 전기적, 기계적 특성을 사용해 통신 케이블로 데이터를 전송 1계층에서 사용하는 통신 단위는 비트이다. 1과 0으로 이루어져 있으며 이..
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 이 문제는 DP와 그리디 알고리즘을 모두 사용하는 문제이다. 큰 수를 만드는 과정은 그리디 알고리즘을 사용하고 작은 수를 만드는 과정은 DP를 사용한다. 큰 수를 만드는 과정은 다음과 같다. 큰 수란 자릿 수가 긴 수를 의미한다. 가장 긴 숫자는 적은 성냥 개비만을 사용하는 숫자를 의미한다. 따라서 성냥개비가 가장 적게 사용하는 1과 7로만 숫자를 나타내면 된다. 이때 주어진 숫자가 짝수인 경우 1로만 ..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 DP를 사용하는 해결할 수 있다. 0부터 N까지의 수 중에 K개의 숫자를 사용해서 N을 만드는 문제이다. 이 문제를 보고 6, 4에 대해 직접 경우의 수를 세워 봤을 때 다음과 같은 표의 결과가 나왔다. K = 1 K = 2 K = 3 K = 4 N = 1 1 2 3 4 N = 2 1 3 6 10 N = 3 1 4 10 20 N = 4 1 5 15 35 N = 5 1 6 21 56 N = 6 1 7 28 84 위 표를 보면 (2,2)의 경우 (2,1) + (1,2)의 합인 것을 볼 수 있다. 따라서 (6,4) =..
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 이 문제는 배낭을 이용한 dp 문제이다. 문제에서 주어지는 동전은 N개이며, 동전의 가치도 입력으로 주어진다. 예제 입력에 따르면 1원 2원의 동전을 통해 1000원을 만들어야한다. 이를 위해서는 1 1 1 .... 1에서 2 2 2 2... 2원까지 총 501가지의 경우의 수가 발생한다. 이 문제를 해결하기 위해서는 1원에서 1000원까지 1원의 동전과 2원의 동전으로 만들 수 ..
