728x90 PS/백준15 [백준/BOJ] 14621번 - 나만 안되는 연애 (Python) 문제링크 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 1. 핵심 알고리즘 유형: 최소 스패닝 트리 크루스칼 알고리즘 성별이 다른, 남자대학교와 여자대학교만 연결되어야 한다. 남-남, 여-여끼리 간선이 연결되면 안된다. 2. 코드(Python) def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent.. 2023. 10. 21. [백준/BOJ] 27172번 - 수 나누기 게임 (Python) · 문제링크 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net · 핵심 : 약수 + 시간복잡도 → 문제 요약 : 내가 다른 수를 나눠서 나머지가 0이면 +1 득점, 나뉘어진 수를 가진 상대방은 -1 감점 1. 시간복잡도 계산 → 바로 떠오르는 풀이는 이중 for문 써서 전부 확인하는 방법 → N = 100,000이므로 이중for문 사용하면 반드시 시간초과 발생 2. 약수 구하기 → 제곱근까지만 확인하기 : 시간복잡도 O(N^(1/2)) 3. +1 과 -.. 2023. 10. 17. [백준/BOJ] 1005번 - ACM Craft (Python) · 문제링크 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net · 핵심 : 위상 정렬 + DP · 코드(Python) # https://www.acmicpc.net/problem/1005 t = int(input()) for _ in range(t): N, K = map(int, input().split()) adj = [[] for _ in range(N + 1)] ind = [0 for _ in range(N + 1)] dp = [0 f.. 2023. 9. 30. [백준/BOJ] 2623번 - 음악프로그램 (Python) · 문제링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net · 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」 1. 방향성이 존재하는 그래프 생성 & 들어오는 간선 수 기록 → 3 1 4 3 → 3 : 가수의 수, 1 4 3 : 가수의 번호 → 1 - 4 / 4 - 3 으로 그래프 연결 2. in-degree = 0인 후보들 적절한 자료구조(리스크, 큐, 스택, 힙 등)에 넣기 3. candiates가 전부 비.. 2023. 9. 29. [백준/BOJ] 1347번 - 미로 만들기 (Python, Java) · 문제링크 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net · 핵심 1. 시작점이 설정되어있지 않다. → 명령어의 최대 길이는 50이므로 넉넉하게 아주 큰 board를 생성하고 적절한 시작점을 임의로 설정한다. → max_n = 200, cr = max_n // 2 , cc = max_n // 2 2. 큰 board에서 이동한 영역을 추출하기 → 도착을 1로 표시 → 사각형을 추출하기 위해서 1이 존재하는 (행, 열)들 중에서 min_r, .. 2023. 9. 25. [백준/BOJ] 2252번 - 줄 세우기 (Python, Java) · 문제링크 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 · 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」 1. 방향성이 존재하는 그래프 생성( 무방향성 그래프, 사이클 있는 그래프의 경우 위상정렬이 쉽지 않음) → adj 그래프 생성 ☆ 2. 들어오는 간선의 수 기록 → 위상정렬에서는 in-degree = 0인 후보군(candiates)을 문제 조건에 부합한 특정 자료 구조(리스트,.. 2023. 9. 25. 이전 1 2 3 다음 728x90 반응형
