본문 바로가기

Studying

 (94)
[백준]_1676 : 팩토리얼 0의 개수(파이썬 and C언어) 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 그냥 n! 을 10으로 계속 나눠서 그 나머지가 0이 아닐 때까지 반복하면 되는 거 아닌가 싶었던 문제이다. 하지만 n이 500까지 허용된다는 것을 간과한 결과 나는 장렬히 런타임에러로 전사하였다. 왜냐하면 500! 은 대략 10의 1134승이기 때문이다... 따라서 직접 n! 을 구하고 나누는 것이 아닌 다른 전략이 필요하다 전략 0의 개수는 무엇에 의해 결정될까? 물론 문제에서 요구하는 것은 1의 자리부터 시작된 연속된 0의 개수이다. 따라서 1023400과 같은 숫자일 경우 2만 출력하면 되는 것이다. 뒷자리 0의 개수는 2와 5의 쌍이 몇 ..
[백준]_18110번 : solved.ac(파이썬 and C언어) 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 백준에서 문제 난이도를 산정하는 방식에 대한 문제이다. 문제를 풀면서 가장 헷갈렸던 것은 코딩을 하다 보면 내림에 너무 익숙해져서 반올림이 그렇게 달갑지는 않았다. 이 문제는 아래의 규칙들만 지키면 된다. 의견이 없으면 0을 출력 모든 의견 중에서 난이도 하위 15%와 상위 15%를 제외하고 나머지 70%를 가지고 평균을 낸다. 단, 모든 결과는 반올림에 준한다(15% 산정, 평균). 전략 입력 받은 숫자들로 이루어진 배열을 오름차순으..
[백준]_10610번 : 30(파이썬 and C언어) 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 처음에 문제를 접했을 때 조금 쫄았다. 왜냐하면 요구 사항들 간의 연관성이 별로 없기 때문이다. 30의 배수인지도 확인하고 수들을 조합해서 만들 수 있는 숫자의 최댓값을 출력해라라니.. 그래도 각 조건들이 요구하는 것이 무엇인지 알 수만 있다면 쉽게 풀리는 문제이다. 조건 파악 일단 어떤 수가 30의 배수이려면 2의 배수이면서 3의 배수이면서 5의 배수이어야 한다. 하지만 이것을 전부 연산하기에는 좀 그렇다;; 그래서 단계를 조금 줄여보자. 만약에 1의 자리 숫자가..
[백준]_9461번 : 파도반 수열(파이썬 and C언어) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 반복적으로 돌아가는 수열같아서 살짝 피보나치 냄새가 나는 문제인 것 같다. 경우들을 나열해 보면서 규칙을 찾아 보자 규칙 찾기 N 1 2 3 4 5 6 7 8 N 번째길이 1 1 1 2 2 3 4 5 N 번째 삼각형의 한변의 길이를 p[N] 이라고 하자. p[4]=p[1]+p[2] p[5]=p[2]+p[3] p[6]=p[3]+p[4] ... 따라서 p[N]=p[N-2]+p[N-3] 을 도출할 수 있다. 시도 1(Python) import sys input=sys.st..
[백준]_1064번 : 평행사변형(파이썬 and C언어) 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net 필자에게 이 문제는 백준 문제풀이 사상 최초로 아이디어가 하나도 안 떠올라 샷건을 치고 구글에 솔루션을 검색하여 예상보다 너무 간단했던 해결책에 절망했던 문제이다. 이 글을 찾아준 독자들 또한 같은 여정을 견디고 온 것이라 생각한다. 이제 이 문제를 구현하려면 어떤 사고과정이 수반되었어야 하는지 살펴나가 보자. 관찰 아마 가장 많이 떠올랐을 해결책은 어차피 세 점이 주어졌을 때 존재할 수 있는 평행사변형은 많아봐야 3개이기 때문에..
[백준]_18221번 : 교수님 저는 취업할래요 18221번: 교수님 저는 취업할래요 성규는 학점이 높고 알고리즘도 잘 다루는 편이라 매년 알고리즘 대회에 나가 수상을 해오곤 한다. 성규의 꿈은 대학교 4학년 칼졸업을 하고 나서 좋은 대기업에 취직하여 빨리 돈을 버는 것이 www.acmicpc.net 개인적으로 설정 자체가 너무 웃겨서 가장 재밌게 풀었던 문제 중 하나로 손꼽힌다 하지만 필자는 대학원 지망생... 얼핏 문제를 보기에는 성규와 교수님 사이의 거리, 성규와 교수님이 각 직사각형의 꼭짓점을 이루는 직사각형 안에 있는 다른 학생(1)들의 수만 고려해 주면 되는 간단한 문제처럼 보인다. 하지만 필자는 이 문제를 무려 6번이나 심지어 파이썬으로!! 틀리고 나서야 정답을 출력받을 수 있었다. 이 글을 보고 있는 사람들은 나와 같은 실수를 하지 않기..
[백준]_11659번 : 구간 합 구하기 4(파이썬 and C언어) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 해석 사용자가 입력한 배열에서 i 번째 요소부터 j 번째 요소까지의 합을 출력하면 된다. 단 i 와 j 가 같을 때는 해당 요소만 출력한다. 문제에서 무리한 요구를 하고 있지는 않지만 시간 초과, 런타임 에러, 메모리 초과만악의 근원들..들을 조심해야 함을 알 수 있다. 쉬운 문제가 괜히 실버 3이 아닐 것이다.. 전략 구간 합이기 때문에 원하는 구간만 잘라서 합을 구해보는 방법이 있을 것이다. 이 방법이 가장 간단해 보이니 시도해 보자. ..
[백준]_1427번 : 소트인사이드(파이썬 and C언어) 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 단순히 존재하는 숫자들을 1자리 숫자로 쪼갠 뒤 내림차순으로 정렬하면 되는 문제이다. 전략 쪼갠 원소(1234 -> 1, 2, 3, 4 )들을 배열 안으로 넣은 뒤 내림차순으로 정렬하는 과정을 통해 최종 답을 도출해 낸다. 시도 1(Python) import sys input = sys.stdin.readline num = list(input().strip()) arr = [] for i in num: arr.append(int(i)) arr.sort(reverse=True) print(''.join(str(n) for n in arr)) 웬만한 ..

티스토리툴바