Henry's Algorithm

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

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

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

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

정확도: 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

다시 취업 준비를 하면서 오랜만에 Codility 문제를 풀어봤다

그 동안 대림산업, 한국음악저작권협회, 딥엑스 등 다양한 곳에 면접을 보았고,

코로나 때문인지 국민은행, 마이다스아이티 등 다양한 곳에서 AI 면접을 보았다.

생각보다 취업이 잘 되지 않아서 조금 복잡한 마음이 있다.

그렇지만 성실하게 공부하고,

이렇게 취업 준비할 수 있는 것 만으로도 감사하면서 보낸다면,

결국 언젠가 나에게 가장 좋을 길이 찾아올 것을 믿는다.

최근에는 취업을 위해서 준비중인게 있다면,

오픽

정보처리기사 실기(필기는 합격><)

이다.

이 외에도 개인 프로젝트를 하곤 했었는데, 바빠져서 우선순위에서 밀리게 되었다.

이런 상황을 너무 자책하거나 힘들어하지 말고,

오히려 성실함과 인내를 배우는 감사의 시간으로 보내야겠다.

"감사로 받으면 버릴 것이 없다" 아멘~

나의 코드

시간 복잡도: 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)의 성능이 나지 않고,

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

알고리즘 문제인지 알았지만

SQL 문제였다.

하지만 SQL 로직에도 알고리즘이 필요하기 때문에 풀어보았다.

다른 일정이 있어서 다 풀진 못했지만 푼 부분까지 정답을 정리해보았다.

1번 문제

-- 코드를 입력하세요
SELECT MAX(DATETIME)
FROM ANIMAL_INS
-- ORDER BY DATETIME

2번 문제

-- 코드를 입력하세요
SELECT MIN(DATETIME)
FROM ANIMAL_INS

3번 문제

-- 코드를 입력하세요
SELECT count(*)
FROM ANIMAL_INS

4번 문제

-- 코드를 입력하세요
SELECT COUNT(DISTINCT(NAME))
FROM ANIMAL_INS

5번 문제

-- 코드를 입력하세요
SELECT ANIMAL_TYPE, count(*)
FROM ANIMAL_INS
WHERE ANIMAL_TYPE IN ('Cat','Dog')
GROUP BY ANIMAL_TYPE

6번 문제

-- 코드를 입력하세요
SELECT *
FROM (
SELECT NAME, COUNT(*) AS COUNT
FROM ANIMAL_INS
GROUP BY NAME) A
WHERE A.COUNT >= 2 AND A.NAME IS NOT NULL
ORDER BY A.NAME

7번 문제

-- 코드를 입력하세요
SELECT hour(DATETIME) HOUR, COUNT(*) AS COUNT
FROM ANIMAL_OUTS
GROUP BY hour(DATETIME)
HAVING HOUR >= 9 AND HOUR <= 19
ORDER BY hour(DATETIME)

8번 문제

-- 코드를 입력하세요
set @a := -1;
SELECT HOUR, IFNULL(COUNT,0)
FROM(SELECT HOUR(DATETIME) AS HOUR1, COUNT(*) AS COUNT
FROM ANIMAL_OUTS
GROUP BY HOUR(DATETIME)) real_table RIGHT JOIN (SELECT *
FROM (SELECT @a:=@a+1 as HOUR FROM ANIMAL_OUTS) A
WHERE A.HOUR >= 0 AND A.HOUR < 24) total_table ON real_table.HOUR1 = total_table.HOUR

2019 카카오 겨울 인턴십을 위한 코딩테스트이다.

프로그래머스가 선정한 쉬운 1단계 문제라고 해서 풀었더니

생각보다 쉽게 정답을 구할 수 있었다.

def solution(board, moves):
    answer = 0
    
    stack_bag = []
    height_arr = []
    
    for i in range(len(board)):
        height = len(board)
        for j in range(len(board)):
            if board[j][i] == 0:
                height -= 1
            else:
                height_arr.append(height)
                break
    
    
    for i in range(len(moves)):
        if height_arr[moves[i]-1] > 0:
            stack_bag.append(board[len(board)-height_arr[moves[i]-1]][moves[i]-1])
            height_arr[moves[i]-1] -= 1
            if len(stack_bag) >= 2 and stack_bag[-1] == stack_bag[-2]:
                
                answer += 1
                del stack_bag[-1]
                del stack_bag[-1]
                
    
    return answer*2

