https://www.hackerrank.com/challenges/insertionsort2/problem Insertion Sort - Part 2 | HackerRank Code Insertion Sort itself. www.hackerrank.com part1에 이은 삽입정렬 문제이다. part1 : https://hse06028.tistory.com/33 이번에는 모든 원소들에 대하여 삽입 정렬을 하면 된다. 알고리즘은 part1과 같다. part1과 다른 점이 하나 있다면 모든 원소들에 대하여 정렬을 하면 된다는 것이다. for문이 두개가 돌아간다. 가장 바깥의 for문은 삽입을 할 원소를 정한다. i=1부터 시작을 했는데 그 이유는 그 원소의 앞 원소들과 대소 비교를 진행해야 한다. 만약 ..
https://www.hackerrank.com/challenges/insertionsort1/problem Insertion Sort - Part 1 | HackerRank Insert an element into a sorted array. www.hackerrank.com 삽입 정렬 문제 배열의 가장 끝에 있는 원소를 대소관계를 비교하여 정렬하는 문제 삽입 정렬의 알고리즘은 다음과 같다. 어떤 원소를 대소 비교 하면서 그 위치가 될때 까지 for문을 돌리고 그리고 그 위치에 해당하면 for문에서 나와서 그곳에 집어 넣어 준다. 원래는 배열의 모든 원소들을 해줘야 하는데 이 문제는 가장 끝 원소만 삽입 정렬을 하면 되었다. 따라서 for문을 두번 돌리지 않고 한번만 돌려서 끝에서 두번째 원소부터 해당..
https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem Cycle Detection | HackerRank Given a pointer to the head of a linked list, determine whether the linked list loops back onto itself www.hackerrank.com 연결리스트 내에서 사이클이 있는지 없는지 확인하는 문제이다. head에서 시작하는 slow와 fast를 두 개 만든다. slow는 한번 움직이고 fast는 두번 움직인다. (slow n번 움직이면 fast는 2n번 움직임) 이때 slow와 fast가 만나게 된다면 cycle이 ..
https://www.hackerrank.com/challenges/tree-postorder-traversal/problem Tree: Postorder Traversal | HackerRank Print the post order traversal of a binary tree. www.hackerrank.com postorder 방식은 트리에서 노드를 LRV로 찾는다. 즉, 노드의 왼쪽, 오른쪽, 노드 자신 순으로 방문한다고 생각하면 된다. 이러한 postorder 방식은 재귀를 이용하면 쉽게 풀 수 있다. (postOrder 함수만 완성시키면 되는 문제여서 postOrder 함수 코드만 올린다.) if문 안을 보면 재귀를 이용하여 함수의 코드를 완성한 것을 볼수있다. postOrder 방식은 LR..
파일을 실행시켰더니 다음과 같이 나왔다 문자열을 입력받고 나서 버퍼의 주소가 출력되는 것 같다. 파일을 실행시킬때 마다 버퍼의 주소가 다르게 나오는 것을 확인할 수 있었다. 보호기법을 확인해보았는데 딱히 걸려있는게 없다. IDA로 파일을 까보았다. scanf로 입력을 받을때 overflow가 일어나는 것을 알 수 있다. 그리고 버퍼의 주소가 출력되는 것을 확인할 수 있었다. ret에 버퍼의 주소를 넣어주는 방식으로 접근을 해보았다. s의크기는 0x88=136이고 sfp의 크기는 4이다. ret전까지의 크기는 140바이트가 되는데 여기에서 25바이트 쉘코드를 사용하게 되면 115바이트를 dummy로 채워주면 될것이다. 또한, 버퍼의 주소가 계속 바뀌기 때문에 recv를 이용하여 받아온다. !!오타가 나면 ..
먼저 파일을 실행해 보았다. 문자를 입력받으면 그 문자를 출력하는 형태인것 같다. 보호기법이 뭐가 있는지 확인해 보았다. NX가 걸려있다. 쉘코드를 사용하지 못한다. IDA를 이용해서 뜯어보자 s를 입력받고 v5에는 s의 길이가 들어가고 printf를 통해 s를 출력한다. s를 입력받을때 그 길이가 제한되어 있지 않으므로 여기서 오버플로우가 발생할 수 있다. s의 크기는 0x110=272바이트이다. 예전에 이런 문제를 풀었는데 이때 함수를 이용하여 문제를 풀었다. 따라서 함수가 뭐가 있는지 확인한다. callMeMaybe라는 함수가 있다. 이 함수의 주소는 0x400606이다. 자세히 살펴보자 이 함수는 쉘을 실행시키는 함수이다. 따라서 이 함수의 주소를 ret에 넣어준다면 풀릴 것이다. s의 크기는 2..
https://www.hackerrank.com/challenges/balanced-brackets/problem Balanced Brackets | HackerRank Given a string containing three types of brackets, determine if it is balanced. www.hackerrank.com 스택을 이용하여 괄호 검사 하는문제 한군데를 캐치하지 못해서 2시간을 낭비했던 문제......(덕분에 이제 못잊을 것 같다) 스택을 배열로 하여 문제를 풀었다. 여는 괄호와 닫는 괄호가 제대로 매치될때 YES를 출력하면 된다. 제대로 매치되지 않으면 NO를 출력하면 된다. 이는 다음과 같다 1. 여는 괄호가 없을때 2. 여는괄호와 닫는 괄호가 매치되지 않을때 3...
https://www.hackerrank.com/challenges/queue-using-two-stacks/problem Queue using Two Stacks | HackerRank Create a queue data structure using two stacks. www.hackerrank.com 두개의 스택을 이용하여 큐를 구성하는 문제 그냥 큐로 풀수도 있으나 중요한 것은 두개의 스택으로 문제를 풀어야 된다는 것이다. 스택은 Last In Last Out 이지만 큐는 Last In First Out이라는 것에 유념을 하여 문제를 풀어야 한다. 두 개의 스택이 있다고 가정을 하자. 먼저 a 스택에 값을 다 집어 넣고 이 스택의 내용들을 b 스택에 옮긴다고 하자. b 스택으로 옮기게 되면 가장 ..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 아직 DFS와 BFS를 안배워서 책의 뒷부분 내용을 참고하여 코드를 짰다. 책에서는 인접리스트로 풀었는데 그냥 인접행렬로 풀었다. 인접리스트로 다시 풀어봐야 될것 같다.
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택을 이용한 문제 push를 할때 '+'가 배열에 들어가고 pop을 할때 '-'가 배열에 들어간다는 점을 이용하여 문제를 풀었다. push함수는 스택에 값을 입력해주고 symbol이라는 char 배열에 '+'를 넣어준다. pop함수는 index의 값을 1줄여주고 symbol에 '-'를 넣어준다. top은 스택의 가..
