JMob

배열의 연속된 구간의 최대 합을 구하는 알고리즘을 분석해 보겠다.위와 같은 배열이 주어졌다면 빨간 구간의 합이 가장 크다. 이때 구간의 합 30을 리턴하는 알고리즘이다. 이 알고리즘은 개의 후보 구간을 검사하고, 각 구간의 합을 구하는데 의 시간이 걸리기 때문에 이 알고리즘은 의 시간이 걸린다. 다음은 같은 연산을 하는, 좀 더 빠른 알고리즘이다. 이 알고리즘에서는 번 수행되는 반복문 두 개를 겹쳤다. 따라서 시간 복잡도는 가 되는 것을 쉽게 알 수 있다. 다음 방법은 분할 정복 기법을 이용한 알고리즘이다. 입력 받은 배열을 우선 절반으로 잘라 왼쪽 배열과 오른쪽 배열로 나눈다. 이때 우리가 원하는 최대 합 부분 구간은 두 배열 중 하나에 속해 있을 수도 있고, 두 배열 사이에 걸쳐 있을 수도 있다. 각..

다음 알고리즘은 정수 배열을 정렬하는 알고리즘이다. 선택정렬선택 정렬은 모든 i에 대해 A[i....N-1]에서 가장 작은 원소를 찾은 뒤, 이것을 A[i]에 넣는것을 반복한다. 즉 가 된다. 따라서 시간복잡도는 이며 빅오는 가 된다. 삽입정렬삽입 정렬에서는 A[0....i]까지는 정렬이 되어 있다고 본다. 즉 i = 4 라면 3 5 7 8 9(i) 13 1 2 A[3]과 비교 했을 때 A[4] > A[3] 이기 때문에 while()문을 빠져 나오게 된다. 하지만 i = 6 이라면 while()문으 로 들어가서 swap()을 실시하는데 이 경우 A[4]...A[3]........A[0] 까지 다 실시하게 된다. 즉 삽입 정렬은 정수 배열이 이미 정렬이 되어 있다면 번 실시한다. 하지만 최악의 경우(역순 ..

간단하게 구현되는 소인수분해 알고리즘 결과로 소인수분해한 값이 담긴 배열을 리턴해준다.

위의 알고리즘은 N개의 배열을 입력 받으면 i번째 있는 값이 N개중 몇번나오는지 체크후 가장 큰 값을 남긴다. 즉 N개의 숫자를 N번 확인 하기 떄문에 시간 복잡도와 빅오는 값을 가진다. 위의 알고리즘은 N개의 배열의 숫자를 전혀 모를때 사용하기 적합하지만, 만약에 숫자의 범위가 주어져 있다면 좀더 좋은 방법이 있다. 위의 알고리즘은 N개의 배열에 숫자의 범위가 1~100 일때 사용할 수 있다. 간단한 예로 시험 점수중 가장 많이 받은 점수를 찾을 떄 쓸 수 있다. 위의 경우처럼 범위가 100까지라면 시간 복잡도는 이며 범위를 k라고 하면 가 된다. 빅오는 이기 때문에 아래의 알고리즘이 더 좋다고 할 수 있다.

문제 해결 과정 1. 문제를 일고 이해하기 문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 과정이 필요하다.2. 재정의와 추상화문제를 추상화 시키고 재정의 하여 문제에 쉽게 접근할 수 있도록 만든다.3. 계획문제를 어떤 방식으로 해결할지, 어떤 알고리즘과 자료구조를 사용할지 결정한다.4. 계획 검증설계한 알고리즘으 모든 경우에 요구조건을 충족하는지 증명하고, 걸리는 수행 시간을 확인하며 메모리 사용량 제한을 지키는지를 검사해야한다.5. 계획 수행검증이 완료되면 프로그램을 작성한다.6. 회고문제를 해결한 과정을 동이켜 보고 개선한다. 문제를 풀지 못 했을 때 문제를 해결하지 못하였을 경우 다른 사람의 풀이 방법을 참조한다. 하지만 복기를 동반하여야 한다.문제 해결 전략문제를 해결하기 위해..

password : hackers proof1. 문제 (small buffer + stdin) 2. 분석- buffer size : 16byte- gets 사용 : stdin 3. 풀이buffer size가 16byte이다. 그리고 buffer 복사를 gets 함수를 이용해서 한다. gets 함수도 size를 지정 하지 않기 때문에 오버플로우를 발생 시킬 수 있는 함수이다. 즉 2번과 같은 방법으로 하되 stdin으로 해주면 된다. 디버깅용 파일을 하나 만들고 디버깅을 한다. disas로 main을 살펴본다. gets()이후 스택을 확인 해야 하니 break point를 main+15에 걸고 실행 한다. A 16개 B 4개 C 여러개....를 입력 후 스택을 살펴 보았다. 스택을 확인해본 결과 0xbff..

password : hacking exposed1. 문제 (small buffer) 2. 분석 - buffer size : 16byte- argc가 2 이상- strcpy 사용 3. 풀이1번 문제와 비교 했을때 차이점은 buffer size가 16byte로 줄었다는 것이다. 1번 문제에서는 buffer size가 256byte이라서 ret를 덮기 위해 264byte를 사용했다. 하지만 ret를 덮어서 변경 했던 주소는 argv[1]이 였던것을 기억해야 한다. 즉 buffer는 ret를 덮기 위해 사용 했을 뿐 정작 필요한 쉘코드는 argv[1]에 있다. 따라서 다음과 같이 해주면 된다. 그럼 실제로 해보겠다. 먼저 디버깅용으로 하나 새로 만든다. disas로 main을 살펴보면 와 같이 나온다. RET를..

UNIX에서 system call을 이용한 파일 복사 #include #include #include #include #define MAX_SIZE 1024 int main(void){ char buf[MAX_SIZE] = {0,}; char input_Name[MAX_SIZE] = {0,}; char output_Name[MAX_SIZE] = {0,}; int input_File, output_File; int testnum; write(1,"Input file name : ",sizeof("Input file name : ")); testnum = read(1,input_Name,sizeof(input_Name)); if(testnum < 0) { write(1,"Input error!!",sizeo..

보호되어 있는 글입니다.

password :hello bof world1. 문제 (simple BOF) 2. 분석 - buffer size : 256byte- argc가 2 이상- strcpy 사용 : arvg[1]를 buffer에 복사 3. 풀이strcpy를 사용해서 버퍼오버플로우를 시켜 해결 하는 문제다. strcpy는 size를 지정하지 않기 떄문에 버퍼오버플로우가 가능하다. 따라서 이를 이용하여 ret를 shell code가 있는 메모리 주소로 덮으면 해결이다. buffer[256] SPF RET 이는 스택 프레임과 쉘코드에 관련된 내용을 모른다면 다음글을 참고하세요스택프레임 : http://jungmonster.tistory.com/112쉘 코드 : http://jungmonster.tistory.com/113 결론!!..