파이썬에서는 힙 자료구조를 heapq 를 통해 제공한다. 이때 최소힙 기능만 사용할 수 있고, 최대힙 기능은 지원하지 않는다.
최소값일 수록 우선순위를 가지고 맨 앞에 배치되니, 최대 힙을 사용하고 싶으면 값들을 넣을 때 -를 붙여 넣고, 출력할때는 -를 달아서 출력하면 최대힙 처럼 사용할 수 있다.
코드 구현
정답 코드
'''
# 최대 힙
'''import heapq
import sys
input = sys.stdin.readline
n = int(input())
tmp = []
for i inrange(n):
value = int(input())
if value !=0:
heapq.heappush(tmp, -value)
else:
ifnot 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 inrange(n):
mapp.append(list(map(int, input().split())))
dx=[0, -1, 0, 1] # 북 서 남 동
dy=[-1, 0, 1, 0] # 북쪽을 y, x 기준 1, 0으로 표기해서 틀렸음 ....... 정신차려!! defsolutions(x, y, dir):
cnt = 0# 청소하는 칸의 개수 while1:
# 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.if mapp[y][x] == 0:
mapp[y][x]=9
cnt+=1
check = 0# 주변 4칸이 모두 청소된 칸인지 확인용 1은 청소필요, 1은 청소 불필요 for i inrange(4):
nx=x+dx[i]
ny=y+dy[i]
if mapp[ny][nx]==0:
#청소 필요한 칸 발견
check =1breakif check == 1:
# 반시계 방향으로 90도 회전dir=dir+1ifdir==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
ifdir ==1:
dir = 3elifdir ==2:
dir =2elifdir == 3:
dir = 1print(solutions(startX, startY, dir))
시간/공간 복잡도
시뮬레이션 문제라 고려하지 않았다.
어려웠던 점
반시계 반향으로 회전하려면, 문제에서 제시한 방향 기준으로 델타 x, y의 배열을 미리 선언할 때 조심해야 한다.
우측 상단 방향이 행, 열 값이 증가하는 상황이라면 북쪽 방향으로 가는것이(1, 0)이겠지만 해당 문제의 경우, 우측 하단으로 가야 행, 열이 값이 증가하는 상황이다. 이런 경우 북쪽으로 가는 것은 (-1, 0)이다.
알게된 점
좌표 문제의 경우, 쪽이 행과 열을 증가시키는 쪽인지 잘 확인하고 이를 고려하여 문제를 풀어야한다.
델타 x, y좌표 배열을 선언할 때도, 문제에서 관련 조건이나 방법을 제시하는지 잘 확인하여 선언해야 한다.
import sys
input = sys.stdin.readline
t = int(input())
def fibonacci(n, count):
if n<=1:
if n ==0:
count[0]+=1if n==1:
count[1]+=1print(count[0], count[1])
return n
a = 0b = 1for 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 inrange(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 notin tmp:
tmp.append(v)
if s == 'check':
ifint(v) in tmp:
print(1)
else:
print(0)
if s == 'remove':
if v in tmp:
tmp.remove(v)
if s == 'toggle':
ifint(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=[]
defbfs(y, x):
queue = deque()
visited[y][x] = True
queue.append([y, x])
while queue:
ny, nx = queue.popleft()
for ii inrange(4):
yy= ny+dy[ii]
xx= nx+dx[ii]
if0<=yy<n and0<=xx<m and mapp[yy][xx]==1and visited[yy][xx] == False:
visited[yy][xx] = True
queue.append([yy, xx])
t = int(input())
for j inrange(t):
m, n, k = map(int, input().split())
mapp = [[0] * m for _ inrange(n)]
visited = [[False] * m for _ inrange(n)]
cnt = 0for i inrange(k):
wm, wn = map(int, input().split())
mapp[wn][wm] = 1for ix inrange(n):
for jx inrange(m):
if mapp[ix][jx]==1and 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==0and m==0:
print(0)
print(0)
exit(0)
dy=[1, -1, 0, 0]
dx=[0, 0, 1, -1]
tmp=[]
for i inrange(n):
tmp2=list(map(int, input().split()))
tmp.append(tmp2)
# 그냥 카운트만 하는애 cnt# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ inrange(n)]
bigN = 0defbfs(cnt, dequeA, visited):
bigN=1while dequeA:
yy, xx, _ = dequeA.popleft()
visited[yy][xx] = Truefor i inrange(4):
nx=xx+dx[i]
ny=yy+dy[i]
if ny<0or nx<0or ny>=n or nx>=m:
continueif visited[ny][nx]==Trueor tmp[ny][nx]==0:
continueif tmp[ny][nx]>=1and 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 inrange(n):
for j inrange(m):
if tmp[i][j] == 1and visited[i][j] == False:
dequeA.append([i,j, 1])
cnt+=1
cnt, bigN = bfs(cnt, dequeA, visited)
tmp3.append(bigN)
check =1print(cnt)
if n == 0and m ==0or 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 inrange(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 inrange(n):
tmp2=input().split()
tmp.append(tmp2)
print(tmp)
