분류 전체보기

(CS) OSI, TCP/IP Layer, TCP vs UDP

OSI 7 Layer OSI(Open Systems Interconnection) 모델은 네트워크 아키텍처를 설명하기 위한 일반적인 프레임워크로, 데이터 통신 시스템의 다른 요소 간의 상호 작용을 설명하기 위해 일곱 개의 계층으로 구성된다. 또한 7단계로 나눔으로써 특정한 계층에 이상이 생기면 다른 계층의 장비 및 소프트웨어를 건드리지 않고도 이상이 생긴 단계만 고칠 수 있다는 장점도 가지고 있다. 1. 물리 계층(Physical Layer) 이 계층에서는 주로 전기적, 기계적, 기능적인 특성을 이용해서 통신 케이블로 데이터를 전송하게 된다. 이 계층에서 사용되는 통신 단위는 비트이며 이것은 1과 0으로 나타내어지는, 즉 전기적으로 신호가 흐르는지 아닌지로 생각할 수 있다. 이 계층에서는 단지 데이터만을..

(C++) 백준 1654번 - 랜선 자르기

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 매개 변수 탐색을 사용해 풀이하였다. 매개 변수 탐색은 다음의 두 조건을 만족할 경우에 사용할 수 있다. 최적화 문제를 결정 문제로 변경할 수 있는지? 위의 결정 문제로 얻어진 함수가 감소 혹은 증가함수인지? 여기서는 N개를 만들 수 있는 최대의 랜선을 구하는 최적화 문제를 랜선의 길이가 X일 때 랜선의 개수가 N개 이상인가 아닌지 구하는 결정 문제..

(C++) 백준 18870번 - 좌표 압축

문제 링크 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 먼저 입력받은 배열을 sort() 메서드를 사용해서 정렬하고, 그 후 unique()와 erase() 메서드를 사용해서 중복을 제거한다. 마지막으로 lower_bound() 메서드를 사용해서 현재 어느 위치에 존재하는지 알아낸다. #include #include #include using namespace std; vector ..

(C++) 백준 10816번 - 숫자 카드 2

문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 sort() 메서드와 해당 값보다 큰 값이 처음으로 나타는 index를 반환하는 upper_bound() 메서드, 해당 값이 처음으로 나타는 index를 반환하는 lower_bound() 메서드를 사용하면 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[500005]; int n,..

(C++) 백준 1920번 - 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 sort() 메서드와 binary_search() 메서드를 활용하여 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[100005]; int n, m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ci..

(C++) 백준 12852번 - 1로 만들기 2

문제 링크 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 백준 1463번과 마찬가지로 입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다. 그리고 연산의 순서대로 출력을 해야 하므로 1로 가는 경로에 있는 다음 값을 배열에 저장하였다. ex) arr[16] = 8, arr[8] = 4, arr[4] = 3, arr[3] = 1 #include using namespace std; int arr[1000005]; int hist..

(C++) 백준 11659번 - 구간 합 구하기 4

문제 링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 처음부터 특정 인덱스까지의 합을 배열에 저장하고, 구간 사이의 합을 구하기 위해 특정 인덱스까지의 합(sum[j-1])에서 구간에 속하지 않는 값의 합(sum[i-2])을 빼는 방식으로 구현하였다. #include using namespace std; int sum[100002]; int num[100002]; ..

(C++) 백준 11726번 - 2xn 타일링

문제 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 2*N 크기의 타일을 채우는 방법은 제일 처음 1*2 크기의 타일을 먼저 채웠을 경우와 제일 처음 2*1 크기의 타일 2개를 먼저 채우고 시작할 경우의 합이다. 즉 2*(N-1) 크기의 타일을 채우는 방법과 2*(N-2) 크기의 타일을 채우는 방법의 합을 구하면 된다. #include using namespace std; int tile[1002]; int..

(C++) 백준 1149번 - RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 house[x][0]은 x번째 집이 빨간색일 때의 최소 비용, house[x][1]은 x번째 집이 초록색일 때의 최소 비용, house[x][2]은 x번째 집이 파란색일 때의 최소 비용을 저장하도록 하였다. #include #include using namespace std; int hous..

(C++) 백준 2579번 - 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다. 마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 ..