[02-07 공부정리]

2018-02-06 공부정리 시작!

오늘은 [리버싱 핵심원리]에서 스택부분을 공부했다.

또, Google Codejam_Africa문제 중 [Odd Man Out] 문제를 풀었다.

[Stack Memory]

프로세스에서 스택 메모리 역할은 다음과 같다.

- 지역변수 저장

- 함수 호출 시, 파라미터 전달

- 복귀주소(Return Address) 저장

또한, 스택 메모리는 FILO(First In Last Out)구조로 되어있는데

말 그대로 선입후출. 먼저 PUSH된 데이터는 제일 마지막에 POP되는 구조다.

스택을 관리하기 위해서 두개의 레지스터가 사용되는데

ESP와 EBP가 그것이다.

ESP는 Stack Pointer이며, 스택의 제일 위쪽을 가르키고 있다.(낮은주소)

EBP는 Base Pointer로 스택 제일 바닥쪽을 가르키고 있다.(높은주소)

스택은 데이터가 Push될 때, EBP(높은주소)에서 ESP(낮은주소)로 쌓이는 모습을 보이는데

이러한 모습을 보고 '스택은 거꾸로 자란다'라는 표현을 쓰기도 한다.

스택에는 아주 중요한 기법이 하나 있다.

바로 Stack Frame기법인데, 이것 때문에 다른 함수들을 호출해도 스택이 터지지 않고 잘 유지 될수 있는 것이다.

[Stack Frame]

코드 첫번째 줄[PUSH EBP]과 두번째 줄[MOV EBP,ESP]이 Stack Frame을 만드는 코드다.

              [Stack top] <- ESP (0x6)

       |    | (0x5)

       |    | (0x4)

       |    | (0x3)

       |    | (0x2)

[Stack bottom] <- EBP (0x1)

이 상황에서 [PUSH EBP]를 하면 EBP의 주소가 스택에 저장이 된다.

=====[PUSH EBP]=====

     

           [Stack top] <- ESP (0x6)

       |  EBP주소(0x1)  | (0x5)

       |    | (0x4)

       |    | (0x3)

       |    | (0x2)

[Stack bottom] <- EBP (0x1)

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

그리고 [MOV EBP,ESP]를 하게되면 EBP와 ESP의 위치가 같아진다.

 

=====[MOV EBP,ESP]=====

                   [Stack top] <- ESP,EBP (0x6)

       |  EBP주소  | (0x5)

       |    | (0x4)

       |    | (0x3)

       |    | (0x2)

[Stack bottom](0x1)

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

이렇게 되면 기존의 함수 스택은 유지가 되면서

새로운 함수가 스택을 사용할 수 있게된다.

[POP EBP]

=====[POP EBP]=====

              [Stack top] <- ESP (0x6)

       |    | (0x5)

       |    | (0x4)

       |    | (0x3)

       |    | (0x2)

        [Stack bottom] <- EBP (0x1)

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

함수가 끝나고 복귀하기 전에 저장[PUSH EBP] 해두었던 EBP주소를 다시 POP으로 꺼내서

기존의 스택을 다시 사용할 수 있는 것이다.

이것이 Stack Frame기법이다. 

---

[Google Codejam_africa]

Google Codejam은 구글에서 개최한 코딩대회다.

Africa는 난이도가 좀 더 낮은 문제들로 구성되어 있는 대회이다.

URL : https://code.google.com/codejam/

문제는 영어로 출제되며, 하나의 문제의 인풋범위값을 기준으로 Small/Large로 선택해서 풀 수있다.

small은 인풋값 범위가 10000정도라면, Large는 100만정도로 극명한 차이를 보인다.

해당 문제는 가장 쉬운문제로

[Odd Man Out]

파티에 초대된 게스트들에게 초대코드를 부여한 뒤

각 케이스 마다 중복되지 않는 초대코드를 출력하면 되는 문제다.

[Sample]

input정보를 보면

N : 테스트 케이스 수

G : 게스트 인원 수

C : 게스트의 초대코드

첫번째 줄 : T를 입력한다.

두번째 줄 : G를 입력한다.

세번째 줄 : G들의 C를 입력한다.

[Odd Man Out SourceCode]

#include <iostream>
using namespace std;
int main()
{
    int n, g;
    int c[1000];
    cin >> n; //Test Case입력
    for (int i = 0; i < n; i++)
    {
        cin >> g; //Test Case의 Guest 수 입력
        for (int j = 0; j < g; j++)
            cin >> c[j]; // Geust Code 입력
        for (int x = 0; x < g; x++)
        {
            for (int y = x + 1; y < g; y++)
            {
                if (c[x] == c[y])
                {
                    c[x] = 0; // 중복되는 코드 0으로 초기화
                    c[y] = 0;
                }
            }
        }
        for (int z = 0; z < g; z++)
        {
            if (c[z] != 0) // 0이 아닌 초대 코드 (중복체크에서 제외된 코드) 출력
                cout << "Case #" << i + 1 << ": " << c[z] << endl;
        }
    }
}

[OddManOut 결과]

해당 문제페이지에 A-large-practice.in 파일이 있다.

해당 파일을 다운받아서 cmd에서 파이프로 .in파일을 인자값으로 넘겨주면

안에있는 테스트값들이 알아서 들어가게 된다.

[OddManOut문제에 대한 내 생각]

제일 최적의 알고리즘은 XOR연산으로 중복체크를 하는 거라고 하는데

내가 머리로 30분동안 생각을 해봐도 XOR연산을 해도 반복문을 2번 써야하기 때문에 

지금 알고리즘과 시간복잡도가 같다라는 결론이 나온다....

내 머리가 못 따라가서 그런것같긴한데..

중복체크를 할때 기준값과 비교값이 있고, 기준값은 중복체크가 끝나면 다음으로 바꿔야 하는데

XOR연산은 결과값으로 같으면 0 이라는 반환값을 내주는 것이지 바로 배열에 해당값들이 0으로 바뀌는게 아니다.

이러한 알고리즘 문제는 정말 많이 보이기때문에 그런 간단한 알고리즘이 존재한다면 꼭 알아두고 싶다..

 반복문을 하나만 써도되는 알고리즘을 아신다면 덧글로 알려주시면 감사하겠습니다..