라떼는말이야

문제 정수 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을 넘지 않는 경우 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐 계수 정렬의 정렬 방법 계수 정렬은 버블 정렬, 병합 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬 ..

퀵 정렬은 이름에서 알 수 있듯이 정렬 알고리즘 중 속도가 빠른 알고리즘이다. 이해가 쉽고 간단한 정렬 알고리즘인 선택 정렬과 삽입 정렬의 시간 복잡도가 O(N^2) 인 것에 비해 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 아이디어는 다음과 같다. 기준이 되는 데이터인 pivot을 하나 선택한다. 일반적으로 가장 많이 사용되는 것은 주어진 array의 첫 번째 요소이다. (array[0]) pivot을 기준으로 pivot 보다 작은 데이터와 pivot보다 큰 데이터로 구분한다. pivot을 pivot보다 작은 데이터와 pivot보다 큰 데이터 사이에 위치시키면 pivot의 위치가 결정된다. [pivot 이하] [pivot] [pivot 초과] pivot보다 작은 데이터와 pivot보다 큰 데이터..

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만 들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 나의 풀이 def solution(number, k)..

문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 입출력 예 설명 이 과학..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 나의 풀이 여러 시도를 해보았는데 생각보다..