Henry's Algorithm

안녕하세요!ㅎㅎ

알고리즘을 공부하는 개발자 Henry입니다!

오늘은 제가 오랜만에 Codility 사이트에서 문제를 한번 풀어보았는데요,

Painless 난이도의 문제여서 비교적 쉽게 풀리나 싶었는데,

생각보다 시간이 걸렸던 것 같습니다.

처의 첫번째 시도는 아래와 같습니다!

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, M):
    # write your code in Python 3.6
    chocolates = [0]*N
    _current = 0
    while chocolates[_current] != 1:
        chocolates[_current] = 1
        _current = (_current+M)%N

    return sum(chocolates)
    pass

배열을 활용해서 정직하게 문제 그대로 풀려고 하였는데요,

이렇게 풀게 되면 정확도는 맞출 수 있었는지는 모르겠지만,

시간효율에 대해서는 Timeout으로 점수를 얻지 못했습니다..ㅠ!

이 문제는 산수로 풀 수 있는 문제입니다.

특별히 Codility에서는 이 문제를 유클리드 알고리즘으로 접근하도록

분류를 해놓았는데요,

아래는 제가 문제를 정확하게 다시 읽고 몇번의 시도 끝에 풀게 된 코드입니다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, M):
    # write your code in Python 3.6
    from math import gcd
    return N//gcd(M,N)

    pass

2줄이면 끝나는 문제이지요..?

때로는 생각나는 대로 무작정 덤비는 것보다,

산수와, 수식 등을 적용할 수 있는지 한번 더 고민해본 후에 문제를 풀어나가는 것도 좋은 방법일 것 같습니다.

그럼 오늘도 즐거운 코딩하세요!

아래는 제가 푼 문제 해설 영상이니 참고하시면 좋을 것 같습니다!ㅎㅎ

https://www.youtube.com/watch?v=7F7fICsnNOQ 

감사합니다!

1보다 큰 모든 정수는 소수와 합성수로 이루어진다.

소수는 1과 자기자신으로만 나누어떨어지는 수이고,

그 외 나머지를 합성수라고 한다.

1은 소수도 합성수도 아니다.

소수를 찾는 방법은 에라토스테네스의 체 방식으로 찾을 수 있다.

1. 2를 제거하고, 2의 배수를 제거한다.

2. 3을 제거하고, 3의 배수를 제거한다.

3. 해당 방법을 sqrt(n)까지 반복한다. - sqrt는 루트

자신 * 자신 < n 때까지만 반복한다.

아래는 생각나는대로 에라토스테네스의 체를 사용하여 문제를 풀려고 했던 방법이다.

하지만 생각대로 쉽게 풀리지 않았다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, P, Q):
    # write your code in Python 3.6
    
    result = []
    for a,b in zip(P,Q):
        
        if b <= N:
            c = b
        else:
            c = N
        result.append(len(get_prime(N,a,c)))
    
    #print(result)
    return result
    pass

def get_prime(num,a,b):
    arr = []
    if num <= 1:
        return arr
    arr2 = []
    
    for i in range(2,num+1):
        flag = True
        for j in range(len(arr)):
            if i%arr[j] == 0:
                flag = False
                break
        if flag:
            if a <= i**2 and i**2 <= b:
                arr2.append(i*i)
            arr2.extend([k*i for k in arr if a <= k*i and k*i <= b])
            arr.append(i)
    return arr2
        

구글링을 통해서 해답을 알게 되었다.

해답은 인덱스를 사용하여 계산을 하는 것이다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

import math

