jiiihye

https://dreamhack.io/wargame/challenges/14/

프로그램을 실행해보면 뭔가 입력하라고 나온다. 

main을 찾기위해서 문자열찾기에 들어왔다. Compar3_the_str1ng이라는 것과 input, correct,wrong등이있다. input을 눌러 main함수 부분을 찾았다.

어떤 문제인지 알기 위해 main함수를 먼저 찾았다.

input에 특정 숫자를 넣으면 Correct나 Wrong이 출력된다는 것을 알 수있다.

test eax, eax 부분이 eax가 0인지 판단하는 곳이다. eax가 0이면 ZF값도 0이다.

je에 ZF가 1이면 wrong출력하고 0이면 correct를 출력한다는 것을 볼 수있다.

내가 입력한 1111이 찍히는 것을 볼 수있다.

위에 문자열 찾기를 통해 보았던 Compar3_the_String이 뭔가 compare비교하는 느낌이 나서 BP를 걸어보았다.

rdx에 Compar3_the_str1ng이 들어있고 rcx에 입력한 1111값이 들어가서 strcmp로 비교되는것을 알 수있다.

32 bit 운영체제는 메모리를 0부터 4,294,967,296 만큼 저장할수있고,

64 bit 운영체제는 메모리를 0부터 18,446,744,073,709,551,616 만큼 저장할수있다.

사용하는 메모리 RAM의 용량에도 제한이 있는데, 32bit 컴퓨터에서는 RAM이 최대 4gb까지 들어간다.

32bit 컴퓨터에서 아무리 많은 용량의 ram을 달아봤자, 결국에는 4byte ram의 효과만 보는것이다.

64bit 컴퓨터에서는 최대 1tb ( 2^10 gb) 만큼의 RAM이 들어간다.

레지스터의 용량이 클수록 메모리에서 더 많은 데이터를 가져와 저장할 수 있어서 처리속도도 빨라진다.

32bit Register : EAX   E(Extended)   

64bit Register : RAX   

64bit 레지스터

범용 레지스터

특정한 용도를 정해두지 않고 다양하게 쓸 수 있는 레지스터이다.

x64 범용 레지스터는 16개

rax rcx r8 r9 r10 r11 rbx rsi rdi rbp r12 r13 r14 r15 rsp rip가 있다.

원칙적으로 용도가 정해져 있지 않지만 관행적으로 쓰임새가 정해져 있는경우도 있다.

rax

함수가 실행된 후 리턴값을 저장 하기 위해 쓰인다. 어떤 함수의 실행이 종료되고 나면 해당 함수의 결과값이 반환될 때 이 rax 레지스터에 담겨 반환된다. 그러나 rax가 리턴값을 위해서만 쓰이는 것은 아니다. 함수가 반환되기 전까지 범용 레지스터로 자유롭게 사용되다가, 종료 후 리턴값을 반환하기 위한 레지스터로는 rax만이 사용된다.

rcx, rdx, r8, r9

x64의 범용 레지스터들 중에서는 함수가 실행될 때 필요한 인자들을 저장하는 용도로 사용하는 레지스터

Windows 64bit에서 함수를 호출할 때 필요한 인자들을 순서대로 저장한다.

첫번째 인자는 rcx에, 두번째 인자는 rdx에, 세번째 인자는 r8에, 네번째 인자는 r9에 하는 방식으로 인자를 레지스터에 담아 함수를 호출한다.

rsp

16개의 범용 레지스터들 중 하나로 분류되지만, 다른 범용 레지스터들과 달리 용도가 정해져 있다. 

rsp는 스택 포인터(Stack Pointer)로, 스택의 가장 위쪽 주소를 가리킨다. 스택은 함수가 사용할 지역 변수들(local variables)을 저장하기 위해 준비해놓는 공간이다

rip

명령어포인터이다. 다음에 실행될 명령어가 위치한 주소를 가리키고 있다. 즉 프로그램의 실행 흐름과 관련된 중요한 레지스터이므로, 범용으로 사용되지 않는 레지스터이다.

