프로그래밍 문제풀이 사이트에서 재미로 해 볼 만한 숏코딩 기법들.

소스코드의 바이트 수를 최대한 줄여보는 것이다.

특정 컴파일러에서만 되는 부분이 있기 때문에 문제풀이 사이트의 컴파일러 종류와 버전을 고려해서 해야 한다...



1. 컴파일러의 특성에 따라 코드를 최대한 생략한다.

gcc컴파일러에서는 #include <stdio.h>를 생략해도 되고,

main함수의 반환형이나 리턴을 생략해도 된다.

main(){printf("Hello Wolrd!");}



2. 문자열 출력만 있는 경우 printf()대신 puts()함수를 사용한다.

2바이트를 더 줄일 수 있다.

main(){puts("Hello Wolrd!");}



3. 반복문을 쓸 때 scanf()함수의 반환값을 이용한다.

scanf()함수는 EOF(end of file)가 입력되었을 때 0을 반환하므로

이것을 이용하여 for문을 작성한다.

for(;~scanf("%d",n);)



4. 배열 입력을 받을 때 포인터를 사용한다.

첨자(subscript)연산자를 사용하는 것보다 1바이트를 더 줄일 수 있다.

경우에 따라 i를 0으로 초기화하는 구문이 필요할 수도 있다.

a[100],i;

main(){  

for(;~scanf("%d",a+i++););

}



5. 배열을 전역변수로 선언한다.

이렇게 선언된 배열은 0으로 초기화되어 있어서 초기화하는 구문을 줄일 수 있다.

a[100];main(){}



6. 변수를 main()함수 안에서 선언하는 대신 매개변수 자리에 쓴다.

세미콜론과 데이터형을 생략할 수 있다.

main(a,b,c,d){}



7. 테스트 케이스 입력을 버린다.

3번에서처럼 scanf()의 반환값을 이용하면 테스트 케이스 입력을 버려도 되는 경우가 있다.

이 코드는 다른 메모리를 침범할 수 있는 위험이 있지만 Judge사이트에서 채점만 통과하면 그만이다...

main(T){

gets(&T);

for(;~scanf("%d",n);){

//n처리

}}



8. 문자열을 선형탐색할 때 널문자의 값이 0인 것을 이용한다.

널 문자('\0')는 정수로 0이기 때문에 for문 조건식에서 조건을 끝내는 데 사용할 수 있다.

char s[100];

gets(s);

for(i=0;s+i++;){

//처리

}



9. 한 테스트 케이스에 대한 결과출력을 for문 증감식에서 한다.

세미콜론을 생략함으로써 1바이트를 더 줄일 수 있다.

for문 안의 구문을 1행으로 만들 수 있으면 2바이트를 추가로 줄일 수 있다. 

for(;~scanf("%d",a);printf("%d",b)){

//처리

}



10. 3항 연산자(?:)를 사용한다.

가독성을 희생하여 짧은 코드를 얻을 수 있다.

puts(a%3?"Fizz":"Buzz");

min=d1<d2?(d1<d3?d1:d3):(d2<d3?d2:d3);



11. 홀짝 판별과 동등비교시 비트 연산자를 사용한다.

홀수/짝수 판별을 할 때 &(AND)연산자를 사용하여 2바이트를 줄일 수 있고,

동등비교를 할 때 != 대신 ^(XOR)연산자를 사용하여 1바이트를 줄일 수 있다.

전자는 연산자우선순위가 아래 예시와 같을 때 해당한다.

if(a&1)   //a가 홀수일 때 참이 됨

if(a^b)   //a!=b일때 참이 됨



12. 특정 컴파일러에 의존적인 함수를 찾는다.

예를 들어 엔디안을 변환하는 POSIX 라이브러리 함수로 이런 문제를 63바이트 이내로 코딩할 수 있다. 



13. 효율적인 알고리즘으로 문제를 푼다.

이 방법이 근본적으로 코드 길이를 줄일 수 있는 방법이다. 

1부터 n까지의 정수를 모두 더하는 코드를 작성할 때 반복문을 사용하는 대신 n*(n+1)/2 로 계산하면 더 짧다.

