데이터 엔지니어링

1. 문제 소개

• 구현 문제에 해당된다
• undo 명령구간에 모든 명령어는 취소하고, 남은 type 명령의 문자를 저장해서 출력하는 문제다.
• undo 명령도 undo 에 의해 취소 될 수 있다.

2.코드

#입력 테스트 케이스 처리
def setTestCase():
    N=input()
    COMMAND_LIST = []
    for i in range(int(N)):
        COMMAND_LIST.append(input())
    return COMMAND_LIST

#커맨드 라인 파싱 
def command_parser(input_command_list):
    command_list = []
    for i in input_command_list:
        split_command = i.split(" ")
        command_type,command_content,seconds = split_command[0],split_command[1],int(split_command[2])
        command_list.append((seconds,command_content))
    
    return command_list


# 입력 처리 
def process_command(command_list):
    text = ''   # 결과 문자열을 담을 변수
    rollback_point=-1   # undo 의 분기를 찾을 카운트
    
    # 명령어는 역순으로 처리
    for command_set in reversed(list(command_list)):
        seconds,command = command_set
        # undo 가 적용되는 마지막 명령어 분기
        if seconds == rollback_point:       
            rollback_point = -1 
            continue
        # undo 가 해당되는 구간의 명령어 skip 분기
        elif rollback_point != -1 and seconds > rollback_point:
            continue
        # undo 명령어를 만났을 때 분기
        elif command.isdigit():
            rollback_point = seconds - int(command)
            if rollback_point < 0:
                rollback_point = 0
            continue
        # 문자 저장
        text+=command
    
    return text[::-1]   # 역순으로 결과 문자열이 저장되었기 때문에 reverse 처리 
        


def solution():
    input_command_list = setTestCase()
    command_list=command_parser(input_command_list)
    result = process_command(command_list)

    print(result)

if __name__=='__main__':
    solution()

3.코멘트

• 스택구조의 프로그램 호출 처리 흐름을 모방하여, 명령어를 역순으로 undo 범위에 해당되는 명령은 취소하여 문제를 해결했다.  
• 생각한 테스트 케이스는 문제가 없었는데 실제 제출시 실패가 있었다.
• 함께 스터디한 스터디원에게 반례 케이스 정보를 얻어 문제를 해결할 수 있었다.
• type/undo 가 0초일때 , 그리고 같은 초에 여러 명령어의 입력이 들어올 경우를 추가하여 테스트 했다. 
• 언제나 그랬지만 함께 열심히 공부한 스터디원에게서 지식을 얻는다. .. (스터디원들에게 고맙다 ) 

1.문제소개

• 모든 정점들간의 최단경로를 구하는 플로이드 와샬을 사용하면서, 출력 요구사항만 맞추면 된다.
• 시간복잡도는 for 루프가 3중으로 수행되기 때문에 O(n3) 이다.
• 공간복잡도는 행렬의 크기만큼 O(n2)이다.

2.코드

def floydWarshall(dag, N):
    for i in range(0, N):
        for j in range(0, N):
            if dag[i][j] == 0 and i != j:
                dag[i][j] = -1  # INF

    for k in range(0, N):
        for i in range(0, N):
            for j in range(0, N):
                if dag[i][k] > 0 and dag[k][j] > 0:
                    dag[i][j] = 1

    for i in range(0, N):
        for j in range(0, N):
            if dag[i][j] <= 0:
                print('{} '.format(0), end='')
            else:
                print('{} '.format(dag[i][j]), end='')
        print()


def main():
    N = int(input())
    dag = []
    for i in range(0, N):
        line = input().split(' ')
        dag += [[int(x) for x in line]]

    floydWarshall(dag, N)


if __name__ == '__main__':
    main()

3.코멘트

• 그래프 문제는 알고리즘도 어렵지만 언제나 전처리부분 작성이 성가시다..

1. 문제 소개

• 그래프 탐색 문제이다
• 깊이, 너비 우선 탐색으로만 구현해도 통과가 가능해보인다.

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

2.코드

def myDFS(N,M,caseMap):
    stack = []
    visited = []
    success = False
    for i in range (0,N):
        visited.append([False for i in range(M)])

    #set start pos
    for i in range(0,M):
        stack.append((0,i))

    while(len(stack) >0):
        loc = stack.pop()
        row = loc[0]
        col = loc[1]

        #out of index case
        if row < 0 or col < 0 or row >= N or col >= M or visited[row][col]:
            continue

        visited[row][col]=True

        #Block case
        if caseMap[row][col] == 1:
            continue

        print("current row : {} col : {}  val : {}".format(row,col,caseMap[row][col]))

        stack.append((row,col-1))
        stack.append((row,col+1))
        stack.append((row-1,col))
        stack.append((row+1,col))
        
        #reach to Out line 
        if (row+1) == N:
            success = True

    return success

