개발새발

[문제] 개구리가 피보나치 수 만큼 뛰어 강 반대편으로 넘어갈 때 최소 점프 수를 구하는 문제 (넘어가지 못한다면 -1을 반환) FibFrog coding task - Learn to Code - Codility Count the minimum number of jumps required for a frog to get to the other side of a river. app.codility.com [코드] 시간복잡도 : O(N*log(N)) 피보나치수를 구한 다음 특정 나뭇잎에 도달할 수 있는지 체크하고 마지막으로 강 건너편에 도달할 수 있는지 체크 (코드가 깔끔하지 않아 개선의 여지가 있음) def solution(A): # write your code in Python 3.6 fib = [0 f..

[문제] 0 ~ N-1 의 배열에서 1~6 칸씩 이동하여 N-1에 도착할 때까지 방문한 index의 값의 합 중 가장 큰 값을 찾는 문제 NumberSolitaire coding task - Learn to Code - Codility In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6. app.codility.com [코드] 시간복잡도 : O(N) 맨 끝에서 부터 1-6칸씩 이동하며 N-1에 도착할 때까지 방문한 index의 값의 합 중 최대값을 기록하고 0번째 배열의 계산 값을 반환 def solution(A): # write your code in P..

[문제] 배열 내 연속된 수들의 합이 가장 큰 경우의 값을 찾는 문제 MaxSliceSum coding task - Learn to Code - Codility Find a maximum sum of a compact subsequence of array elements. app.codility.com [코드] 시간복잡도 : O(N) 배열 내 이전 값들과의 합이 현재 값보다 작다면 다시 현재 값부터 더해나가기 시작한다 def solution(A): # write your code in Python 3.6 answer = -2147483648 sum = 0 for num in A : sum = sum + num sum = max(num, sum) answer = max(answer, sum) return ..

[문제] Codility f&q에서 제공되는 데모 문제 Codility Your browser is not supported You should use a supported browser. Read more app.codility.com [코드] 시간복잡도 : O(N) * Python list의 in 연산자의 시간복잡도는 O(N)임 def solution(A): # write your code in Python 3.6 answer = 1 check = [0 for i in range(1000002)] A.sort() for num in A : if num > 0 : if answer == num : check[num] = 1 answer = answer + 1 elif check[num] != 1 : b..

[문제] 주어진 문자열이 완성된 괄호인지 확인하는 문제 https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/ Nesting coding task - Learn to Code - Codility Determine whether a given string of parentheses (single type) is properly nested. app.codility.com [코드] stack을 활용 시간복잡도 : O(N) def solution(S): # write your code in Python 3.6 stack = [] for s in S : if not stack : stack.append(s) elif stack[-1] ..

[문제] N = A*B 를 만족하는 A, B 중 2*(A+B)의 값이 가장 작은 경우를 찾는 문제 MinPerimeterRectangle coding task - Learn to Code - Codility Find the minimal perimeter of any rectangle whose area equals N. app.codility.com [풀이] 1 부터 N의 제곱근 사이에서 N의 약수를 찾고, 가장 큰 약수를 A로 여겨 2*(A+N/A) 값을 반환 시간복잡도 : O(sqrt(N)) import math def solution(N): # write your code in Python 3.6 root = int(math.sqrt(N)) A = 1 for i in range(1, root+1)..

[문제] 시간이 흐르며 낙엽이 떨어지고 개구리가 반대편 낙엽을 밟으며 강으로 건너갈 수 있는 최소 시간을 구하는 문제 FrogRiverOne coding task - Learn to Code - Codility Find the earliest time when a frog can jump to the other side of a river. app.codility.com [코드] 시간복잡도: O(N) def solution(X, A): # write your code in Python 3.6 setleaf = set() for idx, position in enumerate(A) : setleaf.add(position) if len(setleaf)==X: return idx return -1

[문제] 배열 내 같은 값을 갖지 않는 연속된 수를 갖는 배열의 연속된 부분 집합을 구하는 문제 CountDistinctSlices coding task - Learn to Code - Codility Count the number of distinct slices (containing only unique numbers). app.codility.com [코드] 시간복잡도 : O(N * (N+M)) def solution(M, A): # write your code in Python 3.6 listA = [] answer=0 for a in A: if a in listA: idx = listA.index(a) answer=answer + int((len(listA)*(len(listA)+1))/2) i..

[문제] 배열을 두 개의 배열로 나눈 후 각 배열의 합의 차이가 가장 작은 경우의 값을 구하는 문제 TapeEquilibrium coding task - Learn to Code - Codility Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|. app.codility.com [코드] 시간복잡도 : O(N) def solution(A): # write your code in Python 3.6 lenth = len(A) tape1 = A[0] tape2 = sum(A[1:]) answer = abs(tape1-tape2) for i in range(1, lenth-1) : tape1 = tape1 + A[i] tape2 = tape..

[문제] 배열 내 1~N의 값 중 빠진 수를 찾는 문제 PermMissingElem coding task - Learn to Code - Codility Find the missing element in a given permutation. app.codility.com [코드] 시간복잡도 : O(N) def solution(A): # write your code in Python 3.6 if not A : return 1 A.sort() for idx, value in enumerate(A) : if idx+1 != value : return idx+1 return len(A)+1