J.Althea

비트 연산을 사용하면 빠르거나 간결한 코드를 작성할 수 있다. 이 외에도 활용 방안은 무궁무진하다. 앞으로 생각나는대로 추가할 생각이다. * 2의 거듭제곱과 관련된 수를 곱하거나 나눌 경우에  Shift(>>, <<) 연산을 사용할 수 있다. Example a /= 2;      <->     a >>= 1; a *= 16;     <->     a <<= 4; * 나머지 연산을 And(&) 연산으로 대체할 수 있는 경우가 있다. 2^n - 1에 해당 하는 숫자보다 작으면, 이를 나머지 연산으로 사용할 수 있다. 왜냐하면 이진수로 나타내었을 때, 모든 자리의 숫자가 1이기 때문이다. Example b = 3, m = 4; if (b % 15)     <->     if (b & 15)     <->     if (b & ((1<<m)-1)) * 어떤 숫자가 2의 거듭제곱인지 알고 싶을 때 And(&) 연산으로 간단하게 확인 가능하다. Example if (n & (n-1) == 0)     return true; * Swap 기능을 XOR(^) 연산으로 대체할 수 있는 경우가 있다. 정수형으로 나타낼 수 있는 자료형일 때만 가능하다. Example tmp = a;          <->        a ^= b; a = b;                ...

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을 자료구조에서 활용할 때의 예...

C++의 입력을 담당하는 라이브러리 함수 중에서 cin과 getline이 있다. cin과 getline의 차이를 앎에도 불구하고, 실수를 할 때가 있다. 바로 섞어서 사용할 때다. cin은 띄어쓰기(스페이스 : ' ')와 줄바꿈(엔터 : '\n')를 기준으로 잘라서 입력을 받는다. 다시 말해서, 저 두 문자를 만나면 데이터 하나에 대한 입력이 끝나는 것이다. 여기서 눈에 보이지는 않지만, 버퍼에 문자가 남게 된다. 우리가 입력을 받을 때, cin만 쓴다면 버퍼에 남아있어도 자동으로 무시하기 때문에 어떠한 문제가 발생하지 않는다. getline은 함수의 특성상 버퍼에 문자를 남기지 않는다. 또한, 구분자가 없이 모든 입력을 그대로 받기 때문에 문자열을 받을 때 사용하곤 한다. getline도 그 자체만으로는 어떠한 문제를 발생시키지 않는다. 그러나 cin -> getline을 하는 경우에는 문제가 발생할 수 있다. cin을 사용하면 버퍼에 띄어쓰기나 줄바꿈 문자가 남아있게 되고, 여기서 getline을 사용하면 버퍼에 남아있는 문자를 그대로 받게 된다. 따라서, 같이 사용하는 경우에는 버퍼 처리를 꼭 해주어야 한다. 버퍼에 남아있는 문자가 의미없는 경우 cin.ignore();를 통해서 버퍼를 비우면 된다. cin -> cin.ignore -> getline 순서가 되는 것이다. * C의 scanf와, Java의 new Scanner(System.in).next도 마찬가지로 버퍼에 남긴다. 사용하는 언어가 달라도 입력 라이브러리 함수에 대해서는 사용 목적에 따라 꼭 버퍼 처리를 확인하고 처리하는 습관을 갖자.

첫 번째 문제에서 테스트케이스의 일부분이 실패하길래 디버깅하다가 1시간을 쓴 것 같다.. (0이 들어오진 않고, 로직은 맞았으나 형 변환을 하지 않아서 틀렸다.) - 19/11/16 많이 아쉬웠던 건 모든 문제에 대해서 접근 방법과 구현 방법이 떠올랐는데, 제대로 된 정답을 내지 못한 것이다. 대체로 요번 윈터코딩에서는 규칙성을 찾는 문제 위주로 나온 것 같다. 2번 문제는 정답이지만, 1번 부분점수 상태에서 디버깅 하다가 3번을 제대로 못풀고.. 그래서 아쉬운 대로 내가 풀었던 방법을 적어놓고자 한다. (현재 모든 문제 해결하였습니다.) #1 멀쩡한 사각형 N x M 격자판에 양 꼭짓점으로 대각선을 하나 그었을 때,  직선에 걸치는 사각형을 전체 사각형의 개수에서 빼는 문제이다. 격자의 최소 단위는 1 x 1로 이루어져 있고, w와 h가 주어진다. (범위는 1억까지) 규칙을 찾다가, 정사각형일 때와 아닐 때 를 생각해보았다. 정사각형인 N x N 형태이면, 대각선으로만 걸치므로 w * w - w를 하면 된다. 정사각형이 아닌 N x M 형태이면,  선에 걸치는 사각형들이 오른쪽 또는 아래를 걸쳐서 선을 타고 내려오는 모습이 된다. (그림 참조) 3x3 사각형과 8x12 사각형 대각선이 아닌 오른쪽 또는 아래로만 거쳐서 선에 걸치는 사각형만 있으면 생각하기 쉽다. 그러나, 문제에서 주어진 예제 테스트케이스로 w=8, h=12를 생각해보면 중간마다 정사각형일 때 처럼, 대각선으로 걸치는 경우도 있다. 이 경우가 언제인지를 생각해보자. 그림에서 보면 정확히 2 x 3지점에서 대각선으로 걸치고 있다. 그리고 전체가 2 x 3인 사각형들을 4번 대각선으로 붙인 모습이다. 여기서 생각해볼 수 있는 건 이 2 x 3이 현재 전체 사각형들이 대각선으로 걸치는 최소 단위라는 것이다. 직선이므로, 내부에 존재하는 부분 직선도 ...

프로그래밍에 관심이 많은 Jang입니다. 부족하지만 발전하는 블로거가 되도록 하겠습니다. ^^