시스템 호출시 범용 레지스터 표 표현

32bit 64bit 호출 규약

64bit 환경에서는  rax, rbx, rcx, rdx, rbp, rsp, rsi, rdi + r8~r15 16개가 있다.

함수 호출할때는 최소 6개의 정수/ 포인터 인자는 rdi, rsi, rdx, rcx, r8, r9로 넘겨지고 그 이상은 매개변수가 전달되야 할때 스택을 통해 전달한다.

실수인자는 xmm0 ~ xmm7까지 8개의 레지스터를 순서대로 사용하여 전달하고 그 이상이면 스택을 통해서 한다.

32bit 호출규약

1. cdecl

c 언어에서 사용되는 방식이고 함수호출한 곳 스택을 정리한다.

2. stdcall

Win32 API에서 사용되고 cdecl과 반대로 Callee에서 스택을 정리한다.

3. fastcall

stdcall방식과 같지만 함수에 전달하는 매개변수 일부(2개까지)를 스택이 아닌 레지스터를 이용한다.

ECX, EDX레지스터를 사용해서 함수에 매개변수를 전달한다.

64bit 호출규약

32bit cpu일떄는 여러개지만 64bit CPU는 fastcall호출규약1개를 사용한다.

[참고]

https://sunrinjuntae.tistory.com/34

https://sewcode.tistory.com/13

https://dreamhack.io/learn/3/20#11

https://koharinn.tistory.com/224

최소비용 그래프 알고리즘

통계출산 알고리즘, 재고관리 알고리즘

지폐매수계산 알고리즘

요일 계산 알고리즘

은행이자계산 알고리즘

소프트웨어관리

알고리즘의 효율성

소프트웨어의 구조

검증,확인,3R

마방진 배열 채우기 알고리즘 

5행 5열의 2차원 배열에 대해 5개의 행, 5개의 열, 2개의 대각선에 각각 위치한 5개 원소들의 합이 모두 65로 일정하도록 1부터 25까지의 일련번호를 할당한 알고리즘을 마방진 알고리즘이라부른다.

1 2 3 4 5  밑에보다 작은값

6 7 8 9 10

-> 대각선방향으로 가야됨

1~25까지 배정하는데 13이 가운데 45도 위로 올라가게함.

알고리즘은 어떻게?

규칙 생각

1. 시작지점은 1행의 3열부터 시작, 45도 오른쪽 위로, 1~25까지.

행도 1~5 열도 1~5 이안에 들어가지 않는 것은 6열은 1열로 바꿔주는 규칙 0열이면 5열로 

1. 1행 중간 열에 위치한 1행의 3열에 1을 할당

2. 위치에서 45도 대각선 방향으로 이동하기 위해 행번호는 1씩 감솜시키고 열번호는 1씩 증가시킨다.

이동하기 위해서, 행 번호는 1씩 감소시키고 열번호는 1씩 증가시킨다.

* 감소시킨 행 번호가 1행보다 작으면 마지막 행인 5행으로 재설정하며, 증가시킨 열번호가 마지막 열인 5열보다 크면 1열로 재설정하여 다음숫자를 할당

3. 배정하려는 위치에서 이미 숫자가 배정되어 있으면, 현재 위치보다 행 번호만을 1만큼 증가시켜서 행을 재설정한 후 다음숫자를 할당한다.

순서도

+ 배열 회전시키기

배열 A(5,5)를 시계방향으로 90도 회전시켜 B(5,5)생성하는 알고리즘

A(1,1) -> B(1,5)

A(1,2) -> B(2,5)

A(1,3) -> B(3,5)

규칙이 보인다. A는 열이 1,2,3... B는 행이 1,2,3...

석차구하기 알고리즘

응용 알고리즘 -자료구조

매출액과 석차를 순서대로 출력하는 알고리즘

