라떼는말이야

문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점 이하 ..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

캡처를 좀 늦게했지만 8번째로 풀이했습니다!! 1~2단계 수준인 것 같은데 확실히 저번 주 문제보다 쉬웠고, 사람들의 풀이도 빠르네요 [다른 사람 풀이]에서 MANGBAAM을 발견하면 추천 한 번씩 눌러주세요..ㅎ ※ 전체 소스코드는 가장 밑에 있습니다. 문제 설명 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부여한 표입니다. 예를 들면, SQL의 SI 직업군 언어 점수는 3점이지만 CONTENTS 직업군 언어 점수는 2점입니다. SQL의 HARDWARE, PORTAL, GAME 직업군 언어 점수는 0점입니다. 직업군 언어 점수를 정리한 문자열 배열 table, 개발..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 나의 풀이 아주 간단한 문제 같아 보이지만 정답률이 23%에 그치는 것을 보면 많은 사람들이 의외의 어려움을 겪는 문제인 것이다. 가장 큰 문제는 메모리이다. 8MB 제한인데 10,000,000개의 숫자를 모두 배열이나 리스트에 담아 정렬을 하려면 40MB의 메모리는 잡아먹을 것이다. 그렇기 때문에 모든 숫자를 메모리에 담지 않고도 정렬을 할 수 있어야 한다. 나는..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 나의 풀이 이 문제는 대표적은 DP 문제이다. DP란 Dynamic Programming의 약자로 다음 조건을 만족하는 경우 DP를 사용해 문제를 풀이할 수 있다. 큰 문제를 작은 문..

Python에서 리스트는 굉장히 중요하고 상징적인 자료형이다. 코딩테스트를 할 때 리스트에서 특정 값들을 모두 제거하고 싶을 때가 있다. 리스트에는 remove라는 메서드가 있어 특정 값을 제거할 수 있는데 최초로 발견되는 하나만 제거한다. 예를 들어 li = [1, 3, 5, 5, 7, 7, 8] 인 리스트가 존재할 때 li.remove(5) 를 하면 [1, 3, 5, 7, 7, 8]이 된다. 즉, 5가 여러 번 등장하면 모두 지우지 못하고 최초로 발견된 5만 제거가 된 것이다. 5를 모두 제거하고 싶다면 위와 같은 코드를 작성해 제거 할 수도 있다. 하지만 remove() 메서드는 시간 복잡도가 O(N)이고, 중복된 데이터가 많을 때 여러 번 반복하게 되면 굉장히 시간 소모가 많아진다. 그래서 다음과..

0.3 + 0.6은 0.9가 아니다!! 파이썬으로 0.3 + 0.6을 계산해보면 0.9가 나오지 않는다. 0.89999999999999 라는 근사치가 나온다. if문으로 확인을 해보아도 역시나 다르다고 나온다. 왜 그럴까? 그 이유는 컴퓨터가 2진수를 사용하기 때문이다. 컴퓨터가 실수를 처리할 때 부동 소수점(Floating-point)을 사용하는데, IEEE754 표준에서 실수형을 저장할 때 4Byte 혹은 8Byte를 사용한다. 그래서 실수 값을 표현할 때 정확도에 한계를 가지게 된다. 2진수에서 0.9를 정확히 표현할 수 있는 방법이 없다. 최대한 0.9와 가깝게 표현하지만 실제로는 미세한 오차가 발생하게 되는 것이다. 0.9에서 다른 수를 빼도 마찬가지로 미세한 오차가 발생한다. (단, 0.9 -..

계수 정렬은 특정한 조건에서 가능한 정렬 알고리즘이다. 특정한 조건만 만족한다면 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠른 알고리즘 중 하나이다. 계수 정렬의 시간 복잡도는 무려 O(N + K)이다. (N: 데이터의 개수, K: 데이터 중 최대값) 계수 정렬의 조건 데이터의 크기 범위가 제한된 경우 ex) 0 ~ 100 까지의 점수를 정렬하는 경우 데이터가 양의 정수인 경우 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않는 경우 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐 계수 정렬의 정렬 방법 계수 정렬은 버블 정렬, 병합 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬 ..