데이터 엔지니어링

1.문제 소개

• 그리디/구현 문제 유형이다.
• https://www.acmicpc.net/problem/1051

2.코드

def set_test_case():
    input_str = input().split(" ")
    n,m = int(input_str[0]),int(input_str[1])
    rectangle = []
    for i in range(n):
        row = input()
        rectangle.append(row)

    return n,m,rectangle

def get_max_area(rectangle,x,y):
    distance= 0
    max_area = 0
    while (x+distance) < len(rectangle) and (y+distance) < len(rectangle[0]):
        if (rectangle[x][y] == rectangle[x+distance][y] == rectangle[x][y+distance] == rectangle[x+distance][y+distance]):
            max_area = distance
        distance +=1
    return max_area+1

def solution():
    n,m,rectangle = set_test_case()
    answer = 0
    for i in range(n):
        for j in range(m):
            max_area = get_max_area(rectangle,i,j)
            if max_area > answer:
                answer = max_area

    print(answer*answer)



if __name__ == "__main__":
    solution()

3.코멘트

• get_max_area(사각형의 p1 / 왼쪽 상단 꼭지점 좌표를 기준으로 p2, p3, p4 가 같은 최대 거리를 반환하는 함수)를 모든 지점을 순회하면서 최대 길이를 구한다.
• 퇴근하고 짧은 시간에 풀만한 제일 만만한게 그리디/구현 문제.. 오늘은 일이 잘 안풀리는 날이였다.

1. 문제 소개

• 구현 / 그리디 알고리즘 / 문자열 / 브루트포스 알고리즘 문제에 속한다.
• https://www.acmicpc.net/problem/1969

2. 코드

# 2개의 DNA 뉴클레오티드로부터 해밍디스턴스의 길이를 반환하는 함수
def get_hamming_distance(dna1,dna2,m):
    hamming_distance = 0

    for i in range(m):
        if dna1[i] != dna2[i]:
            hamming_distance += 1

    return hamming_distance

def get_test_case():
    input_str= input().split(" ")
    h,m = int(input_str[0]),int(input_str[1])
    dna_list = ['' for x in range(h)]
    for i in range(h):
        dna_list[i] = input()
    return h, m, dna_list

def solution():
    H,M,DNA_list = get_test_case()
    min_dna = ''

    for i in range(M):
        alphabet_count = [0 for x in range(26)] 
        for dna in DNA_list:
            ch = ord(dna[i])
            alphabet_count[ch % 65] += 1
        max_count = max(alphabet_count)
        org_ch = alphabet_count.index(max_count) + 65
        dna_char = chr(org_ch)
        min_dna += dna_char
    min_hamming_distance_sum = 0

    # 해밍디스턴스의 합을 구하기
    for dna in DNA_list:
        min_hamming_distance_sum+= get_hamming_distance(dna,min_dna,M)
    print(f"{min_dna}\n{min_hamming_distance_sum}")

if __name__ == '__main__':
    solution()

3. 코멘트

• 문제해결의 전략은 아래와 같다.
  • 해밍 디스턴스의 최소가 되는 DNA 문자열 = 입력 문자열 { DNA s(1)..s(n) } 에서 자리 별 최대 중복 문자로 조합된 문자열  
  • 최대 중복수가 같거나 없다면 사전 순 가장 처음으로 오는 영어 문자 배치
  • 문자열 카운팅은 배열과 아스키코드를 이용해서 구하기
• 처음에 예제 입력에서 해답인 DNA s 를 구하는 것으로 생각하고 구현했다가 시간을 버렸다. 
• 역시 문제는 꼼꼼히 읽고 해석해야 한다.. 그리고 오늘 같이 날씨가 너무 좋은 날에 스터디에 참여한 스터디원 들이 고맙다.

1. 문제 소개

• 수학 문제다.
• https://www.acmicpc.net/problem/2292

2. 코드

def solution():
    N = int(input())
    cnt = 1
    iter = 1
    while iter < N:
        iter = (cnt * 6) + iter
        cnt += 1

    print(cnt)




