CS

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..

고등학교때 풀던 신발끈 공식으로 풀었다. 현우진 센세 미안 ㅋㅋ 그래도 신발끈은 신인걸 ㅋㅋ n=int(input()) l=[] for _ in range(n): l.append(list(map(int,input().split()))) l.append(l[0]) plus=0 minus=0 for x in range(n): plus+=l[x][0]*l[x+1][1] minus+=l[x][1]*l[x+1][0] S=abs(plus-minus)/2 print(round(S,2))

옛날에 풀었던 문제 두 번 정렬해서 해결했다. n=int(input()) li=[] for _ in range(n): a,b=map(int, input().split()) li.append([a,b]) cnt=1 li.sort(key=lambda x:x[0]) li.sort(key=lambda x:x[1]) time=li[0][1] for i in range(1,n): if li[i][0]>=time: cnt+=1 time=li[i][1] print(cnt)

생각보다 어려웠던 문제 두개를 정렬해서 하려고 했다. 하나의 첫번째 인덱스에 해당하는 값을 다른 리스트에서 찾고, 그 위치 이후에 있는 값을 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..

슬라이딩 윈도우를 응용하는 문제지만 브루트포스로 해결... 굳이 문자열을 직접 바꿔줄 필요없이, 바꿔야 하는 문자열을 찾는다는 개념이었다. 우선 a의 갯수를 찾고, 그에 따라 브루트포스를 한다. a의 갯수만큼 증가시키면서 만약 문자열 길이를 넘어가는 경우 모듈러 연산을 통해 처음 인덱스로 보내준다. 이렇게 처음부터 끝까지 찾으면 모두 탐색했으므로, 이 중 b의 최소값을 출력한다. s=input() n=len(s) acount=0 m=999999999999999999999999 for x in range(n): if s[x]=='a': acount+=1 for i in range(n): bcnt=0 plus=1 while plus

간단하게 해결했다. 일단 팰린드롬을 체크해야하는데, 문제에서 붙이는 문자열은 무조건 뒤에 붙으므로 맨 뒤의 문자열과 동일한 문자를 갖는 인덱스들로 부터 팰린드롬 체크를 시작한다. 그리고, 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()

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]!..