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 이다. 소수..
실수의 부동 소수점 저장 방식
정수의 저장 방식컴퓨터는 10진수로 표현 된 수를 0과 1로 저장하기 위해 2진수로 변환한 정보를 저장하게 된다.23을 예로 들면23=16(24)+4(22)+2(21)+1(20)이므로, 2진수로 표현하면 10111 이다.(물론 2진수로 변환하는 방법은 다양하다. 23을 2로 나누며 그때의 나머지를 계속해서 저장하는 방법 등. 그러나 뒤에서의 이해를 돕기위해 2의 제곱수로 표현함).이 10111의 수를 1Byte의 메모리에 0001 0111으로 저장하는 방식이다.실수의 표현 방식고정 소수점 방식단어 그대로 소수점의 위치를 고정시켜놓고 수를 표현하는 방식이다.예시) 123.45123.45는 10진수에서 소수점 밑의 두자리를 고정시켜놓고 표현한 것. 보다시피 "정수. 소수"의 형태로 나타낸다.이를 고정소수점 ..
[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
Atomic 연산, CAS (CompareAndSwap)에 대하여, ABA 문제
스핀락, 뮤텍스, 세마포어, 모니터 모두 하나의 Thread가 임계 영역을 Lock한 후 작업을 수행하는 절차이지만 synchronized화 하게 되면 한 개의 Thread가 해당 블락을 전체 lock(점유)하기 때문에 다른 Thread는 아무 작업을 하지 못하게 되고 이로 인해서 기다리는 상황이 발생하고 낭비가 심해진다.그래서 Non-blocking한 방법, Lock-free한 방법으로 동기화 문제를 해결하기 위한 방법이 바로 Atomic 연산이고 이 동작의 핵심 원리는 CAS (Comparre ANd Swam)에 있다.CAS (CompareAndSwap) 알고리즘이란?멀티 쓰레드 환경, 멀티 코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는 것이 아닌 각 CPU에서 캐시 영역에서 메모리를 ..
논 블로킹 알고리즘 (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..
AWS EC2 개념 정리
EC2 (Elastic Compute Cloud)란?아마존 웹 서비스(AWS)에서 제공하는 클라우드 컴퓨팅 서비스클라우드 컴퓨팅은 인터넷(클라우드)을 통해 서버, 스토리지, 데이터베이스 등의 컴퓨팅 서비스를 제공 → AWS에서 원격으로 제어할 수 있는 가상의 컴퓨터를 한 대 빌리는 것후불제 PC방과 같이 사용한 만큼 비용을 지불하기 때문에 탄력적인 이라는 의미의 Elastic이라는 단어가 붙어있다. Elastic은 비용적인 부분 뿐만이 아니라 필요에 따라 성능, 용량을 자유롭게 조절할 수 있다는 의미도 가지고 있다사용해야 하는 이유 효율성 : 클릭 몇 번으로 서버를 생성할 수 있기 때문에 실제 서버를 구축하는 것보다 훨씬 간편하고 효율적비용 절감 : 사용한 만큼만 요금을 지불하면 되므로 비용 절감인스턴스..