백준

정말 쉽지 않았던 문제 뭔가 새로운 방법을 얻은 것 같다. 새로 리스트를 만들어서 재귀시켰더니 메모리 초과가 났다. 그래서 q의 길이를 줄이면서 q를 진행시켰다. from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs(x, y): q.append([x, y]) c[x][y] = 1 while q: qlen = len(q) while qlen: x, y = q.popleft() for i in range(4): X = x + dx[i] Y = y + dy[i] if 0

미로 찾기 + A같은 느낌... 처음에는 dfs를 통해 계속 고르는 개수를 증가시키면서 해결하려고 했으나 결국은 검은 방도 모두 탐색해야하므로, 흰방을 모두 탐색한 뒤에, 검은방 탐색시키면 됐었던 문제. 그래서 흰방은 append를 해줬고, 검은 방은 appendleft를 해주었다. 결국은 bfs의 bfs. 였다. 탐색에 대한 생각을 다시한번 하게 해줬던 문제. #https://www.acmicpc.net/problem/2665 from collections import deque def bfs(x,y): dx=[-1,1,0,0] dy=[0,0,-1,1] q=deque() q.append((x,y)) while q: x,y=q.popleft() for i in range(4): X=x+dx[i] Y=y+..

바보같이 코드 짜서 괜히 엄청 해맸던 문제 일단 한 점의 색깔을 임의로 지정하고, 인접한 점들을 모두 변경해줘야 하기떄문에 dfs보다는 bfs가 나을 것이다. 그래서 코드를 짰는데, 바보처럼 bfs(1)을 실행시켰다. 이러면 1이 독단적으로 떨어져 있는 경우, 코드가 실행이 안된다. 괜히 keyError가 나서 도대체 뭐지 싶었다. 정답코드 #https://www.acmicpc.net/problem/13265 import sys from collections import deque input=sys.stdin.readline def bfs(start): global impossible q=deque() if vis[start]=="B": origin="B" op="W" else: origin="W" op..

백트래킹 문제. dfs로 돌려서 경로를 s에 튜플 형태로 모두 저장했다. 그 후에 s를 set으로 바꿔서 중복을 제거하고 갯수를 세어주면 오케이 #https://www.acmicpc.net/problem/17255 from collections import deque def dfs(start,end,res): vis=deque(res[-1]) if len(vis)==len(l): s.append(tuple(res)) return if start-1>=0: vis.appendleft(l[start-1]) res.append(tuple(vis)) dfs(start-1,end,res) vis.popleft() res.pop() if end+1

상당히 어려웠다. 합을 기록해서 뺀 것과 비교한다는 것을 떠올리기 너무 힘들었다. a+b+c=d라는 식에서 a+b=d-c를 유도해서 풀어야 했다. 그러면 수를 3개만 골라도 되기때문에 O(N^3)으로 풀 수 있다. #https://www.acmicpc.net/problem/2295 n = int(input()) u = set() ans=[] for i in range(n): u.add(int(input())) sums = set() for i in u: for j in u: sums.add(i + j) for i in u: for j in u: if (i - j) in sums: ans.append(i) ans.sort() print(ans[-1])

생각보다 많이 어려웠던... 상상도 못했던 방법으로 해결했던 문제 처음 풀이는 재귀로 했더니 시간복잡도때문에 시간초과가 발생했다. def do(rest,ans,start): mmax=0 ch=0 if rest==0: return ans else: for x in range(start,len(num)): if x+rest

복잡하지만 꼼꼼히 잘 작성해 주면 됐던 문제 마지막에 good을 추가로 출력해주면서, 반례를 잡아주었다. import heapq from collections import deque n=int(input()) line=deque() heap=[] stack=[] #대기줄 for _ in range(n): l=list(map(str,input().split())) for x in l: a,b=x.split('-') b=int(b) heapq.heappush(heap,[a,b]) line.append([a,b]) while heap: target=heapq.heappop(heap) while line: x=line.popleft() if x!=target: if stack: y=stack.pop() if y..

사과와 뱀은 matrix와 visited(덱)에 기록하고, 시간은 힙에 넣어서 보관했다. 방향 계산을 떠올리기 힘들었던 문제 from collections import deque import heapq def change(d, c): if c == "L": d = (d - 1) % 4 else: d = (d + 1) % 4 return d def start(): direction = 1 time = 1 y, x = 0, 0 visited = deque([[y, x]]) matrix[y][x] = 2 if times: ftime=heapq.heappop(times) else: ftime=[] while True: y, x = y + dy[direction], x + dx[direction] if 0

뒤에 들어온 문장부터 확인해서 문자열 리스트에 추가해부고, 겹치는게 하나도 없다면 c만큼 출력하고, 겹치는게 있을때마다 c값을 하나씩 깎아내면 된다. 중복 유무는 딕셔너리로 확인해주었다. r,c=map(int,input().split()) table=[] for _ in range(r): l=list(input()) table.append(l) cnt=r-1 strlist=['' for _ in range(c)] while table: li=table.pop() ch={} k=0 for x in range(c): if ch.get(strlist[x]+li[x]) is None: strlist[x]=strlist[x]+li[x] ch[strlist[x]]=1 else: strlist[x]=strlist[x..

생각보다 까다로웠던 문제 import heapq n=int(input()) m=[] for _ in range(n): m.extend(list(map(int,input().split()))) reverse_sign = lambda x: x*-1 m=list(map(reverse_sign,m)) heapq.heapify(m) for _ in range(n-1): heapq.heappop(m) print(-heapq.heappop(m)) 이렇게 모든 수를 힙에 집어넣고, 출력했더니 메모리 초과가 났다. 이유는 int가 32비트이기 때문이다. 32*1500*1500/1000000 = 72MB이기때문이다. 그래서 힙을 n개로 유지했다. import heapq n=int(input()) heap=[] for _ ..