한 원소만 제외하고 같은 원소가 2개씩 들어있는 배열 ex) {5, 3, 2, 4, 1, 4, 5, 1, 3} 에서 단독으로만 존재하는 원소가 무엇인지 찾으려면, 반복문을 돌릴 필요 없이 모든 원소를 XOR로 누적하면 된다. 



이 밖에도 기계어를 사용하는 등 여러 가지 재미있는 방법들이 많다..







g++ 컴파일러에서 (C++언어)

아래와 같은 헤더를 인클루드하여 사용할 수 있다.


#include <bits/stdc++.h>



해당 헤더파일을 확인해 보면(링크),

cstdio, cstdlib, cmath 등 C언어 표준헤더들과

stack, queue, vector 등과 같은 STL관련 헤더들을 포함하고 있는 것을 볼 수 있다.


프로그래밍 대회 등에서 이 헤더를 사용하여 코딩시간을 단축할 수 있다.

C언어 표준헤더가 아니므로 Visual Studio에서는 사용할 수 없다.



ex)


#include <bits/stdc++.h>


int main()

{

    std::stack<int> s;

    std::queue<int> q;

    std::vector<int> v;


    printf("abc\n");

    printf("%d\n", (int)sqrt(100));

   

    return 0;

}




[](Array subscripting 연산자) 가 *(indirection)보다 우선순위가 높으므로


int *arr2[3]은 배열이며 int * 타입을 3개 담을 수 있는 배열이고

int (*arr2)[3]은 포인터이며, int[3]타입을 가리킬 수 있는 포인터이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    int arr1[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int (*arr2)[3] = (int(*)[3])arr1;
    
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            printf("%d ", arr2[i][j]);
        }
    }
    
    return 0;
}
cs




이전글(2013년) : http://tibyte.kr/160



단항 연산자(unary operator) 중에서 전위 증가(pre-increment)연산자와 후위 증가(post-increment) 연산자를 같은 줄에 사용한 결과를 3개의 컴파일러로 컴파일해 보았다.

이는 undefined behavior로, 컴파일러마다 다른 결과가 나올 수 있다.


사용한 컴파일러는 gcc 4.8.4와 clang 3.4, 그리고 Visual Studio 2015에 포함된 C 컴파일러(이하 VC)이다.



a의 초기값을 5로 했을 때 결과는 아래와 같다.

