데이터 엔지니어링

1. 문제 소개

• prefix sum 과 투포인터 문제다.

2. 코드

import sys
input = sys.stdin.readline


def solution():
    input_str = input().split(" ")
    n, s = int(input_str[0]), int(input_str[1])
    input_str = input().split(" ")
    arr = [int(x) for x in input_str]
    prefix_sum = [0] * (n+1)

    # set two pointer
    sp = 0
    ep = 1
    min_cnt = n

    # set prefix_sum
    while(ep <= n):
        prefix_sum[ep] = prefix_sum[ep-1] + arr[ep-1]
        ep += 1

    ep = 0

    if prefix_sum[-1] < s:
        min_cnt = 0
    else:
        while(sp <= ep and ep <= n):
            if (prefix_sum[ep] - prefix_sum[sp]) >= s:
                if min_cnt > (ep-sp):
                    min_cnt = (ep-sp)
                sp += 1
            else:
                ep += 1

    print(min_cnt)


if __name__ == '__main__':
    solution()

3.코멘트

• 문제에 부분합의 충족조건을 만족하지 않는 경우 0 을 출력하는 조건을 놓쳐 시간을 꽤 썼다.
• 문제를 대충 읽지 말자..

1.문제 소개

• DP 문제에 해당한다.

2.코드

import math
# 이친수 여부
def is_ichin(source):
    result = True
    offset = 1
    while(offset<len(source)):
        if source[offset] == '1' and source[offset-1] == '1':
            result=False
            break
        offset +=1
        
    return result

# 문자열 탐색 방식
def solution():
    N = int(input())
    S = int(math.pow(2,N))
    cnt = 0 
    for num in range(0,S):
        s = bin(num)[2:]
        if len(s) == N and is_ichin(s):
            cnt+=1
        #print(f"num : {num}\t binary : {s} ichin : {is_ichin(s)}")
    
    print(cnt)
          
                  
ichin_array = [0,1,1,2]

def get_ichin(n):
    if n < len(ichin_array):
        return ichin_array[n]
    else:
        ichin = get_ichin(n-1)+get_ichin(n-2)
        ichin_array.append(ichin)
        return ichin
    

    
    
# DP 방식 
def solution():
    N = int(input())
    print(get_ichin(N))
    
solution()

3.코멘트

• 이진수를 만들어 문자열 탐색으로 이친수를 여부를 구하는 함수를 만들어 규칙을 찾아봤다.
• 이친수는 피보나치 수열과 동일한 규칙을 갖고 있었다.
• 중복 호출을 줄이는 방식으로 DP 를 이용해 정답을 출력했다.

1. 문제 소개

• 이분탐색 문제에 해당한다.

2. 코드

import sys

input = sys.stdin.readline



def set_test_case():
    N = int(input())
    input_str = input().split()
    cards = [int(x) for x in input_str]
    M = int(input())
    input_str = input().split()
    your_cards = [int(x) for x in input_str]
    return cards , your_cards

def binary_search(arr,search_value):
    start = 0 
    end = len(arr)
    
    while(start<end):
        mid = (start + end) // 2
        if arr[mid] == search_value:
            return mid
        elif arr[mid] < search_value:
            start = mid+1
        else:
            end = mid
    
    return -1
    
def solution(): 
    cards,your_cards = set_test_case()
    cache = dict()
    for i in cards:
        if i not in cache:
            cache[i] = 1
        else:
            cache[i] +=1
    sorted_card = sorted(cards)
    answer = []
    for i in your_cards:
        if binary_search(sorted_card,i) > -1:
            answer += [str(cache[i])]
        else:
            answer += [str(0)]
    
    print(" ".join(answer))
    
    
            
    
            
    

solution()

3. 코멘트

• 알고리즘을 정리하면 숫자카드를 자료구조 map 에 저장하고, 상근이의 카드를 이분탐색으로 조회하되, 결과는 map 에서 출력한다.
• 육아로 알고리즘 스터디를 진행할 시간과 여유가 없어 아쉽다. 여유가 곧 생길수 있기를..  

1. 문제 소개

• 스택, 자료구조 문제에 해당한다.

2. 코드

# idea 
# 	- 선끼리 교차하지 않는다 -> 인접하는 대칭 단어가 짝을 이루고, 짝을 이룬 단어들 바깥의 단어들은 같은 거리로 짝을 이룬다.
# 	- 정확히 다른 위치의 글자와 짝을 이룬다 -> 홀수 X

# algorithm 
# 	- stack 에 word character 를 하나씩 push
# 	- 이전 character 가 동일한 단어는 pop() 
# 	- stack 의 크기가 0 인 경우는 good word 로 판단
 
def input_test_case():
    N = int(input())
    words = []
    for i in range(0,N):
        words += [input()]
        
    return words

def check_good_word(word):
    stack = []
    pre_char_idx = -1

    for c in word :
        if pre_char_idx >=0 and stack[pre_char_idx] == c :
            stack.pop()
            pre_char_idx -=1
        else:
            stack.append(c)
            pre_char_idx+=1
        
    return True if len(stack) == 0 else False
    

