백준

최근 알고리즘을 너무안했다... 그래서 하는 재활운동. 파이썬 하다가 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와 목적지로 저장되어 있..

DFS로 해결했다. p라는 리스트에 진실을 아는 사람 번호를 넣는다. stack에 p리스트를 복사해서 넣는다. p배열에 있는 값들의 vis값을 1로 바꿔주고, stack에서 하나씩 꺼내어 party 리스트의 한줄씩 골라 비교한다. 비교했을때, party 리스트의 한 줄 안에 stack에서 꺼낸 값이 있으면, stack에 party리스트 안의 값(r)을 추가하고, p리스트에도 추가한 뒤에 vis[r]=1한다. 이렇게 되면 마지막에는 p값에 파티를 통해 진실을 알게된 모든 사람이 담기게 된다. 이를 다시 한번 party리스트와 비교하여 되는 리스트만 뽑아주면 되겠다. n,m=map(int,input().split()) p=list(map(int,input().split())) party=[] for x in..

처음에 풀때는 그 전 문제가 재귀여서 그런지 재귀로 풀었다. import sys s=list(sys.stdin.readline().rstrip()) bomb=list(sys.stdin.readline().rstrip()) def check(a,bomb): d = [] col=len(bomb) row = len(a) for x in range(row): if a[x]==bomb[0] and x+(col-1)

지문이 길어서 찾아보고 한다고 이해하는데 반나절은 걸린듯한 문제. 요약하면 a*b^(-1) = a*b^(X-2)%1000000007이므로 a*b^(X-2)%1000000007를 시간 안에 해결해야 하는 문제다. 재귀로 해결했다. S=1000000007 def ans(n,s): return s*mul(n,S-2)%S def mul(b,t): if t==1: return b%S if t%2==0: tmp=mul(b,t//2) return (tmp*tmp)%S else: return b*mul(b,t-1)%S SUM=0 m=int(input()) for _ in range(m): n,s=map(int,input().split()) SUM+=ans(n,s) SUM%=S print(SUM)

행렬 곱셈 이해하는데 시간이 걸렸던 문제... 교육과정에 행렬이 없어서 마주했을때 당황했다. 1 2 3 4 를 제곱했는데 왜 저렇게 되지? 이 생각을 했다. 이 문제를 통해 알 수 있었던 것은 나는 반복문 이해도가 꽤나 떨어지는 편이라는 것이다. 2중까진 가능한데 3중부터 영 별로다. 그래서 플로이드 와샬도 거의 암기식으로 외웠다가 최근에 왜 경유점이 반복문 밖에 존재하는지 이해했다. 분할 정복을 통해서 해결했다. n,t=map(int,input().split()) orgin=[] for _ in range(n): orgin.append(list(map(int,input().split()))) def multiple(m1,m2): res=[[0 for _ in range(n)] for _ in range..

dp지만 4MB 메모리 제한이 있다. dp 배열을 선언하려면, 아니 애초에 입력한 값을 배열에 등록하려면 n의 제한이 100,000까지이므로 4*3*100,000byte가 필요하다. 이건 12MB이므로 진작에 메모리 초과가 일어난다. 3개짜리 배열을 선언해서 해결했다. import sys input = sys.stdin.readline n = int(input()) maxdp=[0,0,0] mindp=[0,0,0] tmp1=[0,0,0] tmp2=[0,0,0] for _ in range(n): a,b,c=map(int,input().split()) for x in range(3): if x==0: tmp1[0]= a+ max(maxdp[x],maxdp[x+1]) tmp2[0]= a+ min(mindp[x..