분류 전체보기 118

분할 정복을 이용한 행렬 거듭 제곱

dp[i] = 1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3] ... dp[i - K] 위와 같은 점화식으로 dp[N]를 구해야 한다고 생각해보자. 일단 dp를 하나하나 구한다고 하면 총 O(NK)의 시간복잡도가 나올 것이다. 그러나 이를 잘 최적화하면 O(K^3 log N) 안에 dp[N]을 구할 수 있다. 바로 행렬 거듭제곱을 이용하는 것인데, 그 전에 "행렬 곱셈을 한다"가 어떤 의미인지 한 번 해석을 해보도록 하겠다. 다음과 같은 행렬 두 개가 있다고 가정하자. [1, 2, 3] [10] [1, 0, 0] [20] [0, 1, 0] [30] 그리고 위 행렬을 곱하면, 다음과 같은 행렬이 나올 것이다. [1*10+2*20+3*30 = 140] [1*10+0*20+0..

mathematics 2023.02.27

[reversing] Go 바이너리 분석

ctftime.org에서 Go 바이너리를 발견해 Go 공부를 시작했다. C언어로 개발하던 짬이 있어선지 언어 습득은 2시간 정도 걸렸고, 그렇게 습득한 언어로 여러가지 코드를 짜보며 어셈으론 어떻게 나오는지 확인해봤다. 1. 함수 호출 함수를 호출할 때 인자를 어떻게 전달하는지 알아보기 위해 인자를 10개로 갖는 함수를 하나 선언하고, 어셈블리어로 확인해봤다. C언어에서는 rdi, rsi, rdx, rcx ... 순으로 인자가 전달됐는데, Go에서는 인자가 rax, rbx, rcx, rdi, rsi, r8, r9, r10, r11 .... 이런 식으로 전달된다. 가변 인자는 C언어와 비슷하게 스택에 쌓고 가변 인자의 시작 주소와 개수를 전달한다. 가변 인자와 관련해 발견한 특징 중 하나는 인자 하나당 1..

reversing 2023.02.23

[layer7 ctf] 리버싱 라이트업(총 2문제)

1. tea_time 일단 문제 파일을 열자마자 프로그램 루틴이 보였다. int __cdecl main(int argc, const char **argv, const char **envp) { char v4; // al int i; // [rsp+8h] [rbp-188h] int v7; // [rsp+Ch] [rbp-184h] unsigned int v8; // [rsp+10h] [rbp-180h] unsigned int v9; // [rsp+14h] [rbp-17Ch] int v10; // [rsp+1Ch] [rbp-174h] int j; // [rsp+20h] [rbp-170h] int k; // [rsp+24h] [rbp-16Ch] char *v13; // [rsp+28h] [rbp-168h] in..

reversing 2022.12.19

2022 한국정보올림피아드 1차 1교시 풀이(비버챌린지 제외)

- 1번 문제 일단 A가 C보다 순위가 낮으므로, A 9 ... 6 -> 6 ... 14 -> 11 -> 8 -> 14 ... 이런 식으로 모든 사이클을 구해보았다. 위 사이클에선 반복 주기를 찾을 수 있는데, 첫 번째 사이클은 4, 두 번째는 5, 세 번째는 2, 네 번째는 1, 다섯 번째는 3이다. 이런 정보와 최소공배수 개념을 이용해 a^m이 되기 위해 a를 몇 번 제곱해야 하는지 알아낼 수 있다. 일단 (a^m)[1]=2이므로, 첫 번째 사이클은 총 2+4k번 반복됐다는 걸 알 수 있다. 따라서 m은 3, 7, 11, 15, 19 ... 중 하나가 될 수 있다. 다음으로 (a^m)[3]=15이므로, 두 번째 사이클은 총 0+5k번 반복됐다는 걸 알 수 있다. 따라서 m은 1, 6, 11, 16, ..

mathematics 2022.11.30

C언어 프로젝트 - 콘솔 3d 게임 만들기

학교에서 C언어 프로젝트로 수행평가를 한다길래 타워 디펜스 게임을 만들기로 했고, 뭔가 특별한 점을 주고 싶어 3d로 제작하게 되었다. 아마 이번 블로그글에서 3d 게임 제작 과정 등을 설명하고, 다음 블로그글부터 이 프로그램을 직접 IDA로 분석하면서 리버싱 공부도 해볼 참이다. 일단 시연 영상부터 보자. 시연 영상(https://www.youtube.com/watch?v=pNkv3bDInOk&ab_channel=GGJ) 그렇겐 안 보이지만 어쨌든 타워 디펜스 게임이다. 일단 이 프로그램을 다운받고 readme.txt를 읽고 한 번 플레이하고 오자. 거기에 이 게임의 룰, 조작법 등이 적혀 있다. 그럼 이제 대략적인 코드 구현 방법을 설명하도록 하겠다. 플레이어 플레이어에 관한 정보를 저장하기 위해 구..

programming 2022.11.21