본문 바로가기

파이썬

 (320)
[Python] 4659번 비밀번호 발음하기 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 24/01/13 살짝 구현량이 있는 구현 문제이지만, 문제에서 요구하는 것을 그대로 구현하면 쉽게 해결할 수 있는 문제다. 문제 접근 방식: 문제에서 요구하는 세 가지 조건을 판단해야 한다. 첫번째, 모음을 포함하고 있을 것. 두 번째, 모음 3개 또는 자음 3개가 연속으로 오면 안 될 것. 세 번째, 같은 글자가 연속으로 두 번 오면 안 될 것, 다만 'ee'나 'oo'는 예외다. 이 세 ..
[Python] 14395번 4연산 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 24/01/12 단순한 BFS문제다. 문제 접근 방식: BFS문제다. 다만 $10^9$짜리 배열을 만들어서 방문 처리를 하기가 곤란했기 때문에, 방문 처리는 딕셔너리로 해결했다. 키-값 쌍이 존재하는 경우에는 방문 처리가 되어있다고 간주하고, 키는 정수, 값은 그때의 방법을 담은 문자열로 구현했다. 숫자 범위가 큶에도 BFS가 잘 작동하고 바꿀 수 없는 경우를 빠르게 판단할 수 있는 이유를..
[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이 답이 된다는 접근이었다. 생각해 보니 정말 틀린 접근 방식이었고,..

티스토리툴바