CS/자료구조 & 알고리즘

최장 증가 수열 (LIS, Longest Increasing Subsquence)

최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다.이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다.아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다.이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자.다이나믹 프로그래밍을 이용한 방법 : O(N^2)이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다.하지만 수열에 존재하는 수의 개수가 k개일 때, 1개 이상의 원소를 갖는 모든 부분수열의 가짓수는 2^k개이므로, 모든 부분수열을 확인해 이들..

RIP, OSPF, BGP 장단점

RIP (Routing Information Protocol), OSPF (Open Shortest Path First) 및 BGP (Border Gateway Protocol)는 모두 동적 라우팅 프로토콜이다.RIP - 거리 벡터 라우팅 프로토콜라우터가 인접한 이웃과 정보를 교환하면서 전체 네트워크에 대한 정보를 점차 완성해 나가는 방식이다. 장점)구성이 간단하다작은 네트워크에서 잘 작동한다단점)홉수 제한이 15개로 작다수렴 속도가 느리다무한 계산 문제가 발생할 수 있다OSPF - 링크 상태 라우팅 프로토콜라우터가 전체 네트워크의 상태 정보를 가지고 있으며, 이를 기반으로 최단 경로 트리를 계산하여 최적의 경로를 결정하는 방식이다. 장점)VLSM (Variable Length Subnet Mask)을 ..

라우팅 알고리즘

1. 동적 라우팅에 사용되는 알고리즘① 거리벡터(Distance Vector) : RIP, IGRP가. 개요- 모든 이웃 라우터들에게 자신이 가진 모든 정보(불완전한 정보 포함)를 주기적으로 알려준다.- 목적지 네트워크의 distance vector 정보를 서로 교환하여 라우팅 테이블을 작성- 목적지까지 경로를 제공하지 않으며, 단지 목적지까지의 최소비용(홉수)만 제공 나. 특징- 노드 변경 시 주기적으로 이웃한 노드와 자신의 라우팅 테이블을 공유 [산기, 14년3회]- 소규모 네트워크에 적합, 라우팅 테이블을 서로 교환 다. 장단점- 장점 : 네트워크의 distance 값에 대한 정보만 저장하기 때문에 장비의 메모리를 적게 사용- 단점 : 일정 시간마다 주기적으로 라우팅 정보를 발송함으로 네트워크 트래..

암호화 알고리즘

정보를 안전하게 전송하거나 저장하기 위해 사용되는 수학적인 절차다.대칭 키 암호화 (Symmetric Key Encryption)빠르고 효율적이지만, 키를 안전하게 공유해야 한다AES (Advanced Encryption Standard)현재 가장 널리 사용되는 대칭 키 암호화 알고리즘 중 하나미국 국립표준기술연구소(NIST)에 의해 2001년에 공식적으로 표준으로 채택AES는 128비트, 192비트, 256비트 세 가지 키 길이를 지원하며, 블록 암호화 방식을 사용블록 암호화는 고정된 크기의 데이터 블록을 암호화하는 방식으로, AES에서는 128비트 블록 크기를 사용DES (Data Encryption Standard)초기 미국 국립표준기술연구소(NIST)에서 정한 표준으로 사용현재는 보안성이 약해짐에..

휴리스틱 알고리즘 (Heuristic Algorithm)

우리가 문제 해결 시 흔히 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 사실 실생활에서 쓰기엔 매우 한정적이다. 예를 들어, 인공지능 체스 프로그램을 알고리즘으로 짠다고 할 때 우리가 가장 먼저 떠올릴 수 있는 것은브루트 포스(brute force) 방식이다. 즉, 가능한 모든 말의 움직임을 다 해보는 것이다. 하지만 이 방식은 어림도 없는게 움직일 수 있는 말과 이동 가능한 칸이 너무 많기 때문에 만약 이 방식으로 프로그램을 개발했다고 하면, 죽을 때까지 게임이 끝나지 않을 것이다. (경우의 수가 10^120 가지라고 한다.)그렇다고 해서 분할 정복 기법을 사용하자니 적절한 분할 방법이 생각나질 않고 동적 계획법을 사용하자니 메모리가 턱없이 모자르다. 결국 ..

