본문 바로가기
728x90

PS91

[백준/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.
[코드트리 챌린지] 7주차 - 시뮬레이션(격자 안에서 단일 객체를 이동) 문제링크 https://www.codetree.ai/cote/13/problems/move-to-larger-adjacent-cell?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 상하좌우에 우선순위가 존재한다. 따라서 dr, dc 만들 때 순서를 주의한다. 가장 큰 숫자로 가는 것이 아니라 가장 큰 숫자가 여러개이면 우선순위가 높은 방향으로 이동한다. 따라서 우선순위에 맞게 dr, dc를 설정하고 나보다 더 큰 숫자가 있으면 다음 방향은 보지 않고 움직인다. simula.. 2023. 10. 23.
[백준/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.
[코드트리 챌린지] 6주차 - 시간최적화(Priority Queue) ★ 핵심 : Priority Queue는 우선순위가 있는 큐! 1. Java의 Priority Queue import java.util.PriorityQueue; public class Main { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); } } · Java에서의 PriorityQueue 는 기본적으로 최소 우선순위 큐 · 자주 사용되는 메서드 1) add() - 우선순위 큐에 데이터 추가 2) size() - 현재 우선순위 큐에 들어있는 데이터의 수 반환 3) isEmpty() - 비어있으면 true, 아니라면 false 4) peek() - 최솟값에 해당하는 데이터 반환 5) poll() - 최솟값.. 2023. 10. 16.
[코드트리 챌린지] 5주차 - 그래프 탐색(DFS) ★ 핵심 : DFS(깊이우선탐색) https://www.codetree.ai/cote/13/problems/seperate-village?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai · 핵심 1. 각 마을의 위치를 찾기 위해 전체 board영역에 이중for문 돌면서 '벽이거나 이미 방문한 곳'을 제외하고 DFS 진행 → global cnt 도입하는 대신 cnt(사람의 수)를 dfs 내에서 초기화하고 return값으로는 누적되는 cnt값 출력 → dfs 함수 종료되고 변수 cnt에 .. 2023. 10. 9.
728x90
반응형

티스토리툴바