기록보관소

경제적 유인(incentive)은 사람들이 어떠한 행동을 하도록 만드는 어떠한 요인을 일컫는다. 만약 사람들이 합리적인 선택을 한다면 이익과 비용을 비교하여 이익이 커지도록 행동하므로 경제적 유인은 사람들의 행동에 큰 영향을 미친다. 따라서 어떠한 정책이나 전략을 계획할 때 부작용을 방지하기 위해서는 영향을 미칠 수 있는 유인 구조에 대해 충분한 관심을 기울여야 한다.

대개 많은 경우 어떠한 상황 속에서 선택하게 된다. 이때 현재 상태에서 이루어지는 작은 변화를 한계적 변화(marginal changes)라고 한다. 이러한 한계적 변화는 상황의 마지막에서 이루어지며 그때의 변화로 인한 편익과 비용을 고려하여 편익이 더욱 커지도록 하는 방향으로 선택이 이루어진다. 이때 편익과 비용은 현재 상황에 따라 유동적으로 평가된다. 대개 소유량, 소비량 등의 상태에 따라 편익과 비용이 결정되기도 한다. 이러한 한계적 변화는 오로지 현재 시점만을 고려한 선택이므로 전체적인 경제적 이익과 거리가 있을 수 있다.

어떠한 선택을 하였을 때 발생하는 비용은 그것을 함으로써 추가로 발생하는 비용을 포함한다. 그중에 시간적인 비용, 즉 기회비용(opportunity cost)으로 불리는 비용도 있다. 어떠한 선택을 했을 때 그 선택으로 인해 반드시 할 수 없게 되는 모든 것의 가치를 비용으로 환산해야 한다.

어떠한 선택을 하기 위해서는 다른 무언가를 포기해야만 한다. 이러한 관계를 상충 관계(trade-off)라고 한다. 여러 선택지가 존재함을 인지하는 것은 그 자체로 해답을 주지는 않지만 여러 방면으로 고심하게 하여 조금 더 합리적인 결정을 내릴 수 있도록 도와준다.

랜선 자르기 문제는 이진 탐색을 활용한 문제입니다. 랜선 길이의 최소값과 최대값을 통해 가장 작게 자를 수 있는 길이, 크게 자를 수 있는 길이를 구할 수 있습니다. 이 범위 내의 길이로 랜선을 잘라서 문제에서 요구하는 개수 이상을 만들고면서 동시에 길이를 최대화하여야 합니다. 이 길이를 찾기 위해서 이진탐색을 활용합니다. 범위의 가운데 길이로 랜선을 잘랐을 때 나오는 개수가 원하는 개수보다 작다면 토막의 길이는 더욱 작아져야하므로 범위의 상한을 가운데보다 1만큼 작은 값으로 변경합니다. 잘랐을 때 나오는 개수가 많거나 같으면 가운데 길이 미만의 길이로 나누었을 때는 더 작은 토막길이로 더 많거나 같은 랜선 토막을 만들어낼 수 있다는 의미가 되므로 범위의 하한을 가운데 길이로 변경합니다. 가운데 길이보다..

숫자 카드 2는 이진탐색을 사용하는 문제입니다. 숫자를 정렬시킨 후 이진 탐색을 하는 문제입니다. 2021.07.19 - [알고리즘/문제풀이] - [BOJ 1920번]수 찾기 [BOJ 1920번]수 찾기 수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이 ark-hive.tistory.com 이전 문제와 비슷한 방법을 사용하나 테스트 케이스의 크기가 다르기 때문에 조금은 신경을 써야 했습니다. 정렬의 경우 퀵솔트의 경우 최악의 경우 N^2이 될 수 있어서 시간초과를 내었습니다. 따라서 항상 고르게 시간을 소요하는 병합 정렬을 이용해만 합니다. 이진 탐색의 경..

리스트에서 정렬된 원소 중 특정 원소를 logn 시간 내에 찾는 알고리즘이다. 혹은 특정 원소가 리스트에 없음을 확인하는 알고리즘이다. 리스트의 중간값과 찾고자 하는 값을 비교하고 만약 찾고자 하는 값이 더 크면 리스트의 하한을 중간보다 1만큼 높은 값으로 바꾸고, 더 작으면 리스트의 상한을 중간보다 1만큼 낮은 값으로 바꾼다. 탐색하는 범위를 절반씩 줄여나가면서 결국에는 원하는 값을 리스트에서 찾거나 찾지 못하게 된다. 절반씩 범위를 줄여나가므로 lgN만큼의 시간이 소요된다.

수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이진 탐색 알고리즘을 사용해야 합니다. 작성한 코드는 다음과 같습니다. #include int N,M; int number[100020]; int temp; void quicksort(int low, int high) { if (low >= high) return; int pivot =number[high]; int index = low; int temp; for (int i = low;i