J.Althea

동적 프로그래밍을 설계하는 데 있어서, 가장 먼저 고려해야 할 것은 변수 간의 규칙성 이다. 규칙을 찾아 점화식 을 작성할 수 있게 되면, 가장 간단한 코드 작성으로도 답은 구할 수 있는 상황이 된다. 여기에서 추가적인 최적화 (불필요한 연산 제거)를 통해서 시간을 단축할 수 있다. 즉, 메모이제이션(Memoization) 을 통해서 연산이 중복되는 것을 방지해야 한다. 1. 점화식 2. 메모이제이션 3. 더 최적화할 방법 찾기 1번을 만족시키게 되면, 완전 탐색(Brute-force) 으로 볼 수 있고, 1번과 2번을 모두 만족시켜야 동적 프로그래밍(Dynamic Programming) 이라고 볼 수 있다. 추가로 어려운 문제의 경우, 3번까지 활용해야 제한 시간 내에 해결할 수 있다. https://www.acmicpc.net/problem/14501 DP(Dynamic Programming) 를 연습할 수 있는 문제이다. 위의 문제를 풀다가, 재귀 로 푸는 방법은 쉽게 떠올랐으나 반복 문으로 푸는 방법이 바로 떠오르지 않아서 여러 코드를 분석해보았다. 여러 가지 방법이 있겠지만, 시간복잡도와 이해하기 쉬운 코드를 기준으로 선별하였다. 풀이 방법에 따라 어떤 변수를 고려하고, 어떻게 접근해야 하는지 생각해볼 수 있겠다. 0. 점화식 i번을 선택하지 않을 경우 : f(i + 1) i번을 선택하는 경우 : f(i + t(i)) + p(i) f(i) = max(f(i + 1), f(i + t(i)) + p(i))    (i <= n) f(i) = 0    (i > n)  1. 재귀적인 방법 int n, d[ 16 ], t[ 16 ], p[ 16 ]; int f( int index) { if (index == n) return 0 ; if (index > n) return INT_MIN; if (d[index] != - 1 ) return d[...

우리가 코딩하면서, 가장 많이 사용하는 자료구조 개념은 무엇일까 생각해보았다. 또, 그 중 중요하면서 유용한 것이 무엇일까 생각해보았다. 배열(array) , 해시 개념을 사용한 맵(map) , 집합(set) 같은 자료구조가 아닐까 생각이 들었고, (트리를 이용한 map, set도 있기 때문에 '해시 개념을 사용한'이라고 하였다) 검색과 생각 끝에 공통적인 개념이 사용됨을 알았다. 해시 테이블의 개념을 살펴보면, key - value 를 이용하여 원하는 자료구조를 순차 탐색할 필요 없이 바로 찾아가는 것에 있다. 그리고 이를 흔히 말하는 상수 시간 O(1) 로 볼 수 있다. 먼저, 배열을 살펴보자. 배열은 정수(0, 1, 2, ... )를 이용해서 해당 위치에 있는 자료를 바로 불러올 수 있다. 이것은 key - value로 나타내면, int형을 갖는 key와 각기 다른 타입을 갖는 value로 볼 수 있다. 즉, 배열은 key가 정수인 해시 테이블 이라고 볼 수 있다. 그러면 배열을 선언하면, 내부적으로는 어떤 일이 일어날 것인지 추측해볼 수 있다. 일단, 배열의 원하는 원소에 바로 접근하려면, 기본 주소가 필요하다. 즉, 배열의 기본주소 Base Address를 저장할 변수가 필요하다. 다음으로는 value에 해당하는 자료형의 크기를 저장할 변수가 필요할 것이다. 왜냐하면, int 32형의 경우 4byte를, int 64형의 경우 8byte가 배열 한 칸을 움직이는 최솟값이 되기 때문이다. (배열의 해당 원소의 주소 = base address + offset, offset = sizeof(자료형) * index) 그럼 좀 더 확장하여, 해시 테이블에서 사용되는 모든 타입의 key 에 대해선 어떻게 계산할까? key가 string이라고 가정하면, 문자열 abc와 문자열 bca는 위의 인덱스 개념처럼 서로 다른 위치를 가르치게 해야 한다. 그러면, 이 문자열들을 각기 다른 key를 갖게 해야 하는데, 컴퓨터 내부적으로는 숫자 이진수 0과 1로 ...

우리는 인텔의 x86-IA32를 줄여서 32bit 운영체제라고 부르고, x86-64(또는 x64)를 줄여서 64bit 운영체제라고 부른다. 이전에 AMD에서 32bit가 호환가능한 64bit OS를 선보이고, 인텔도 x64 이후 x86-64를 출시하면서 이제는 어떤 것이든 호환가능한게 당연한 상식이 되었다고 알고 있다. 따라서 호환가능함을 당연한 전제를 깔고 시작한다. 32bit 로 표현 가능한 메모리의 크기는 대략적으로 4GB(2^32)가 된다. 포인터는 변수의 메모리 주소를 가르키기 때문에, 우리가 사용하려는 주소값을 모두 가르킬 수 있는 크기가 필요하다. 따라서 위의 32bit 의 경우에는 어떤 변수 타입의 포인터라도 4byte 크기면 충분 하다. 64bit 의 경우에 포인터의 크기가 8byte 인 것도 위와 같은 논리를 따른다. 그런데, Visual Studio를 비롯한 컴파일러에서 x86, x64를 선택하여 컴파일하는 기능이 있다. 이를 이용하면, 사용가능한 메모리의 크기가 정해지므로 이에 따라서 포인터의 크기가 정해지게 되는 것이다. 결론적으로 운영체제의 표현 비트에 따라서 포인터의 크기가 변하는 것이 아니라, 컴파일 설정 에 따라서 변하게 된다. [참고] https://stackoverflow.com/questions/16823752/why-size-of-void-pointer-is-4-on-windows-64-bit-platform