CS/자료구조 & 알고리즘

논 블로킹 알고리즘 (Non-blocking Algorithms)

개념동시성에서의 논 블로킹 알고리즘이란 쓰레드간의 공유된 상태(자원)로의 접근을 서로 중단없이 수행하는 것이다. (어떤 알고리즘에서 한 쓰레드의 정지가 여기에 관련된 다른 쓰레드의 정지를 유발하지 않는다)블로킹 동시성 알고리즘A: 쓰레드에 의해 요청된 동작을 수행 - 또는B: 쓰레드가 동작을 수행할 수 있을 때까지 대기 많은 종류의 블로킹 알고리즘과 동시성 블로킹 자료구조가 있다. 예를 들어, java.util.concurrent.BlockingQueue 인터페이스의 구현체들은 모두 블로킹 자료구조이다. 쓰레드가 BlockingQueue에 요소를 삽입하려 하는데 큐에 공간이 없다면 쓰레드는 공간이 생길 때까지 대기한다. 다음 다이어그램은 공유된 자료구조를 보호하는 블로킹 알고리즘의 동작을 보여준다.논 블..

블로킹과 논블로킹 큐 (Blocking/Non-Blocking Queue)

1. BlockingQueue- Queue가 꽉 찼을 때의 삽입 시도 / 비어 있을 때의 추출 시도를 막는다- 구현체 모두 Thread-safe 하다 1) ArrayBlockingQueue- 고정 배열에 일반적인 Queue를 구현한 클래스- 생성 후 크기 변경 불가 2) LinkedBlockingQueue- 선택적으로 Bound가 가능한 LinkedList로 구현한 Queue 3) PriorityBlockingQueue- PriorityQueue와 같은 정렬 방식을 지니는 용량 제한이 없는 Queue 4) SynchrousQueue- Queue 내부로의 insert 작업이 다른 쓰레드의 remove 작업과 반드시 동시에 일어나야 한다.  2. Non Blocking Queue1) ConcurrentLin..

최장 증가 수열 (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)을 보장하기 때문에 일반적으로 힙을 ..