Henry's Algorithm

다시 취업 준비를 하면서 오랜만에 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/

시간 복잡도: 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
    
    right_map = {}
    left_map = {}
    
    for i in A:
        try:
            right_map[i] += 1
        except:
            right_map[i] = 1
    
    count = 0
    left_leader = 0
    left_length = 0
    right_length = len(A)
    left_leader_count = 0
   
    for i in range(len(A)):
        right_map[A[i]] -= 1
        right_length -= 1
        
        try:
            left_map[A[i]] += 1
        except:
            left_map[A[i]] = 1
            
        left_length += 1
        
        # get left leader
        if left_map[A[i]] > left_leader_count:
            left_leader = A[i]
            left_leader_count = left_map[A[i]]
        
        # get equi leader
        if right_map[left_leader] > right_length//2 and left_leader_count > left_length//2: 
            count += 1
        
    
    return count
        
    
    pass