def solution(N, P, Q):
    # write your code in Python 3.6
    # N+1의 개수를 가진 빈 배열을 만들어준다.
    arr = [0]*(N+1)
    semi_cnt = [0]*(N+1)
    each_sum = 0

    #1~N 까지의 범위의 수를 소수와 소수의 배수로 구분함
    i = 2
    while i <= math.sqrt(N):
        if arr[i] == 0:
            j = i*i
            while j <= N:
                arr[j] = i
                j += i
        i += 1
    #print(arr)

    # 인덱스를 통해서 문제를 풀어준다.(소수일때, 나누고 나눈 값이 다시 소수라면 +1)
    for i in range(1,N+1):
        if arr[i] != 0:
            j = i//arr[i]
            if arr[j] == 0:
                each_sum += 1
        semi_cnt[i] = each_sum

    #rint(semi_cnt)

    result = []

    # 범위에 따라 소수의 개수를 차감하여 값을 배열에 넣어준다.
    for i,j in zip(P,Q):
        result.append(semi_cnt[j]-semi_cnt[i-1])

    #print(result)
    return result

    pass

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    arr__ = [0]*(2*len(A)+1)
    arr = []
    
    saved = [-1]*(2*len(A)+1)
    
    for i in range(len(A)):
        arr__[A[i]] += 1
    
    
    for i in range(len(A)):
        divisor = 0
        
        if saved[A[i]] != -1:
            arr.append(saved[A[i]])
            continue
        
        for j in range(1,int(A[i]**0.5)+1):
            
            if A[i]%j == 0:
                divisor += arr__[j]
                
                if A[i]/j != j:
                    divisor += arr__[A[i]//j]
            
            j += 1
                    
        arr.append(len(A)-divisor)
        saved[A[i]] = len(A)-divisor
            
    
    return arr
                
    pass

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

• A[0], A[1], ..., A[K − 1],
• A[K], A[K + 1], ..., A[2K − 1],
  ...
• A[N − K], A[N − K + 1], ..., A[N − 1].

What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows:

• one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
• two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
• three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

If A cannot be divided into some number of blocks, the function should return 0.

For example, given:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000].

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Peaks 문제는 봉우리를 최소 1개씩 포함하고 있는 Block의 개수를 구하는 문제이다.

최대 블록의 개수를 Return 해주면 되는데,

그 방법을 구체적으로 어떻게 짜야되는지 다양하게 시도하다가 

결국 답지를 보고 풀었다.ㅜㅜ!!

그래도 이 방법 잘 알아두어야겠다.

