본문 바로가기
728x90

BOJ10

[백준/BOJ] 4233번 - 가짜 소수 (Python) 문제링크 https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net 1. 핵심 1) 10억 이상 소수 판정 - 에라토스테네스의 체로는 10억 이상의 소수 판정 불가능 - 소수 판정 하는 방법: 제곱근까지 나눠서 확인하기 2) 비트연산을 활용한 거듭제곱 2. 코드(Python) # https://www.acmicpc.net/problem/4233 # 소수 구하기 def isPrime(n): for i in range(2, i.. 2023. 11. 2.
[백준/BOJ] 27172번 - 수 나누기 게임 (Python) 문제링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 1. 핵심 1) 유형 DP: [@+작은 팰린드롬+@] 작은 팰린드롬 양쪽의 @만 확인해서 더 큰 팰린드롬 [@+작은 팰린드롬+@] 인지 확인 2) 왜 reversed(range(n))을 할까? IF. reveresed가 아니라 range(n)을 생각해보자. → 인덱스의 범위가 (0, x)가 팰린드롬을 확인하기 위해서는 작.. 2023. 10. 28.
[백준/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.
728x90
반응형

티스토리툴바