def solution():
    words = input_test_case()
    count = 0 
    for w in words:
        if check_good_word(w):
            count+=1
            
    print(count)       
    
solution()

3. 코멘트

• 참고로 예제 3번의 입력 예제는 아래 처럼 교차하지 않도록 짝을 이룬다.

• 육아로 한 동안 스터디를 진행하지 못하다가, 오랜만에 했는데 즐겁고 뿌듯했다.
• 오랜 기간 함께 스터디에 참여해주셨던, 찬의님이 취업해서 너무 기쁘다. ( 대기업으로 가셨다 !! )
• 찬의님과 함께 오래 함께한 유진님께서 사고로 중환자실에 입원하셨는데, 다행이 수술은 잘 진행됐다고 했다. 빨리 나으셔서 밝은 모습으로 뵙길 기도한다. 

1. 문제 소개

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

2. 코드

import sys
input = sys.stdin.readline


# Ti = 처리시간
# Si = 마감시각

# Idea) 끝의 마감시각부터 처리시간을 빼가면서, 일 시작시각을 계산한다.

# 1) 마감시각 기준 정렬 
# 2) 일 업무(테스트 케이스)별로, 일 시작 시각 계산.

# 	prev_Si = 이전 업무 시작 시각 기준으로 처리하되 현재 마감 시각보다 크면 값 갱신: 마감시각 - 처리시각 

# 	IF prev_Si > Si:
# 		prev_Si = Si
# 	prev_Si -= Si 

def set_test_case():
    N =  int(input())
    N_CASE=[]
    
    for i in range(0,N):
        case = input().split(" ")
        set_case = (int(case[0]),int(case[1]))
        N_CASE.append(set_case)
    N_CASE.sort(key = lambda x : x[1],reverse=True)
    return N_CASE

def solution():
    work_array = set_test_case()
    prev_Si = work_array[0][1]
    for Si,Ti in work_array:
        if prev_Si > Ti :
            prev_Si = Ti
        prev_Si = prev_Si - Si

    if prev_Si < 0:
        prev_Si = -1

    print(prev_Si)
    
solution()

3. 코멘트

• 끝에서 부터 업무 시작 시각을 계산하면, 답을 더 편하게 구할수 있다는 아이디어를 찬의님(스터디원) 리뷰를 보고 다시 풀었다.
• 오늘도 하나 배웠다.

1. 문제 소개

• 수학 유형 문제에 해당한다.

2. 코드 

import sys
input = sys.stdin.readline

# 1) 빨대 길이가 저장된 배열을 정렬
# 2) 가장 긴 쪽 부터 3개의 빨대로 삼각형 성립 조건 을 검사
# 3) IF 성립조건  = True  -> 삼각형 변의 합 계산 후 출력
# 4) IF 성립조건 = False -> 다음 크기의 빨대로 이동


def set_test_case():
    N = int(input())
    n_side = []
    for i in range(0,N):
        n_side += [int(input())]

    return n_side


def isValidTriangle(triangle):
    t_side = sorted(triangle,reverse=True)
    # 가장 긴 변 = C
    # 삼각형 성립 조건  C < A + B
    if t_side[0] < (t_side[1] + t_side[2]):
        return True
    else:
        return False
    
def solution():
    n_side = set_test_case()
    n_side = sorted(n_side)
    maximum_sum_triangle = -1
    for i in range(len(n_side)-1,1,-1):
        if isValidTriangle(n_side[ (i - 2) : (i + 1 )]):
            maximum_sum_triangle = sum(n_side[ (i - 2) : (i + 1 )])
            break
        
    print(maximum_sum_triangle)

solution()

3. 코멘트

• 파이썬으로 제출 시 런타임에러가 발생한다면,  sys.stdin 패키지의 입력함수를 이용하길 권한다.
• 오랜만에 유진님, 용범님과 재밌게 문제 풀이했다. 

1. 문제 소개

• 수학 유형 문제에 해당한다.

2. 코드

def set_test_case():
    A = []
    B = []
    T = input() 
    for i in range(0,2):
        org = input().split(" ")
        if i == 0 :
            A = [int(x) for x in org]
        else:
            B = [int(x) for x in org]

    return A,B


def solution():
    A,B = set_test_case()
    S = 0 
    A = sorted(A)
    B_I = []  # B 배열의 크기 별 순위 인덱스
    MAP_B = {} # Key : B 인덱스의 값, avlue : B 인덱스의 위치

    for idx,va in enumerate(B):
        MAP_B[va] = idx  # 
        
    for i in sorted(B,reverse=True):
        B_I +=[MAP_B[i]] # B 배열의 각 요소별 크기 순번 저장
    
    for idx,va in enumerate(A):
        S_PART = va * B[B_I[idx]]
        S += S_PART

    print(S)



solution()

3. 코멘트

• 수학을 이용해서 풀지 않았.. 

1. 문제 소개

• 수학 유형 문제에 해당한다.

2. 코드 

def set_test_case():
    T = int(input())
    CASE = []
    for i in range (0,T):
        line = input().split(" ")  # 입력 문자열을 공백구분자로 분리 
        line = [int(x) for x in line]  # 연산을 위해 str -> int 형 변한
        CASE.append(line)  # 케이스들을 새로운 list 에 담음

    return CASE
        
