데이터 엔지니어링

1. 문제 소개

• 백트래킹 알고리즘 유형 문제에 해당한다.

https://www.acmicpc.net/problem/15649

2. 코드

STACK = []
VISIT = []
N,M=0,0

def input_test_case():
	input_str= input().split(" ")
	N,M = int(input_str[0]),int(input_str[1])

	return N,M
# N 4,2  / 1,2,3,4 
def combinations(NUM,CNT):
	global VISIT,STACK,N,M
	if CNT==M:
		parsed_stack = map(lambda x: str(x),STACK)
		print(" ".join(parsed_stack))
		
		return 0

	for i in range(1,N+1):
		if NUM == i or VISIT[(i-1)]:
			continue

		STACK.append(i)
		VISIT[i-1]=True
		combinations(i,CNT+1)
		STACK.pop()
		VISIT[(i-1)]=False

def solution():
	global VISIT,STACK,N,M 
	N,M=input_test_case()
	
	VISIT = [False]* N
	combinations(0, 0)
	#print(f'N :{N} \t M : {M}')
	
def main():
	solution()
	

main()

3. 코멘트

• 백트래킹 쉽게 요약하면 탐색과정에 더 이상의 해가 없는 경우를 IF 조건으로 만들어 다음 탐색으로 넘어가는 알고리즘이다.
• combinations()에서 DFS 로 탐색을하고, 백트래킹 탈출 조건을 수열의 길이가 M 일때로 잡고, 정답을 출력하도록 했다.

1. 문제 소개

• 수학, 브루트 포스 알고리즘 유형 문제에 해당한다.

https://www.acmicpc.net/problem/1057

2. 코드

def set_test_case():
    input_str= input()
    parse_str = input_str.split(" ")
    N, A, B  = int(parse_str[0]),int(parse_str[1]),int(parse_str[2])
    return N,A,B    
    
def divide(num):
    if num == 1:
        return num
    elif num % 2 != 0:
        return num//2 + 1
    else:
        return num//2

def solution():
    N,A,B = set_test_case()
    round_count = 0
    while(True):
        round_count +=1 
        A = divide(A)
        B = divide(B)
        if A == B :
            break
    print(round_count)

def main():
    solution()
    
if __name__ == '__main__':
    main()

3. 코멘트

• 사실.. 실행 예제를 손으로 그려보며, 직감적으로 규칙을 찾았기 때문에 수학적 접근으로 풀진 못했다.
• 문제 설명에 따라서, 토너먼트 라운드가 올라갈 때 새로운 팀 번호가 부여되는데, 팀 번호가 부여되는 규칙이 있고, A와 B 팀 번호가 같아 두 팀이 붙을 때 라운드를 출력하면 된다고 생각했다.
• 처음에는 히든 케이스 때문에 통과하지 못했었는데, 함께 스터디한 유진님이 나와 비슷한 접근 방식으로 해결했고, 도움을 받아 통과했다.
• 새해 첫 스터디였다. ㅎㅎ

1. 문제소개

• 브루트포스, 백트래킹 유형 문제에 해당한다.

https://www.acmicpc.net/problem/14889

2. 코드

import itertools
import sys
input = sys.stdin.readline

# variables for backtracking
VISIT = []
M = []
N = 0 
MIN_SCORE = 100


def set_test_case():
    M = []
    N = int(input())
    for i in range(0,N):
        line  = input().split(' ')
        x = list(map(lambda x: int(x),line))
        M += [x]
        
    return M,N


# return Score difference of Two Team
def comparison_team(A,B,M):
    A_score=  0 
    B_score = 0 
    for i in A:
        DIFF = set(A)- set ([i])
        for j in DIFF:    
            A_score += M[i][j]
    for i in B:
        DIFF = set(B)- set ([i])
        for j in DIFF:   
            B_score += M[i][j]
    return abs(A_score - B_score)



