알고리즘

MST문제 PRIM을 사용했고, 그중 가장 큰 경로를 삭제해주면 두개의 마을(그래프)로 분할된다는 점을 이용했다. import heapq import sys input=sys.stdin.readline n,m=map(int,input().split()) route=[[] for _ in range(n+1)] vis=[0 for _ in range(n+1)] for _ in range(m): a,b,c=map(int,input().split()) route[a].append((c,b)) route[b].append((c,a)) cost=0 maxcost=0 heap=[(0,1)] cnt=0 while heap: if cnt==n: break nowcost,now=heapq.heappop(heap) if v..

생각보다 어려웠던 문제 두개를 정렬해서 하려고 했다. 하나의 첫번째 인덱스에 해당하는 값을 다른 리스트에서 찾고, 그 위치 이후에 있는 값을 outarr에 저장해서 n-len(outarr)를 하려고 했다. import sys input=sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) l=[] for _ in range(n): l.append(list(map(int,input().split()))) l.sort(key=lambda x:x[0]) seoryu=l[:] stop=l[0] l.sort(key=lambda x:x[1]) myeongeop=l[:] mtop=l[0] outarr=[] for x in range(n): if my..

숫자라기보다 정말 높이라고 생각하고, 그림을 그려보아서 빠르게 접근할 수 있었던 문제. 정렬되었을 때, 높이차가 가장 안나게 하려면 현재 통나무 인덱스의 다음다음번째 인덱스를 옆으로 가져와야 한다. 다만 갑자기 max쓸지, min쓸지 하다가 좀 헤맸다. t=int(input()) for _ in range(t): m=0 n=int(input()) l=list(map(int,input().split())) l.sort(reverse=True) for x in range(n-2): m=max(m,abs(l[x]-l[x+2])) print(m)

사용시간과 마감시간을 리스트에 입력받아서, 마감시간 기준으로 오름차순 정렬을 해준다. 해당 마감시간 이전에 해당하는 사용시간들을 모두 더해서 마감시간보다 큰지 비교하고, 크다면 -1을 반환하고 프로그램을 종료한다. 그렇지 않다면, 마감시간에서 사용시간을 빼서 최소값에 저장한다. 최소값을 출력한다. n=int(input()) m=float('inf') l=[] for _ in range(n): t,s=map(int,input().split()) l.append([t,s]) l.sort(key=lambda x:x[1]) for x in range(len(l)): S=l[x][0] for y in range(x): S+=l[y][0] if l[x][1]

s=input() l=[] ret=[] start=0 for x in range(len(s)): if s[x]==':': l.append(s[start:x]) start=x+1 l.append(s[start:]) for x in l: if len(x)==4: ret.append(x) elif len(x)==3: ret.append('0'+x) elif len(x)==2: ret.append('00'+x) elif len(x)==1: ret.append('000'+x) else: ret.append('') tmp=[] for x in range(len(ret)-1): if ret[x]=='': t=9 if ret[x+1]=="": t=10 for i in range(t-len(ret)): tmp.appen..

간단하게 해결했다. 일단 팰린드롬을 체크해야하는데, 문제에서 붙이는 문자열은 무조건 뒤에 붙으므로 맨 뒤의 문자열과 동일한 문자를 갖는 인덱스들로 부터 팰린드롬 체크를 시작한다. 그리고, while s[i]==s[j]로 하나씩 인덱스를 좁히며 (i+=1, j-=1) i==j인 경우나, 예시 ) abcba i>j인 경우, 예시) abaaba 팰린드롬 문자열이므로 시작문자열의 인덱스+총 문자열의 길이를 출력해주었다. s=input() i=0 cnt=0 length=len(s) for x in range(length): j=length-1 ck=0 if s[x]==s[j]: i=x while s[i]==s[j] and i=j: print(x+length) exit()

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