본문 바로가기

Programming456

[C/C++] 백준 #1003 피보나치 함수 이 문제는 6개월전에 백준 문제들을 본격적으로 풀면서 풀었던 문제입니다. 난이도는 Silver III 문제입니다. 피보나치 함수는 아주 간단한 구조를 가지고 있는데, 다양한 성질 등이 발견되면서 자주 거론되는 수열입니다. C/C++ 언어를 배울 때에는 재귀함수(자기호출함수)의 개념을 익히는 데에 하노이 타워와 자주 거론됩니다. 이 문제는 정답률이 높은 편은 아닙니다. 아마 초기문제여서 그럴 수도 있겠네요.https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.www.acmicpc.net 피보나치 수열은 초기화 값에 따라서 수열이 조금씩 틀려지는데요.fib(0) = 0, f.. 2019. 12. 16.
[C/C++] 백준 #1002 터렛(수학) 이 문제는 백준 사이트에 가입하고 처음 풀었던 것 같습니다. 지식인에서 백준 알고리즘 문제를 물어보았는데, 답변을 달기 위해서 백준 알고리즘에 가입했고, 그 후 몇문제를 풀었던 기억이 납니다. 당시에는 연세대를 다닐때였으니까, 연세대로 등록을 했었는데, 벌써 몇년 전 일이네요. 꽤 오래전부터 프로젝트 오일러 사이트에 익숙했었던 탓에, 백준과 같이 실제 채점서버가 있는 사이트는 거의 안 했었는데, 최근에 다시 시작했습니다. 이 문제의 정답 비율은 19%로 상당히 낮은데, 사실 문제의 난이도보다는 문제의 설명이 알아듣기 힘들어서인 듯 하다. 문제를 푼 사람들이 설정한 문제의 난이도는 Silver IV입니다. . 문제의 링크입니다. https://www.acmicpc.net/problem/1002 1002번.. 2019. 12. 16.
로또 출력하기 지식인에서 1:1 질문이 들어와서, 답변을 해주었는데, 마감하고 비공개 처리해서, 여기에 글을 남기네요. 홍길동이라는 사람이 늘 같은 번호로 로또를 사는데, 로또에 당첨된 내역을 출력하는 문제입니다. 원소스가 너무 엉망이라서 좀 많이 고쳤어요. 사실 프로그램 자체는 어려울게 없습니다. 배열로 숫자를 그대로 저장하면, 정렬도 안 되어 있고, 로또번호를 검증하는 것 자체가 오래걸리죠. 그리고 보너스 숫자 처리도 귀찮고요. 그래서 일반숫자는 2를, 보너스 숫자는 1을 넣는 방식으로 짜보았습니다. #include int main(void) { int luck[5][6]= {{1,2,3,4,5,6}, {10,15,25,35,40,42}, {1,9,11,22,23,25}, {9,28,31,34,35,36}, {1,.. 2019. 11. 28.
요즘은 백준 알고리즘 사이트 풀고 있습니다. 프로젝트 오일러 사이트 하다가, 회사 사람들하고 시작했던 백준 사이트. 어느덧 1,000문제를 넘어서긴 했는데, 아직까지 탑순위권 사람들하고 격차는 멀기만 하네요. 초창기에는 많은 문제를 풀었지만, 시작한지 이제 4달? 정도 되었는데, 슬슬 지겨워지고 있네요. 티스토리 블로그 기록도 점점 안 하고 있지만. 10위권으로 들어가는 게 목표인데, 문제가 너무 많네요. 특히 특이케이스에 걸리면, 골치 아프고. 가능하면 이미 나온 솔루션이 아니라 나만의 방법을 찾으려고 하다보니 벽이 느껴질 때가 많네요. 예를 들어서 BFS로 조금 무식하게 풀 수 있는 문제를 오더를 줄이기 위해서 DFS를 이용해서 O(|V||E|)으로 풀어본다던지. 하고 싶은 일들은 많은데, 귀차니즘+나태니즘의 연속. 2019. 11. 21.
프로젝트 오일러 #71 순서가 있는 분수 어려움 정도는 10%로 크게 어려움 없이 풀 수 있는 문제입니다. 분수문제가 연속으로 3문제가 나와있는데, 기약분수를 만드는 것만 잘 이해하면 풀 수 있는 문제들입니다. 아래는 이 문제의 원문이 있는 곳입니다. https://projecteuler.net/problem=71 Problem 71 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 분수를 표현하는 방법은 여러가지가 있을 수 있습니다. 그 중 유일한 표현법을 얻기 위해서 기약분수를 사용합니다. 기약분수로 표현을 할 때, 우리는 분수의 크기를 비교할 수 있죠. 그런데, 분모의 상한을 주게되면, 자연수를 나열하듯이 .. 2019. 11. 18.
프로젝트 오일러 #70 오일러의 수 순열 #69 문제와 비슷하게 이 문제도 오일러의 수를 다루고 있습니다. 난이도는 20%이네요. 문제 자체는 해석하는 데 있어서 어려움이 없습니다. n에 대한 오일러의 수가, n과 자릿수도 같고, 숫자의 조합도 같다면, 그 수는 순열수라고 할 수 있습니다. 이러한 순열수가 되는 10억 미만의 n 중에 그 비율이 최소가 되는, (즉, 상대적으로 오일러의 수가 크게 나오는) n을 찾으라는 것입니다. 이 문제를 #69와 같이 풀 수도 있겠지만요. 순열수가 되어야 한다는 조건 때문에, 일단 무식하게 프로그램을 짜보았습니다. 아쉽게도 무식하게 프로그램을 작성하면 시간이 많이 걸립니다. 전 12초정도 시간이 걸리네요. 순열수인지 아닌지는 9로 나눈 나머지가 동일한지 검사했습니다. 일단 그렇게 하면 많은 경우의 수가 줄어듭.. 2016. 9. 29.
728x90

티스토리툴바