문제 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5)..
문제 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 제한사항 arr은 길이 1이상, 15이하인 배열입니다. arr의 원소는 100 이하인 자연수입니다. 입출력 예 설명 접근 두수의 최대공약수는 두수를 곱하고 최대 공약수로 나눠주는 식으로 구할수 있다 이때 파이썬의 math모듈의 gcd를 사용하면 최대공약수를 구할수 있다. math모듈의 gcd의 사..
소수를 찾는 방법으로 하나 외우고 있으면 좋을것 같다 소수를 찾는 코테 문제하나를 풀어봤는데 기존에 모든 경우의 수(2와 3부터 시작하는 모든 홀수) 를 넣어서 찾는 방법은 시간초과가 되어버렸다.(소수탐색 자체만 해도 O(n)이고 만약 두 소수의 곱으로 이뤄진 숫자에서 두 소수를 찾아라 하는 문제일 경우 반복문을 이용해야 되므로 O(n^2)의 경우가 되는 문제가 있었다.) 에라토스테네스의 체를 사용한다면 O(N^1/2)의 시간복잡도로 계산할수 있다 주로 대량의 소수를 한꺼번에 판별해야할 경우에 사용한다 방식(파이썬) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지운다. 3도 지워지지 않았기 때문에 ..
