재미있는 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

댓글을 달아 주세요

프로그래머를 위한 문제 #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);

Mitsuru 블로그에 재미있는 LINQ 문제가 올라와 있네요..
 
문제는
 
var values1 = newstring[] { "1", "2", "3" };
var values2 = newstring[] { "A", "B" };
 
var q = ?
 
foreach (var v in q)
    Console.WriteLine(v);

 
 
뭐.. 내가 볼땐 조인하라는 말 같은데,, 저는 나름대로 아래와 같이 풀어 보았습니다.

답은 여러가지 나올 수 있겠죠? 같이 푸실 분은 아래를 보지 마시고, 원문 먼저 보시고 맞춰보세요 ^^

 
원문
 














 
var values1 = new string[] { "1", "2", "3" };
var values2 = new string[] { "A", "B" };
 
var q = from a in values1
               from b in values2
               orderby a+b ascending
               select a+b;
 
foreach (var v in q)
        Console.WriteLine(v);
 
실제 쿼리문만 보시면 될 것 같네요. 허벌나게 간단하죠?
 
엇. 쓰고보니, 두 번째 댓글에 비스므리 하게 답을 누가 달아놓았네요 +_+;
그래도 여기까지 쓴게 아까워서…
 
텨텨 =3=3=3
Posted by 땡초 POWERUMC
TAG LINQ, Quiz

댓글을 달아 주세요