백준
-
[Python] 백준 14567 선수과목알고리즘/문제풀이 2021. 12. 15. 17:31
1. 문제 링크 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 2. 문제 요약 1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지 출력한다. 3. 아이디어 정리 위상 정렬 진입 차수가 0인 모든 노드에 큐 넣기 큐가 빌 때까지 반복 큐에서 원소를 꺼내 나가는 간선 제거 새롭게 진입차수가 0이 된 노드에 큐 넣기 & 결과 넣기(최소 이수 학기, 현재 노드 결과 + 1) 4. 문제 풀이 4-1. 내풀이 import sys from collections ..
-
[Python] 백준 15656 N과 M (7)알고리즘/문제풀이 2021. 12. 12. 12:43
1. 문제 링크 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 문제 요약 N개의 자연수 중 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 3. 아이디어 정리 증가하는 순서 출력이므로 정렬을 진행한다. 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건 같은 수 여러 개 가능하기 때문에 for 문에 조건을 없이 넣는다. 4. 문제 풀이 4-1. 내 풀이 import sys def dfs(list_): if len(l..
-
[Python] 백준 21921 블로그알고리즘/문제풀이 2021. 11. 27. 21:28
1. 문제 링크 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 2. 문제 요약 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는가 3. 아이디어 정리 누적합을 먼저 구한다. 슬라이딩 윈도우로 특정 기간 동안 최대 값인 경우 방문자 수와 기간을 갱신한다. 4. 문제 풀이 4-1. 내 풀이 n, x = map(int, input().split()) # 블로그 일수, x일 동안 가장 많이 들어온 방문자 arr = list(map(..
-
[Python] 백준 12865 평범한 배낭알고리즘/문제풀이 2021. 11. 27. 21:22
1. 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 문제 요약 3. 아이디어 정리 3-1. 냅색 문제 개념 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. dp[i][j] = max(현재 물건 가치 + dp[이전 물건][현재 가방..
-
[Python] 백준 13975 파일 합치기 3알고리즘/문제풀이 2021. 11. 26. 17:10
1. 문제 링크 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 2. 문제 요약 두 개의 파일을 계속 합하여 최종적으로 하나의 파일을 완성하는데 필요한 비용의 총합을 구한다. 3. 아이디어 정리 우선순위 큐 최소힙을 이용하여 가장 작은 2개의 파일을 얻는다. 두 파일을 합하여 다시 최소 힙에 넣고 파일이 1개가 될 때까지 진행한다. 4. 문제 풀이 4-1. 내 풀이 import sys import heapq for _ in range(int..
-
[Python] 백준 4358 생태학알고리즘/문제풀이 2021. 11. 26. 16:55
1. 문제 링크 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 2. 문제 요약 나무의 종이 전체 몇 %를 차지하는지 구하기 3. 아이디어 정리 defaultdict를 이용하여 모든 dict 값이 0으로 세팅 입력된 값 + 1을 해준다. 나무의 종이 차지하는 비율을 출력한다. 4. 문제 풀이 4-1. 내풀이 import sys from collections import defaultdict dict_ = defaultdict(int)..
-
[Python] 백준 1476 날짜계산알고리즘/문제풀이 2021. 11. 3. 13:56
1. 문제 링크 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 2. 문제 요약 몇 년인지 구하는 문제 3. 아이디어 정리 단순 구현 4. 문제 풀이 4-1. 내 풀이 E, S, M = map(int, input().split()) # 지구, 태양, 달 ne, ns, nm = 1, 1, 1 ans = 1 while True: if ne == E and ns == S and nm == M: break ne += 1 ns += 1 nm += 1 ans ..
-
[Python] 백준 17086 아기 상어 2알고리즘/문제풀이 2021. 10. 30. 00:17
1. 문제 링크 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 2. 문제 요약 안전거리 최댓값 구하기 3. 아이디어 정리 bfs 탐색을 통해 최단 거리 구하기 4. 문제 풀이 4-1. 내 풀이 import sys from collections import deque dx = [-1, -1, -1, 0, 1, 0, 1, 1] dy = [-1, 0, 1, 1, 1, -1, 0, -1] n, m = map(int, sy..