알고리즘

힙을 사용했다. 근데 동시에 가져올때 상민이 것(B)가 먼저 나와야하므로 임시 배열에 저장한 다음, B인 것 부터 힙에 넣어줬다. import heapq heap=[] tmpl=[] B=[] R=[] a,b,n=map(int,input().split()) for _ in range(n): t,c,m=map(str,input().split()) t=int(t) m=int(m) time=t first=1 for _ in range(m): if not first: if c=='B': time=time+a elif c=='R': time=time+b tmpl.append([time,c]) first=0 for x in tmpl: if x[1]=='B': heapq.heappush(heap,x) for x in ..

오랜만의 DFS 무엇을 리스트와 딕셔너리에 저장할지 고민하는데 시간이 많이 걸렸다. 중요한 건 " 환승 "이다. 따라서 환승 못하는 역들에 대해서는 굳이 dfs연산을 할 필요가 없다. 환승 할 수 있는 것들은 h[x]의 길이가 2보다 크다. 이것들에 대해서만 dfs연산을 진행했다. def dfs(start, dest,cnt): havetogo=[] for x in route[start]: if x==dest: return cnt if len(h[x])==1 and x not in vis: #환승 못하는 것들 vis.append(x) else: if x not in vis: vis.append(x) havetogo.append(x) for x in havetogo: return dfs(x, dest,cnt..

처음에는 슬라이싱과 집합을 생각하지 못해서 시간초과가 났다. import sys sys.stdin.readline s=input() chk={} res=[] for x in range(len(s)): l=[] for i in range(len(s)-x): l.append(s[x+i]) if chk.get(''.join(t for t in l))!=1: res.append(''.join(t for t in l)) chk[''.join(t for t in l)]=1 print(len(res)) 집합을 쓰면 딕셔너리를 안써도 된다. import sys sys.stdin.readline s=input() res=set() for x in range(len(s)): for y in range(x, len(s)):..

실버 3에 40분을 태워? 자료구조는 너무 어렵다. 배워야 할게 산더미다. 스택과 딕셔너리를 통해 해결했다. 딕셔너리를 통해 스택에 그 값이 있는지 체크하고, pop을통해 출력한다. 열받는점은 k개 출력할려고 했는데 k보다 작은 값을 출력할 때의 테스트 케이스가 들어가있어서 런타임 에러가 뜬다는 것이다. #https://www.acmicpc.net/problem/13414 import sys input=sys.stdin.readline d=[] stack=[] check={} k,l=map(int, input().split()) now=0 for _ in range(l): n=input().rstrip() d.append(n) while d: tmp=d.pop() if check.get(tmp)!=1: ..

자료구조 종합세트 stack, heap, deque까지 쓸려고 했으나 deque은 못썼다. 첫 생각에 덱을 사용해서 앞에서 빼서 뒤로 넣는 순환을 만들려고 했는데 반복문으로 쉽지 않았다. 그래서 넘기는 배열을 따로 선언해주고 stack을 넘겨 비교를 통해 해결했다. 시간을 너무 많이 썼다. 아직 많이 부족하다. #우선 순위 숫자가 높은게 먼저 적재, 낮은 건 나중에 적재 #우선순위가 같으면 무게 무거운 것 먼저 적재. import heapq import sys limit_number = 15000 sys.setrecursionlimit(limit_number) def cal(stack,l,std): global cost next=[] for x in l: if x[0]==std: priority[std]..

def do(l): l[0]=l[0]+l[1] l[1]=l[0] n,m=map(int, input().split()) l=list(map(int, input().split())) for x in range(m): l.sort() do(l) print(sum(l)) 정렬을 이용하면 매우 쉽게 풀 수 있다. 그러나 heap을 사용해서 풀어보자. import heapq n,m=map(int, input().split()) l=list(map(int, input().split())) heapq.heapify(l) for _ in range(m): tmp=heapq.heappop(l)+heapq.heappop(l) heapq.heappush(l,tmp) heapq.heappush(l,tmp) print(sum(l..

입력받은 문자열에서 x개 떨어진 문자열을 붙여서 result에 저장한다. result 다음값에 저장되는 값부터 끝까지 리스트와 비교해서 그 값이 안에 존재한다면 놀랍지 않은 문자열이므로 check를 0으로 바꿔준다. while (1): l=input() if l=='*': break check=1 for x in range(1,len(l)): result=[] for y in range(len(l)): if y+x

최근 느낀점이 나는 자료구조를 완전히 이해하지 못했다는 점이다. 그래서 당분간은 자료구조에 대한 문제만 풀 생각이다. 처음에는 리스트를 통해 해결하려고 했으나, 리스트 조회에 시간이 많이 걸려서 실패했다. 문제를 통해 배운점은 딕셔너리.get(key)를 통해 값을 구할 수 있다는 것이다. 이렇게 접근하게 되면 없는 키값을 입력해도 오류가 발생하지 않는다. 그래서 이를 이용한 것이 max(딕셔너리, key=딕셔너리.get)인데 이를 통해 key값중 최고 값을 구할 수 있다. import sys input=sys.stdin.readline n=int(input()) for _ in range(n): d=dict() land=list(map(int, input().split())) check=0 for x i..

https://0422.tistory.com/104 1967 백준 파이썬 이 문제를 풀려면 어떤 임의의 점에서 가장 많이 떨어진 점은 지름의 한 점에 해당한다는 점을 알고 있어야 한다. 그림을 통해 보면 원 내부의 직선에서 어떤 점을 잡든, 그 점에서 가장 먼 점은 0422.tistory.com 이전 게시글과 거의 똑같은 유형의 문제. 해설은 전 게시글과 동일하기에 쓰지 않겠다. 다만, 차이점은 이전 문제는 BFS로 해결했다면, 이번 문제는 다익스트라로 해결했다. import heapq INF=int(1e9) def dik(start): heap=[] distance=[INF for _ in range(n+1)] distance[start]=0 heapq.heappush(heap,(start,0)) wh..

이 문제를 풀려면 어떤 임의의 점에서 가장 많이 떨어진 점은 지름의 한 점에 해당한다는 점을 알고 있어야 한다. 그림을 통해 보면 원 내부의 직선에서 어떤 점을 잡든, 그 점에서 가장 먼 점은 원의 지름의 한 끝에 해당하는 점이 된다. 그리고, 그 점에서 가장 먼 점을 찾아 연결하면 그것이 바로 원의 지름에 해당한다. 따라서 이런 트리가 있다고 가정해 보자. 이 노랑색 루트 노드에서 가장 먼 점은 빨강색 노드이다. 그리고 빨강 노드에서 가장 멀리 떨어진 점을 찾는다. 이게 바로 파란색 점이다. bfs를 통해 해결했다. 다익스트라를 통해 해결해도 문제 없을 것 같다. from collections import deque n=int(input()) tree=[[] for _ in range(n+1)] for..