(원본 코드는 https://github.com/tibyte/asm/blob/master/unary.c 에서 볼 수 있다.)


위 그림에서처럼 컴파일러에 따라 결과가 다르게 나오는 것을 볼 수 있다.


소스코드가 어떻게 번역됐는지 확인하기 위해 오브젝트 파일을 생성하고 디스어셈블한다.






1. 디스어셈블된 코드 생성




 

$gcc -g -c unary.c -o unary-gcc.o

$objdump -dS -M intel unary-gcc.o > unary-gcc.txt

$clang -g -c unary.c -o unary-clang.o

$objdump -dS -M intel unary-clang.o > unary-clang.txt


gcc와 clang에서 -c옵션은 오브젝트 파일을 생성하는 것이고 -g는 디버깅 옵션으로, 소스코드를 포함시킬 수 있다.


objdump에서 -d옵션은 디스어셈블,  -S옵션은 소스코드 포함 옵션이다.

-M옵션은 인스트럭션을 AT&T 문법으로 출력할 것인지, Intel문법으로 출력할 것인지를 결정하는 옵션인데, 기본값은 AT&T로, 아래와 같은 형태로 출력된다.  





-M intel 옵션을 붙여 주면 아래와 같이 인텔 형식으로 된 결과를 얻을 수 있다.






Microsoft Visual Studio 2015에서 디스어셈블된 코드를 확인하려면

코드에 중단점을 건 후 F5로 디버그를 시작하고  Debug - Windows - Disassembly를 클릭하면 된다.







2. b = (a++) + a 분석


a의 초기값은 5이다.


GCC

mov    eax,DWORD PTR [a]

lea    edx,[rax+0x1]

mov    DWORD PTR [a],edx

mov    edx,DWORD PTR [a]

add    eax,edx

mov    DWORD PTR [b],eax

(1행) eax 레지스터에 5를 넣는다.

(2행) edx 레지스터에 6을 넣는다.

(3행) a에 6을 넣는다.

(4행) edx 레지스터에 6을 넣는다.

(5~6행) b에 5+6의 결과인 11을 넣는다.

b는 11이 된다.


lea 명령에서 rax 레지스터는 eax레지스터의 64비트 버전이므로

저장된 4바이트 값을 읽었을 때 같은 값이 나온다.



Clang
mov    ecx,DWORD PTR [a]
mov    edx,ecx
add    edx,0x1
mov    DWORD PTR [a],edx
add    ecx,DWORD PTR [a]
mov    DWORD PTR [b],ecx

(1행) ecx 레지스터에 5를 넣는다.

(2~3행) edx 레지스터에 6을 넣는다.

(4행) a에 6을 넣는다.

(5~6행) b에 5+6의 결과인 11을 넣는다.

b는 11이 된다.


VC
mov         eax,dword ptr [a] 
add         eax,dword ptr [a] 
mov         dword ptr [b],eax 
mov         ecx,dword ptr [a] 
add         ecx,1  
mov         dword ptr [a],ecx 
(1~2행) eax 레지스터에 6을 넣는다.
(3행) b에 6을 넣는다.
(4~6행) a에 5+1의 결과인 6을 넣는다.

b는 10이 된다.






3. b = (++a) + (a++) 분석


a의 초기값은 5이다.


GCC

add    DWORD PTR [a],0x1

mov    eax,DWORD PTR [a]

lea    edx,[rax+0x1]

mov    DWORD PTR [a],edx

mov    edx,DWORD PTR [a]

add    eax,edx

mov    DWORD PTR [b],eax

b에는 eax값과 edx값의 합이 들어가는데, 맨 처음에 a에 1을 더하여 6이 되고
그 다음 복사해 온 eax값에 1을 또 더하여 edx 레지스터에 복사하므로
b는 6+7의 결과인 13이 된다.


Clang
mov    ecx,DWORD PTR [a]
add    ecx,0x1
mov    DWORD PTR [a],ecx
mov    edx,DWORD PTR [a]
mov    esi,edx
add    esi,0x1
mov    DWORD PTR [a],esi
add    ecx,edx
mov    DWORD PTR [b],ecx
gcc와는 다르게 esi 레지스터를 사용하여 더한 값은 ecx+edx의 연산결과에 포함되지 않으므로
b의 값은 6+6의 결과인 12가 된다.



VC
 mov         eax,dword ptr [a] 
 add         eax,1  
 mov         dword ptr [a],eax 
 mov         ecx,dword ptr [a] 
 add         ecx,dword ptr [a] 
 mov         dword ptr [b],ecx 
 mov         edx,dword ptr [a] 
 add         edx,1  
 mov         dword ptr [a],edx 
clang 결과와 비슷하게 a에 대한 증가 연산 중 하나가 b값이 결정된 후에 계산되므로
b는 6+6 = 12가 된다.




4. 결론



증감연산자를 한 줄 내에서 여러 개 사용하면 연산의 실행순서가 불분명하여

값이 어떻게 변할지 예측하기 어렵고 컴파일러마다 다른 결과가 나오기도 한다.

따라서 이러한 코드를 작성하지 말아야 할 것이다..


Clang 컴파일러에서는 이런 구문을 컴파일할 경우 'multiple unsequenced modifications' 라는 warning을 띄워 준다.





참고 : undefined behavior





프리프로세서인 #include에 대한 간단한 실험을 해 보았다.


코드 중간에서 소스코드가 있는 txt파일을 로드해도 전처리 과정에서 include가 처리되기 때문에 정상적으로 컴파일된다.


main.c


#include <stdio.h>

int main(void)
{
#include "source.txt"   //'hello world!'가 출력된다.
	return 0;
}

 



source.txt


printf("hello world!\n");

 



https://github.com/tibyte/practice/tree/master/C/include



GetNext()는 pos값을 다음 값으로 만들기 때문에

먼저 임시변수를 만들어 현재 pos값을 저장해두고 그 임시변수 위치에 해당하는 요소를 지워야 한다.


POSITION pos = list.GetHeadPosition();

POSITION posTemp;

while(pos != NULL) {

    posTemp = pos;

    CMyType myType = list.GetNext(pos);

    if(....CMyType이 요소삭제조건일 때) {

       list.RemoveAt(posTemp);

    }

}



POSITOIN타입이

typedef __POSITION* POSITION;

와 같이 정의되어있기 때문에 getNext()에서 pos값을 변경할 수 있는것이다.

우선 windows.h 헤더를 포함해야 한다.

BOOL gotoXY(int x,int y)
{
    COORD pos;   //short 타입의 X, Y 속성이 들어 있는 구조체이다.
    pos.X=x;
    pos.Y=y;
    return SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),pos);
}




