데이터 엔지니어링

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/1009

2.코드

def solution():
    n = int(input().strip())
    for i in range(n):
        a ,b  = map(int,input().split(" "))
        x = a
        number_rules = []
        number_rules += [x%10]
        
        # 1의 자리 숫자의 규칙을 찾기 위한 루프
        for i in range(10):
            x = x * a
            x = x % 10
            number_rules += [x%10]


        # 중복을 제거하고 순서를 보장하기 위한 리스트로 전처리
        distinct_rules = []
        for v in number_rules:
            if v not in distinct_rules:
                distinct_rules.append(v)


        # 결과의 위치를 구하기
        idx = b % len(distinct_rules) -1

        # 0번의 경우 10번 컴퓨터를 의미하므로 정답 출력 보정
        if distinct_rules[idx] == 0:
            answer = 10
        else:
            answer = distinct_rules[idx]
        print(answer)



if __name__ == '__main__':
    solution()

3.코멘트

• 브론즈 문제임에도 단순하게 푼다면 시간 제한에 걸릴 수 있다.
• a**b 의 범위가 10억 대 범위라서, 반복문으로 구현했다가는 시간제한에 걸린다. 
• 컴퓨터 번호 이하의 숫자를 pow 연산 범위 안에서 발생하는 규칙을 구한 다음, 정답 인덱스를 구해서 출력했다.

1.문제 소개

• 구현/문자열 문제유형이다.
• https://www.acmicpc.net/problem/2852

2.코드

# Main Idea
# 1) 입력 테스트 케이스의 데이트 문자열 타입을 처리하기 편한 초 단위로 변환
# 2) 점수를 낸 로그를 반복문으로 돌면서, 점수를 낸 직전 스코어의 승자 팀이 있는 경우 1팀과 2팀의 이긴 시간을 누적 저장
# 3) 마지막에는 승팀의 존재 여부를 확인하고, 이긴 시간을 추가 보정

# 입력 데이터 파싱
def set_test_case():
    n = int(input())
    score_log = []
    for i in range(n):
        input_str= input().split(" ")
        team = int(input_str[0])
        score_time_str = input_str[1].split(":")
        minutes = int(score_time_str[0])
        seconds = int(score_time_str[1])

        total_seconds = minutes * 60 + seconds
        score_log += [[team,total_seconds]]

    return score_log
def get_winner(a_score,b_score):
    return 0 if a_score > b_score else 1

def get_format_answer(seconds):
    minutes = seconds //60
    seconds = seconds % 60
    return f"{minutes:02d}:{seconds:02d}"
def solution():
    score_log  = set_test_case()
    current_score = [0,0] # 1, 2팀의 누적 점수
    last_winner = -1
    answer = [0,0] # 1,2 팀의 정답출력을 위한 리스트

    for idx,t in enumerate(score_log):

        # 이전 스코어가 동점이 아닌경우 계산
        if current_score[0] != current_score[1] :
            last_winner = get_winner(current_score[0], current_score[1])
            answer[last_winner] += t[1]-score_log[idx-1][1]

        # 누적 점수 저장
        if t[0] == 1:
            current_score[0] +=1
        else:
            current_score[1] +=1

    if current_score[0] != current_score[1]:
        last_winner = get_winner(current_score[0], current_score[1])
        answer[last_winner] += 60*48 - score_log[-1][1]

    print(get_format_answer(answer[0]))
    print(get_format_answer(answer[1]))

if __name__=='__main__':
    solution()

1.문제 소개

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

2.코드

# Main Idea :
# 	- 정답을 편하게 구하기 위해 자료구조를 만든다
# 		(lt,height)
# 		* lt = 왼쪽 방향으로 키가 큰 사람 수 
# 		* height = 키 
# 	- lt,height 순서로 정렬 한다.
# 	- 정답 배열을 만든다
# 	- 정답 배열에 lt 조건 대로 height 를 저장한다
# 	- lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 구한다.
# 	- 정답 배열에 원소 추가
# 		- 위치(cursor) 기준으로 오른쪽 배열 복제.
# 		- 정답배열 위치(cursor)에 원소를 추가하고 + 오른 쪽 배열 복제본 복사 

def set_test_case():
    n = int(input())
    input_str = input().split(" ")
    arr = []
    input_str = list(map(int,input_str))
    for i,v in enumerate(input_str):
        arr += [(v,(i+1))]

    return arr

def solution():
    # 테스트 케이스 입력
    arr = set_test_case()

    # 왼쪽 방향 자기보다 키 큰 사람의 수 기준으로 정렬
    sorted_arr = sorted(arr, key=lambda x: x[1], reverse=True)
    # 키 큰 사람의 수가 동일할 경우 키가 큰 사람 기준으로 내림 차순 정렬
    sorted_arr = sorted(sorted_arr, key=lambda x: x[0], reverse=False)
    # 정답 배열 선언
    answer = [0] * len(sorted_arr)


    for item in sorted_arr:
        cursor = 0
        height = item[1]
        cnt = item[0]
        #lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 찾음
        while cursor < len(arr) and answer[cursor] > 0 and cnt > 0 :
            if answer[cursor] > height :
                cnt -=1
            cursor += 1
        # 정답 배열에 원소 추가
        right_part = answer[cursor:-1]
        answer[cursor] = height
        answer[cursor+1:] = right_part

    # 정답 출력
    answer = list(map(str,answer))
    print(" ".join(answer))


if __name__ == '__main__':
    solution()

3.코멘트

• 단순히 입력 케이스 배열에서 규칙을 찾아 정답을 구할 수 있는 방법으로 접근하려면 더 어렵다. 유형대로 그리디하게 풀어야 한다.
• 그 동안 서로 많이 바빠서 4개월만에 알고리즘 스터디원들이 모여 재미있게 진행했다.
• 앞으로는 조금 더 자주 볼 수 있기를 기대한다.

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.성능 비교를 위한 예제코드

import time
import dis

SIZE=10000000
def func_forloop():
    start_time = time.time()
    factor = 1
    bucket = []
    for i in range(SIZE):
        bucket.append(i * factor)
    print(len(bucket))
    end_time = time.time()
    print(f"bucket size = {len(bucket)} \nfunc_forloop execution time : {(end_time - start_time)* 1000}ms")

    
def func_list_comprehension():
    start_time = time.time()
    factor = 1
    bucket =[i * factor for i in range(SIZE)]
    end_time = time.time()
    print(len(bucket))
    print(f"bucket size = {len(bucket)} \nfunc_list_comprehension execution time : {(end_time - start_time)* 1000}ms")
    

func_forloop()
func_list_comprehension()

dis.dis(func_forloop)
print('--------------------------')
dis.dis(func_list_comprehension)

2.요약

• dis 를 통해 변환된 바이트 코드를 볼 수 있다.
• for loop 는 리스트에 요소를 추가하는 작업을 append method 를 쓰고, list comprehension 은 LIST_APPEND 라는 바이트 코드를 쓴다.
• 인터프리터 모드에서 동작하는 프로그램에서 ListComprehension 에서 바이트를 특별 처리하므로 성능이 빠르다. 구글링해보면 타 블로그에서 컴파일 할 경우 for loop와 성능이 비슷해진다는 실험을 봤다. 따라서 list comprehension 만을 고집할 필요도 없다.

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의 테스트케이스 정도는 시뮬레이션 방식으로 통과가 가능할 것 같아, 간단한 시뮬레이션을 구현했다.
• 그 동안 프로젝트 때문에 알고리즘 스터디를 오랜만에 참여했다. 앞으로는 더 열심히 하자.