if __name__ == '__main__':
    solution()

3. 코멘트

• 육각형 벌집은 1개에서 7 번 -> 19번 -> 37번 .. 이렇게 증가하는데 6의 배수로 증가한다.
• 이 규칙을 알면 몇 번째 벌집 안에 있고, 총 몇번 이동해야 하는지 구할 수 있다.

1. 문제 소개

• 실버 수준 구현 문제다.
• https://www.acmicpc.net/problem/2563

2. 코드

def set_test_case():
    T = int(input())
    rectangles = []
    for i in range(T):
        in_temp = input().split(" ")
        r = [int(in_temp[0]),int(in_temp[1])]
        rectangles.append(r)

    return rectangles

def solution():
    size = 10
    max_size = 100
    area = 0

    matrix = [[0 for i in range(max_size)] for j in range(max_size)]
    rectangles= set_test_case()

    # 색종이 영역 마킹
    for rectangle in rectangles:
        for j in range(rectangle[0],rectangle[0]+size):
            for k in range(rectangle[1],rectangle[1]+size):
                matrix[j][k] = 1

    # 색종이 영역 완전 탐색 = 배열 요소 1은 1X1 의 넓이로 본다.
    for i in range(max_size):
        for j in range(max_size):
            if matrix[i][j] == 1:
                area+=1

    print(area)

if __name__ == '__main__':
    solution()

3. 코멘트

• 처음에는 색종이의 꼭지점 좌표를 이용해, 겹치는 영역 또는 빈 영역이 발생할 수 있는 경우의 룰(특징)을 정의해서 사각형을 계산해 답을 도출 하는 방법으로 고민했다. ( CCW, 컨벡스헐 알고리즘을 적용해서 풀 수 있다는 피드백) 
• 내가 생각한 방식은 꽤 복잡하고, 주어진 조건(도화지 크기, 색종이 수 제한) 과 1초라는 제한 시간은 완전 탐색 방식으로 푸는게 간단하다는 스터디원의 풀이를 보고 나도 다시 풀었다. 
• 방법은 간단하게 도화지 크기 (100 * 100)의 2차원 배열을 만들고, 색종이의 영역 만큼 마킹을 한 후 마킹된 원소를 넓이로 보고 답을 출력한다.
• 오랜만에 알고리즘 스터디를 해서 너무 재밌었다. 생업 때문에 자주는 아니더라도 꾸준히 모였으면 좋겠다.
• 이 글을 보고 알고리즘 스터디에 관심이 있는 분들은 언제든지 연락을... :) 

1. 문제 소개

• 자료 구조 큐를 이용해야 하는 문제다.

2. 코드

from collections import deque

def set_test_case():
    in_line = input().split(" ")
    n,m = int(in_line[0]),int(in_line[1])

    in_line = input().split(" ")
    pop_list = [int(x) for x in in_line]

    return n,m,pop_list

def pop_simulate(q,v):
    dir= 1 if q.index(v) > len(q)//2 else - 1
    turn=0

    while(True):
        if q[0] == v:
            q.popleft()
            break
            
        else:
            q.rotate(dir)
            turn += 1
    return turn

def solution():
    n,m,pop_list = set_test_case()
    turns = []
    q = deque([i for i in range(1,n+1)])

    #q.rotate(1) # to right
    
    for v in pop_list:
        result = pop_simulate(q,v)
        turns +=[result]
    print(sum(turns))


if __name__=="__main__":
    solution()

3. 코멘트

• pop 할 원소의 위치가 큐 길이의 중앙 값을 기준으로 비교 후에 왼쪽으로 이동시킬 지 , 오른쪽으로 이동시킬 지 방향을 구한다.
• 2초 제한과 50의 테스트케이스 정도는 시뮬레이션 방식으로 통과가 가능할 것 같아, 간단한 시뮬레이션을 구현했다.
• 그 동안 프로젝트 때문에 알고리즘 스터디를 오랜만에 참여했다. 앞으로는 더 열심히 하자. 

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번의 입력 예제는 아래 처럼 교차하지 않도록 짝을 이룬다.

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