J.Althea

Visual Studio처럼 0으로 나누었을 때, 0으로 처리해주는 개발환경이 있고 아닌 경우가 있다. 따라서, 0으로 나누어질 수 있는 경우가 있으면 예외처리를 하자.

알고리즘 문제를 풀다가 다른 분의 코드와 시간 복잡도 상에서는 거의 차이가 없는 것 같은데, 왜 이렇게 차이날까 하던 적이 있었다.  뭘까 뭘까 하면서 열심히 찾다가 값 복사에 의한 속도 차이였음을 알았다. 실제로 STL중에 vector 변수를 쓰다가 변수를 읽거나 변경할 때 그냥 넘겨주었던 경우가 있었다.  따라서 기본형의 변수가 아니면 C++, C# 기준으로, &(레퍼런스, 참조자)를 적극 활용하자. (C, Java는 참조자가 없지만 객체의 주소를 넘기는 방식인 pass-by-address로 전달 가능하며, Java는 따로 키워드를 쓸 필요가 없고, C는 *를 써서 가능하다. ) https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value * 혼동을 위한 정리 C++, C# : pass-by-value, pass-by-reference C, Java : pass-by-value, pass-by-address pass-by-value : 똑같이 복사하는 것 (별개의 데이터가 하나 더 생긴다.) pass-by-address : 값이 저장된 주소를 복사하는 것 (값만 바꿀 수 있고, 원래의 변수 상태를 바꿀 수 없다.) pass-by-reference : 변수 그 자체를 참조하는 것 (값과 원래의 변수 그 자체를 바꿀 수 있다.)

