전체 글

(C++) 백준 1931번 - 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 회의실을 사용할 수 있는 회의의 개수를 최대로 하기 위해선 종료 시간이 가장 이른 순으로 사용하게 하면 된다. 그렇기에 회의가 종료되는 시간의 오름차순으로 정렬을 해놓고 시작 시간이 지나지 않은 가장 빠른 회의가 회의실을 사용하도록 하면 된다. #include #include #define X first #define Y second using namespace std; pair meetings[100005]; int n, cnt, cur, mn; bo..

(C++) 백준 11047번 - 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 가장 동전 수를 적게 이용하려면 금액이 큰 동전부터 빼가면서 계산해야 한다. 금액이 오름차순으로 입력되기 때문에 배열의 뒷부분부터 계산해 나가는 식으로 풀이하였다. #include using namespace std; int coins[12]; int n, k, cnt; i..

(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..