# factorial 을 재귀로 간단히 구현
def factorial(n):
    if n <=1:
        return 1
    return n * factorial(n-1)


def solution():
    case = set_test_case() # 입력 케이스 처리 
    for i in case :
        r,n = i # 강의 서쪽은 r, 동쪽은 n 에 대입
        p = factorial(n-r) * factorial(r)  # 조합의 구한 분모 값 계산
        c = factorial(n)  # 조합의 분자 값 계산
        print(c//p) # 정답 출력 

solution()

3. 코멘트

• 아래 조합 공식을 이용하여 문제를 풀면 쉽다.

• 너무 오랜만에 포스팅을 하는 것 같다. 요즘 회사 업무량이 많고, 주말에 여유가 없어 취미로 시작한 알고리즘 스터디도 좀처럼 참여가 어렵다. 그래도 꾸준히 해야겠지. +_+..

1.문제 소개

• 구현, 시뮬레이션 유형 문제에 해당한다.

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

2. 코드

import sys
input = sys.stdin.readline

def set_test_case():
    command_line = int(input())
    commands=[]
    for i in range(0,command_line):
        commands+=[input()]

    return commands

def move_turtle(location,direction,move):
    # location[0] -> X 축 location[1] -> Y 축
    if direction ==3 or direction ==2:
        move = move * -1
        
    if direction == 0 or direction ==2:
        location[1] = location[1] + move
    elif direction == 1 or direction == 3:
        location[0] = location[0] + move
    else:
        pass

    return location

def move_direction(current, direction):
    # 0 : up , 1 : right , 2 : down , 3: left
    if direction == 'R':
        current = (current+1)%4
    elif direction == 'L':
        current = (current-1)%4
    else:
        pass
    return current

def solution():
    commands = set_test_case()
    
    for command in commands:
        turtle_direction = 0 # default direction -> UP
        turtle_location=[0,0] # default location
        maximum_location=[0,0,0,0] # UP , RIGHT, DOWN, LEFT 
        
        for c in command:

            # set location by command
            if c == 'L' or c=='R':
                turtle_direction = move_direction(turtle_direction,c)
            elif c == 'F':
                turtle_location = move_turtle(turtle_location,turtle_direction,1)
            elif c == 'B':
                turtle_location = move_turtle(turtle_location,turtle_direction,-1)
            
           # save maximum location of turtle  
            if c == 'F' or c == 'B':
                if turtle_location[0] > maximum_location[1]:
                    maximum_location[1]=turtle_location[0]                    
                    
                elif turtle_location[1] > maximum_location[0]:
                    maximum_location[0]=turtle_location[1]
                    
                elif turtle_location[0] < maximum_location[3]:
                    maximum_location[3] = turtle_location[0]
                
                elif turtle_location[1] < maximum_location[2]:
                    maximum_location[2] = turtle_location[1]
            
        # result print
        if (maximum_location[1] == 0 and maximum_location[3] ==0) or (maximum_location[0] == 0 and maximum_location[2] ==0): 
            print(0)
        else:
            print((abs(maximum_location[0])+abs(maximum_location[2])) * (abs(maximum_location[1])+abs(maximum_location[3])))
            

if __name__=='__main__':
    solution()

3. 코멘트

• IF 문이 많아 좋은 코드로 만들진 못했지만, 요약하자면 move_direction,turtle 로 거북이의 방향과 위치를 명령어기반으로 갱신해주고, 동서남북 방면의 최대값을 저장해 정답을 출력했다.
• 최근 폼도 떨어지기도 했고, 매트릭스 좌표 계산이 머릿속으로 빨리 빨리 안되서 속상했다.
• 다른 스터디원의 풀이 방식을 보니, 내 로직이 쓸데없이 더 복잡해보였지만.. 뭐어쩌겠나.. ㅇㅅㅇ.. 공부해야지. 

1. 문제 소개

• 수학 유형 문제에 해당한다.

2. 코드

import sys
input = sys.stdin.readline

def set_test_case():
    F = int(input())    # 다친 손가락 위치
    M = int(input())    # 다친 손가락의 최대 사용 횟수 
    return F,M

def solution():
    F,M = set_test_case()
    result = 0 

    if F==1:
        result = 8*M
    elif F==5:
        result = 8 * M +4
    else:
        if M % 2 == 0 :
            result = 4 * M + (F-1)
        else:
            result = 4 * M + (5-F)
            
    print(result)
            
if __name__=='__main__':
    solution()

3.코멘트 

• 손가락 위치 별 별로 최대사용 횟수 이후 셀 수 있는 숫자를 직접 하나 하나 구해서, 손가락 위치 별 규칙을 구한다.
• 다친 손가락이 1 / 5 / 2 ~ 4 일 때 아래의 규칙을 발견할 수 있고, 코드로 작성했다.

• 처음엔 작성한 알고리즘에 구멍이 있었는데, 금일 함께 스터디했던 유진님의 도움으로 코드를 보정할 수 있었다.
• 역시 공부는 꾸준히 해야 한다...