[구름톤 챌린지]블로그학습일기 3주차(1)

벌써 3주차이다. 지금 보니까 블록색깔이랑 캐릭터 옷 색이랑 같은 색이다.(3주째 되고나서야 알게된 내 관찰력 무엇..)

11일차 : 통증(2)

# -------------------------------------------------------------------------
# A와 B는 배수관계가 아니다. => 그리디 방식으로 해결 할 수 없다 => DP해결방법을 고려해볼까?
# -------------------------------------------------------------------------
import sys

input = sys.stdin.readline

N = int(input())

#dp 테이블 초기화
dp = [float('inf')] * ((10**6)+1)
Ap, Bp = map(int, input().split())

dp[0] = 0
for i in range(1, N+1):
    # dp[]테이블 인덱스 체크
    if i - Ap >= 0:
        dp[i] = min(dp[i], dp[i-Ap]+1)
    if i - Bp >= 0:
        dp[i] = min(dp[i], dp[i-Bp]+1)

if dp[N] == float('inf'):
    print(-1)
else:
    print(dp[N])
    
# -------------------------------------------------------------------------
# top-down방식 시간 초과(test Case 5~24번)
# 재귀 + Dp 방식으로 풀어보려고 했으나 시간 초과로 Fail
# 식을 입력하면 계산에 대한 내용은 컴퓨터에게 맡기니 코드는 보기 좋으나 stack overflow 때문에
# 코딩 테스트에서는 최대한 지양해야겠다...
# -------------------------------------------------------------------------
import math
import sys
# 입력 받기
N = int(input())
Ap, Bp = map(int, input().split())
dp = [float('inf')] * (10**6+1)

def solve(pain):
    if pain == 0:
        return 0
    if pain < 0:
        return float('inf')
    
    dp[pain] = min(solve(pain - Ap), solve(pain - Bp)) + 1
    return dp[pain]

result = solve(N)
if result == float('inf'):
    print(-1)
else:
    print(result)

A와 B는 배수관계가 아니다. 그런데 통증 수치를 0으로 만들라고 한다.
여기서 그리디 방식으로는 풀 수 없다. 배수 관계가 아니므로 나누어 떨어진다는 보장을 할 수 없기 때문이다. => 따라서 DP로 접근한다.

bottom-up 방식과 top-down방식 모두 풀어보았는데
top-down방식은 재귀로 인해 시간 초과가 났다(testCase 5~24번)
sys.setrecursionlimit(1000000)으로 재귀 깊이 제한을 늘려줘도 소용 없었다. 반복적으로 함수 호출 반환을 하므로 스택 오버플로우가 발생한다.
앞으로 최대한 bottom-up으로 풀도록 해야겠다.

12일차 : 발전기

# ------------------------------------
# DFS
# 상하좌우 서로 연결되어있는 집의 그룹 개수 구하기

# 실패(Runtime Error) : testcase 4, 10, 11, 12, 13, 14, 19, 22 
# ------------------------------------
import sys
input = sys.stdin.readline

# 행,열 크기
N = int(input().rstrip())
M = []
visited = [[0]*N for _ in range(N)]

cnt = 0

for _ in range(N):
    M.append(list(map(int, input().rstrip().split())))

def dfs(x, y):
    # 방문 처리
    visited[x][y] = 1
    
    # 상하 좌우
    for dx, dy in [(-1,0), (1,0),(0,-1),(0,1)]:
        nx = x + dx
        ny = y + dy

        if 0<=nx<N and 0 <= ny<N and M[nx][ny]== 1 and visited[nx][ny] == 0:
            dfs(nx, ny) 
            

for i in range(N):
    for j in range(N):
        # 1이고 아직 방문하지 않았다면 dfs 돌리기
        if M[i][j] == 1 and visited[i][j] == 0:
            dfs(i, j)
            cnt += 1

print(cnt)


# ------------------------------------
# BFS 통과 코드 
# ------------------------------------
from collections import deque
import sys
input = sys.stdin.readline

# 행,열 크기
N = int(input().rstrip())
M = []
visited = [[0]*N for _ in range(N)]

cnt = 0

for _ in range(N):
    M.append(list(map(int, input().rstrip().split())))

