TCP/IP 프로토콜 스택 인터넷 기반의 데이터 송수신을 목적으로 설계된 스택 큰 문제를 작게 나눠서 계층화 한 결과 데이터 송수신의 과정을 5개의 영역으로 계층화 한 결과 각 스택 별 영역을 전문화하고 표준화 함 7계층으로 세분화가 되며, 5계층으로도 표현함 APPLICATION 계층 TCP 계층 UDP 계층 IP계층 LINK 계층 물리계층 물리&링크 계층의 기능 및 역할 물리적인 영역의 표준화 결과 기존 Layer1, Layer2 프로토콜 그대로 적용 LAN, WAN, MAN과 같은 물리적인 네트워크 표준 관련 프로토콜이 정의된 영역 아래의 그림과 같은 물리적인 연결의 표준이 된다. IP 계층의 기능 및 역할 IP는 Internet protocol을 의미함 경로의 설정과 관련이 있는 프로토콜 TCP/..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 분할 정복 알고리즘을 사용하는 문제로, 2^n * 2^n 크기의 2차원 배열을 4등분하여 r행 c..

힙(heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙은 다음과 같은 힙 속성을 만족한다. A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있는데, 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 한다. 키 값의 대소관계는 오직 부모노드와 자신노드 사이에만 성립하며 형제 노드간에는 대소관계가 정해지지 않는다. 각 노드의 자식노드 최대 개수는 힙의 종류에 따라 다르나 일반적으로 자식노드의 개수가 최대 2개인 이진 힙을 사용한다. 힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는..

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

BFS (너비 우선 탐색) BFS는 탐색을 할 때 너비를 우선으로 수행하는 그래프 탐색 알고리즘이다. 너비 우선 탐색은 최단 경로를 찾아야 할 때 많이 사용한다. 재귀 함수로 구현하지 않고 큐(Queue)로 주로 구현한다. BFS를 그래프를 저장 할 때는 인접 행렬과 인접 리스트로 구현하는 방법이 있는데 인접 행렬은 시간 복잡도가 O(V^2) (V는 정점의 수), 인접 리스트는 O(V + E) (V는 정점, E는 간선) 이라 인접 리스트가 더 빠르기 때문에 주로 인접 리스트로 저장한다. C++ BFS 구현 bool visited[101] = {}; void bfs(vector graph[], int start) { queue q; q.push(start); visited[start] = true; whi..

이진 탐색 Lower Bound, Upper Bound 이진 탐색은 찾는 값이 존재하는지 탐색하여 하나의 값을 찾는 것이라면 lower bound와 upper bound는 이진 탐색에서 살짝 변형시킨 방식으로 중복된 값이나 상한, 하한선을 찾는 경우 등의 다양한 방식으로 활용할 수 있다. 이진탐색 포스팅 Lower Bound Lower Bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾는다. [1, 2, 3, 3, 3, 4, 5] 라는 리스트에서 3을 타겟으로 Lower Bound를 찾으면 결과로 나오는 인덱스는 3이 처음 등장하는 2가 된다. Upper Bound Upper Bound는 타겟보다 큰 값이 나오는 처음 위치를 찾는다. 위와 같은 [1, 2, 3, 3, 3, 4, 5] 의 리스트에..

분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다. 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다. 분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다. DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다. 공통점 문제를 가장 작은 단위가 될 때까지 나눠서 분할함 차이점 동적 계획법 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법) 분할 정복 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함) 분할 정복을 설계하는 방법 1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문..