첫번째 대리점부터 마지막 25번째 대리점까지 각 대리점 i 에 대해 매출액 A(i)을 일볅하고 현재까지는 전체에서 1등이라고 A(i)를 초기화 한다

대리점 i의 매출액 A(i)를 전체 25개 대리점 매출액 A(i)과 25번 비교하여 자신의 매출액보다 큰 경우에만 자신의 석차 R(i)의 값을 1씩 증가시켜 석차를 하나씩 낮추도록 한다.

1, 동점자를 자신보다 상위자로 보지 않고 석차를 낮추는 방식

2. 동점자를 자신보다 상위자로 보아 석차를 낮추는 방식

+반복기소 사용하여 간단하게 표현

선택정렬 알고리즘

학생 100명의 영어 성적을 오름차순으로 선택정렬하는 알고리즘

(오름차순, 내림차순)

1. 전체 데이터 n개 가장 작은수 선택해서 왼쪽 1번째 자리에 오도록한다.

2. 가장 왼쪽 데이터 1개를 제외한 데이터 n-1개를 빅하여 그 가장 작은 수를 선태갛여 왼쪽에서 2번쨰 자리에 오도록한다.

3. 가장 왼쪽 데이터 2개를 제외한 데이터 n-2개를 빅하여 그 가장 작은 수를 선태갛여 왼쪽에서 3번째 자리에 오도록 한다.

4. 더이상 비교할 필요가 없을 때 까지 이런 과정을 반복한다

-예를들어, 5개의 영어 점수가 주어졌을떄 오름차순

순서도

버블정렬 알고리즘

학생 100명의 영어성적을 오름차순으로 버블정렬하는 알고리즘

순서도

+ 버블정렬에서 중첩 반복 구조와 스와핑 서브루틴을 활용

삽입정렬 알고리즘

학생 100명의 성적 오름차순으로 삽입정렬하는 알고리즘

오름차순 삽입정렬

- 삽입 정렬은 알고리즘이 진행되는 동안 1정렬이 이미 이루어진 데이터그룹 a와 2정렬이 아직 이루어지지 않은 데이터 그룹 b등 총 2개의 그룹을 나누어 진행한다.

- 정렬이 아직 이루어지지 않은 그룹 b에 한개의 데이터 꺼내 정령이 이미 이루어진 그룹 a의 적절한 위치에 삽입하여 진행한다. 이것 때문에 삽입 정렬이다.

- 그룹 b에서 그룹 a로 이동하는 데이터를 키라고 부른다. 키는 그룹 b에 남아있는 데이터들 중에 가장 좌측 데이ㅣ터를 뽑는다. 뽑은 키가 존재하지 않으면 삽입정렬은 종료된다.

병렬정렬 알고리즘

오름차순으로 정렬된 배열 A(M)과 내림차순으로 정렬된 배열 B(N)을 병합정렬이라 하여 오름차눗ㄴ의 배열 C(M+N)을 생성하는 알고리즘을 제시해라. 단 배열 A(M)과 배열 B(N)에는 900000이하의 정수가 저장되어 있으며 모든 배열의 첨자는 1부터 시작

문제 문제 공략

- A(M)은 오름차순으로 이미 정렬되어 있고 B(N)은 내림차순으로 이미 정렬되어 있으므로, 각 배열에서 가장 작은 원소인 A(1)과 B(N)부터 병합정렬 실시

퀵정렬 알고리즘

학생 100명 성적 오름차순으로 퀵정렬하는 알고리즘

정렬중 가장 빠른시간안에 할수있는 퀵정렬, recursion을 사용한다. 자기자신을 부르는

pibot number 축이 퀵정렬에서 중요한 용어이다. 어떤 숫자들을 정렬했는데  

순서도

이분검색과 순차검색

이분검색 bs 순차검색 ss

제일 가운데랑 찾고자 하는 숫자랑비교, 같지않으면 왼쪽이나 오른쪽에 있음. 다시 서치

이분검색은 배열 변수 e에 대해 데이터 k가 있는 위치를 찾아주는 알고리즘