전체 글 검색 결과

해당 글 904건
부동 소수점 : 왜 0.1을 저장하면 오차가 생길까요?

부동 소수점은, 가수부와 지수부로 나누어서 저장을 합니다. 즉, (a)*2^b꼴로 저장을 하는데요. 이 때, a는 1보다 크거나 같고, 2보다 작은 실수입니다. 즉, (1.xxx)*2^b 꼴로 저장을 한다는 겁니다. 여기까지는 그리 어렵지 않을 것이라고 생각합니다. 보통 부동 소수점, 우리가 흔히 알고 있는 float이나 double형은 이런 식으로 저장이 됩니다. 지수부랑, fraction. 즉 가수부랑 나누어서 저장을 하고 있는데요. 이 fraction 부분은 (1.xxx)*2^b로 표현했을 때, 0.xxx 부분을 저장한다고 보시면 됩니다. 0.xxx를 2진수로 표현해서 저장할 겁니다. 그러면, 실제로 0.1이 어떻게 저장되는지 봅시다. 저는 먼저 double과 long long이 같은 메모리 공간을..
코딩/C 2019. 6. 29. 19:50
c++ bitset (비트셋) 예제 : 쉽게 이해해 봅시다.

이번에는 c++에 있는 bitset 이라는 친구에 대해서 잠깐 알아볼 거에요. 보통, 비트 연산자를 이용해서 상태를 관리할 때, & 연산자를 쓰고 를 쓰고, | 같은 것을 조합해 가면서 쓰셨을 거에요. 익숙해 지면 그렇게 어렵지는 않습니다만, 그래도 조금 더 쉽게, 집합에 x가 포함되는지, 그렇지 않은지, x를 제거하고, x를 추가하는 연산을 조금 더 간편하게 할 수 있는 방법이 없을까요? 이러한 것들은, bitset을 이용해서 너무 쉽게 할 수 있습니다. 그 전에, 이것이 어떠한 구조를 가지고 있는지 간략하게 살펴 봅시다. 많이 물어보시는 가 내부적으로 어떻게 동작하는지부터 간단하게 소개해 보겠습니다. 먼저 비트셋은 word 단위로 이루어진 배열입니다. 그 안에 상태들이 저장이 되어 있는데요. 우리가 ..
레퍼런스/예제 2019. 6. 28. 23:49
dfs 심화편 : 깊이 우선 탐색의 단점을 어떻게 보완하는가?

dfs, 그러니까 깊이 우선 탐색의 단점은 크게 2가지입니다. 해가 없는 경로에 깊이 빠진다. 그렇기에 유한 시간 내에 끝나지 않을 수도 있다. 그리고, 해를 구했을 때, 그것이 최적이 아닐 수도 있다. 이 2가지 때문에, 보통 최단 거리를 구할 때에는 사용하지 않아요. 그런데, 이걸 잘 보완하면 절찬리에 써먹을 수도 있어요. 절찬리에 잘 써먹을 수 있는 문제 중에 하나를 예로 들어봅시다. 어떠한 세제곱 수를 k개 더해서 n을 만들어야 합니다. k값은 최소가 되어야 합니다. 예를 들어서, 43은 3^3 + 2^3 + 2^3으로 만들 수 있습니다. 물론 1^3을 43개 써서 만들 수도 있지만, 43개보다 작게 만들 수 있는 방법이 존재하기 때문에, 답이 될 수 없습니다. 이 문제는 어떻게 풀어야 할까요? ..
자료알고/알고리즘 2019. 6. 28. 01:14
외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자

우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘 2019. 6. 27. 04:21
c언어 비트 이동 연산자 (<<, >>) : 어떤 것을 조심해야 할까요?

어제, 비트 연산자 내용을 하면서 이런 이야기를 했을 거에요. >>와 33을 하면 어떤 값이 나오는지도 봅시다. 잘 모르겠네요. 표준에서는 이러한 연산의 결과는 정의되지 않는다고 이야기 합니다. 정리하면, a가 int형이라면, b가 sizeof(int)보다 같거나 큰 경우에 (ab)의 결과값은 정의되지 않습니다. 이런 실수는 보통 하지 않으시니까, 넘어가도록 하겠습니다. 먼저 a
코딩/C 2019. 6. 26. 02:39