본문 바로가기

파이썬

 (320)
[Python] 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 22/10/09 스택을 이용해서 푸는 문제로, 괄호 문자열 문제를 풀었다면 응용해서 풀 수 있는 문제이다.(유사한 유형임) 문제 접근 방식: 괄호 문자열이 옳은지 그른지 판단하는 문제와 동일하지만, 차이점은 괄호 문자열은 시작과 끝이 정해져 있지만 이 문제 같은 경우는 시작과 끝이 괄호 문자열처럼 명확하지 않다는 것이다. 나는 괄호 문자열의 풀이에서 힌트를 얻어, 스택에 문자들을 계속 쌓다가 현재 문자가 스..
[Python] 14496번 그대, 그머가 되어 https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 22/10/08 단순 BFS문제이다. 문제 접근 방식: 이 문제에서 요구하는 바는 a를 b로 바꾸기 위해 필요한 최소 치환 횟수이다. 결국 어느 정점에서 다른 한 정점으로 가는 최소 거리를 구하는 문제와 별 다를 바가 없으므로, BFS로 해결할 수 있다. 구현하는데 주의할 점은 행렬과 같이 주어진 그래프와는 다르게 실제 간선으로 그래프가 주어져서, 그 ..
[Python] 4172번 sqrt log sin https://www.acmicpc.net/problem/4172 4172번: sqrt log sin 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 한 줄에 하나씩 주어진다. 각 줄에는 \(i\)가 주어지며, 이 수는 0보다 작지 않고, 백만보다 크지 않다. 입력의 마지막 줄에는 -1이 주어지며, www.acmicpc.net 22/10/08 DP라고 보기에도 조금 민망할 정도로, 이미 점화식을 문제에서 다 주었다. 이를 메모이제이션 기법을 활용하여 단순 구현만 하면 되는 문제이다. 문제 접근 방식: 처음에는 입력마다 DP값을 구해주도록 했는데, 시간초과가 났다. 그래서 입력 전에 미리 DP값을 다 구해주고(전처리 과정), 입력 할 때마다 그 값을 출력하도록 바꿔주었다. 구현은 math모듈의 floo..
[Python] 4375번 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 22/10/08 처음에는 특별한 규칙이 있는 문제인 줄 알고 괜히 시간을 오래 썼었다. 알고 보니 그냥 단순한 브루트 포스라는 것을 알고 그냥 깡 구현하여 문제를 풀었다. 문제 접근 방식: 어떤 정수가 주어지면, 그에 맞춰서 가장 작은 1로만 구성된 그 정수의 배수의 자릿수를 출력하는 것이 우리의 목표이다. 때문에 파이썬의 큰 수 연산에 대한 장점을 살려서 10을 곱하고 1을 하는 연산을 반복하다 입력받은 N으로 나눠질 때, 그 자리 수를 출력하도록 단순 ..
[Python] 2556번 별 찍기 - 14 https://www.acmicpc.net/problem/2556 2556번: 별 찍기 - 14 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. www.acmicpc.net 22/10/08 번외 문제다. 문제 접근 방식: 직각삼각형을 출력하면 된다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 n = int(input()) for i in range(n): print('*'*n)
[Python] 20130번 Metroidvania Extreme https://www.acmicpc.net/problem/20130 20130번: Metroidvania Extreme 첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다. www.acmicpc.net 22/10/08 독특한 아이디어가 돋보이는 BFS문제로, 일반적인 BFS가 아니라 더 재미있게 느껴졌던 문제이다. 문제 접근 방식: 일단 당연히 시작 지점부터 무지성으로 BFS를 진행하면 안 된다. 해당 알파벳의 대문자 지점은 해당 알파벳의 소문자가 열쇠인데, 그 열쇠를 얻어야만 대문자 지역을 지날 수 있다는 제약조건이 걸려있기 때문이다. 이 문제의 핵심 아이디어는, 대문자 지역을 방문했을 때 열쇠를..
[Python] 1924번 2007년 https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 22/10/08 단순 구현 문제로, 파이썬의 datetime모듈을 사용했다. 문제 접근 방식: 파이썬의 datetime모듈에서 toordinal메서드를 활용하여 구현하였다. 이 메서드는 날짜를 입력받으면 1년 1월 1일로부터 그 날짜가 몇 일 지났는지를 반환하는 함수인데, 2007년 x월 y일이 2007년 1월 1일로부터 몇 일이 지났는가를 toordina..
[Python] 11719번 그대로 출력하기 2 https://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net 22/10/08 의외로 몇 번 틀렸던 문제로, 오답의 원인을 알아내면서 의외의 수확을 거둘 수 있었던 문제였다. 문제 접근 방식: 구현하는 것 자체는 어렵지 않은데, 몇 번 틀렸었다. 그 이유는 input대신에 sys.stdin.readline을 사용했다는 점이다. 나는 이 문제를 try except구문을 사용해서 EOFError가 되면 종료하는 형식으로 했는데, sys.st..

티스토리툴바