데이터 엔지니어링

1. 문제 소개

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

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

2.코드

# 1. valid_check 
#   - 폴리오미노 유효성 검사 
#   - x 가 짝수개수인지 체크 
# 2. custom_split
#   - X와 . 을 분리 
# 3. convert
#   - AAAA , BB 우선순위로 폴리오미노 문자 조합

def set_test_case():
    T = input()
    return T

def valid_check(s):
    result = True
    for case in s.split('.'):
        case_len = len(case)
        if case_len %2 != 0:
            result = False
            return result

    return result

def custom_split(input_str):
    split_list = []

    last_dot_point=-1
    cursor = 0 

    while (cursor < len(input_str)):

        # 첫번째 문자가 닷(.) 이 아닌 경우 ,  연속적인 닷(.)이 아닌경우 
        if input_str[cursor] == '.':
            if cursor > 0 and not (input_str[cursor-1] == '.'):
                split_list.append(input_str[last_dot_point+1:cursor])
                last_dot_point = cursor
            else:
                last_dot_point = cursor
            split_list.append('.')
        
        # 마지막 커서 도달 시 잔여 문자 처리 
        if cursor == len(input_str)-1 and cursor != last_dot_point:
            split_list.append(input_str[last_dot_point+1:])
            
        cursor +=1
    return split_list

def convert(split_list):
    result ='' 
    for case in split_list:
        if case[0] =='X':
            cursor = 0 
            while(cursor < len(case)):
                if len(case[cursor:]) >= 4:
                    result +='AAAA'
                    cursor +=4
                else:
                    result +='BB'
                    cursor+=2
        else:
            result+=case
    
    return result

def solution():
    #s = '...'
   # s = '..XXXX..XX.'
#    s= 'XX.XXXXXXXXXX..XXXXXXXX...XXXXXX'
    s = set_test_case()
    split_str = custom_split(s)
    if not valid_check(s):
        result = '-1'
    else:
        result = convert(split_str)
    print(result)

if __name__=='__main__':
    solution()

3. 코멘트

• custom_split() 에서는 입력 문자열의 문자를 하나 하나 순회하면서, 닷(.) 과 X를 분리하고, convert() 에서는 사전 순 ordering을 위해 AAAA, BB 순서로 문자를 치환하는 방식이다.
• 최근에 이직한 새 회사에 적응하느라 스터디를 많이 못하기도 했고..  뇌가 굳은건지.. 간단한 로직이라 생각했는데 구현이 빨리 빨리 안되서 속상하다.
• 스터디 새 멤버도 충원됐고, 앞으로 꾸준히 공부해야겠다. :D 

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. 문제 소개

• 입력 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차례 실패가 있었다.
• 처리 시간과 메모리 공간, 그리고 반례 케이스에 대한 고민을 깊게 하는 습관이 필요하다.