간단하지만, 실수하기 쉬운 것들을 정리해보았다. (1) 현재 자료형에 대한 연산을 할 때, 오버플로우 가능성을 생각한다. 예:     long long solution(int w, int h)     {         return w * h; (X)         return (long long)w * h; (O)     }     int main()     {         int a = 100,000,000, b = 99,999,999;          solution(a, b);     } (2) 현재 자료형을 다른 자료형으로 형변환할 때, 오버플로우 가능성을 생각한다. 예:     long long a = 123,456,789,123,456,789;     double b = a;  (X) <- 대략적으로 10^16을 넘어가는 숫자를 그대로 담을 수 없다. (3) 영문과 숫자에 관련된 문자를 처리할 때, char가 127을 넘어가는 것을 생각한다. (C, C++) 대소문자를 변환할 때나 더해주는 작업을 할 때, 1byte 내에서 해결하려고(?) 문자형을 정수형으로 바꿔주지 않고 하는 경우가 많다. 이때, 실수하지 않도록 유의하자. (C#, Java의 경우는 char가 유니코드를 기반으로 한 2byte로 설정 되어있다.)   (4) 연산이나 함수 사용중에 형변환 되는 부분을 생각한다.

실수형의 부정확함(?)에 대해서 생각해보다가, 어떤 분의 블로그를 보게 되었다. 우리는 아래의 문제에 대한 답을 생각해볼 수 있다. (1) double a = 0.1 + 0.1; double b = 0.2; if (a == b)     printf("same"); else     printf("different"); Output : ? (2) double a = 0.1 + 0.2; double b = 0.3; if (a == b)     printf("same"); else     printf("different"); Output: ? (3) double a = 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1; double b = 1.0; if (a == b)     printf("same"); else     printf("different"); Output : ? 위의 문제의 답은 (1) same, (2) different (3) different 이다. 이 이유에 대해서 간단히 말하면, 컴퓨터의 모든 명령은 0과 1로 이루어진 이진수로 동작하기 때문이다. 즉, 실수 표현도 이러한 이진수로 표현하려고 하기 때문에 오차가 발생할 수 있는 것이다. (컴퓨터 구조마다 이진수의 오차를 처리하는 방법에 따라 결과값이 다를 수 있다.) 위의 문제를 직접 이진수로 표현해보자. 0.1 = 1/16 + 1/32 + 1/256 + ... 계산하다보면 알겠지만, 절대 정확하게 나타낼 수가 없다. 0.5와 같이 딱 떨어지는 값은 나타낼 수 있겠지만, 무수히 많은 실수가 오차를 갖는다. 위와 같이 10진수 체계에서 딱 떨어지는 값이여도 2진수 체계에서 무한한 길이를 갖는다면, 오차가 생기는 것을 알 수 있다. 확장해서 무한소수를 이진수...

유전 알고리즘을 이용한 테트리스 게임을 개발중이였다. 게임속도 증가 버튼을 누르면 속도가 증가하다가 최대점에 됐을 때, 블록을 두는 과정을 생략하는 Skip 모드가 있다. 이 Skip 모드가 켜지면 필드에 적절한 위치로 블록을 바로 그려넣는데, 문제는 현재 블록에 목표 블록을 초기화할 때 발생할 뻔 했다. * 수정 전 코드 * 수정 중 코드 (문제 발생 가능한 상황 : count !=0 인 상태에서 oSkip == true로 코드에 진입시,  사용자가 다시 oSkip == false 한경우) * 수정 후 코드 수정 전 코드에서 Skip 모드인지 아닌지에 대한 조건을 계속 검사해주는 것이 싫어서, 조건문 없이 Skip 모드이면 값을 업뎃해주고 하려고 했으나 중간에 섬짓한 느낌이 들어서 다시 수정해버렸다. 이게 최선인지 고민해봐야겠다. @_@

#1 Simple Recursion long long fib(long long n) {     if (n <= 1)         return n;     return fib(n - 1) + fib(n - 2); } Time complexity: < O(2^n) : 1.6^n Used thinking: a literal representation of the Recurrence formula. #2 Fast Simple Recursion const long long MAX = 100; long long fibResult[MAX]; long long fib(long long n) {     if (n <= 1)         return n;     else if (fibResult[n] != 0)         return fibResult[n];     return fibResult[n] = fib(n - 1) + fib(n - 2); } Time complexity: < O(n^2) Used thinking: 'Memoization' memorization is a concept in which previously used values are stored and not repeated for the same value. #3 Simple Iteration const long long MAX = 100; long long fibResult[MAX] = { 0, 1 }; long long fib(long long n) {     for (int i=2; i<=n; i++)         fibResult[n] = fibResul...

보통 Visual Studio에서 C++으로 코드를 작성할 때 Debug 모드로 하는 경우가 많다. 그래서 이것을 신경쓰지 않고 있다가 완전탐색(Brute-force search) 문제를 푸는데  이상함을 느꼈다. https://www.acmicpc.net/problem/1436 위의 문제에서 n이 최대 10000까지인데, 내가 작성한 코드에 10000을 넣고 돌리면 5초가 넘게 걸렸기 때문이다. (문제에서 시간 제한은 2초) 그래서 찾아보니, Debug 모드에서의 실행속도가 Release 모드보다 훨씬 느릴 수 있다는 것이다. 나의 부족함을 깨닫고 바로 Release 모드로 바꿔서 돌리니 순식간에 나와버렸다. 아래는 각 모드의 특징을 간단하게 적어보았다. Debug mode :   실행파일에 디버깅 정보를 포함하여 언제든지 디버깅이 가능하다. 디버그에 필요한 정보들을 실행시 계속 체크함으로써 속도가 느리다. Release mode : 디버깅 정보가 없고, 코드를 최적화하여 실행 파일 크기를 최대한 줄여준다. 초기화 하지 않으며, 같은 문자열 상수라도 서로 다른 공간에 할당된다. 따라서 속도나 크기면에서 상당한 차이를 보일 수 있다.

알고리즘 문제를 풀면서 STL 자료구조를 자주 사용하게 됐는데, 정렬 기준을 재정의해주는 함수를 작성하다가 functor의 존재를 알게 되었다. function은 일반적으로 우리가 알고 있는 함수이다. functor을 구글에 쳐보면 수학적 용어로 함자라고 나오는데, 이 개념이 프로그래밍에서 어떻게 쓰이는지 궁금해서 찾아보았다. functor는 일반적으로 함수의 기능을 갖고 있다. 거기에 더해서 어떤 특징이 있을까? 첫 번째 특징은 상태를 가질 수 있다. 바꿔말하면, 클래스나 구조체와 같이 쓰인다는 것이다. 그래서 functor를 함수 객체(function object)라고도 한다. 두 번째 특징은 범위를 갖는 자료구조에서 해당하는 범위에 적용 가능하다. 배열과 리스트류의 자료구조를 정렬하거나 모든 데이터를 더하는 연산을 할 때 functor의 이름을 한번 호출하면서 목적을 해결할 수 있게 된다. 그래서 STL과 함께 자주 사용된다. 그러면 operator()와의 관계는 무엇일까? operator()는 함수 호출을 재정의하는 용도로 사용한다. 즉, operator() 내부에 함수의 기능을 작성하고 사용할 때 우리는 함수를 호출하듯이 간편하게 사용할 수 있게 된다. 다시 말하면, 위의 functor의 역할은 함수를 보다 스마트하게 쓰고 싶어서 인데, operator()를 사용하여 함수를 정의하면, 다른 불필요한 과정없이 사용하고자하는 함수의 기능만 간편하게 사용할 수 있게 된다. 더해서, sort에서 비교 하는 함수 cmp를 단순한 기존 형태로 구현할 수 있지만, priority_queue<T, vector<T>, cmp<T>> pq에서 쓰일 때에는 operator()를 재정의하여 구현해야하는 차이점이 있다. 아래 코드는 단순하게 더하는 역할을 하는 sum의 예제와 절댓값 순서대로 정렬하고 싶어서 만든 cmp와 C++에서 제공되는 greater을 자료구조에서 활용할 때의 예...