1. 인터넷 구성 요소 호스트: 네트워크 기능을 포함하는 컴퓨터로 응용 프로그램을 수행하는 주체이다. 라우터: 목적지까지 가장 최적의 경로를 찾아서 서로 다른 네트워크에 속한 호스트 간의 데이터 교환이 가능하게 해주는 장치이다. 통신 프로토콜: 호스트-호스트, 호스트-라우터, 라우터-라우터 사이의 통신하기 위한 정해진 절차와 방법이다. 2. TCP/IP 인터넷에 연결된 서로 다른 기종의 컴퓨터들이 데이터를 주고받을 수 있도록 하는 표준 프로토콜로 TCP와 IP를 비롯한 각종 프로토콜을 총칭한다. 클라이언트-서버 모델: 사용자인 클라이언트의 요구에 대응하여 네트워크 상의 서버가 웹 페이지를 보낸다. 점대점 통신: 각 통신이 네트워크 상의 한 점(호스트)으로부터 시작해 다른 점(호스트)으로 전달한다. 1) ..

이진 탐색 트리(BST) 각각의 노드가 최대 2개의 자식 노드를 가지는 이진 트리의 구조를 갖추고 있다. 연결 리스트로 구현된다. 기본 원리 모든 노드의 값은 유일하다. 루트 노드를 기준으로 왼쪽에 있는 값들은 루트 노드의 값보다 작다. 루트 노드를 기준으로 오른쪽에 있는 값들은 루트 노드의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 문제 #include using namespace std; typedef struct node_struct { int data; struct node_struct* left; struct node_struct* right; }node; node* insert_node(node* root, int value) { if (root == NULL) { root..

binary_search, lower_bound, upper_bound 정렬되어 있는 배열, 컨테이너 등을 대상으로 탐색한다. binary_search: 탐색 대상이 되는 값이 존재하는지 확인하고 들어 있다면 true, 없다면 false를 반환한다. lower_bound: 찾고자 하는 값 이상이 처음 나타나는 위치를 반환한다. upper_bound: 찾고자 하는 값을 초과하는 값이 처음 나타나는 위치를 반환한다. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www..

이분 탐색(Binary Search) 선형 자료구조가 정렬되어 있을 때 특정한 값을 빠르게 찾는 방법이다. 문제 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개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. www.acmicpc.net #include #include using namespace std; int main() { int N, M; int a[100000]; cin >> N..

분할 정복(Divide and Conquer)말 그래도 문제를 분할과 정복으로 나눠서 해결하는 것을 말한다.분할 단계에서는 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아질수록 풀기 쉬워지기 때문이다.대체로 분할 정복은 재귀 호출을 사용한다. 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.www.acmicpc.net#include #include using namespace std;i..

그리디(Greedy)각 단계에서 최선의 선택을 하는 알고리즘으로 탐욕적 기법이라고도 부른다.Greedy Choice Property (탐욕 선택 속성)국소 최적 선택이 전체 최적 해로 이어진다.현재 단계에서 가장 좋아 보이는 선택이 이후에도 전체적으로 최적인 결과로 이어진다는 속성이다.Optimal Substructure (최적 부분 구조)문제를 더 작은 문제로 나눌 수 있고, 그 작은 문제의 최적해들을 조합해서 전체 최적해를 만들 수 있어야 한다.Exchange Argument (교환 논법)임의의 최적해를 그리디 해와 다르게 만들 수 있다면, 이를 점진적으로 바꿔서 그리디 해처럼 만들 수 있고 성능이 떨어지지 않는다. 문제 https://www.acmicpc.net/problem/1931 1931번: ..