본문 바로가기

백준/Silver(1~5)

 (33)
[백준]_1543번 : 문서 검색(파이썬 and C언어) 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문서에서 주어진 단어가 몇 번이나 포함되어 있는지 중복을 제외하고 세야 하는 문제이다. 예를 들어 ababababa의 문서가 주어지고 검색 단어가 aba라면 ababababa → ababababa 이므로 답은 2이다. 전략 따라서 이 문제를 풀기 위해서는 입력받은 문자열을 하나씩 쪼개어 배열에 저장한 뒤 검색 단어의 존재 여부에 따라 검사의 위치를 이동시켜 주는 방법을 선택해야 한다. 이해를 돕기 위해 위의 예시를 다시 사용하겠다. 0 인덱스부터 시작해서 찾고자 하는..
[백준]_1929번 : 소수 구하기(파이썬 and C언어) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 전략 여느 때와 다름없이 검사할 범위가 큰 소수 문제는 에라토스테네스의 체를 사용하는 문제이다. 시간 초과가 안 나오게 조심해야 하는 문제들 중 하나이기 때문에 시간복잡도를 최소화시키면서 코딩을 해야 한다. 시도 1(Python) m,n=map(int,input().split()) for i in range(m,n+1): if i==1: continue for j in range(2,int(i**0.5)+1): if i%j==0: break else: print(i) 왠지 모르게 느리다(522..
[백준]_11055번 : 가장 큰 증가하는 부분 수열(파이썬 and C언어) 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 처음에 진짜 어떻게 접근해야 될지 하나도 몰라서 쩔쩔맸던 문제이다. 결국 질문 게시판에 들어가서 힌트를 조금 얻으려고 했는데 모든 질문들이 하나 같이 dp 리스트를 선언한 것을 알게 되었다. 사실 나는 dp(동적 계획법:dynamic programming) 문제인지도 모르고 문제에 덤볐던 것이다;; 잠시 문제를 접어두고 나서 dp를 조금 공부한 다음에 문제를 풀어 보기 시작했다. 당연히 풀릴 리가 없다ㅋ..
[백준]_9020번 : 골드바흐의 추측(파이썬 and C언어) 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 논리 과정을 세우는 데는 그다지 어렵지 않았는데 막상 소수 판별을 하는 부분에서 시간 초과가 계속 났던 문제이다. 또한 이 문제에서 가장 까다로운 조건인 "만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다"을 어떻게 해결하는지도 골머리였다. 전략 다행히 n은 4 이상 10000 이하이기 때문에 10000 이하의 소수들을 먼저 배열에 저장해 주고 나중에 돌아와서 '이 숫자가 소수인가?=이 숫자가..
[백준]_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..

티스토리툴바