CS/백준 풀이

자료구조 종합세트 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..

입력을 받은뒤에 리스트를 정렬하고, 작은 것 4개까지 꺼내어 비교하여서 result에 집어넣는다. result를 정렬 한 뒤에 3번째(2번째 인덱스에 추가한다.) n=int(input()) l=[] result=[] for _ in range(n): l.append(int(input())) l.sort() cnt=0 miin=0 result=[] for x in l[:4]: for y in l[:4]: if x!=y: tmp1=int(str(x)+(str(y))) result.append(tmp1) result.sort() print(result[2])

입력받은 문자열에서 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..

최근 알고리즘을 너무안했다... 그래서 하는 재활운동. 파이썬 하다가 C하다가 다시 파이썬 하니 같은 문제를 봐도 뭔가 더 어렵게 느껴지는 것 같다. 간단한 dfs문제다. def dfs(x,y,number): if len(number)==6: if number not in result: result.append(number) return dx=[-1,1,0,0] dy=[0,0,-1,1] for i in range(4): X=x+dx[i] Y=y+dy[i] if 0

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

순열 모듈을 이용해서 해결했다. 그 후에는 집합을 통해서 중복을 제거하고, 그 뒤에 정렬을 해준다. from itertools import permutations n,m=map(int,input().split()) num=list(map(int,input().split())) num=(list(set(permutations(num,m)))) num.sort() for x in num: for t in x: print(t,end=" ") print()

별거 없는 다익스트라 문제. 하는김에 다익스트라를 복습해 보자. 다익스트라는 시작점으로부터 어떤 도착점 까지의 최단 거리를 구하는 알고리즘이다. 그래서 g라는 리스트에 가는데 걸리는 (시간,목적지)를 저장한다. 그리고 다익스트라 함수안에서 distance라는 리스트를 만든다. 여기에다가 최단 거리를 갱신해 줄 것이다. 최단거리를 갱신해야 하므로 int(1e9)로 선언한다. 그 후에 힙을 만들어서 cost와 start를 넣어준다. 그리고 힙에 저장된 것이 없을 때 까지 cost, now를 꺼내어서 비교한다. 이때, 저장된 cost가 distance[now]보다 크면 더이상 볼 필요가 없으므로 넘어간다. 그렇지 않다면, g[now]에 있는 리스트들을 반복시킨다. g[now]는 cost와 목적지로 저장되어 있..