정답 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    peaks = []
    
    for i in range(1, len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peaks.append(i)
            
    for i in range(len(peaks),0,-1):
        if len(A) % i == 0:
            block_size = len(A)//i
            block = [False]*i
            block_cnt = 0
            for j in range(len(peaks)):
                idx = peaks[j] // block_size
                if block[idx] == False:
                    block[idx] = True
                    block_cnt += 1
            
            if block_cnt == i:
                return block_cnt
        
    return 0
        
    pass

처음에 봤을 때,

문제를 이해하는데는 그렇게 어렵지 않았다.

그냥 약수 구해서 두 값 더해서 *2 해주면 되는데,

그 중 최소값을 찾는 문제구나 라는 생각만 하였고 접근했다.

첫 시도했을 때는 아래의 코드와 같다.

그런데 80%의 정확도만 나왔다.

그 원인을 살펴보니 큰 수에 대해서는 for문에서 i 가 일일히 +1씩 되면서 진행되는 부분이

성능이 좋지 않음을 알 수 있었다.(Timeout Error 발생ㅜㅜ)

그래서 for i in range(2,int(i/2)): 처럼 나누기 2를 해보기도 하고 그랬는데,

역시나 마찬가지였다.

# 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
    
    check = N
    max_perimeter = 2*(1+(N))
    
    for i in range(1,N+1):
        
        # 반복되는 값이 가장 최근의 몫의 값보다 커지면 그만
        if i >= check:
            break
        
        # 0으로 나눠지면 약수
        if N%i == 0:
            max_perimeter = min(max_perimeter,2*(i+(N/i)))
            check = N/i
    
    return int(max_perimeter)
    
    pass

잠깐 들었던 생각이

이전에 풀었던 Codility 문제 중에 CounterFactors라는 문제에서도 약수를 구하는 문제였는데,

조금 다르게 접근했던 것 같은 기억이 있어서 찾아보았다.

https://datacodingschool.tistory.com/69

그리고 그 결과 같은 방법으로 For 문을 돌리고 100% 정확도를 얻을 수 있었다.

약수를 구하는 문제에는 이제 i*i 라는 방식을 사용해주어야겠다.

두번째 시도했을 때 코드

# 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
    
    max_perimeter = 2*(1+(N))
    number_iter = 1
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            max_perimeter = min(max_perimeter,2*(number_iter+(N/number_iter)))
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        max_perimeter = min(max_perimeter,4*number_iter)
    
    return int(max_perimeter)
    
    pass
   

이번주 토요일에 이베이 코딩테스트,

다음주 토요일에 LG U+ 코딩테스트가 있는데,

매일 꾸준히 3문제씩 공부해야겠다.

맨 아래 코드에 정답 나와있습니다.

==============아래 코드들은 성공하기까지의 과정 =============

처음 봤을때, 문제가 이해가 잘 안되는 것이 가장 큰 문제!

그래도 해석해서 처음 푼 풀이방법

정확도: 40%ㅜㅜ

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    #print(A)
    
    if len(A) <= 2:
        return 0
    
    pre_peak_idx = 0
    current_peak_num = 0
    result_peak_num = 0
    peak_idx_arr = []
    
    for i in range(1,len(A)-1):
        #print(peak_idx_arr)
        # 만약 피크라면
        if A[i-1] < A[i] and A[i+1] < A[i]:
            # 최초 피크라면
            if current_peak_num == 0:
                current_peak_num += 1
                peak_idx_arr.append(i)
            # 피크가 2개 이상이라면
            else:
                # 조건에 부합하는지
                peak_idx_arr.append(i)
                for j in range(len(peak_idx_arr)-1,0,-1):
                    if abs(peak_idx_arr[j]-peak_idx_arr[j-1]) < (current_peak_num+1):
                        del peak_idx_arr[j-1]
                        break
                        
                if len(peak_idx_arr) == current_peak_num:
                    continue
                else:
                    current_peak_num += 1
                    
            
    #print(peak_idx_arr)
    
    
    return len(peak_idx_arr)
                    
            
            
    pass

다시 풀어봐야겠다..!! 화이팅!

다시 풀어보았다

정확도: 66% (peak의 개수가 많아지는 상태에서는 다수의 Timeout 에러 발생)

- 코드 -

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) < 2:
        return 0
    
    peak_arr = []
    
    for i in range(1,len(A)-1):
        # 피크라면
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_arr.append(i)
            
    #print(peak_arr)
    
    length_peak_arr = len(peak_arr)
    
    if len(peak_arr) == 0:
        return 0
    
    for j in range(len(peak_arr),0,-1):
        current_index = 0
        num_of_peak = 1
        
        for i in range(1,len(peak_arr)):
            if abs(peak_arr[i] - peak_arr[current_index]) < j:
                continue
            else:
                num_of_peak += 1
                current_index = i
            
            if num_of_peak == j:
                return j
            
            
    return num_of_peak
    
    
    pass

이중 for문은 역시 안좋다

대충 감을 잡은 거 같다.

다시 풀어봐야겠다!!

임시 저장 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) < 2:
        return 0
    
    num_peaks = 0
    peak_arr = []
    
    for i in range(1, len(A)-1):
        # 피크인 경우
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_arr.append(i)
    
    print(peak_arr)
    
    if len(peak_arr) == 0:
        return 0
    
    if len(peak_arr) == 1:
        return 1
    
    peak_cnt_ = 1
    peak_num_ = 1
    
    for j in range(len(peak_arr),1,-1):
        
        for i in range(len(peak_arr)):
            
            if peak_arr[i] >= peak_j*j:
                peak_num_ += 1
                peak_cnt_ += 1
            
            if peak_arr[i] >= peak_arr[0]+j*peak_cnt_:
                peak_num_ += 1
                peak_cnt_ += 1
            if peak_num_ == j:
                return peak_num_
           
    
    pass

7월6일 재도전

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) <= 2:
        return 0
    
    peaks = []
    
    for i in range(1,len(A)-1):
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peaks.append(i+1)
            
    if len(peaks) == 1:
        return 1
        
    if len(peaks) == 0:
        return 0
    

    num = len(peaks)
    
    try:
        for i in range(1,num):
            j = 1
            if len(peaks) < i+1:
                break
            while j < i+1:
                if peaks[j] >= peaks[j-1]+(i+1):
                    j += 1
                else:
                    del peaks[j]
    except:
        return len(peaks)
        
    return len(peaks)
            
            
    
            
            
            
            
            

====================================================================================

잠깐 코딩을 쉬었다가 다시 시작한다.

