개발/알고리즘 문제
1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번?
2018. 1. 16.1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다. 123, 124, 125, 134, 135, 145, 234, 235, 245, 345 조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다. nCr =n! r!(n−r)!, 단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다) 간만에 풀었다.간단한데 문제를 자꾸 이해 못해서 몇 번 고침. from math import fact..
[Codility] CountDiv
2017. 11. 14.0. 문제세 개의 integer A, B, K 가 있다. A와 B 사이에 있는 integer 중 K로 나누어 떨어질 수 있는 수의 개수를 구하여라. 1. 답변 문제는 쉬웠는데 예외 사항을 체크하지 못해 여러 번 돌려야 했다. A나 B가 0일 경우엔 아무 수로나 나누어 떨어지는데 이걸 그냥 넘어감 A가 K 이상일 경우, B가 K 이상일 경우를 나눠 몫을 구하고, A가 0일 경우엔 결과값에 1을 더했다. def solution(A, B, K): result = 0 if A >= K: result = B // K - (A-1) // K elif B >= K: result = B // K if A == 0: result += 1 return result 2. 결과
[Codility] MaxCounters
2017. 11. 13.0. 문제리스트 A와 N개의 카운터가 주어진다. 카운터는 처음에 모두 0으로 세팅되며, N이 5이면 카운터는 (0, 0, 0, 0, 0) 이다. 이때, 만약 1
[Codility] MissingInteger
2017. 11. 12.0. 문제 N개의 상수로 이루어진 리스트 A가 있다. 이때 A 안에 '없는' 가장 '작은' 자연수(0보다 큰)를 리턴한다. 1. 답변 def solution(A): if max(A) < 1: return 1 else: sorted_a = sorted(set([a for a in A if a > 0])) for idx, val in enumerate(sorted_a, 1): if idx != val: return idx return sorted_a[-1]+1 음 쉬웠음 시간복잡도 O(N) 혹은 O(N * log(N))
[Codility] FrogRiverOne
2017. 11. 10.0. 문제position 0에 있는 개구리가 하나 있다. 이 개구리는 X를 이동하여 X+1의 위치로 이동하고 싶어한다.(그러니까 A[0]에서 A[X+1]로 이동한다는 거) 리스트 A는 개구리가 건널 수 있는 잎의 위치리스트다. 배열의 index는 초(second)이고, value는 나뭇잎이 놓이는 위치이다. 그러니까, 개구리가 5로 이동하고 싶은데 리스트 A가 [1, 3, 1, 4, 2, 3, 5, 4] 면 6초가 지나야 개구리가 원하는 위치로 갈 수 있다는 거. 만약 배열이 [1, 3, 1, 3, 4] 이라면 개구리는 원하는 곳에 가지 못하고, 이럴 땐 -1을 리턴해야 한다. X와 A가 파라미터로 주어질 때, 개구리가 원하는 위치로 이동할 때까지 걸리는 시간을 구하라. 1. 답변 문제를 처음에 잘못 이..
[Codility] PermCheck
2017. 11. 9.0. 문제N개의 상수로 이루어진, 비어있지 않은 리스트 A가 있다. A 순열(permutation)은 1부터 N 까지의 중복되지 않는 숫자의 연속이다. 주어지는 리스트 A가 순열인지 판별하라. 1. 답변 이번 것도 난이도가 매우 낮았다. def solution(A): sorted_a = sorted(set(A)) if len(sorted_a) == len(A) and sorted_a[-1] == len(A): return 1 else: return 0 시간복잡도는 O(N) or O(N*log(N))
[Codility] FrogJmp
2017. 11. 7.0. 문제작은 개구리 하나가 X에서 Y(혹은 그보다 더 멀리)로 이동하고 싶어한다. 개구리는 매 점프마다 D만큼 이동한다. 개구리가 원하는 위치에 도달할 때까지 필요한 최소 점프 횟수를 구하라. 1. 답변 Codility에서 print()가 된다고 python3를 지원한다고 생각했던 게 오산이었다. 문제를 읽고 왜 이렇게 쉽지 하고 1-2분 만에 풀었는데, 정답률 44%.. python2와 python3의 round() 함수가 다른 값을 내놓는 다는 걸 처음 알았다.(python2를 쓴 적이 거의 없으니..) 처음 짰던 코드는 이렇다. def solution(X, Y, D): return int(round((Y - X) / D + 0.5)) 깨달음(?)을 얻고 난 뒤의 코드. 시간복잡도 O(1)def s..
[Codility] TapeEquilibrium
2017. 11. 6.0. 문제 비어있지 않은 리스트 A에 N개의 숫자가 있다.(N은 2와 100,000 사이의 숫자) 그리고 0 < P < N 의 조건을 가지는 자연수 P가 있다. 자연수 P에 의해 리스트 A는 이렇게 둘로 나눠지게 된다. A[0], A[1], ..., A[P − 1] A[P], A[P + 1], ..., A[N − 1] 이때 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| 의 가장 작은 값을 구하라. 1. 답변 처음에 답변은 다 맞췄으나 TimeoutError가 났다. for p in range(1, len(A)): diff = abs(sum(A[:p]) - sum(A[p:])) 위와 같이 간지나게 풀었는데... 루프를 돌 때마다..
[Codility] PermMissingElem
2017. 11. 5.0. 문제 주어진 리스트 A는 N개의 서로 다른 숫자로 이루어져 있다. 그리고 이 리스트에는 [1..(N + 1)] 이렇게 1부터 N+1까지의 숫자가 무작위로 섞여있는데 항상 하나의 숫자가 빠져있다. 이 빠진 숫자를 구하시오. 1. 답변 주의할 점은... - 리스트 아이템이 하나일 경우 - 첫 번째(1) 혹은 마지막(N+1)이 빠졌을 경우 이걸 감을 못잡아서 계속 고쳤다... def solution(A): if A: sorted_A = sorted(A) for idx, n in enumerate(sorted_A, 1): if idx != n: return idx return sorted_A[-1]+1 else: return 1 enumerate() 는 내장함수인데 실제 업무에서도 굉장히 유용하게 쓰고 있다.
[Codility] CyclicRotation
2017. 11. 4.0. 질문 인자 값으로 리스트 A와 상수 K를 받는다. 리스트 A의 값들은 K만큼 오른쪽으로 이동하며 리턴값은 전부 이동하고 난 뒤의 A이다. 1. 답변 def solution(A, K): if A: if len(A)
[Codility] OddOccurrencesInArray
2017. 11. 2.0. 문제 1개 이상의 숫자가 들어있는 리스트 A가 주어진다. 여기 리스트 A에서는 모든 아이템들이 2개, 혹은 4개, 6개 이렇게 짝수 개의 짝을 이루고 있다. 딱 하나만 빼고. 예를 들자면 이렇다.A = [1, 9, 6, 3, 3, 1, 7, 6, 9]여기서 짝이 없는 하나의 숫자를 찾아 리턴해야 한다. 1. 답변 꽤 빠르게 짰는데, 처음엔 리스트 A를 set으로 중복 제거하고, 이 set을 for loop로 돌려 A.count(num) 이런 식으로 리스트 A 내의 숫자를 카운트하게 했는데... 너무 느려서 performance에서 점수 깎임. 검색해보니 sorted(리스트) 이 함수가 정말 빠르다고 해서 사용했다. 아이템이 짝수이거나 리스트의 길이가 1인 경우 등의 예외사항을 모두 try/excep..
[Codility] BinaryGap
2017. 11. 1.0. 코딩 소모임에서 코딜리티codility, 해커랭크hackerrank 를 알게되었다. 코딜리티는 여기저기서 들어보긴 했는데 가입해서 문제를 풀어보는 건 처음이었다. 자동 채점 방식을 그닥 좋아하지 않아서 프로젝트 오일러를 좋아했었는데, 이것도 익숙해지면 괜찮을 듯. 1. 문제 binary gap은 1000010001과 같은 2진법 수에서 1과 1사이에 있는 0의 개수이다. 리스트 N이 주어지면 여기에서 가장 긴 binary gap을 찾아야 한다. - 마지막이 1이 아닌 0으로 끝날 경우를 체크해주어야 한다. 이걸 체크 안해서 틀림 2. 답변 def solution(N): bin_str = bin(N).replace('0b', '') bin_gap_list = list(filter(None, bin_s..