728x90 반응형 Python169 2022.02.17 [백준] (python 파이썬) 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 다음 문제는 위상 정렬을 사용하면 쉽게 해결할 수 있다. 이유는 각 비교 학생들을 앞에 서야 하는 학생 쪽으로 화살표를 그리면 진입 차수와 진출 차수를 알 수 있다. 그래서 진입 차수가 0이면 앞에 서야하는 학생이 없는 뜻이기 때문에 deque를 이용하여 진입차수가 0인 학생들을 result에 저장 후 출력했다. 이 때 각 학생의 진입 차수 즉 앞에.. 2022. 2. 17. 2022.02.16 [백준] (python 파이썬) 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 해당 문제는 위상 정렬을 사용하여 푸는 문제이다. 위상 정렬은 아래의 블로그에서 공부하고 코드를 작성했다. https://freedeveloper.tistory.com/390 [이것이 코딩 테스트다 with Python] 36강 위상 정렬 4https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5Y.. 2022. 2. 16. 2022.02.16 [백준] (python 파이썬) 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 이 문제를 3가지 조건으로 생각했다. 1. 카드더미가 1개만 들어왔을 경우 계산할 필요가 없으므로 바로break걸어서 0출력 2. 카드더미가 2이상일 경우 heap에서 최소값을 2개 뽑아서 더한 후, 더한 값을 다시 heap에 push하고, 더한 값을 ans에 더함. 3 카드더미가 2개일 경우 최소값2개를 뽑아 더한 후 ans에 출력. 그리고 while 문 끝남(2개남은 것을 .. 2022. 2. 16. 2022.02.16 [백준] (python 파이썬) Yonsei TOTO https://www.acmicpc.net/problem/12018 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 풀이 이 문제는 두개의 힙을 이용하여 해결했다. 1. 합격자와 불합격자를 담을 힙을 만든다. 2. Pass의 길이가 뽑는 인원보다 작으면 heappush해준다 3. Pass가 꽉찾으면 Fail에 heappush해준다. 이 때, (-i, i)로 저장해줌 (불합격자의 최고값과 합격자의 최저점을 비교하기 위해) 4. 합격자의 최저점이 불합격자의 최고점보다 작으면 두 값을 바꿔줌. 5. 각 수강.. 2022. 2. 16. 이전 1 ··· 28 29 30 31 32 33 34 ··· 43 다음 728x90 반응형
