본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 2057번 팩토리얼 분해 https://www.acmicpc.net/problem/2057 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 22/09/15 같은 그룹원에게 추천받아서 풀었던 그리디 문제인데, (그리디인 줄 모르고 풀었었다) 접근방법을 틀리게 할 때가 많았던 문제이다. 역시 그리디는 그리디인줄 모르고 풀어야 그 진정한 어려움을 알 수 있다고 했던가, 정말 힘들었다. 이후에 브루트 포스로 풀 수 있다는 것을 깨닫고, 조금 허탈함을 느끼긴 했다. 문제 접근 방식: 맨 처음에 접근 할 때 잘 모르겠어서 그룹..
[Python] 4948번 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 22/09/15 마찬가지로 그룹 채점 현황에 있는 무작위 문제 중 한 문제를 푼 것으로, 기존에 있던 에라토스테네스의 체 코드를 재활용하여 문제를 쉽게 풀었다. 문제 접근 방식: 문제가 n을 입력받으면 n과 2n 사이에 있는 소수의 개수를 출력하는 것이 문제이므로, 에라토스테네스의 체를 구현하면 될 것이라고 생각했다. 에라토스테네스의 체는 다음과 같이 구현했다. 먼저 크기가 정해진 배열을 ..
[Python] 5637번 가장 긴 단어 https://www.acmicpc.net/problem/5637 5637번: 가장 긴 단어 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 www.acmicpc.net 22/09/14 그룹 채점 현황에 있는 무작위 문제를 풀었다. 어렵지 않은 실버 문제였다. 다만, 정규표현식을 사용하여 문제를 해결하지는 않았다. 문제 접근 방식: 태그랑은 조금 다르게 그냥 구현했는데, 일단 E-N-D가 나올 때까지 반복 입력받으므로 while문을 사용했다. 단어들을 모아놓는 words리스트를 먼저 선언했다. 이후 입력 받을 때마다 그 줄을 공백으로 분리하여..
[Python] 16113번 시그널 https://www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 www.acmicpc.net 22/09/14 좀 귀찮았던 문자열 겸 그래프 문제였다. 아이디어 자체는 매우 쉬웠으나 예외 처리하는 부분이 좀 있어서 구현이 귀찮았었다. 문제 접근 방식: 접근 자체는 매우 단순하게 접근했다. 기본적으로 1을 제외한 숫자는 가로 3칸 세로 5칸으로 이루어져 있고, 우리는 숫자를 알아내고 싶다. 따라서 입력받은 문자열을 세로 5칸이 되도록 쪼개서 행렬로 바꾸도록 구현했다.(첫번째 귀찮았..
[Python] 15904번 UCPC는 무엇의 약자일까? https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 22/09/14 이 문제 또한 문자열 문제이지만 스택으로 접근했다. 정확히 말하면 정수 카운팅에 가깝지만, 어쨌든 그것 또한 스택을 추상적으로 모델링한 것이므로 스택을 이용한 것에 가깝다고 볼 수 있다. 문제 접근 방식: 문제는 일부 문자열을 지워서 UCPC를 만들 수 있는가를 묻는 문제이다. 나는 문자열을 하나씩 반복하여 돌다가 맨 처음에 U를 만나면 stack을 +1 해..
[Python] 17413번 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 22/09/14 조금 귀찮았던 문자열 문제로, 스택을 이용하여 문제를 접근했다. 문제 접근 방식: 문제 자체는 간단하다. 공백을 기준으로 단어가 정해지는데, 원래 문자열이 주어지면 단어만 전부 뒤집어서 출력해주는 문제이다. 나는 뒤집는다는 점에 주목하여 문자 하나하나를 스택에 담다가 공백을 만나면 그 스택을 뒤집어서 전부 출력하는 것으로 접근했다. 하지만 여기에서 ..
[Python] 2684번 동전 게임 https://www.acmicpc.net/problem/2684 2684번: 동전 게임 동전게임은 주로 두 사람이 함께 즐기는 게임이다. 이 중 3-동전게임은 여러 명이 할 수 있는 게임이다. 각 사람은 각각 3-동전수열 중 하나를 선택한다. 3-동전수열이란 앞 뒤 앞과 같은 수열이 www.acmicpc.net 22/09/14 브론즈 문제라서 뇌 빼고 코딩했다. 그냥 문자열 비교를 해서 풀었다. 근데 좀 더 단순한 구현도 있을 것 같다. 문제 접근 방식: 3중 for문으로 구현했다. 제일 바깥쪽 for문은 3-동전수열 중 하나를 뽑는 for문, 두 번째와 세 번째 for문은 문자열 비교를 실행하는 for문인데, 이 문자열 비교를 40개짜리 문자열과 미리 뽑아놓은 3-동전 수열끼리 진행하는 것이다. 가능..
[Python] 5525번 IOIOI https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 22/09/14 은근 아이디어를 요구했던 문제이다. 창의적이고 재미있었던 문제였다. 문제 접근 방식: 처음에는 문자열 S안에 Pn이 몇 개 있는지 물어봐서 인덱스를 하나씩 돌려가며 Pn이랑 매칭이 되는지 판별하는 알고리즘을 짰었다. 그랬더니 문자열의 길이가 M이므로 대략 O(MN) 만큼의 시간 복잡도가 걸린다는 것을 유추할 수 있..

티스토리툴바