재미있는 C 언어 문제

인터넷 RSS 피드를 구독해서 보다가 재미있는 C 언어 코드를 발견했다. 조금 난해하게 보이는 코드다. 이런 코드로 신입 개발자 면접 시험을 보면 재미있겠단 생각이 든다.

문제의 C 언어 코드는 다음과 같다. 소스 코드와 실행 결과가 전혀 매치가 안되는 이 또라이 같은 코드를 보고 순간 멈칫 할 것이다. 하지만 조금 귀 기울여 보면 말 되는 코드다.

이 링크를 클릭하면 즉시 컴파일 된 실행 결과도 함께 볼 수 있다.

main()
{
int a,b,c;
int count = 1;

for (b = c = 10; 
a = "- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
Hq!WFs XDt!"[b+++21]; )
for(; a-- > 64 ; )
putchar ( ++c=='Z' ? c = c/ 9:33^b&1);

return 0;
}

/* 실행 결과
                    !!!!!!                                                     
                    !!!!!!!!!!                                                 
                     !!!!!!!!!!!!!!!                                           
                       !!!!!!!!!!!!!!                                          
                     !!!!!!!!!!!!!!!                                           
                      !!!!!!!!!!!!                                             
                      !!!!!!!!!!!!                                             
                        !!!!!!!!!!!!                                           
                        !!!!!!!!                                               
                        !!!!!!!!!!                                             
                       !!!!!!!!!!!!!!                                          
                     !!!!!!!!!!!!!!!!                                          
                    !!!!!!!!!!!!!!!!                                  !!!!!    
                  !!!!!!!!!!!!!!!!!!!                               !!!!!!!!!! 
                 !!!!!!!!!!!!!!!!!!!!!!!                 !         !!!!!!!!!!  
            !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!              !!     !!!!!!!!!!!!    
           !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!      !!!!!!!!       
            !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!      
             !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!       
              !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  !!!!!!!!!!!!       
       !!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!!!!!        
      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!      !!!!!         
          !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!!          
        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !          
          !!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                       
           !!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                         
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                          
                 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                           
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                               
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                               
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!                                 
                  !!!!!!!!!!!!!!!!!!!!!!!!!!                                   
                  !!!!!!!!!!!!!!!!!!!!!!!!!                                    
                   !!!!!!!!!!!!!!!!!!!!!!!!                                    
                    !!!!!!!!!!!!!!!!!!!!                                       
                    !!!!!!!!!!!!!!!!!!!                                        
                     !!!!!!!!!!!!!!!!                                          
                      !!!!!!!!!!!!!!!!                                         
                      !!!!!!!!!!!!!!!                                          
                       !!!!!!!!!!!!!!                                          
                        !!!!!!!!!!!!                                           
                        !!!!!!!!!!!!                                           
                        !!!!!!!!!!!!                                           
                          !!!!!!!!                                             
                          !!!!!!                                               
                           !!!!                                                
*/

코드 분석

이 코드는 C 언어 문법에 어긋나지 않지만 알아보기 힘들게 교묘하게 섞어 놨다. 잘 보면 위의 코드를 이해할 수 있는 몇 가지 단서를 발견할 수 있다.

1. 문자의 배열

이 코드를 잘 보면, for (b = c = 10; a = "- FIGURE?, .. 중간 생략 .. Hq!WFs XDt!"[b+++21]; )
a 변수에 대입 되는 값은 "...문자열..."[인덱스] 값인 char 문자가 된다.

b = 10 초기 값을 가지므로 배열의 인덱스 값은 [11+21], 즉 32번 문자부터 시작하므로 a 변수의 문자열 "- FIGURE?, UMKC,XYZHello Folks,\" 은 그냥 더미(쓰레기) 값임을 알 수 있다.

2. 섞어 놓은 문법 풀기

이 코드에서 for (b = c = 10; a = "- FIGURE?, .. 중간 생략 .. Hq!WFs XDt!"[b+++21]; )
배열 인덱스를 나타내는 [b+++21] 코드는 [(b++)+21] 로 풀어 쓸 수 있다.

putchar ( ++c=='Z' ? c = c/ 9:33^b&1); 코드는 일반적인 삼항식이다.
삼항식인 ++c=='Z' ? c = c/ 9:33^b&1 코드는 (++c == 'Z') ? (c = c / 9) : (33 ^ b & 1) 이렇게 풀어 쓸 수 있다.

이 두 가지의 문법적인 부분만 발견하고 풀어냈다면 다 한 것이나 다름 없다.

(++c == 'Z')는 ASCII 코드 표를 참고해 보면 (++c == 90)이 되고, c = 10인 초기 값을 갖는다. 그러므로 80번 반복 후에 c=c/9 코드의 값은 언제나 10=90/9이 되므로 10인 ASCII 코드인 'new line', 새로운 행에서 문자를 계속 찍는다.

(33 ^ b & 1) 코드는 (33 xor b and 1) 비트 연산과 같다. xor, and 연산 중 and 연산이 더 우선 순위이므로 (b and 1) xor 33 이렇게 표현할 수 있겠다.

33 - (b ^ 1) 코드로 최종적으로 표현되는데, b^1은 홀수면 1, 짝수면 0이 된다. ASCII 코드 표를 참고해 보면 33,32 값은 각각 '!' 문자와 'Space' 문자가 된다.

아래는 ASCII 코드 표 이므로 참고하기 바란다.

ASCII 코드표
ASCII 코드표

코드가 실행되는 순서대로 ASCII 값을 대입해 보면, 코드가 어떻게 실행 결과처럼 출력 되는지 이해할 수 있을 것이다.

보기 쉬운 코드로 변경

코드를 자세히 보니 별 것 아니란 걸 느꼈을 것이다. 이 코드를 리팩토링여 알아보기 쉬운 코드로 아래와 같이 바꿀 수 있다. 그럼 같은 결과를 얻을 수 있다. 혹시 잘 이해가 되지 않는다면 아래의 코드를 if 문법으로 변경해 보면 더 보기 편할 것이다.

int main()
{
    int a,b,c;

    char *str = "- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
Hq!WFs XDt!";

    for (b = c = 10; a = *(str + (b++) + 21); ) {
        for(; a-- > 64 ; ) {
            putchar ( ++c==90 ? c = c / 9 : 33 - (b&1));
        }
    }   
}
Posted by 땡초 POWERUMC

댓글을 달아 주세요

[퀴즈] 프로그래머를 위한 문제 #3

요즘 퀴즈를 풀다보니 재미가 들렸나, 필자가 문제를 하나 내보려고 한다. 어려울 수도, 그렇지 않을 수도 있는 문제이며, 효율적인 코드를 작성하는 것 보다 최대한 짧게 짜는 것이 목적이다.

문제의 유형과 정답의 유형은 지난 문제를 참고하면 된다.

미로 찾기 게임

문제는 미로 찾기 게임이다.

  1. 10 x 6 (가로, 세로) 크기에 * 문자가 채워진 직사각형
  2. 미로의 크기가 변해도 실행 가능해야 한다.
  3. 문자 S 는 입구 위치, 문자 E는 출구 위치이다.
  4. S 문자와 E 문자 사이에는 공백으로 연결된 길이 있고, 길은 여러 갈래일 수 있다.
  5. 길(공백)은 2x2(가로, 세로) 이상의 공간을 가질 수 없다.
  6. 미로 찾기를 시작하는 함수가 호출되기 이전의 초기화를 위한 코드는 코드 길이에서 제외된다.
  7. 코드 길이는 최대한 짧게 작성한다. (알고리즘 효율성은 측정 안함)
  8. 개발 언어는 무관, 언어별로 가장 짧게 작성한 코드가 우승(?)



미로 찾기 게임 예제 코드

// 아래의 변수의 초기화는 코드 길이에서 제외된다.  
map = """  
**********  
** **    E
*   * ****
* * * *  *
* *    * *
S ****   *  
**********"""

y = map.indexof("S") / maxX
x = map.indexof("S") % maxX  

// 아래 코드 부터 코드 길이를 잰다. 개행 문제는 코드 길이에서 제외  
void explore(x,y)
{
    // ...생략...
}  

정답

아래는 필자가 작성한 코드이다. 짧게 작성하는 방법은 여러 가지이므로 혹시 여러분들께서 C++ 또는 자바스크립트, C# 등으로 작성하신 코드는 댓글로 달아주세요.

Python( 파이썬 )

아래 주석의 begin code/end code 사이의 문자는 총 273 문자. 방향에 대한 가중치를 주면 훨씬 빠르게 길을 찾을 수 있지만, 여기에선 구현을 제외했다.

#123456789
m = """  
**********  
** **    E
*   * ****
* * * *  *
* *    * *
S ****   *  
**********"""

X = m.index("\n", 1) - 1
Y = m.count("\n") - 1
m = m.replace("\n", "")  

(y, x) = divmod(m.index("S"), X)  

### 총 273 바이트 ###  
########### begin code ############  
def E(x,y,a):  
 n=m[x+(y*10)]  
 if n=="*"or x<0 or x>X or y<0 or y>Y:return None

 # print "%d, %d" % (x, y)  
 if n=="E": print("END");quit()

 while a!=2 and E(x+1,y,1)!=None:pass  
 while a!=1 and E(x-1,y,2)!=None:pass  
 while a!=8 and E(x,y+1,4)!=None:pass  
 while a!=4 and E(x,y-1,8)!=None:pass  

E(x,y,0)  
############# end code ##############


## 실행 결과 ##  
0, 5  
1, 5  
1, 4  
1, 3  
1, 2  
2, 2  
3, 2  
3, 3  
3, 4  
4, 4  
5, 4  
6, 4  
6, 5  
7, 5  
8, 5  
8, 4  
8, 3  
7, 3  
5, 3  
5, 2  
5, 1  
6, 1  
7, 1  
8, 1  
9, 1  
END  


Posted by 땡초 POWERUMC

댓글을 달아 주세요

프로그래머를 위한 문제 #2

얼마 전 OKJSP 를 통해 이런 문제를 보았다.

문제는 아래의 코드 중 /* INPUT */ 주석에 알맞은 코드를 넣어, victory() 메서드가 호출되도록 완성하여라.

필자의 컴퓨터에서는 답이 (function-48)(); 로 나왔다. 

typedef int (*f)(); 
int variable = 1;   

int function() {     
   if(variable == 1 ) return 
      /* INPUT */       
   5; 
   victory();  
}   

int main() 
{     
   function();
   return 0; 
}  

[문제 코드] 위의 INPUT 주석에 알맞은 코드를 넣어라.

단 제약 조건이 있습니다.

  • 다음의 문자는 사용할 수 없음 : main, victory, asm, %, *, _, #, /, “, ‘
  • 최대 11자
  • 세미콜론(;)은 한 번만 써야 함

문제 해결 과정 #1

일단 Visual Studio 2012 C++ 로 작성한 코드인데, 이 코드는 답을 찾아가기 위한 중간 코드이다.

이 코드를 보자마자 ‘스택 프레임(Stack Frame)’을 이용해야겠다는 맘을 먹고 코드를 작성했다. Visual Studio에서 만든 C++ 프로젝트의 속성으로 들어가서 RTC 런타임 체크 기능을 꺼야 한다. 그렇지 않으면 스택을 덮어 쓸 수가 없이, AccessViolation 오류가 발생할 것이다.

프로젝트 속성 -> 구성 속성 -> C/C++ -> Code Generation -> Basic Runtime Checks -> Default 로 변경

#include "stdafx.h"  
#include <iostream>  

using namespace std;  

int victory()
{
    cout << "victory" << endl;
    return 0;
}  

typedef int (*f)();  
int variable = 1;  

int function()
{
    int a;
    int n = (int)(&a) + 8;// 일반적으로 스택은 위로 자라므로,  EBP + 4 의 위치를 구함

    // victory 메서드 시작 위치는 현재로 부터...  765임
    cout << (int)(&victory) - (int)(&function) << endl;  
    *(void**)n = (void*)((int)(&function) - 765);    

    if(variable == 1 ) return
    /* INPUT */ 
    5;
    victory();
}  

int _tmain(int argc, _TCHAR* argv[])
{
    function();
    return 0;
}  

// 실행 결과  
// -765  
// victory  

대충 그림이 나왔으니 코드를 /* INPUT */ 에 들어갈 수 있도록 예쁘게 다듬어주면 될거라고 생각했다. 그런데 VC++은 타입체크가 너무 강한지 몰라도 어떻게 예쁘게 다듬어도 오류가 난다. 줸장~ 문제와는 상관 없이 좀 더 만져봐야 겠다.

문제 해결 과정 #2

오늘 정성태 과장님이 이 문제를 보고 이야기를 나누었고 답을 보여주셨다. 답은 링크를 통해 방문하면 된다.

과장님 왈, VC++ 에서는 컴파일이 안될거라고, GCC에서 컴파일 했다고 알려주셔서 나도 얼른 GCC로 바꿨다. 궁극적으로 위의 문제 해결 과정 #2 방법을 GCC로 간결하게 표현했다. 어쨌든 정성태 과장님과 답이 거의 같다.

정성태 과장님이 아니었으면 VC++만 가지고 매달렸을텐데, 문제를 풀 수 있도록 도와주신 울 과장님께 ㄱㅅ ㄱㅅ ^^

# include <stdio.h>  

int victory()
{
    printf("victory\n");
    return 0;
}


typedef int (*f)();  
int variable = 1;  

int function()
{
    // victory 메서드가 얼마만큼 떨어져있나 찍어봄... 48만큼...
    printf("%d\n", &function - &victory);  


    if(variable == 1 ) return

        (function-48)();      /* <------- INPUT CODE */
    ;

    5;

    victory();

}  

int main(int argc, const char * argv[])
{
    printf("---------------\n");
    function();
    return 0;
}   

// 실행 결과  
48
victory  


Posted by 땡초 POWERUMC

댓글을 달아 주세요

  1. orbit 2016.12.20 14:16 Address Modify/Delete Reply

    재미있는 글이네요
    저는 VS2015에서 이렇게 풀었습니다.

    #include "stdafx.h"
    #include "victory.h"

    #ifdef _DEBUG
    #define new DEBUG_NEW
    #endif

    #include <iostream>

    int victory()
    {
    std::cout << "victory" << std::endl;

    return 0;
    }

    typedef int(*f)();
    int variable = 1;

    int function() {

    f foo = (f)((int)function - ((int)function - (int)victory));

    if (variable == 1) return
    /* INPUT */ foo();
    5;
    victory();
    }

    int main()
    {
    function();
    return 0;
    }

프로그래머를 위한 문제

프로그래머라면 알쏭달쏭한 논리적인 문제를 좋아하는 편인 것 같다. 답이 팍~ 나오는 문제보다 역량에 따라 코드의 아름다움이 달라지는 것을 추구하는 프로그래머라면 더욱 그렇다.

문제: 1부터 1만까지 8은 모두 몇 개가 나오나?

문제는 쉽다. 1부터 1만까지 8이라는 문자 개수만 카운팅하면 된다. 그런데 이렇게 간단한 문제를 코딩해 놓고 보면 맘에 안든다. 더 짧게…. 아래의 문제를 각 언어별로 풀어보았는데, 바이트 수는 캐러지 리턴(carriage return) 문자를 모두 제거한 바이트 수이다.

참고로, 이 문제는 ‘닷넷(.NET) 프로그래머 모임’ 에서 처음 본 문제인데, 오래 전의 일이라 게시글의 링크를 도저히 찾기가 힘들어서 링크를 남기지 못했다.

여러분 중 문제를 풀어보려고 한다면, 바로 아래에 답이 있으니 브라우저를 먼저 종료하길 바란다.

파이썬(python)

파이썬을 배운지 얼마 안되던 때에 이 문제를 만나서 파이썬으로 풀어보았다. 누가 짜도 최종적으로 아래의 코드가 될거다. 처음에는 이렇게 짧게 가능한 파이썬이 맘에 안들었지만, 이제는 맘에 든다. ㅋ;

더 이상은 짧게 안되지 싶다.

# 총 38 바이트   
(str(list(range(1,10001))).count('8'))  

C#

C# 코드로 짜면 아래처럼 된다. 아래의 코드는 확장 메서드와 람다 표현식이 전부다.

혹시나 요걸 비트 연산으로 풀어봤는데, 아래 코드보다 길어지더라. 뭐 내가 짠 코드라 길어질 수도 있겠다.

// 총 84 바이트  
Console.WriteLine(Enumerable.Range(1,10000).Sum(o=>o.ToString().Count(n=>n=='8')));   

Java

Java 8 정식이 나오면 Lambda 지원. 다만 C#의 확장 메서드를 언어상 지원하지 않으므로 Where, Select, Take, Skip 과 같은 확장 메서드는 사용하지 못할 것 같다. 어쨋든 Java 로 이 문제를 짧게 풀수 있는 경쟁력이 없으므로 패스!

C++ Update - 2013-07-04

C++에 대해 조예가 깊지 않아서 내 머리로는 더 짧게 안된다. 이 코드는 위의 파이썬과 C#과는 알고리즘(?)이 좀 틀리다. 어쩔 수 없다. 짧게 하려면…

// 총 146 바이트  
vector<int> v(10000);  
auto n=1,s=0;  
generate(v.begin(),v.end(),[&n, &s](){  
auto m=to_string(n);  
s+=count(m.begin(),m.end(),'8');  
return n++;});  
cout<<s;

아래 댓글에 더 짧은 C++ 코드를 올려주신 HATENA [링크] 님께서 올려주신 코드 입니다. Update - 2013-07-04

// 총 94 바이트
int c=0;
for(int i=1;i<10001;i++){
auto s=to_string(i);
c+=count(s.begin(),s.end();'8');}
cout<<c;

JavaScript - Update 2013-07-03

본 코드는 아래 댓글의 ddd 님께서 작성하신 자바스크립트 코드 입니다.

// 총 94 바이트  
var a=[];
for (var i=1;i<10001;i++)
a[i]=i;
console.info(a.join("").replace(/[^8]/gi,"").length);
Posted by 땡초 POWERUMC

댓글을 달아 주세요

  1. 황정현 2013.07.02 09:33 Address Modify/Delete Reply

    예전에 자바스크립트로 한번 풀어봤었네요... 근데 너무 길어요...
    for(var i = 0, len = 10000, count = 0, tmp = ""; i < len; i++){
    var arr = [];
    tmp = (""+i);
    for (var j = 1, len2 = tmp.length; j <= len2; j++)
    {
    arr[j] = tmp.substring((j - 1), j);
    if(arr[j].indexOf("8";) > -1) count++;
    }
    }
    console.log(count);

  2. ddd 2013.07.03 17:53 Address Modify/Delete Reply

    javascript 는 이정도 면 될듯한데
    var a = [];
    for (var i = 1; i < 10001; i++)
    a[i] = i;
    alert(a.join("";).replace(/[^8]/gi, "";).length);

    javascript 는 반복문 안쓸수 없나요 ㄷㄷ

    • 엄준일 2013.07.04 10:28 Address Modify/Delete

      댓글로 적어주신 소스 코드를 제 포스트에 업데이트 했습니다.
      ddd 님 사이트 링크를 남기고 싶었는데,
      링크가 없어서 아쉽네요 ㅠ

  3. HATENA 2013.07.04 11:27 Address Modify/Delete Reply

    항상 블로그 잘 보고 갑니다.
    C++은 vector, generate 안써도 쉽게 풀릴거같은데요 ㅎㅎ.

    int c=0;
    for(int i=1;i<10001;i++){
    auto s=to_string(i);
    c+=count(s.begin(),s.end();'8');}
    cout<<c;

    요거면 100byte 이내로 끝날거같습니다.
    파이선 코드길이 ㅎㄷㄷ하내요 ㄷㄷㄷ

  4. java론 2014.01.07 15:46 Address Modify/Delete Reply

    자바로는 아래처럼....
    int a=0;
    for(int i=0;i<10001;i++) {
    a+=(""+i).replaceAll("[^8]","";).length();
    }

  5. 김인혜 2014.04.06 03:56 Address Modify/Delete Reply

    마이너한 스크립트 언어입니다.
    AutoHotkey

    Loop 10000
    _ .= A_Index
    Msgbox % RegExReplace( _, "8", "", @ ) ? @ :

  6. 지나가다 2015.12.15 15:03 Address Modify/Delete Reply

    만들고 나니 위분거랑 같네요 ㅡㅡ;
    int result = 0;
    for (int i=0; i<=10001; i++) {
    result += String.valueOf(i).replaceAll("[^8]", "";).length();
    }
    return result;

  7. 행인 2016.11.20 15:28 Address Modify/Delete Reply

    Acm 문제에서 간간히 등장하는 유형이네요.
    그 당시 풀때 속도 문제 때문에 reject떠서 수학적으로
    규칙을 찾아서 accept 받았던 기억이 나네요

  8. 재밌네요 2016.11.29 16:02 Address Modify/Delete Reply

    Javascript 좀더 짧게~
    --------------------------------------
    var i,s,r; for (i = 1; i < 10001; i++) s += '' + i; r = s.split('8').length-1;
    console.log(r);