def bfs(r, c):
    # 큐 생성
    q = deque([(r,c)])

    # 방문처리
    visited[r][c] = 1

    while q:
        r, c = q.popleft()

        # 상하좌우
        for dx, dy in [(-1,0), (1, 0), (0, -1), (0, 1)]:
            nx = r + dx
            ny = c + dy

            # 범위 체크
            if 0<= nx <N and 0 <= ny < N and M[nx][ny] == 1 and visited[nx][ny] == 0:
                q.append((nx, ny))
                visited[nx][ny] = 1

for i in range(N):
    for j in range(N):
        if M[i][j] == 1 and visited[i][j] == 0:
            bfs(i, j)
            cnt += 1
            
print(cnt)

연결된 노드들의 그룹 개수(발전기의 최소 개수)니까, DFS,BFS로 연결된 노드만 전부 찾아서 visited로 방문을 체크 해주고 더이상 방문할 곳이 없으면 발전기 최소 개수를 증가시켜준다.

근데 DFS로 풀면 일부 테스트케이스가 런타임 에러가 발생한다. 마찬가지로 재귀로 인해 스택 오버플로우가 발생하기 떄문인것 같다.
(재귀 깊이 제한을 늘려주었더니 실패 테스트 케이스가 감소함.)

문제 출제해주신 분께서도 재귀적으로 해결하기 보다 비재귀적으로 해결하라고 하신다. DFS로 풀려면 stack을 이용해서 푸는 방법을 고려하는 것도 방법인 것 같다.

13일차 : 발전기(2)

from collections import deque
import sys
input = sys.stdin.readline

# 행,열 크기
N, K = map(int, input().split())
M = []
visited = [[0]*N for _ in range(N)]

cnt = [0]*31

for _ in range(N):
    M.append(list(map(int, input().rstrip().split())))

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0:
            q = deque([(i, j)])

            # 방문처리
            visited[i][j] = 1
            temp_cnt = 1
            while q:
                x, y = q.popleft()

                # 상하좌우 체크
                for dx, dy in [(-1,0), (1, 0), (0, -1), (0, 1)]:
                    nx = x+dx
                    ny = y+dy

                    # 범위 체크
                    if 0<= nx < N and 0<= ny < N and M[nx][ny] == M[x][y] and visited[nx][ny] == 0:
                        temp_cnt += 1
                        q.append((nx, ny))
                        visited[nx][ny] = 1

            if temp_cnt >= K:
                cnt[M[i][j]] += 1
                        
# 가장 많은 단지가있는 경우 Mrc가 더큰 건물 유형을 뽑음(cnt 리스트 뒤에서 부터 탐색)                        
print(len(cnt)-1 - cnt[::-1].index(max(cnt)))

12일차 발전기 문제와 비슷하다. 단, 단지의 기준K가 주어지고, K개 이상 연결된 건물의 유형만 단지 개수를 증가시켜준다.

단지의 개수가 가장 많은 건물유형 번호를 출력하면된다. 만약 단지의 개수가 같은 건묾 유형 번호가 있다면, 더 큰 건물의 유형번호를 출력하면된다.

로직을 작성하는 건 딱히 어려움없었다. 발전기 문제에 있던거 가져와서 조금 변형했다 ㅎㅎ

출력할때 어떻게하면 한줄로 뽑아낼 수 있을까 고민 했는데
cnt[::-1]로 리스트를 반대로 탐색하면서 최초로 발견된 최대값 인덱스를 뽑아오고, 배열크기 - 1에 빼줘서 로 원래 인덱스 값으로 돌려놓는다.

개인적으로 완전탐색을 풀때보다 오히려 쉬운것 같다. 통증(2)와 발전기 문제는 둘다 재귀를 이용한 풀이와 반복문을 이용한 풀이 둘다 생각하다보니 "반복문이 있는데 왜 재귀를 쓸까?"라는 원론적인 궁금증이 생기게 되어서 정리하게되었다.

앞으로 모을 블록 총 7개 남았다. 나름 매일 아침마다 잠도 깰겸 알고리즘 문제 푸는 것도 좋은 것 같다. 챌린지가 끝나면 오히려 아쉬울 것 같다.