* 문제 링크 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net * 문제 유형 주어진 조건에 맞게 경사로만 설치해주면 되는 전형적인 시뮬레이션 * 문제 해설 시뮬레이션유형의 문제를 풀 때는 주어진 조건을 꼼꼼하게 읽는 것이 중요하다. (필자는 꼼꼼하지 못한 탓에 경사로 위에 경사로를 놓으면 안된다는 것을 읽지 못하고 2시간동안 삽질했다.) 시간제한은 2초, 지도의 크기는 최대 100X100이고 (1

개념 서로 다른 n개의 수 중에 r개를 선택 nCr = n! / (n-r)! * r! 리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다. 구현 재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다. nCr에서 n nCr에서 r 기저 조건을 위한 idx 어느곳을 탐색할지 정하는 curr 그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다. 나열한 수를 담을 배열 나열되어져야 할 수를 담은..

개념 완전탐색은 알고리즘에 입문하는 사람들이 가장 처음으로 접하는 내용일것입니다. 그만큼 어려운 내용은 아니며, 말 그대로 완전히 탐색하는 것입니다. 영어로는 brute-force라고 하는데, 이것을 번역해보면 "무식하게 풀기"라는 뜻입니다. 구현 완전탐색을 할 때 사용되어지는 방식은 크게 두가지로 볼 수 있습니다. 1. Iterative 2. recursion 1번은 for문을 이용한 풀이 이고 2번은 재귀 호출을 이용하여 푸는 방법입니다. 예를 들어, 1부터 n까지의 합을 구하는 코드를 구성해보겠습니다. // iterator // 조건 : n >=1 // 1~n의 합을 반환한다. int sum(int n) { int ret = 0; for (int i = 1; i < n; ++i) ret += i; ..

원리 1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함. 2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴 3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 4. 분할된 리스트들에서 1-3번 과정을 반복한다. 위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다. 앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다. [ 16, 11, 6, 19, 12, 2, 2, 10 ] pivot값은 맨앞의 값..

원리 1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할) 2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복) 3. 정렬 한 결과를 병합한다. (병합) [ 16, 11, 6, 19, 12, 2, 2, 10 ] 정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다. 분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다. 구현 template vector MergeSort(co..

원리 1. 집합의 최댓값을 구해서 최대값만큼의 메모리를 차지하는 카운팅 배열을 만든다. 2. 각원소의 개수를 카운팅시킨다 3. 카운팅 배열의 누적합을 구한다. 4. 카운팅 배열을 통해 순서대로 수를 나열한다. [ 15, 13, 10, 7, 5, 5, 1, 0, 7 ] 카운팅 배열에는 다음과 같이 구성될 수 있습니다. Index 0 1 5 7 10 13 15 count 1 1 2 2 1 1 1 다음을 누적합의 표입니다. Index 0 1 5 7 10 13 15 count 1 2 4 6 7 8 9 이때, 누적합을 구하는 이유는 어느 인덱스에 원본 원소가 들어갈지 순서를 강제하기 위해서 입니다. 정렬된 원소들이 들어갈 배열의 인덱스를 카운팅배열의 데이터 - 1로 설정 해줌으로서 정렬 해줄 수 있습니다. 예를들..