[C/C++] 백준 #2108 통계학(수학)
이번 문제는 통계학에서 자주 사용되는 평균, 중위값, 최빈값, 범위를 구하는 것입니다. https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 여기에서는 히스토그램을 구하면, 위의 4가지를 다 구할 수가 있습니다. 예를 들어서 3이 4번 나타났고 5가 7번 나타났고, 10이 2번 나타났다면, 평균은 (3*4+5*7+10*2)/13 이 됩니다. 중위값은, 13+1을 2로나눈 값인 7이 위치한 히스토그램 값을 찾으면 됩니다. 그러면 중위값은 5가 되겠죠. 최빈값은 히스..
2023. 3. 31.
[C/C++] 백준 #2096 내려가기(동적 계획법)
내려가기 문제는 간단한 형태의 동적 계획법(Dynamic Programming)을 사용하면 됩니다. 동적 계획법을 사용하지 않고, DFS나 BFS를 이용해서 풀 수는 있지만, 그렇게 하면 시간이 많이 걸립니다. 다익스트라 알고리즘을 사용해도 동적 계획법을 적용한 것과 같은 효과를 낼 수 있습니다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 설명을 이해하기 어려웠습니다. 주어진 N이 주어지면, 3xN 형태의 공간이 발생합니다. 맨 위층에서는 3칸..
2023. 3. 30.
[C/C++] 백준 #2089 -2진수(수학)
이번 문제는 실제 사용할 일은 거의 없는 -2 진법 이야기입니다. 간혹 수학에서는 마이너스 진법이나 복소수 진법과 관련되어 이야기 되기는 합니다. 대표적으로 \(1+i\)진법 같은 경우가 있습니다. https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 문제 자체는 오답을 낼 가능성이 있는 것을 제외하고는 크게 어렵지는 않습니다. 일반적으로 양수 진법이라..
2023. 3. 28.