Day11 통증 (2) - 구름LEVEL (goorm.io)
내 풀이 과정
음... 초등학교 다닐 즈음에 하나하나 숫자를 바꿔가며 환상을 조합을 찾아내던 문제와 비슷해보였다.
그래서 그냥 그렇게 찾게 코드를 작성해봤다. 어차피 내가 찾는거 아니고 컴퓨터가 찾아줄거니까.. 사실 이게 답이 맞는지는 잘 모르겠다.
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
N = int(input())
A, B = map(int, input().split())
acmax = N//A
result = -1
for ac in range(acmax+1):
bc = (N-(A*ac))//B
if (B*bc + A*ac) == N :
result = ac+bc
break
print(result)정해 코드
동적 프로그래밍이 필요한 문제라고 한다. 동적프로그램이 뭔지 이해하기 위해 한참 공부해야할것 같다...
내가 작성한 코드는 특정상황*( 아래의 조건이 아닌 경우) 매우 비효율적인 탐색을 할 수 있는 코드다 아래의 코드를 이용하면 좀더 효율적인 계산 결과를 뽑아낼 수 잇다.
N = int(input())
A, B = map(int, input().split())
dp = [float('inf')] * (N + 1)
dp[0] = 0
for i in range(N + 1):
if i - A >= 0:
dp[i] = min(dp[i], dp[i - A] + 1)
if i - B >= 0:
dp[i] = min(dp[i], dp[i - B] + 1)
print(dp[N] if dp[N] != float('inf') else -1)
Day12 발전기 - 구름LEVEL (goorm.io)
내 풀이 과정
점점 어렵다. 1이 연결된 덩어리를 찾아햐는데 어떻게 찾아야할지 감을 잡는데도 한참 시간이 걸렸고, 결국 24시간이 지난 뒤 해설을 보며 공부 한 뒤에야 풀어낼 수 있었다.
import numpy as np
N = int(input())
M = [[0 for _ in range(N+2)]]
dr =[-1, 0, 0, 1]
dc =[0, -1, 1, 0]
for _ in range(N):
M.append(list(map(int, ('0 '+input()+' 0').split())))
M.append([0 for _ in range(N+2)])
G = np.zeros((N+2,N+2),dtype = int)
generator = 0
def dfs(i, j):
stack = [(i, j)]
while stack:
y, x = stack.pop()
if not M[y][x]:
continue
M[y][x] = 0
for k in range(4):
ny, nx = y + dr[k], x + dc[k]
if not M[ny][nx]:
continue
stack.append((ny, nx))
for r in range(1,N+1):
for c in range(1, N+1):
if M[r][c]:
generator += 1
dfs(r, c)
print(generator)
정해 코드
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
result = 0
def dfs(i, j):
stack = [(i, j)]
while stack:
y, x = stack.pop()
if not arr[y][x]:
continue
arr[y][x] = 0
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if ny in (-1, N) or nx in (-1, N) or not arr[ny][nx]:
continue
stack.append((ny, nx))
for i in range(N):
for j in range(N):
if arr[i][j]:
result += 1
dfs(i, j)
print(result)
Day13 발전기 (2) - 구름LEVEL (goorm.io)
내 풀이 과정
12일차 해설이 공개 된 뒤에 등장한 문제로 12일차의 탐색 방법을 변형하여 해결해냈다.
건물 유형을 판정해야 했고, 단지의 조건을 판단해 해당 유형의 단지카운트를 세어주었다.
import numpy as np
N, K = map(int, input().split())
dr =[-1, 0, 0, 1]
dc =[0, -1, 1, 0]
dan_g =[]
M = [[0 for _ in range(N+2)]]
for _ in range(N):
M.append(list(map(int, ('0 '+input()+' 0').split())))
M.append([0 for _ in range(N+2)])
G = np.zeros((N+2,N+2),dtype = int)
def dfs(i, j):
stack = [(i, j)]
countzip = 0
while stack:
y, x = stack.pop()
if not M[y][x]:
continue
numberzip = M[y][x]
M[y][x] = 0
countzip +=1
for k in range(4):
ny, nx = y + dr[k], x + dc[k]
if not M[ny][nx] or not(M[ny][nx] == numberzip) or M[ny][nx] == 0:
continue
stack.append((ny, nx))
return countzip, numberzip
for r in range(1,N+1):
for c in range(1, N+1):
if M[r][c]:
a,b= dfs(r,c)
if a >= K : dan_g.append(b)
dan_g.sort(reverse=True)
print(max(dan_g, key=dan_g.count))
정해 코드
이미 배운 구조라 그런지 거의 비슷한 코드로 작성되었다.
나는 리스트 초기화를 위해 numpy로 작성하고 있고 정해코드에서는 리스트컴프리헨션을 사용하고 있다.
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def dfs(i, j):
stack = [(i, j)]
M = arr[i][j]
cnt = 0
while stack:
y, x = stack.pop()
if arr[y][x] != M:
continue
arr[y][x] = 0
cnt += 1
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if ny in (-1, N) or nx in (-1, N) or arr[ny][nx] != M:
continue
stack.append((ny, nx))
return cnt
N, K = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
count = [0] * 31
for i in range(N):
for j in range(N):
if arr[i][j]:
M = arr[i][j]
if dfs(i, j) >= K:
count[M] += 1
result, temp = 0, 0
for i in range(31):
if temp <= count[i]:
result = i
temp = count[i]
print(result)