알고리즘과 휴리스틱의 차이

테스트 케이스의 효율성소프트웨어의 높은 품질을 위해 테스트를 진행할 때, 테스트 케이스를 작성하여 이에 따라 테스트를 실행하고, 실패율로 품질을 측정하는 방식을 선택하는 회사들이 많다. 하지만 현재까지 제품의 모든 경우의 수가 고려되고 전부 테스트 케이스로 옮겨지는 것은 사실상 현실적으로 불가능하며, 이러한 부분은 따라서 수치로 계산되지 못한다. 그렇다면, 이러한 테스트 결과 수치가 소프트웨어의 품질을 증명한다고 할 수 있을까?   테스트 케이스는 시간이 지나며 제품의 기능이 발전하고 늘어날 수록, 같이 늘어난다. 그만큼 테스트 수행 시간도 늘어나기 때문에, 결국 부분적 회귀 테스트를 테스트 전략을 많이 선택한다. 이러다 보면, 오랫동안 건드려지지 않는 위험요소가 적은 부분도 있을 테고, 그 부분의 테스..

힙 (Heap) / 이진 힙 (Binary Heap)

정의힙 (heap)은 이진 힙 (binary heap)이라고도 하며, 최댓 값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조다. 힙은 다음과 같은 속성을 가지고 있다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트노드에 있음2. 최소 힙 (Min Heap)부모 키값이 자식노드 키값보다 작은 힙Key(parent) ≤ Key(ch..

우선 순위 큐 - Priority Queue

속성1. 모든 항목에는 우선 순위가 있다2. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외된다.3. 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공된다. 4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같다.(여기서 높은 값이 높은 우선순위를 갖는다고 가정.)input : 4 → 8 → 2큐 : 4 → 8 → 2우선순위 큐 : 8 → 4 → 2기본 동작enqueue()- queue에 새 요소를 삽입.dequeue() - queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환.peek() - queue에서 최대 우선순위 요소를 반환.구현  힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 ..

스택 포인터와 프레임 포인터

스택 프레임 (Stack Frame) 기본적으로 함수가 호출될 때마다 전달한 인자와 정의한 지역(자동) 변수가 높은 주소부터 낮은 주소의 방향으로 차례대로 저장되는 구조이다. 이외에도 다른 함수를 호출할 때 복귀할 주소(다음 실행할 명령어의 주소), 프레임 포인터 및 보존되는 레지스터들이 스택에 저장된다. 스택 포인터는 함수 호출 시작부터 피호출 프로그램이 실행되는 단계 차례대로 저장되는 값들을 저장하기 위해 현 시점에서 저장할 메모리의 위치를 가리킨다. 스택 프레임에 저장되는 값 - 복귀 주소 - 호출자 루틴의 프레임 포인터 - 사용하던 보존 레지스터 - 피호출자에 전달하는 인자 - 피호출자에서 사용되는 지역 변수들 프레임 포인터 (Frame Pointer) 함수 호출이 끝난다면 상위 호출로 돌아기전에..

에이전트의 정의

에이전트(Agent)는 인공지능 분야에 있어서 핵심 개념이 될 수 있다. 다음과 같이 정의를 내릴 수가 있다 "복잡한 동적 환경에서 목표를 달성하려 시도하는 시스템" 특징 특정 목적에 대해 사용자를 대신하여 작업을 수행하는 자율적 프로세스이다. 독자적으로 존재하지 않고 어떤 환경(운영 체제, 네트워크 등)의 일부이거나 그 안에서 동작하는 시스템이다. 지식 기반(Knowledge Base)과 추론 기능을 가지며, 자원 또는 다른 에이전트와의 정보 교환과 통신을 통해 문제를 해결한다. 스스로 환경의 변화를 인지하고 그에 대응하는 행동을 취하며, 경험을 바탕으로 학습하는 기능을 가진다. 분류 Simple Reflex Agents Condition-Action Rule을 내부에 가지고 있으며, 환경으로부터 받는..