def dfs(depth,member_idx):
    global VISIT,M,N,MIN_SCORE

    # return condition
    if depth == (N//2):
        A = []
        B = []
        for i, v in enumerate(VISIT):
            if v :
                A +=[i]
            else:
                B +=[i]
        score = comparison_team(A,B,M)
        if MIN_SCORE > score:
            MIN_SCORE = score
        return 0

    for i in range(member_idx+1,N):
        VISIT[i] = True
        dfs(depth+1,i)
        VISIT[i]=False
    
    return 0 
            
# backtracking method
def solution2():
    global VISIT,M,N,MIN_SCORE
    M,N = set_test_case()
    VISIT =[False]* N
    MIN_SCORE = 100 
    dfs(0,-1)
    print(MIN_SCORE)


# simple method
def solution():
    # M = score map , N = Soccer member count
    M,N = set_test_case()
    member = [x for x in range(0,N)]

    combi_member = list(itertools.combinations(member,N//2))
    score = 100
    for case in combi_member:
        # two team
        A=[]
        B=[]
        team_bit_map = [False] * N
        
        # Divid team 
        for i in case:
            team_bit_map[i]=True
            A += [i]
        
        for i,v in enumerate(team_bit_map):
            if v == False:
                B += [i]
    
        # score calculate
        local_score = comparison_team(A,B,M)

        if score > local_score :
            score = local_score
    # answer 
    print(score)

def main():
    solution2()
    
if __name__ == '__main__':
    main()

3. 코멘트 

• 총 2가지 방식의 솔루션을 사용했다.
• 첫 번째 방법은 팀 조합(combination)을 library 를 이용하여 구한 뒤, 점수 계산을 했다.
• 함께 스터디한 찬의, 용범님이 백트래킹 방식으로 문제를 해결한 후 리뷰해줘서 같은 방식으로 구현해봤다.
• 두 번째 방법은 팀 조합(combination)을 DFS와 유사한 백트래킹을 이용하여 구한뒤, 점수 계산을 했다.
• 깊이 우선탐색을 경로 탐색 문제를 해결할 때만 떠올렸는데, 조합을 구할때 사용할 수 있다는 것을 또 배웠다. 

1. 쿠버네티스란?

• 오픈 소스 플랫폼
• 오케스트레이션 시스템
• 컨테이너화된 워크로드와 서비스를 관리

는 공식 홈페이지에 소개 내용이지만, 내가 이해한 내용은 이렇다.

• 런타임 의존성과 함께 애플리케이션을 패키징하는 컨테이너를 많이 쓰기 시작한다. -> 컨테이너 런타임을 지원하면 어디에서 실행하던 동일한 동작을 보장하니까
• 하지만 컨테이너는 변경이 불가하다. 즉 애플리케이션의 업데이트가 발생하면 새로 이미지를 빌드 해야 한다.
• 쿠버네티스는 이러한 경우 서비스 중단 없이 업데이트를 가능하게 해주고, 이 밖에 운영 측면의 스케일링, 리소스 관리 등을 해주는 녀석이다.

2. 왜 쿠버네티스를 사용하지?

• high Availability = no downtime
• Scalability
• High Performance
• Disaster recovery

위 장점때문에 사람들이 많이 사용하는 것 같은데 구성이 멀티 클러스터로 되어있기 때문이라고 생각한다면 저 장점을 더 이해하기 쉬울 것 같다.

3. 쿠버네티스 아키텍쳐

• 일반적인 쿠버네티스 배포 → 쿠버네티스 클러스터 생성
• 쿠버네티스 클러스터
  • 모든 클러스터는 최소 한 개의 워커 노드, 1개의 마스터 노드를 가짐
  • 워커 노드
    • 동작중인 파드를 유지시키고, 쿠버네티스 런타임 환경을 제공하며 모든 노드 상에서 동작
  • 컨트롤 플레인 = 마스터 노드
    • 워커노드와 클러스터 내 파드를 관리한다
    • 컨트롤 플레인이 여러 컴퓨터에 걸쳐 실행되고, 클러스터는 여러 노드를 실행하므로 내결함성과 고가용성이 제공됨

컨트롤 플레인

• 주요 컴포넌트
  • kube-apiserver
    • 쿠버네티스 컨트롤 플레인의 프론트 엔드
    • UI, API, CLI 를 제공
  • etcd
    • 모든 클러스터 데이터를 담는 쿠버네티스 뒷단의 저장소
    • 키-벨류 저장소
    • kubernetes backking stroe
  • kube-scheduler
    • 노드가 배정되지 않은 새로 생성된 파드를 감지
    • 실행할 노드를 선택하는 컨트롤 플레인 컴포넌트
    • ensure pods placement
    • 서버의 리소스또한 감지한다. 몇번 노드에서 메모리 30% 쓰고 뭐 이런 정보들
  • kube-controller-manager ( cm )
    • 컨트롤러 프로세스를 실행하는 컨트롤 플레인 컴포넌트
    • 4가지 구성요소
      • 노드 컨트롤러: 노드가 다운되었을때 통지와 대응에 관한 책임
      • 레플리케이션 컨트롤러 : 시스템의 모든 레플리케이션 컨트롤러 오브젝트에 대해 알맞은 수의 파드들을 유지시켜주는 책임
      • 엔드포인트 컨트롤러 : 엔드포인트 오브젝트를 채움 ( 서비스와 파드 연결 )
      • 서비스 어카운트 & 토큰 컨트롤러 : 새로운 네임스페이스에 대한 기본 계정과 api 접근 토큰을 생성
      • keeps track of whats happening in the cluster
  • cloud-contgroller-manager (ccm)
    • 클라우드 별 컨트롤 로직을 포함하는 쿠버네티스 컨트롤 플레인 컴포넌트
    • 3가지 구성요소
      • 노드 컨트롤러 : 노드가 응답을 멈춘 후 클라우드 상에서 삭제되었는지 판별하기 위해 클라우드 제공 사업자에게 확인
      • 라우트 컨트롤러 : 기본 클라우드 인프라에 경로를 구성하는 것
      • 서비스 컨트롤러 : 클라우드 제공 사업자 로드밸런서를 생성, 업데이트, 그리고 삭제 하는 것

워커 노드

• 주요 컴포넌트
  • kubelet
    • 클러스터 각 노드에서 실행되는 에이전트
    • 파드에서 컨테이너가 동작하도록 관리
  • kube-proxy
    • 클러스터의 각 노드에서 실행되는 네트워크 프록시
    • 노드의 네트워크 규칙을 유지 관리
  • 컨테이너 런타임
    • 컨테이너 실행을 담당하는 소프트 웨어
    • 컨테이너 런타임 인터페이스를 구현한 모든 소프트웨어 지원

1. 문제 소개

• 입력 N( 계단의 높이 ) 까지 올라 갈 수 있는 경우의 수를 출력하는 문제다.
• 계단은 1, 2칸씩만 올라갈 수 있다.
• leetcode 난이도 easy 수준의 문제다.

2. 코드

class Solution:
    def climbStairs(self, n: int) -> int:
        n1 = 1
        n2 = 2
        br = 3 

        if n < 3 :
            return n
        else:
            while(br <= n ):
                n3 = n1 + n2
                n1 = n2
                n2 = n3

                br +=1

            return n3

3. 코멘트

• 계단 N 번째 높이까지 올라갈 수 있는 경우의 수는 이전 높이의 경우의 수를 포함하고 있다. 
• 계단 5개까지 손으로 경우의 수를 따져보니 규칙이 있었다.

1. 문제 소개

• 주어진 배열에서 입력값이 삽입될 적합한 위치를 출력하면 된다.
• leetcode 난이도 easy 수준의 문제다.
• 이분 탐색을 이용하면 O(logN) 으로 해결할 수 있다.

2. 코드

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0 
        end = len(nums)-1
        mid = 0  
        while(start <= end ):
            mid = ( start + end ) //2 
            if nums[mid]==target:
                return mid
            elif nums[mid] <= target:  # search right partitiion
                start = mid+1
            else:               # search left partition
                end = mid-1

        if nums[mid] < target:
            return mid+1
        else:
            return mid

3. 코멘트

• 입력 케이스가 배열에 존재하지 않는 경우에는 가장 근접한 위치를 찾게 되는데, 정답을 출력할 때는 적합한 위치가 되도록 조건문을 이용해 보정했다.
• 개인 일정으로 알고리즘 스터디에 계속 불참 하고 있는데, 다음 주에는 꼭 참여해야겠다....

1. 문제 소개

• 주어진 배열에서 최대 부분합을 구하는 문제다.
• leetcode 난이도 easy 수준의 문제다.
• 카데인 알고리즘을 이용하면 O(N)으로 해결할 수 있다.

2. 코드

class Solution:
    # Brute Force - 
    def get_maximum_sum(self,arr:List[int]):
        start = 0 
        end = len(arr)
        maximum_sum=arr[start]
        while(start<end):
            mid=start+1
            pre_sum=sum(arr[start:mid])
            while(mid<end):
                mid+=1
                if pre_sum < sum(arr[start:mid]):
                    pre_sum = 	sum(arr[start:mid])	
            if maximum_sum < pre_sum:
                maximum_sum=pre_sum
            start+=1

        return maximum_sum
    
    def kadane_algorithm(self,arr:List[int]):
        start = 0
        end = len(arr)
        maximum_sub_array = arr[start]
        start=0
        current_sum = 0
        while(start < end):
            current_sum = max(arr[start],current_sum+arr[start])
            if current_sum > maximum_sub_array:
                maximum_sub_array = current_sum
            start+=1

        return maximum_sub_array


    def maxSubArray(self, nums: List[int]) -> int:
        
        return self.kadane_algorithm(nums)

3. 코멘트

• 카데인 알고리즘은 각 최대 부분합을 구할 때 이전 최대 부분합을 이용해서 구하는 것이 핵심이다.
  • 흐름을 텍스트로 설명하자면  
  •  subArray_1 = new element
  •  subArray_2 = subArray_1 + new element
  •  subArray_3 = subArray_2 + new element
  • .. 쭉 배열의 끝까지..
• 각각의 subArray (최대부분합)을 구할 때는 (이전 최대부분합+현재인덱스)과 현재 인덱스를 비교해서 큰 값을 구한다.  

1. 문제 소개

• 그리디 문제에 해당한다.
  
  

https://www.acmicpc.net/problem/1449

2. 코드

def set_test_case():
    N,L = input().split(" ")
    N,L = int(N),int(L)
    leak_pos = []
    leak_pos_org = input().split(" ")
    for v in leak_pos_org:
        leak_pos += [int(v)]

    return N,L,sorted(leak_pos)
         
def solution(N,L,leak_pos):
    cnt = 1 
    l = L
    
    start = 0 
    end = start+1

    while(end < N):
        if (leak_pos[end]-leak_pos[start]) >= L :
            cnt+=1
            start = end 
            end = start +1
        else:
            end+=1
        
    print(cnt)  

    

def main():
    N,L,leak_pos = set_test_case()
    solution(N,L,leak_pos)


if __name__=='__main__':
    main()

3.코멘트 

• 자연수 범위에는 0이 들어가지 않는데, 0의 입력케이스 까지 생각했다가 코드를 다시 수정했다..

1. 문제 소개

• 배열, 해시 테이블을 이용해야 하는 문제에 속한다.
• leetcode 에서도 난이도 easy 수준의 문제다.
• 최근 블라인드에 이 문제에 대한 이야기가 인기글로 올라와서, 풀어봤다. 

2. 코드

#Runtime: 60 ms, faster than 83.47% of Python3 online submissions for Two Sum.
#Memory Usage: 15.3 MB, less than 42.38% of Python3 online submissions for Two Sum.


class Solution:


    # Brute Force - 가장 단순한 접근 -> time complexity : (n2), space complexity : o(1)
    def twoSum(self, nums,target):

        target_indices = []

        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    target_indices+=[i,j]
                    return target_indices

        return target_indices


    # Two - pass Hash Table -> time complexity : (n), space complexity : o(n)
    def twoSum(self, nums,target):
        hash_map = {}
        target_indices = []
        # 자료구조를 해시 맵으로 생성
        for idx,va in enumerate(nums):
            hash_map[va]=idx
        
        # look up 
        for idx,va in enumerate(nums):
            minus_value = target - va
            if minus_value in hash_map and hash_map[minus_value] != idx:
                target_indices+=[idx,hash_map[minus_value]]        
                break
        
        return target_indices


    # One pass hash Table -> time complexity : (n), space complexity : o(n) 
    def twoSum(self, nums,target):
        hash_map={}

        for idx,va in enumerate(nums):
            minus_value = target-va
            if minus_value in hash_map:
                return [idx,hash_map[minus_value]]
            
            hash_map[va]=idx

    def test(self):
        nums = [2,1,94,3,-2]
        target = 92
        result = self.twoSum(nums,target)
        print(result)



if __name__ == '__main__':
    s = Solution()
    s.test()

3.코멘트

• 난 첫 번째 Brute Force 라고 부르는 방식으로 문제를 풀었다.  (심플한 방법을 제일 좋아하기도 하고, 저 방법이 가장 먼저 떠올랐다. )
• leetcode는 문제 제출에 대한 피드백이 비교적 잘 되있다. (시각화나, 해설, discussion도 있고..)
• 첫 번째 방식보다, 해시 기반의 자료구조를 이용했을때 시간복잡도가 매우 낮았다.
• 해시 맵을 만드는 방법도 생각을 안 한건 아니었지만, 해시 맵을 만든다고 하더라도, nums 배열의 full scan 비용  * 해시 맵 안에서 key 를 scan 비용을 더 하면 O(N2) 이 될거라고 생각했는데 아니었다. (해시 맵안에서는 키를 순회하는게 아니라 맵에 키가 있는지만 보면 되니까.. -_-; ) 
• Hash를 이용하면 Lookup 시간을 O(n) 에서 O(1)로 줄일 수 있다. 

1. 문제 소개

• 구현 문제에 해당한다.
• 외부 알고리즘 기법을 적용해야 하는 수준의 문제는 아니지만, 인덱스 범위를 초과하는 반례 케이스들을 생각해야 한다.

https://www.acmicpc.net/problem/124

2. 코드

# -*- encoding: utf-8 -*-
#import sys
#input = sys.stdin.readline

def set_test_case():
    commands = []
    switch_size= int(input())
    switch = input().split(' ')   
    switch = [int(x) for x in switch] 

    command_num = int(input())
    for i in range(0,command_num):
        command = input().split(' ')
        #command = map(lambda x: int(x),command)
        commands+=[[int(x) for x in command]]

    return switch,commands


def switch_process(switch,gender,switch_pos):
    switch=switch
    switch_interval = switch_pos
    if switch_pos == 0 :
        return switch

    # 남자의 경우 입력처리
    if gender == 1:
        while(switch_pos > 0 and switch_pos <= len(switch)):

            switch[switch_pos-1] = switch[switch_pos-1] ^ 1  # XOR 연산, index -1 처리
            switch_pos+=switch_interval   # 배수 처리 

    # 여자의 경우 입력처리
    elif gender == 2:
        symmetry = True     #대칭 여부의 flag 변수
        l =switch_pos -2  # 대칭점 기준 왼쪽 포인터
        r = switch_pos  # 대칭점 기준 오른쪽 포인터
        
        switch[switch_pos-1] = switch[switch_pos-1] ^ 1  # 대칭 여부와 상관없이, 대칭점의 스위치는 전환

        while(symmetry and l >= 0 and r < len(switch)): # 대칭되는 스위치를 찾는 범위가 리스트의 범위를 벗어나지 않는 조건

            if switch[l] == switch[r]:
                switch[l] = switch[l] ^ 1
                switch[r] = switch[r] ^ 1
                l -= 1
                r += 1    
            else:
                # 대칭되지 않는 조건
                symmetry=False

    # 입력 케이스 예외처리 부분
    else:
        #exception
        pass
    return switch

def solution(switch,commnads):
    for command in commnads:
        gender,pos = command[0],command[1]
        switch = switch_process(switch,gender,pos)
    
    # 최대 출력 스위치 조건을 만족하기 위한 처리
    num_by_line = 20
    for i in range(0,len(switch),num_by_line):
        print(*switch[i:i+num_by_line],sep=' ')


def main():
    switch,commands = set_test_case()
    solution(switch,commands)

if __name__ == '__main__':
    main()

3. 코멘트

• 구현은 어렵지 않았지만, 반례 케이스를 너무 가볍게 생각하여 2차례 실패가 있었다.
• 처리 시간과 메모리 공간, 그리고 반례 케이스에 대한 고민을 깊게 하는 습관이 필요하다.