8.12일

66%의 코드(다수의 Time error 발생)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    peak_arr = []
    
    for i in range(1,len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_arr.append(i)
            
    print(peak_arr)
    
    result_peak_num = 0
    
    if len(peak_arr) == 1:
        return 1
    else:
        start_peak_num = 1
        while start_peak_num < len(peak_arr):
            # 몇개의 봉우리를 찾아야하는지
            start_peak_num += 1
            # 기본 1로 시작함(이미 하나 찾은거로 가정)
            current_peak_num = 1
            s = peak_arr[0]
            # 1개 찾고, 2개 찾고 ..
            for i in range(1,len(peak_arr)):
                e = peak_arr[i]
                
                if abs(e-s) >= start_peak_num:
                    # 여기가 다시 시작이 된다
                    s = e
                    current_peak_num += 1
                    
                    if current_peak_num == start_peak_num:
                        result_peak_num = max(result_peak_num,start_peak_num)
            
    #print(result_peak_num)
    
    return result_peak_num
    
    pass

==============아래는 성공한 코드 =============

8월 21일 코드

드디어 풀었다!!

물론 구글링을 조금 하긴 했지만, 

어느정도 혼자 힘으로 풀 수 있었다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    # peak가 있는 인덱스만 모아놓은 리스트 초기화
    peak_arr_list = []
            
    
    # peak가 있는 인덱스만 모아놓은 리스트 값 채워넣기
    for i in range(1,len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_arr_list.append(i)
    
    # 만약 peak가 0개라면 return 0
    if len(peak_arr_list) == 0:
        return 0
    
	# 만약 peak가 1개라면 return 1
    if len(peak_arr_list) == 1:
        return 1       
        
    # peak_arr_list 출력 테스트
    #print(peak_arr_list)
    
    # peak_arr 라는 리스트 초기화
    peak_arr = [0]*len(A)
    peak_arr[0] = -1
    peak_arr[-1] = -1
    peak_idx = -1
    
    # peak_arr 값 채워넣기
    for i in range(len(A)-2,0,-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_idx = i
            
        peak_arr[i] = peak_idx
    
	# peak_arr 출력 테스트
    #print(peak_arr)
    
    max_num_flag = -1
    
    # 1에서 len(A)까지 반복 -> 최대 peak 개수는 len(A)가 될 수 있음
    for i in range(1,len(peak_arr_list)+1):
    
    	# index는 매 loop마다 1값으로 초기화
        index = 1
        
        # num_flag는 매 loop마다 peak 조건을 만족하면 +1씩 해줌
        num_flag = 0
        
        # num_flag가 loop보다 작으면 반복 -> 같아지면 해당 num_flag는 가능한 개수이다.
        while num_flag < i:
            try:
                if peak_arr[index] != -1:
                    num_flag += 1
                    index = peak_arr[index] + i
                else:
                    return max_num_flag
            except:
                return max_num_flag
        
        # 만약 이전 loop의 peak 개수보다 크면 max_num_flag 초기화
        max_num_flag = max(num_flag,max_num_flag)
                
    # for 끝나면 가장 최대 peak 개수를 의미하는 max_num_flag 반환
    return max_num_flag
                
    pass

해당 내용을 풀이해주는 영상을 만들었습니다.

어려우신 분들은 보시면 도움이 될 것 같습니다!!(하단 링크 참조)

https://www.youtube.com/watch?v=8DvYb9lVcRM&feature=youtu.be

나의 코드

시간 복잡도: O(sqrt(N)) or O(N)

# 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
    
    if N == 1:
        return 1
    
    cnt = 0
    
    for i in range(int(N/2)):
        # 약수이면
        i = i+1
        if N/i%1 == 0:
            if N//i < i:
                break
            if N//i == i:
                cnt += 1
            else:
                cnt += 2
                
    return cnt        
    pass
    

누군가의 코드

시간복잡도: O(sqrt(N))

# 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
    
    number_iter = 1
    factor_cnt = 0
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            factor_cnt += 2
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        factor_cnt += 1
        
    return factor_cnt
    pass

약수의 경우 이렇게 풀면 꼭 O(N)의 성능이 나지 않고,

조금 더 빠른 추출이 가능하다. 참고!