[TIL #24] 24일차 오늘의 공부 (2023.03.26 일)

TIL 2023.03.26 🐣

오늘 배운 것 👩🏻‍💻

알고리즘

• 백준 6064 카잉 달력 : 겨우 이해했다. 그래서 블로그로 정리했다. 글이 잘 읽히도록 쓰는 건 정말 어렵다는 것을 새삼 또 느꼈다. 휴 😮‍💨
  • 포스팅 : 2023.03.26 - [알고리즘] - [Python] 백준 6064_카잉달력 (최소공배수 활용)
• 백준 1780 종이의 갯수
  • 실패 소스

    # 종이의 갯수
    import sys
    n = int(sys.stdin.readline().rstrip())
    paper = []
    for _ in range(n):
        paper.append(list(sys.stdin.readline().rstrip().split()))
    cnt = {'-1':0, '0':0, '1':0}
    
    def cutPaper(x, y, n):
        if n == 1:
            cnt[paper[x][y]] += 1
            return
        
        # 모두 같은 수인지 확인
        paperNum = paper[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if paper[i][j] != paperNum:
                    paperNum = paper[i][j]
                    break
        # 9개로 자를지 여부 확인
        if paperNum == paper[x][y]: 
            cnt[paperNum] += 1
            return
        
        # 9개로 자르기 : paperNum 값이 바꼈다면 종이가 같은 수가 아님
        paperSize = n // 3
        for i in range(0, 3):
            for j in range(0, 3):
                cutPaper(x + (i * paperSize), y + (j * paperSize), paperSize)
    
    cutPaper(0, 0, n)
    # 결과 출력
    print(cnt['-1'])
    print(cnt['0'])
    print(cnt['1'])

  • 다른 코드 참고하지 않고 후루룩 짠 코드라 되게 뿌듯해하면서 제출했는데 바로 틀렸습니다! 😅
  • 이중 for문으로 paper 범위 내에 다른 숫자가 있는 경우 paperNum을 paper[i][j] 값으로 변경한다. 이중 for문이 끝난 뒤 paperNum 값이 초기값이였던 paper[x][y]와 다르다면 범위 내에 다른 숫자가 있다는 것으로 판단하여 9개로 종이를 자르도록 하였다. 👉 이게 바로 실패요인!
  • 이중 for문을 break 할 때, 내부에 있는 j값 for문만 break 되고 외부의 for문은 break 되지 않는다. 따라서 paperNum의 값을 paper[x][y]와 동일한 값으로 바꾸게 된다면, 범위내의 다른 값을 감지하지 못하게 된다.
  • 따라서 cutFlag를 사용해서 이중 for문 전체가 break되도록 수정했다.
  • 최종 소스

    # 종이의 갯수
    import sys
    n = int(sys.stdin.readline().rstrip())
    paper = []
    for _ in range(n):
        paper.append(list(sys.stdin.readline().rstrip().split()))
    cnt = {'-1':0, '0':0, '1':0}
    
    def cutPaper(x, y, n):
        if n == 1:
            cnt[paper[x][y]] += 1
            return
        
        # 모두 같은 수인지 확인
        paperNum = paper[x][y]
        cutFlag = False
        for i in range(x, x + n):
            for j in range(y, y + n):
                if paper[i][j] != paperNum:
                    cutFlag = True  # 다른 수가 있는 경우 종이 자르기
                    break
            if cutFlag:
                break
    
        if not cutFlag: 
            cnt[paperNum] += 1  # 해당 숫자의 종이 수 증가
            return
        
        # 9개로 자르기 : cutFlag가 바꼈다면 종이가 같은 수가 아님
        paperSize = n // 3
        for i in range(0, 3):
            for j in range(0, 3):
                cutPaper(x + (i * paperSize), y + (j * paperSize), paperSize)
    
    cutPaper(0, 0, n)
    # 결과 출력
    print(cnt['-1'])
    print(cnt['0'])
    print(cnt['1'])

• 백준 1992 쿼드 트리 : 1780번 문제와 비슷한 문제
  • [왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래] 4개의 영역으로 나뉘며, 0 또는 1로 압축될 수 있다.
  • 괄호 () 출력으로 구분이 필요하다. 👉 재귀 호출 전에 괄호로 내용을 감싸도록 출력해줬다.

  • # 쿼드 트리
    import sys
    n = int(sys.stdin.readline().rstrip())
    video = []
    for _ in range(n):
        video.append(list(sys.stdin.readline().rstrip()))
    
    def divideVideo(x, y, n):
        if n == 1:
            print(video[x][y], end='')
            return
        
        # 모두 같은 수인지 확인
        divideFlag = False
        for i in range(x, x + n):
            for j in range(y, y + n):
                if video[i][j] != video[x][y]:
                    divideFlag = True  # 다른 수 체크
                    break
            if divideFlag:
                break
    
        if not divideFlag: 
            print(video[x][y], end='')  # video[x][y]로 압축
            return
        
        # 4개 영역 : 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
        size = n // 2
        print("(", end='')
        divideVideo(x, y, size)
        divideVideo(x, y + size, size)
        divideVideo(x + size, y, size)
        divideVideo(x + size, y + size, size)
        print(")", end='')
    
    divideVideo(0, 0, n)

• 백준 11403 : 플루이드 워셜 알고리즘 활용 문제
• 백준 7569 토마토 : 7576번 문제와 비슷한 문제, 똑같은 토마토 문제인데 상자의 높이(h)가 추가되며, 앞 뒤의 상자에도 영향을 미친다.
  • 따라서 앞과 뒤의 상자에도 영향을 주기 위해 방향 두개 (-n, 0), (n, 0) 을 추가했고, 상하좌우 체크할 때 같은 층인지 확인하도록 추가했다.

  • # 토마토2 
    import sys
    from collections import deque
    def bfs(n, h, pos):
        dirs = [(-1, 0, True), (1, 0, True), (0, -1, True), (0, 1, True), (-n, 0, False), (n, 0, False)] # 위, 아래, 왼쪽, 오른쪽,
        queue = deque(pos)
        answer = 0
        while queue :
            x, y, date = queue.popleft()
            for dx, dy, sameBox in dirs:
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= (n * h) or ny < 0 or ny >= m:
                    continue
                start = (x // n) * n   # 층 시작 범위
                if sameBox and (nx < start or nx >= start + n):   # 상하좌우가 같은 층이 아닌 경우
                    continue
                if tomato[nx][ny] == -1:
                    continue
                if tomato[nx][ny] == 0:
                    tomato[nx][ny] = date + 1
                    queue.append((nx, ny, tomato[nx][ny]))
    
            answer = max(date, answer)
    
        for t in tomato:
            if 0 in t:
                return -1
            
        return date
    
    m, n, h= map(int, sys.stdin.readline().rstrip().split())
    tomato = []
    for _ in range(n * h):
        tomato.append(list(map(int, sys.stdin.readline().rstrip().split())))
    pos = []    # 익은 토마토 좌표
    for i in range(n * h):
        for j in range(m):
            if tomato[i][j] == 1:
                pos.append((i, j, 0))
    print(bfs(n, h, pos))

클린코드

• 클린코드 이제는 파이썬이다 8장_파이썬에서 빠지기 쉬운 함정들

추가적으로 하면 좋을 것

기타 🤔

오늘은 오랜만에 알고리즘을 중점으로 공부했다. 재밌다. 3월 안에 백준 골드 3을 달성할 수 있을 것 같다. 두근!