보통 set메서드가 있으면 get메서드가 있기 마련이지만
커서위치를 얻으려면 GetConsoleCursorPosition같은게 없어서 좀 다른방법을 써야 한다.
여기서는 GetConsoleScreenBufferInfo()함수를 쓰는데

buf.dwCursorPosition역시 COORD 타입이다.

COORD getXY()
{
    COORD pos;
    CONSOLE_SCREEN_BUFFER_INFO buf;
    GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&buf);
    pos.X = buf.dwCursorPosition.X;
    pos.Y = buf.dwCursorPosition.Y;
    return pos;
}




int *A;

A는 int형 포인터이다.


int B[5];

B는 크기가 5인 int형 배열이다.


int *C[5];

연산자우선순위에서 배열첨자인[]가 먼저이므로 C는 배열이다. 크기가 5인 배열.

즉 int형 포인터(int *)를 5개 담을 수 있는 배열이다.


int (*D)[5];

괄호 안을 먼저 처리하므로 D는 포인터이다.

크기가 5인 int형 배열(int [5])의 포인터를 할당할 수 있는 포인터인 것이다.


int *(*E)[5];

D와 같이 괄호 안을 먼저 처리하므로 E는 포인터이다.

이 것 역시 남은 부분을 보면 E가 무슨 포인터인지 알 수 있는데,

남은부분이 int *[5]이므로 E는 int *[5]의 포인터를 담을 수 있는 포인터가 된다.

이 int *[5]꼴은 C와 같은 형태이다. 이것을 참조해서 정리해 보면

E는'int형 포인터(int *)를 5개 담을 수 있는 배열'의 포인터을 할당할 수 있는 포인터이다.


int *F[5][4];

[]가 먼저 처리되므로 F는 이차원배열이다.

int * 형태의 데이터를 5x4로 담을 수 있는 크기가 20인 이차원배열. 


int (*G[5])[4];

역시 우선순위를 따져보면 G는 크기 5의 배열이다.

남은부분은 int (*)[4]로, 이는 D와 같은 꼴이다.

즉 G는, D와 같은 형태의 데이터를 5개 담을 수 있는 배열.


int *(*H[5])[4];

H 역시 배열이며, 남은부분은 int *(*)[4]이고,

이는 E와 같은 형태이다.

즉 H는, E와 같은 형태의 데이터를 5개 담을 수 있는 배열.

 


관련글 : http://tibyte.kr/252


1.

전위/후위 증감 연산자를 복합적으로 썼을 경우에 대한 분석을 간단하게 해 보았다.

C언어로 코드를 작성하여 VC++컴파일러로 x86어셈블리를 뽑았다.



2. 사례

1) 전후위 연산자를 앞뒤로 쓴 경우


 int a=1;

00E53427  mov         dword ptr [ebp-8],1 

int b=1;

00E5342E  mov         dword ptr [ebp-14h],1 

int c=1;

00E53435  mov         dword ptr [ebp-20h],1 

int num1 = b+++a+++c;

00E5343C  mov         eax,dword ptr [ebp-14h] 

00E5343F  add         eax,dword ptr [ebp-8] 

00E53442  add         eax,dword ptr [ebp-20h] 

