파이썬에서는 힙 자료구조를 heapq 를 통해 제공한다. 이때 최소힙 기능만 사용할 수 있고, 최대힙 기능은 지원하지 않는다.
최소값일 수록 우선순위를 가지고 맨 앞에 배치되니, 최대 힙을 사용하고 싶으면 값들을 넣을 때 -를 붙여 넣고, 출력할때는 -를 달아서 출력하면 최대힙 처럼 사용할 수 있다.
코드 구현
정답 코드
'''
# 최대 힙
'''
import heapq
import sys
input = sys.stdin.readline
n = int(input())
tmp = []
for i in range(n):
value = int(input())
if value !=0:
heapq.heappush(tmp, -value)
else:
if not tmp:
print(0)
else:
print(-heapq.heappop(tmp))
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 발견되는 즉시!! 반시계 방향으로 90도 회전해야한다.
코드 구현
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
startY, startX, dir = map(int, input().split())
mapp = []
for i in range(n):
mapp.append(list(map(int, input().split())))
dx=[0, -1, 0, 1] # 북 서 남 동
dy=[-1, 0, 1, 0] # 북쪽을 y, x 기준 1, 0으로 표기해서 틀렸음 ....... 정신차려!!
def solutions(x, y, dir):
cnt = 0 # 청소하는 칸의 개수
while 1:
# 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
if mapp[y][x] == 0:
mapp[y][x]=9
cnt+=1
check = 0 # 주변 4칸이 모두 청소된 칸인지 확인용 1은 청소필요, 1은 청소 불필요
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if mapp[ny][nx]==0:
#청소 필요한 칸 발견
check =1
break
if check == 1:
# 반시계 방향으로 90도 회전
dir=dir+1
if dir==4:
dir = 0
sx=x+dx[dir]
sy=y+dy[dir]
if mapp[sy][sx]==0:
# 전진함
x = sx
y = sy
# 청소가 필요 없는 경우
if check ==0:
nny = y-dy[dir]
nnx = x-dx[dir]
if mapp[nny][nnx]==1:
return cnt
else:
x=nnx
y=nny
if dir ==1:
dir = 3
elif dir ==2:
dir =2
elif dir == 3:
dir = 1
print(solutions(startX, startY, dir))
시간/공간 복잡도
시뮬레이션 문제라 고려하지 않았다.
어려웠던 점
반시계 반향으로 회전하려면, 문제에서 제시한 방향 기준으로 델타 x, y의 배열을 미리 선언할 때 조심해야 한다.
우측 상단 방향이 행, 열 값이 증가하는 상황이라면 북쪽 방향으로 가는것이(1, 0)이겠지만 해당 문제의 경우, 우측 하단으로 가야 행, 열이 값이 증가하는 상황이다. 이런 경우 북쪽으로 가는 것은 (-1, 0)이다.
알게된 점
좌표 문제의 경우, 쪽이 행과 열을 증가시키는 쪽인지 잘 확인하고 이를 고려하여 문제를 풀어야한다.
델타 x, y좌표 배열을 선언할 때도, 문제에서 관련 조건이나 방법을 제시하는지 잘 확인하여 선언해야 한다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dic = {}
revDic = {}
for i in range(n):
tmpS = input().strip()
dic[i+1]=tmpS
revDic[tmpS]=i+1
for i in range(m):
tmpV = input().strip()
if tmpV.isdigit():
tmpV= int(tmpV)
print(dic[tmpV])
else:
print(revDic[tmpV])
시간/공간 복잡도
O(n)
어려웠던 점
자료구조 조회할 때, 시간초과를 해결하기 위해서는 리스트보다 해시테이블을 구조인 딕셔너리 사용(O(1)) 이 더 빠르기 때문에 효과적이다.
알게된 점
키 값을 통해 값을 찾거나 밸류 값을 통해 값을 찾아야 하는 경우, 두개의 딕셔너리를 활용하면 아주 효율적이다.
문자열이 숫자 값인지 확인할때, 대상.isdigit()함수를 사용하면 확인할 수 있다. (숫자일 경우 True 반환)
import sys
input = sys.stdin.readline
t = int(input())
def fibonacci(n, count):
if n<=1:
if n ==0:
count[0]+=1
if n==1:
count[1]+=1
print(count[0], count[1])
return n
a = 0
b = 1
for i in range(2, n+1):
c = a + b
a = b
b = c
print(a, b)
return b
for i in range(t):
n = int(input())
count = [0, 0]
fibonacci(n, count)
# 0 1 1 2 3 5 8
시간/공간 복잡도
O(n)
최적화 및 개선
피보나치 함수 알고리즘을 구현할 때, 재귀함수로 구현후 시간 초과가 나면 DP로 구현하면 시간 복잡도를 줄일 수 있다.
import sys
input = sys.stdin.readline
n = int(input())
tmp = []
for i in range(n):
entire = input().strip()
if entire=='all':
tmp = list(range(1, 21))
elif entire=='empty':
tmp.clear()
else:
s, v = entire.split()
v = int(v)
if s == 'add':
if v not in tmp:
tmp.append(v)
if s == 'check':
if int(v) in tmp:
print(1)
else:
print(0)
if s == 'remove':
if v in tmp:
tmp.remove(v)
if s == 'toggle':
if int(v) in tmp:
tmp.remove(v)
else:
tmp.append(v)
시간/공간 복잡도
O(n)
어려웠던 점
입력값의 타입에 대해 잘 고려하지 않아서 조건문이 제대로 실행되지 않았던 점
sys모듈에서 input()함수를 사용할 때, 개행문자(/n)가 붙어서 조건문이 제대로 실행되지 않았던 점
느낀점
sys모듈에서 input()함수를 사용할 때, 개행문자(/n)를 꼭 처리하여 문제를 해결해야겠다.
이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 이때 지렁이의 개수를 +1 한다
bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 심겨진배추가 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 값이 0이 아니고 방문한 적이 없으면 현재자리의 방문체크를 해준다.
그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다.
코드 구현
정답 코드
import sys
from collections import deque
input=sys.stdin.readline
dx= [0, 0, 1, -1]
dy= [1, -1, 0, 0]
answer=[]
def bfs(y, x):
queue = deque()
visited[y][x] = True
queue.append([y, x])
while queue:
ny, nx = queue.popleft()
for ii in range(4):
yy= ny+dy[ii]
xx= nx+dx[ii]
if 0<=yy<n and 0<=xx<m and mapp[yy][xx]==1 and visited[yy][xx] == False:
visited[yy][xx] = True
queue.append([yy, xx])
t = int(input())
for j in range(t):
m, n, k = map(int, input().split())
mapp = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
cnt = 0
for i in range(k):
wm, wn = map(int, input().split())
mapp[wn][wm] = 1
for ix in range(n):
for jx in range(m):
if mapp[ix][jx]==1 and visited[ix][jx] == False:
cnt+=1
bfs(ix, jx)
answer.append(cnt)
for i in answer:
print(i)
시간/공간 복잡도
따로 생각하지 않았다.
최적화 및 개선
따로 하지않음
어려웠던 점
BFS는 큐에 넣기 전에 방문처리를 해야 중복 방문처리를 하지 않게 된다는 것을 알게됐다.
그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다.
좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다.
이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다.
bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다.
이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다.
값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다. 큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다.
순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다.
그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다.
코드 구현
정답 코드
import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque
if n==0 and m==0:
print(0)
print(0)
exit(0)
dy=[1, -1, 0, 0]
dx=[0, 0, 1, -1]
tmp=[]
for i in range(n):
tmp2=list(map(int, input().split()))
tmp.append(tmp2)
# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
bigN=1
while dequeA:
yy, xx, _ = dequeA.popleft()
visited[yy][xx] = True
for i in range(4):
nx=xx+dx[i]
ny=yy+dy[i]
if ny<0 or nx<0 or ny>=n or nx>=m:
continue
if visited[ny][nx]==True or tmp[ny][nx]==0:
continue
if tmp[ny][nx]>=1 and visited[ny][nx]==False:
tmp[ny][nx] = bigN+1
bigN=bigN+1
visited[ny][nx]=True
dequeA.append([ny,nx, bigN])
return cnt, bigN
tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
for j in range(m):
if tmp[i][j] == 1 and visited[i][j] == False:
dequeA.append([i,j, 1])
cnt+=1
cnt, bigN = bfs(cnt, dequeA, visited)
tmp3.append(bigN)
check =1
print(cnt)
if n == 0 and m ==0 or check ==0:
print(0)
else:
print(max(tmp3))
시간/공간 복잡도
따로 생각하지 않았다.
최적화 및 개선
따로 하지않음
어려웠던 점
BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다.
알게된 것
함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일
여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다.
import sys
n, m = map(int, input().split())
input=sys.stdin.readline()
tmp=[]
for i in range(n):
# tmp2=list(input.split())
tmp2=input.split()
print('tmp2', tmp2)
tmp.append(tmp2)
print(tmp)
문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다.
괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
괄호를 붙인 경우 (input()):
괄호를 붙이면 함수가 실제로호출된다.함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다.
import sys
n, m = map(int, input().split())
input=sys.stdin.readline
tmp=[]
for i in range(n):
tmp2=input().split()
tmp.append(tmp2)
print(tmp)
s1 = input()
s2 = input()
m=len(s1)
n=len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i][j-1], dp[i-1][j])
result =''
startm = m
startn = n
print(max(dp[-1]))
if max(dp[-1])!=0:
while 1:
if dp[startm][startn]==0:
break
# 위에것이 더 큰지
if dp[startm][startn] == dp[startm-1][startn]:
startm-=1
# 왼쪽 것이 더 큰지
elif dp[startm][startn] == dp[startm][startn-1]:
startn-=1
# 둘다 안크면 대각선 이동
# 값도 넣어줌
elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
startm-=1
startn-=1
result+=s2[startn]
print(result[::-1])
시간/공간 복잡도
0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에
2. 따라서 0행0열 0행 2열 0행 4열... 2행 0열 2행 2열.... 이렇게 맵의 크기만큼 조회한다.
2-1. 출발지 기준 이때 오른쪽으로 한칸, 아래로 한칸, 아래 오른쪽으로 한칸 을 리스트에 넣는다.
2-2. 리스트에서 두번재로 큰 수만 모아서 또다른 리스트를 만든다.
2번을 맵의 원소가 1개 남을때 까지 반복하다보면 결과 값이 나온다.
코드 구현
정답 코드
import sys
n = int(input())
block=[]
for i in range(n):
tmp = list(map(int, sys.stdin.readline().strip().split()))
block.append(tmp)
while 1:
if len(block[0])==1:
print(block[0][0])
break
makeBlock = [item[:] for item in block]
block = []
for i in range(0, len(makeBlock),2):
tmp=[]
for j in range(0, len(makeBlock[0]),2):
realT=[makeBlock[i][j], makeBlock[i][j+1], makeBlock[i+1][j], makeBlock[i+1][j+1]]
realT.sort(reverse=True)
tmp.append(realT[1])
block.append(tmp)
