알고리즘(python)/정렬 검색 결과
13 개의 검색 결과가 있습니다.
알고리즘(python)/정렬

[Python]위상정렬 백준 1766

문제 https://www.acmicpc.net/problem/1766 위상정렬읠 하는것은 동일하다. 위상정렬의 특성상 따라 여러가지 출력값을 가질수 있다. 이 문제는 한가지 값만 나올수 있도록 조건이 있다.쉬운 문제를 먼저 즉 진입차수가 0일때도 순서가 있다.최소힙을 이용하여 가장 쉬운(문제 번호가 작은) 문제부터 출력 할수 있도록 해주면 된다. 1234567891011121314151617181920212223242526272829303132import sysimport heapq N,M=map(int,sys.stdin.readline().split())tree=[[] for _ in range(N+1)]inDegree=[0 for _ in range(N+1)] q=[]#문제 순서for _ in ra..

2020. 4. 14. 14:45
알고리즘(python)/정렬

[Python]위상정렬 백준 1005

문제 https://www.acmicpc.net/problem/1005 동적계획법을 적용하여 구하는 위상정렬이다.위상 정렬에서 큐에서 값들을 뺄때 진입차수 뿐만 아니라 이전 건물까지 걸리는 시간+이번 건물을 짓는 시간과 이전 DP값을 비교하여 더 오래 걸리는시간으로 갱신해주면된다. 해당 건물이 지어지기위해서는 앞에 지어질 건물들의 걸리는 시간들 중에서 가장 긴 시간에 맞춰주어야 모든 건물을 짓고 해당 건물을 지을 수 있기 때문이다. 1234567891011121314151617181920212223242526272829303132333435import sysfrom collections import deque T=int(sys.stdin.readline()) for _ in range(T): N,K=ma..

2020. 4. 14. 01:11
알고리즘(python)/정렬

[Python]위상정렬 백준 3665

문제 https://www.acmicpc.net/problem/3665 순위를 간선으로 표현하여 위상정렬을 할 때 각 순서를 이어주는것 만으로는 불충분하다.5 4 3 2 1이런 순서가 있다고 할때5->44->33->22->1이렇게만 만들어주면 안된다.위상정렬을 할 수 있도록5->35->25->14->24->13->1위의 간선도 만들어 주어 진입차수표가 아래처럼 만들어지도록 간선을 추가해야된다.team 5 4 3 2 1indegree 0 1 2 3 4 이렇게 만들어주면 이제 변한 순위의 간선들을 스왑해주면 된다.22 43 4라면4->24->3으로 바꾸어주고 진입차수표를 갱신시켜준다.이전 진입차수표에서 2,3의 진입차수를 1씩 줄여주고 4의 진입차수를 2늘려주면된다.변경된 순위에 따라 갱신된 간선과 진입차수..

2020. 4. 13. 10:47
알고리즘(python)/정렬

[Python]위상정렬 백준 2252

문제 https://www.acmicpc.net/problem/2252 위상정렬이란?어떤 일을 하는 순서를 찾는 알고리즘이다.아래 사이트를 참고하였다.https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html위상정렬은 다양한 답을 가질수 있으며 사이클이 포함되어있다면 위상정렬은 불가능하다.원리는 진입차수를 이용하여 진입차수가 0인 노드를 큐에 넣어주고 큐를빼면서 연결된 노드의 진입차수를 갱신한다. 이때 진입차수가 0이된다면 해당노드를 큐에 넣어주는 방식으로 큐가 빌때까지 반복해주면 된다.만약 사이클이 있다면 진입차수가 0이하로 내려가게 된다. 1234567891011121314151617181920212223242526272829303..

2020. 4. 12. 21:46
알고리즘(python)/정렬

[Python]정렬 백준 10814

문제 https://www.acmicpc.net/problem/10814 이문제에서 나이가 같으면 가입순 즉 안정 정렬이 필요하다는것을 알수있다.https://hellowoori.tistory.com/48정렬의 마지막 문제이기도 하니 각 정렬에대한 특징들을 알필요가 있을거 같아서 찾아봤다.코드는 stable(안정) 정렬인 병합정렬을 사용하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import sys n=int(sys.stdin.readline())group_list=[] while n>0: n-=1 age,name=sys.stdin.readline().spl..

2020. 1. 2. 17:15
알고리즘(python)/정렬

[Python]정렬 백준 1181

문제 https://www.acmicpc.net/problem/1181 각 단어의 길이를 비교 후 길이가 같다면 사전순으로 정렬하면된다.같은단어가 여러번일 경우 한번만 출력한다는 내용까지 잘읽고 출력하면된다.알파벳 소문자로만 이루어진 단어이기때문에 비교조건에 특별히 char형으로 바꾸어 비교할 필요는 없을거같다.정렬방법은 단어가 많지않아 기본정렬로도 가능할거 같지만 병합정렬을 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576import sys n=int(sys.stdin.readline(..

2020. 1. 2. 14:20