00E53445  mov         dword ptr [ebp-2Ch],eax 

00E53448  mov         ecx,dword ptr [ebp-8] 

00E5344B  add         ecx,1 

00E5344E  mov         dword ptr [ebp-8],ecx 

00E53451  mov         edx,dword ptr [ebp-14h] 

00E53454  add         edx,1 

00E53457  mov         dword ptr [ebp-14h],edx 


→ num1 = b+++a+++c;에 대한 어셈블리 코드를 보면 처음 4행은 num1에 대한 연산을 하는 부분이다. 

ebp-14h, ebp-8, ebp-20h 메모리의 수를 그냥 더해서 2bp-2Ch(num1 변수)메모리에 복사한다.

num1의 결과값은 1+1+1 = 3이 된다.

그리고 그 다음줄(00E53448)부터 3행에서 ebp-8 메모리(변수 a)에 1을 더하고,

마지막 3행에선 ebp-14 메모리(변수b)에  1을 더해 두고 있다.

이처럼 앞뒤로 ++a++ 꼴이 될 경우엔 왼쪽 부터 처리된다는 것을 볼 수 있다.(당연한 일이겠지만...)






2) 같은 변수에 대해 전후위 증감 연산을 여러 번 쓴 경우


int a=5,b=5,c=5,num1,num2,num3;

00E5339E  mov         dword ptr [ebp-8],5 

00E533A5  mov         dword ptr [ebp-14h],5 

00E533AC  mov         dword ptr [ebp-20h],5 

num1 = (++a)+(++a);

00E533B3  mov         eax,dword ptr [ebp-8] 

00E533B6  add         eax,1 

00E533B9  mov         dword ptr [ebp-8],eax 

00E533BC  mov         ecx,dword ptr [ebp-8] 

00E533BF  add         ecx,1 

00E533C2  mov         dword ptr [ebp-8],ecx 

00E533C5  mov         edx,dword ptr [ebp-8] 

00E533C8  add         edx,dword ptr [ebp-8] 

00E533CB  mov         dword ptr [ebp-2Ch],edx 

→ 식에서 ++a 부분을 먼저 처리한다. 이 때, 한 번 증가 연산을 하고 나서 

  그 값을 다시 ebp-8 메모리에 복사하고 그 값을 다시 레지스터로 읽어와

  다음 1을 더하는 작동을 하므로 a변수는 총 2 증가하게 된다.

  여기까지가 ++a를 두 번 연산한 단계이다.

  그리고 결과값인 num1변수(ebp-2Ch 메모리)의 값으로는 a를 두 번 더한 7+7 = 14가 나온다.


num2 = (b++)+(b++);

00E533CE  mov         eax,dword ptr [ebp-14h] 

00E533D1  add         eax,dword ptr [ebp-14h] 

00E533D4  mov         dword ptr [ebp-38h],eax 

00E533D7  mov         ecx,dword ptr [ebp-14h] 

00E533DA  add         ecx,1 

00E533DD  mov         dword ptr [ebp-14h],ecx 

00E533E0  mov         edx,dword ptr [ebp-14h] 

00E533E3  add         edx,1 

00E533E6  mov         dword ptr [ebp-14h],edx 

→ 앞의 항과 뒤의 항을 먼저 더하고 ebp-38h메모리(num2변수)에 복사 후

ebp-14h메모리(b변수)는 ecx레지스터와 edx레지스터를 거쳐 증가가 두 번 된다.

결과값은 num은 5+5=10 이고 b는 7이다.


num3 = (++c)+(c++);

00E533E9  mov         eax,dword ptr [ebp-20h] 

00E533EC  add         eax,1 

00E533EF  mov         dword ptr [ebp-20h],eax 

00E533F2  mov         ecx,dword ptr [ebp-20h] 

00E533F5  add         ecx,dword ptr [ebp-20h] 

00E533F8  mov         dword ptr [ebp-44h],ecx 

00E533FB  mov         edx,dword ptr [ebp-20h] 

00E533FE  add         edx,1 

00E53401  mov         dword ptr [ebp-20h],edx

