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..
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은 스택의 가..
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상정렬을 사용하는 문제이다. C로 열심히 풀어보려 하였으나 내 실력이 부족해서 구현이 잘 안되었다... 그래서 C++로 풀었다. 참고한 문서 https://m.blog.naver.com/PostView.nhn?blogId=chansung0602&logNo=221035052821&proxyReferer=https:%2F%2Fw..
https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 큐의 기본을 다지기 좋은 문제였다.
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. www.acmicpc.net 이진 탐색을 이용하여 수를 찾는 문제이다. 이진 탐색을 이용하기 위한 전제조건은 바로 오름차순으로 정렬이 되어 있어야 한다는 점이다. 오름차순으로 정렬하기 위한 정렬방법은 두가지 방법이 있다. 하나는 qsort, 또다른 하나는 bubble sort bubble so..