아래 링크를 통해 문제를 풀 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/64061

아래는 나의 알고리즘 강의이다~~~><

https://www.youtube.com/channel/UCYYao-BSPaetw7N2GFFJ-Yw?view_as=subscriber

이건 그냥 조건문으로 푼거같긴 한데, 그래도 구글링 안하고 풀긴 풀었다. 오예!

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    #A
    #[3][2][-6][4][0]
    
    if len(A) == 1:
        return A[0]
    
    front_sum = [0]*len(A)
    back_sum = [0]*len(A)
    current_sum = 0
    
    for i in range(len(A)):
        if A[i] + current_sum > 0:
            front_sum[i] = A[i] + current_sum
            current_sum = A[i] + current_sum
        else:
            front_sum[i] = A[i] + current_sum
            current_sum = 0
    
    current_sum = 0
    
    for i in range(len(A)-1,-1,-1):
        if A[i] + current_sum > 0:
            back_sum[i] = A[i] + current_sum
            current_sum = A[i] + current_sum
        else:
            back_sum[i] = A[i] + current_sum
            current_sum = 0
    
    max_sum = max(A)
    
    for i in range(len(A)-1):
        if front_sum[i] + back_sum[i+1] > max_sum:
            max_sum = front_sum[i] + back_sum[i+1]
            
    return max_sum
        
    
    pass

차분하게 이해하려고 노력하니 풀린다!!

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    
    #A
    #23171 21011 21123 21366 21013 21367
    
    #A = [21011,23423,24333,14235,40293,23102]
    
    if len(A) < 2:
        return 0
        
    
    max_sorted_arr = [0]*len(A)
    min_sorted_arr = [0]*len(A)
    
    min_value = A[0]
    max_value = A[-1]
    
    for i in range(len(A)-1):
        if min_value > A[i]:
            min_value = A[i]
        min_sorted_arr[i] = min_value
        
    for i in range(len(A)-1,0,-1):
        if max_value < A[i]:
            max_value = A[i]
        max_sorted_arr[i] = max_value
        
    
    max_profit = 0
    
    for i in range(len(A)-1):
        if max_profit < max_sorted_arr[i+1] - min_sorted_arr[i]:
            max_profit = max_sorted_arr[i+1] - min_sorted_arr[i]
            
    return max_profit
        
        
            
    
        
    pass


def df(x):
    return x[1]

생각이 잘 안나서,

구글링 했다.

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    l_max_slice_sum = [0]*len(A)
    r_max_slice_sum = [0]*len(A)
    
    for i in range(1,len(A)-2):
        l_max_slice_sum[i] = max(l_max_slice_sum[i-1]+A[i],0)
    
    for i in range(len(A)-2,1,-1):
        r_max_slice_sum[i] = max(r_max_slice_sum[i+1]+A[i],0)
            
    max_slice_sum = l_max_slice_sum[0] + r_max_slice_sum[2]
    
    for i in range(1,len(A)-1):
        max_slice_sum = max(max_slice_sum,l_max_slice_sum[i-1]+r_max_slice_sum[i+1])
    
    return max_slice_sum
    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
    
    
    #A
    #[0][1][2][3][4][5][6][7]
    # 3  2  6 -1  4  5 -1  2
    
    #A = [6, 1, 5, 6, 4, 2, 9, 4]
    
    front_sum = [0]*len(A)
    back_sum = [0]*len(A)
     
    for i in range(1,len(A)-2):
        if front_sum[i-1]+A[i] > 0:
            front_sum[i] = front_sum[i-1]+A[i]
            
            
            
        
    for i in range(len(A)-2,1,-1):
        if back_sum[i+1]+A[i] > 0:
            back_sum[i] = back_sum[i+1]+A[i]
            
    
    max_sum = 0
    
    for i in range(0,len(A)-2):
        if front_sum[i] + back_sum[i+2] > max_sum:
            max_sum = front_sum[i] + back_sum[i+2]
    
    
    return max_sum
    
    pass

첫번째 코드는 아래의 사이트 참고했다.

https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/