CS/자료구조 & 알고리즘

외판원 순회 (TSP) 알고리즘 개념

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다. 브루트 포스로 해결한가지 정말정말 무식한 방법이 있긴 하다. n개의 점들을 도는 순서를 순열을 통해 구해놓고, 그 경로를 따라 가면서 거리를 구하는 것이다. 하지만 알다시피, n개 점들의 순열의 경우의 수는 n!개이다... n이 20만 되어도 2,432,902,008,176,640,000가지, 한국말로 '243경' 개의 경우의 수를 따져 주어야 한다.동적 계획법으로 해결1~n번 도시가 있고, 이 중 몇 개의 도시를 거친 후에 지금 판매원이 i번 도시에 있다.그럼, 이 중에서 거쳐오지 않았던 도시들 중에서 다음 도시를 정해야 한다.우리는 다음 도시로 이동했다고 '가정' 하는 방식을 사용할 것이다.좀 더 이..

실수형 (float) 자료형의 메모리 구조, 실제로 변환해보기

exponent : 지수부 (지수 부분)matissa : 기수부 (분수 부분) float형 실수의 전체 구조 IEEE 754 표준은 binary32에 대해 다음과 같이 명시한다.부호 비트 : 1 비트지수부 비트 : 8 비트가수부 비트 : 정밀도는 24 비트 (실제로 메모리엔 23 비트로 표현) 부호부 1 비트는 실수값이 양수일 때 0, 음수일 때 1로 표현된다. 지수부 8 비트를 unsigned char로 봤을 때, 실제 값에서 127을 더한 값을 저장하며 저장된 값의 범위는 다음과 같다.stored bits :    0    actual value :  -127 (실제 지수값을 표현하는 것이 아닌 특정 의미가 있음)stored bits :    1    actual value :  -126stored ..

float 자료형의 메모리 구조 (컴퓨터의 실수 표현)

실수형은 IEEE의 부동소수점 형식을 사용하는데 4바이트(32비트) 표현의 경우 아래와 같이 이루어져 있다. 정수의 경우 2의 보수법을 이용해서 간단하게 메모리에 저장된 비트를 확인할 수 있지만 실수는 조금 더 복잡하다.아래의 단계를 거치면 실수가 메모리에 어떻게 표현이 되는지 알 수 있다. 위에 나와있는 -101.625를 컴퓨터의 표현 방법으로 바꿔보겠다1단계 - 이진수로 바꾸기이진수로 바꾸기 위해서는 나눗셈과 곱셈을 하면 된다. 일단 부호를 제외하고, 정수 부분은 2로 나누기를 연속으로 해서 2진수로 바꿔주자 101/2 = 50 ... 150/2 = 25 ... 025/2 = 12 ... 112/2 = 6 ... 06/2 = 3 ... 03/2 = 1 ... 1 정수 부분은 1100101 이다. 소수..

[C++] 조합 (Combination) 구할 수 있는 알고리즘

개념n개의 값 중에서 r 개의 숫자의 순서를 고려하지 않고 나열한 경우의 수, 순열은 반대로 고려한다. 예시) [1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미계산식으로는 nCr 이라고 표현한다.nCr= nPr / r!= n! / ((n-r)! * r!)예시로 서로 다른 3개의 숫자(1,2,3) 중 중복되지 않으면서 순서와 관계 없이 2개를 뽑는다고 가정해보자3C2= 3! / 1! * 2!= 3! / 2!= (3x2x1) / (2x1)= 3로 총 3개의 경우의 수가 나오게 된다 (1,2 / 1,3 / 2,3) 조합의 점화식 n-1Cr-1 + n-1Crn-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때예시){1,2,3} 에서 3C..

[C++] multimap 값 가져오기

#include #include using namespace std;int main(){ multimap a; a.insert(pair(1, 2)); a.insert(pair(1, 2)); a.insert(pair(2, 4)); cout ::iterator it = a.begin(); it != a.end(); ++it) cout first second first second

논 블로킹 알고리즘 (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 값에 대한 정보만 저장하기 때문에 장비의 메모리를 적게 사용- 단점 : 일정 시간마다 주기적으로 라우팅 정보를 발송함으로 네트워크 트래..