https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 시간복잡도가 O(nlogn)인 정렬은 heap sort, merge sort, quick sort가 있다. 그중에서 merge sort로 문제를 풀어보았다. Merge Sort(합병 정렬) 처음에 백준에 제출할때 pos++, left++이런식으로 코드를 작성했는데 이렇게 했더니 틀리고 pos=pos+1, left=left+1로 썼더니 맞았다. 뭔차이점이 있는지 모르겠다. (혹시 아시는..
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있다. 예를 들면 삽입 정렬, 버블 정렬 등이 있다. 1. 버블 정렬 버블정렬은 이웃하는것과 하나하나씩 비교를 하여 정렬을 한다. 따라서 하나하나씩 비교를 할때 모두다 오름차순이면 더이상 진행을 하지 않아도 된다. 따라서, i가 n-1부터 시작을하여 i의 값을 1씩 줄어들게 만들고 i이하의 범위 내에서 가장 큰 수는 배열에서 i의 위치에 오도록 만든다..
https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 �� www.acmicpc.net '한수'를 이해하지 못한다면 은근 까다로운 문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다 예를들어, 123 인경우 1, 2, 3은 공차가 1인 등차수열을 이루므로 한수이다. 951의 경우 9, 5, 1은 공차가 4인 등차수열로 한수이다. 777의 경우 7, 7, 7은 공차가 0인 등차수열로 한수이다. 십의자리 수는 무조건 등차수열일수 밖에 없다. 십의 자리 수..
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..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 활용하는 문제이다. 다이나믹 프로그래밍은 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다. 분할정복 문제와도 비슷한데 다른 점은 다이나믹 프로그래밍은 겹치는 문제가 발생하기 때문에 메모이제이션 등이 필요하다. 이미 계산한 정보를 배열에 저장하여 나중에 동일한 계산을 해야할 때 저장된 값을 반환한다. 첫번째는 top-down 방식으로 작성하였다. 계산한 정보를 저장할 배열을 d라고 했고 1000001 크기를 가지도록 했다. f(n)이 최소횟수라 하자...
