CS/백준 풀이

KMP알고리즘을 이용하는 문제 kmp알고리즘은 기본적으로 투포인터와 비슷한 맥락으로 풀이한다. 패턴부분의 접두사, 접미사의 길이를 구하고, 이를 통해서 문자열을 계산한다. s=input() p=input() #p의 접두사, 접미사 구하기 l=[0 for x in range(len(p))] i=1 j=0 while i0 and p[j]!=p[i]: j=l[j-1] if p[j]==p[i]: j+=1 l[i]=j i+=1 j=0 for i in range(len(s)): while (j>0 and s[i]!=p[j]): j=l[j-1] if s[i]==p[j]: if j==len(p)-1: print("1") exit() else: j+=1 print("0") 위의 코드에서 while i0 and s[i]!..

정말 쉽지 않았던 문제 뭔가 새로운 방법을 얻은 것 같다. 새로 리스트를 만들어서 재귀시켰더니 메모리 초과가 났다. 그래서 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..

원래는 힙을 사용해서 풀려고 했으나... 도대체 무엇이 반례인지 모르겠지만 계속 틀렸다고 나와서 접근 방식을 바꿨다. 실패한 코드 import heapq n=int(input()) l=[] cnt=0 heap=[] for _ in range(n): x=int(input()) l.append(x) now=l[0] heapq.heappush(heap,now) for x in range(n): if now!=l[x]: now=l[x] heapq.heappush(heap,now) while heap: target=heapq.heappop(heap) for x in range(n): if l[x]==target: start=x break end=start for x in range(start,n): end=x i..

백트래킹 문제. 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