본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 31218번 자료 구조의 왕 https://www.acmicpc.net/problem/31218 31218번: 자료 구조의 왕 흐즈로는 어느 날 집 주변 잔디밭에 무성히 자란 잔디를 보고, 새로 산 잔디깎이 로봇의 성능을 시험해 보기로 했습니다. 잔디밭은 $n$개의 행과 $m$개의 열을 가진 2차원 격자로 구성되어 있으며, www.acmicpc.net 24/01/10 실수할 수도 있는 구현 문제로, 생각 없이 구현하다가는 시간 초과를 받을 수도 있는 문제이다. 약간의 세심함이 필요한 문제다. 문제 접근 방식: 초반 접근 방식은 문제에서 요구하는 것 처럼 쿼리 1, 쿼리 2, 쿼리 3에 대한 함수를 각각 구현하여, 각 요청을 받을 때마다 해당 함수를 불러오는 방식으로 구현했다. 나이브하게 구현했더니 시간초과가 났다. 문제는 쿼리 3에..
[Python] 31217번 Y https://www.acmicpc.net/problem/31217 31217번: Y 첫 번째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 분리되어 주어집니다. ($1 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2},2\times 10^5)$) 두 번째 줄부터 $m$개의 줄에 $i$번째 간선이 연결하는 정 www.acmicpc.net 24/01/09 간단한 차 수열+조합론 문제이다. 좋은 문제라고 생각된다. 문제 접근 방식: Y 그래프의 중심이 되는 루트를 각각의 정점마다 생각해보자. 즉, 우리는 $1, 2, \cdots, N$번 정점까지 있을 때, $i$번 정점이 Y 그래프의 루트가 되는 경우를 $1$번 정점부터 $N$번 정점까지 모두 더하여 최..
[Python] 31216번 슈퍼 소수 https://www.acmicpc.net/problem/31216 31216번: 슈퍼 소수 소수는 수학을 사랑하는 누구에게나 매우 중요한 개념입니다. $1$보다 크면서 약수가 $1$과 자기 자신뿐인 자연수를 소수라고 부릅니다. 흐즈로는 소수 중에서도 더욱 특별한 소수가 있다고 생각 www.acmicpc.net 24/01/08 간단한 소수 판정 응용 문제다. 문제 접근 방식: 문제는 매우 간단하다. 소수를 오름 차순으로 나열하여 $k$번째 소수가 있을 때, 이 $k$가 소수라면 그 소수를 슈퍼 소수라고 한다. 우리의 목적은 $n$이 주어지면 $n$번째 슈퍼 소수를 찾는 것이 우리의 목적이다. 여기서 주어지는 $n$은 최대 $3,000$까지이다. $100$만 이하의 소수의 개수는 $78,498$개이므로, ..
[Python] 10978번 기숙사 재배정 https://www.acmicpc.net/problem/10978 10978번: 기숙사 재배정 N이 4인 경우, 봄학기 때 4명의 학생 (민수, 동화, 갑도, 석주)이 각각 기숙사 A,B,C,D에 배정이 되었다면, (민수-B, 동화-A, 갑도-D, 석주-C), (민수-B, 동화-C, 갑도-D, 석주-A), (민수-B, 동화-D, 갑도-A, 석주 www.acmicpc.net 23/12/08 단순 교란 순열 문제이다. 알면 매우 쉽게 해결할 수 있다. 문제 접근 방식: 그냥 문제를 보면 교란 순열의 개수를 구하는 것과 같음을 알 수 있다. 교란 순열에 대한 간략한 설명은 다음 링크를 참고하자. https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97..
[Python] 14503번 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 24/01/07 구현/시뮬레이션 문제로, 문제에서 요구하는 바를 그대로 구현하면 맞았습니다를 받을 수 있는 정직한 문제다. 문제 접근 방식: 이 문제를 접근할 때에 기존에 이렇게 $N \times M$형태의 map이 주어지고 이 위에서 BFS나 DFS를 진행하는 문제를 풀어봤다면 어떻게 접근할지 조금은 감이 잡힐 수 있을 것이다. 북, 동, 남, ..
[Python] 23630번 가장 긴 부분 수열 구하기 https://www.acmicpc.net/problem/23630 23630번: 가장 긴 부분 수열 구하기 $N$개의 자연수로 이루어진 수열 $A = \{A_1, A_2, …, A_N\}$가 주어진다. 다음의 조건을 모두 만족하는 $A$의 부분 수열 $\{A_{i_1}, A_{i_2}, ..., A_{i_m}\}$ 중 가장 긴 수열의 길이를 출력하라. $A_{i_1} ~\&~ A_{i www.acmicpc.net 24/01/04 비트마스킹의 아이디어를 사용하는 애드 혹 문제이다. 문제 접근 방식: 처음에 아주 나이브하게 접근해서 틀렸습니다를 받았다. 이 접근 방식은, 모든 배열의 값을 AND연산했을 때 0이 나온다면 (배열의 길이)-1이 답이 된다는 접근이었다. 생각해 보니 정말 틀린 접근 방식이었고,..
[Python] 14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 24/01/06 BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다. 문제 접근 방식: 문제 자체는 단순하다. 벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다. 즉, $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다. BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다...
[Python] 1708번 볼록 껍질 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 23/10/02 기하 알고리즘 중 대표적인 알고리즘, 볼록 껍질 알고리즘을 연습할 수 있는 좋은 문제이다. 이 문제를 통해 볼록 껍질을 구현하는 템플릿 코드를 구성하면 좋을 것이다. 문제 접근 방식: 일반적으로 볼록 껍질을 구현하는 데에는 두 가지 방법이 존재한다. 이 문제의 해설에서는 두 가지 방법 모두 소개할 것이다. 첫번째 방법은 그라함 스캔이다. 그라함 스캔의 원리는 간..

티스토리툴바