본문 바로가기

백준

 (47)
[백준]_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..
[백준]_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번이나 심지어 파이썬으로!! 틀리고 나서야 정답을 출력받을 수 있었다. 이 글을 보고 있는 사람들은 나와 같은 실수를 하지 않기..

티스토리툴바