python 2차원 배열 최댓값
array = [[1,2,3],[3,4,5],[2,1,2],[0,0,1]]
temp = map(max,array) # -> [3,5,2,1]
temp2 = max(temp) # -> 518111번 _ 마인크래프트 문제
N, M ,B = list(map(int,s.readline().split()))
array = [list(map(int,s.readline().split())) for _ in range(N)]
listMax = max(map(max,array))
listMin = min(map(min,array))
result = int(1e9)
resultH = 0
for k in range(listMin,listMax+1):
ans = 0
block = B
for i in range(N):
for j in range(M):
if array[i][j] > k :
ans +=(array[i][j] - k) * 2
block += 1
else:
ans +=abs(array[i][j] - k) * 1
block -= 1
if block < 0 :
continue
if result > ans:
result = ans
resultH = k
print(result, resultH)이렇게 3중 for문을 돌리니까 시간초과가 떠서 다른 방법을 찾아야했다. 결국 시간 초과를 줄이는 방법은 For문을 줄이는 방법이 제일 효율적이기 때문에 for문을 하나 줄여야 했고 갯수를 list에 넣어서 한번에 계산하는 방식으로 해결했다.
N, M ,B = list(map(int,s.readline().split()))
array = [list(map(int,s.readline().split())) for _ in range(N)]
listMax = max(map(max,array))
listMin = min(map(min,array))
height_cnt = [0 for _ in range(listMax+1)]
for i in array:
for j in i:
height_cnt[j] += 1
result = int(1e9)
resultH = 0
for k in range(listMin,listMax+1):
ans = 0
block = B
for i in range(listMax+1):
if i < k:
ans = ans+ (k-i)*height_cnt[i]
block -= height_cnt[i] * abs(k - i)
elif i > k:
ans = ans + (i-k)*height_cnt[i]*2
block += height_cnt[i] * abs(k-i)
if block < 0 :
continue
if result >= ans and resultH <= k:
result = ans
resultH = k
print(result, resultH)실수한 부분
- 1 1 0
- 0 과 같은 예시일 때 resultH <= k 일때를 고려 안해서 틀림
- 같은 시간이면 더 높은 곳일 때를 출력해야되는데, 그 부분을 고려안함안전 영역 - DFS
from sys import stdin as s
import sys
sys.setrecursionlimit(100000)
s = open('input.txt','rt')
dx = [0,1,0,-1]
dy = [1,0,-1,0]
n = int(s.readline())
array = [list(map(int, s.readline().split())) for _ in range(n)]
def dfs(x,y,depth):
for i in range(4):
if 0 <= x+dx[i] < n and 0 <= y+dy[i] < n and array[x+dx[i]][y+dy[i]] > depth and visited[x+dx[i]][y+dy[i]]:
visited[x+dx[i]][y+dy[i]] = False
dfs(x+dx[i], y+dy[i], depth)
result =0
print(max(map(max,array)))
for k in range(max(map(max, array))):
visited = [[True] * n for _ in range(n)]
ans =0
for i in range(n):
for j in range(n):
if visited[i][j] == True and array[i][j] > k:
ans+=1
visited[i][j] = False
dfs(i,j,k)
result = max(ans,result)
print(result)안전 영역 - bfs
from sys import stdin as s
import sys
from collections import deque
sys.setrecursionlimit(100000)
s = open('input.txt','rt')
dx = [0,1,0,-1]
dy = [1,0,-1,0]
n = int(s.readline())
array = [list(map(int, s.readline().split())) for _ in range(n)]
result =0
def bfs(x,y,depth):
queue = deque()
queue.append((x,y))
visited[x][y]= True
while queue:
hx,hy= queue.popleft()
for i in range(4):
nx = hx + dx[i]
ny = hy + dy[i]
if 0 <= nx < n and 0<= ny < n and array[nx][ny] > depth and not visited[nx][ny]:
queue.append((nx,ny))
visited[nx][ny] = True
#for i in range(max(map(max,array))):
for k in range(max(map(max,array))):
visited = [[False] * n for _ in range(n)]
ans =0
for i in range(n):
for j in range(n):
if not visited[i][j] and array[i][j] > k:
ans +=1
bfs(i,j,k)
result =max(result,ans)
print(result)보물섬
from sys import stdin as s
from collections import deque
import copy
s = open('input.txt','rt')
N, M = list(map(int,s.readline().split()))
array = [list(map(str,s.readline().rstrip())) for _ in range(N)]
dx = [0,-1,0,1]
dy = [1,0,-1,0]
global result
result =0
def bfs(x,y):
global result
maps = [item[:] for item in array]
h = 0
q = deque()
q.append((x,y,h))
maps[x][y] = 'W'
ans = 0
while q:
hx ,hy,hh = q.popleft()
ans = max(ans,hh)
for i in range(4):
nx = hx + dx[i]
ny = hy + dy[i]
nh = hh
if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] != 'W':
maps[nx][ny] = 'W'
q.append((nx,ny,nh+1))
return ans
for i in range(N):
for j in range(M):
if array[i][j] == "L":
if i> 0 and i+1<N and array[i-1][j] == "L" and array[i+1][j] =="L":
continue
if j> 0 and j+1<M and array[i][j-1] == "L" and array[i][j+1] =="L":
continue
result = max(result,bfs(i,j))
print(result)처음에 로직대로 L인 육지에서 시작해서 방향마다 bfs로 탐색해서 최단거리를 찾아줘서 풀었는데 57%쯤 채점하고 계속 시간초과가 발생했다.
- 실수한 부분
- 탐색 시작하고자 하는 곳이 가장자리가 아닐때는 최단거리가 될 수 없기 때문에 해당하는 부분을 제외하고 검사하면 시간초과가 나지 않는다.
- W L L
- L L L
- W W L
- 이런 지도라 생각했을 때 (1,1)은 좌우로 L이기 때문에 탐색 시작지점으로 적합하지 않다.브루트 포스 문제는 중요한 것 같아서 dfs, bfs 둘 다 풀어 보았고, 앞으로 한참은 브루트 포스 문제를 중점으로 풀어야 될 것 같다.
브루트 포스 문제 리스트
| NO | LV | 유형 | 제목 | 비고 |
|---|---|---|---|---|
| 18111 | S2 | 브루트 포스 | 마인 크래프트 | 첫 시도 시간초과 |
| 14889 | S2 | 브루트 포스 | 스타트와 링크 | 완전 탐색으로 6개 중에 3개를 조합하고 싶다면 dfs탈출 조건을 n//2로 주면 된다 |
| 2468 | S1 | 브루트 포스 | 안전 영역 | dfs, bfs모두 풀어봄 |
| 2589 | G5 | 브루트 포스 | 보물섬 | 첫 번째 시간 초과, 예외처리 해주니 통과 |
| 1018 | S4 | 브루트 포스 | 체스판 다시 칠하기 | for문 4개 돌리면 되는데 괜히 bfs로 하려다가 시간 잡아먹음 |
진정한 경제적 자유란 무엇인가?
" 무엇이 찬양받아야 하는가? 내 생각으로는 우리 자신의 욕망에 부응하는 행동을 하지 않는 것이 되어야 한다. ... 자기존중감을 충족시킬 때 주어지는 찬사만이 진실한 기쁨을 가져올 수 있다. "
- 마르쿠스 아우렐리우스, 명상록. 6.16, 2b-4a
생활 방식은 가치관을 반영한다. 더 많이 갖고자 열망하고 더 많은 수입과 더 많은 성취를 갈망할수록 실제 삶을 즐길 가능성은 줄어든다.
세 가지 훈련
" 지혜와 선을 기르기 위해 세 가지 영역에서 훈련을 해야 하네. 첫 번째는 욕망과 혐오에 관련된 것이지. 욕망의 흔적을 놓치지 않고 살피며 항상 경계해야 해, 두 번째는 충동을 따르지 않는 것이야. 이는 합리적인 이유를 따라 행동하고 부주의하지 않아야 함을 뜻한다네. 세 번째는 올바른 판단력이야. 우리 마음을 기만하지 않고, 평정심을 유지할 수 있도록 노력해야 하는 것이네. 그리고 이 영역들 가운데 가장 중요하고 조심스럽게 훈련해야 하는 것은 첫 번째 영역이야. 우리가 마음이 욕망과 혐오에 빠져들 때만큼 강렬한 감정은 없다네"
- 에픽테토스, 대화록, 3.2.1-3a
세 영역은 조금씩 다르지만 분리되어 있지 않고 불가분의 관계에 있다. 세 영역을 갈고닦아 삶에서 실천할 수 있을 때, 우리는 정신을 맑고 깨끗하게 할 수 있을 것이다.
만트라의 힘
" 끊임없는 성찰을 통해 마음속 올바르지 않은 인상들을 씻어 버려야 한다. 나는 죄악과 욕망, 참자아를 가리는 모든 방해물로부터 내 영혼을 지키기 위해, 그리고 자연의 참된 본성으로 나아가기 위해 성찰한다. 나는 사물의 본성을 가려내고 그 가치에 따라 사물을 사용할 것이다. 자연이 우리에게 준 이 힘을 기억하라. "
- 마르쿠스 아우렐리우스, 명상록, 8.29
"사념이 들어오지 못하게 하는 힘이 내 안에 있다. 나는 진리를 바라 볼 수 있다."
