본문 바로가기

알고리즘

백준 1003 피보나치 함수 문제풀이와 해설 은근히 헷갈리는 문제이긴 했는데, 헤메다가 결국 풀이했습니다 :) ​ 피보나치의 합계를 푸는거라면 좀 수월할텐데, 재귀호출에서 0과 1이 나오는 횟수를 풀라니 크레이에게는 좀 난해했습니다. ​ 피보나치 수열에서 재귀호출로 계산할 때 0과 1이 연산에 들어가는 횟수인지 숫자가 클수록 기하급수적으로 늘어나더라구요. ​ 이것 저것 고민하다가 인터넷 다른 분의 게시글도 참고하긴 했지만, 결국은 독자적으로 초고속으로 작동하도록 새로 만들었습니다. ​ long long 형 변수로 선언해서 60피보나치의 0과 1의 갯수까지도 계산할 수 있으며 ( 79로 시도해봤었는데 숫자 범위 초과로 엉뚱한 숫자가 구해지더라구요. 혼란드린점 죄송합니다 ) 60피보나치일 경우라도 연산시간은 10ms 이내인듯 합니다 :) 측정해보기는 .. 더보기
백준 1012 유기농배추 문제풀이 및 해설 오늘 살펴볼 문제는 1012번입니다 :) 유기농 배추를 심는 한나를 도와 병충해를 막는데 몇마리의 지렁이가 필요한지 알아내는 소스를 짜는 것이군요. ​ 스토리가 있어서 재미있습니다 ㅎㅎ 문제 살펴봅니다~ ​ 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가.. 더보기
백준 1009 분산처리 문제풀이 및 해설 오늘은 백준 앞번호대 문제를 살펴볼텐데요. 자연수의 기본 원리를 알면 쉽게 풀수 있는 문제이나 모르면 앞번호대일지라도 혼동될 수 있는 문제입니다 :) ​ 문제 한번 살펴볼까요? ​ 문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 .. 더보기
백준 1011번. Fly me to the Alpha Centauri 우주 여행 알고리즘 문제군요 :) ​ 이 문제는 여러 해법이 존재할 수 있을법 한데요. ​ 크레이에게는 약간 어려운 문제이긴 했으나 다음번에 유사한 패턴이 나오면 훨씬 시간을 단축해서 풀 수 있을듯 합니다. ​ 다른분의 풀이를 참조하긴 했지만 원리만 이해하고 고민하는 방법과 코딩은 새로 했으니까요. ​ 경우의 수까지는 적용하지 않고 반복패턴에 의한 풀이 방법을 적용했습니다. ​ 문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 .. 더보기
백준 알고리즘. 10809번. 알파벳 찾기 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. ​ 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. ​ 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. ​ 예제입력 baekjoon 예제출력 1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 .. 더보기
백준알고리즘 1065번 문제 풀이 & 해설 문제 ​ 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. ​ 입력 ​ 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. ​ 출력 ​ 째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. ​ 해설 ​ 본 문제는 등차수열인데 얼핏 알기에는 5, 10, 15, 20과 같은 수열로 착오할 수 있습니다. 문제지문에 보시면, 어떤 정수 X 의 자릿수가 등차수열을 이룬다면 이라고 적혀 있지요. 여기서 자릿수란, 숫자가 1자리인지 2자리 숫자인지, 3 또는 4자리 숫자인지 말하는 것입니다. .. 더보기
백준 알고리즘 4673번 풀이와 해설 백준 알고리즘 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(.. 더보기
백준알고리즘 1008번 풀이 문제 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. ​ 입력 첫째 줄에 A와 B가 주어진다. (0 < A, B < 10) ​ 출력 첫째 줄에 A/B를 출력한다. 절대/상대 오차는 10-9 까지 허용한다. ​ 예제입력 1 3 예제출력 0.33333333333333333333333333333333 이 문제는 무지 간단해 보이는데 한가지를 모르면 좀 어려울수도 있습니다. ​ 그냥 무턱대고 cout b; cout.precision(20); cout 더보기