def inputCase():
    NM= input().split(" ")
    N,M=int(NM[0]),int(NM[1])
    caseMap = []
    for i in range (0,N):
        inline = input()
        flatten = [int(x) for x in inline]
        caseMap.append(flatten)
    return N,M,caseMap

def solution():
    N,M,caseMap = inputCase()
    rs=myDFS(N,M,caseMap)
    if rs ==True:
        print("YES")
    else:
        print("NO")
    #print(caseMap)    



solution()

3.코멘트

• DFS, BFS는 할 때마다 자꾸 까먹는다.
• 비슷한 문제 유형을 계속 풀어봐야 할 것 같다

1. 문제 소개

• 이분탐색을 이용하여 문제를 풀어야 한다

2.코드 ( python )

TOTAL_COMPUTERS=0
MIN_COMPUTERS=0
MAX_COMPUTERS=0

def getMinMinute(servers):
    global TOTAL_COMPUTERS, MIN_COMPUTERS,MAX_COMPUTERS
    start=0
    end=MAX_COMPUTERS

    while(start<end):
        mid=(start+end)//2
        sumOfComputer=0

        for i in servers:
            if i>mid:
               sumOfComputer+=mid
            else:
                sumOfComputer+=i
        #if sumOfComputer==MIN_COMPUTERS:
         #   start=end
        if sumOfComputer<MIN_COMPUTERS:
            start=mid+1
        else:
            end=mid
        
    return end
    

def solution():
    global TOTAL_COMPUTERS,MIN_COMPUTERS,MAX_COMPUTERS
    arr=[]
    N=int(input())
    for i in range (0,N):
        in_line=input().split(' ')
        tmp=[int(x) for x in in_line]
        if max(tmp)>=MAX_COMPUTERS:
            MAX_COMPUTERS=max(tmp)
        TOTAL_COMPUTERS+=sum(tmp)
        arr+=tmp


    if TOTAL_COMPUTERS%2==0:
        MIN_COMPUTERS= (TOTAL_COMPUTERS//2)
    else:
        MIN_COMPUTERS= (TOTAL_COMPUTERS//2)+1
    print(getMinMinute(arr))

if __name__=='__main__':
    solution()

3.코멘트

1. 문제 소개

• 그리디 문제로 분류 된다.
• 체인의 개수와 길이로, 하나의 긴 체인을 묶기 위한 최소한의 고리 수를 찾는 문제이다.
• 체인의 길이는 고리의 개수와 같고, 체인을 분리하거나 연결할 수 있다는 내용을 이해해야 한다.

2.코드 ( python ) 

# 고리의 최소 개수 리턴 
def getMinimumChainRing(chains,v_chains):
    # 마지막 고리 위치
    endRingPos = chains-1
    # 시작 고리 위치
    startRingPos = 0
    while(True):
    	# 고리의 위치가 만나는 지점에서 break 
        if  startRingPos == endRingPos:
#            print("minimum chain Ring count : {} ".format(chains - 1 endRingPos))
            break
        elif v_chains[startRingPos]==0:
            startRingPos+=1
        else:
            v_chains[startRingPos]-=1
            endRingPos-=1

    return (chains - endRingPos -1)



def solution():
	# 입력값 전처리 
    chains = int(input())
    org_v_chains = input().split(" ")
    #chains = 5
    #org_v_chains=[1,1,1,2]
    #org_v_chains=[4,3,5,7,9]
    v_chains = [int(x) for x in org_v_chains]
    
    # 체인 개수와 정렬된 상태의 체인 길이 배열을 매개변수로 전달 
    minRings = getMinimumChainRing(chains,sorted(v_chains))
    
    # 정답 출력
    print(minRings)


if __name__=="__main__":
    solution()

3.코멘트

• 예제 입출력이 이해가 잘 안갔지만, 함께 스터디한 찬의님의 도움으로 이해할 수 있었다.
  • ex) 5 / 4,3,5,7,8.  
  • 3짜리를 하나 빼서 4,5,7,8 사이에 하나씩 연결하면, 최소 3개의 고리가 필요하게 된다.
• 아이디어
  • 체인을 정렬한다
  • 최소 길이의 체인부터 고리를 하나씩 빼서, 마지막 위치에서부터 차례로 연결한다. 
  • 시작 포인터에서 고리를 빼고, 마지막 포인터에서 고리를 연결하여 둘이 만나는 지점에서 break 후 정답을 출력한다.