→  처음 3행을 보면 c값은 1 증가하여 6이 된다.

   그 다음 3행에서 c+c를 하여 num3(ebp-44h 메모리)에는 12가 들어간다. 

  마지막 3행에서 c변수에(ebp-20h 메모리) 1을 더한다.


위 세 가지 사례들을 종합해 보면, 식의 전위 증감 연산자들이 먼저 처리되어

그 결과(전위증감연산)를 반영한 값으로 식이 계산된 후에, 후위 증감 연산자가 처리된다는 것을 알 수 있다.





3) 함수의 인자에 썼을 때.


function(n++,++n);

00B517E5  mov         eax,dword ptr [ebp-8] 

00B517E8  add         eax,1 

00B517EB  mov         dword ptr [ebp-8],eax 

00B517EE  mov         ecx,dword ptr [ebp-8] 

00B517F1  mov         dword ptr [ebp-0d0h],ecx 

00B517F7  mov         edx,dword ptr [ebp-8] 

00B517FA  add         edx,1 

00B517FD  mov         dword ptr [ebp-8],edx 

00B51800  mov         eax,dword ptr [ebp-8] 

00B51803  push        eax  

00B51804  mov         ecx,dword ptr [ebp-0d0h] 

00B5180A  push        ecx  

00B5180B  call         00B511C2 

00B51810  add         esp,8 


↓ 이 코드가 동작할 때 두 개의 메모리와 eax ecx edx 레지스터의 상태를 표로 만들어 보았다. 

   (글을 작성하다 n을 선언하는 부분을 빼먹었는데, n의 초기값은 10 이였다고 하겠습니다.)


00B517E5  mov         eax,dword ptr [ebp-8] 

00B517E8  add         eax,1 

00B517EB  mov         dword ptr [ebp-8],eax 

→ 함수호출시 두 개의 인수 중 두 번째가 스택에 나중에 들어가므로 먼저 처리된다(후입선출)

  즉 function(n++, ++n)에서 뒤쪽의 ++n이 먼저 처리되는 것이다.

 n변수(ebp-8 메모리)에 1을 더해 둔다. 

그러면 이 시점에서 n의 값은 11.



00B517EE  mov         ecx,dword ptr [ebp-8] 

00B517F1  mov         dword ptr [ebp-0d0h],ecx 

00B517F7  mov         edx,dword ptr [ebp-8] 

00B517FA  add         edx,1 

00B517FD  mov         dword ptr [ebp-8],edx 

→ n의 값을 ebp-0d0h 메모리에 복사한다.

  그리고 n에 1을 더한다. 이 시점에서 n은 12.



00B51800  mov         eax,dword ptr [ebp-8] 

00B51803  push        eax  

00B51804  mov         ecx,dword ptr [ebp-0d0h] 

00B5180A  push        ecx  

→ ebp-8 메모리의 값을 eax레지스터로 복사해 와서 함수 스택에 push 한다.

  그리고 ebp-0d0h 메모리의 값도 함수 스택에 push.

  먼저 push 되는게 마지막 인자이다.

  그래서함수 내부에서 매개변수의 값을 찍어보면

  첫 번째 인자의 값은 11,

  두 번째 인자의 값은 12이다.



00B5180B  call         00B511C2 

00B51810  add         esp,8 

→ 다음에 실행할 인스트럭션이 있는 주소 00B511C2로 이동한다.
  함수가 4바이트 매개변수 2개를 썼으므로 esp레지스터에 4*2=8을 더한다.



3. 결론
전,후위 증감 연산자를 헷갈리지 않게 의미가 잘 드러나도록 쓰자.. 

내용추가+)
3가지 컴파일러로 컴파일해 본 결과 : http://tibyte.kr/252



========================================================================






#include <stdio.h>

void main()
{
   int a = 2;
   int b = 7;

   printf("a=%d, b=%d\n",a,b);

   b = a-b;
   a = a-b;
   b = a+b;

   printf("a=%d, b=%d\n",a,b);

}


c를 사용하지 않고 정수 a와b를 교체

최근 관련글 : ( http://www.tibyte.kr/158 )


+ Recent posts

티스토리툴바