개발새발

[문제] 개구리가 피보나치 수 만큼 뛰어 강 반대편으로 넘어갈 때 최소 점프 수를 구하는 문제 (넘어가지 못한다면 -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 ..

[문제] 주어진 문자열이 완성된 괄호인지 확인하는 문제 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)..

[문제] 원 형태로 놓인 N개의 초콜렛을 M칸씩 이동하며 먹었을 때 먹을 수 있는 초콜렛의 수를 세는 문제 [코드] 시간복잡도 : O(N+M) (성능 테스트 Fail) def solution(N, M): # write your code in Python 3.6 answer=1 check = [0] * N check[0]=1 current=0 while True : current = current + M if check[current%N] == 1 : break; else : check[current%N] = 1 answer = answer+1 return answer 시간복잡도 : O(log(N+M)) (성능 테스트 Pass) 최대 공약수 활용 import math def solution(N, M): #..

[문제] 2진수에 대해 1로 둘러싸인 연속된 0의 숫자를 세어 가장 큰 연속된 0의 개수를 출력하는 문제 [코드] # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(N): # write your code in Python 3.6 binary = bin(N) start=0 cont=0 answer=0 for b in binary: if b=='1' and start==0: start=1 elif b=='0' and start==1: cont+=1 elif b=='1' and start==1: answer = max(answer, cont) cont=0 return answe..