백준
BaekJoon(1003)::피보나치 함수
문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제파악 피보나치수열 아마 쉽게 알 수 있는 문제일 것이다. 피보나치 수열이란? 첫째 및 둘째 항이 1이며 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열 그렇다면, 이 문제는 피보나치수열에서 무엇을 원하는 건지 알아봐야 한다. 피보나치수열의 점화식은 다음과 같다 $$f(n) = f(n-1)+f(n-2) \quad and \quad n \geqq 2$$ 정의상 n은 3 이상일 수 있지만 편의상 0번째 항의 값을 0으로 생각한다면 2 이상으로 생각해도 무관하다. 그리고 피보나치를 재귀로 구현하면 다음과 같다. int fibonacci(int n) { if..
BaekJoon(9461)::파도반 수열
문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제파악 파도반 수열은 리처드 파도반에 의해 이름이 붙여졌으며, 오른쪽 그림과 같이 삼각형들이 한변의 길이를 공유한 상태로 나선형으로 계속해서 이어지는 삼각형이다. 해당 수열이 진행을 보면 다음과 같다 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 수열과 같은 문제를 풀다보면 대부분 점화식을 찾아내면 쉽게 해결할 수 있다. 파도반 수열의 점화식은 다음과 같다 $$f(n)=\begin{cases}1 & \mbox{if }n..
BaekJoon(2447)::별찍기-10
문제 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제파악 재귀적인 패턴으로 별이 찍혀있음(N은 3의 거듭제곱) 크기 3의 패턴은 가운데 공백이있음. 해당 패턴이 재귀에 따라서 커지면서 반복됨. 문제의 기본이 되는 가장작은 사이즈는 우측그림에서 보다시피 초록색영역으로 출력이 된다. 다만 재귀의 형태를 좀더 자세히 보고자 N=9로 확장해보면 파랑색영역으로 보이는것을 알 수 있고 그보다 크 27일때는 빨강의 영역이다. 그리고 별찍기의 특성상 별이 그려지면 탈출을 시켜주고 해당영역이 ..
BaekJoon(9020)::골드바흐의 추측
문제 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 파악 해당 문제는 제목에서도 말하듯이 골드바흐의 추측을 통해 해결할 수 있다. 골드바흐의 추측은 2보다 큰 짝수는 두소수의 합으로 나타낼수 있다는 추측으로 해당 수를 골드바흐 수라고 한다. 주어진 골드바흐의 수는 두 소수의 합들로 나타낼 수 있다. 여러 소수쌍중 해당 값의 차이가 가장 작은 것을 출력한다. 위 정리에서 알 수 있듯 우선 소수판별을 위해 에라테토스테네스의 체를 먼저 작성한다. 문제풀이 #include #include ..
BaekJoon(1850)::최대공약수
문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 파악 : 1로 이루어진 수의 최대공약수는 두 수의 길이의 최대공약수가 해당 공약수의 길이가 되며 그 공약수 또한 1로 이루어지게 된다. : 왜냐하면 두 수는 1로 이루어져 있기 때문에 위와 같은 이해가 만들어진다. 예시 1, 11, 111, 1111 → 1 11, 1111, 111111 → 11, 1111 문제풀이 : 두 수의 길이의 최대공약수를 구하면 그 값이 주어진 두수의 최대공약수의 길이가 된다. #include #inclu..
BaekJoon(1085)::직사각형에서 탈출
문제 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제파악 사각형 내부에 x,y가 주어짐(조건 참고) 벽면에 가장 가까운 거리를 찾으면 된다(최소값) 문제풀이 위 그림의 h-y, w-x, x, y의 값 중 최소값을 구해주면 된다 #include using namespace std; int main() { int x, y, w, h; cin >> x >> y >> w >> h; int min = x; if (min > y) min = y; if (min > w - x) min = w - x; i..
BaekJoon(2869)::달팽이는 올라가고 싶다
문제 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > a >> b >> v; ..
BaekJoon(2292)::벌집
문제 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제파악 위 구역을 보면 n번째 범위에 있는 구역까지 n번 이동함을 볼 수 있다. 빨간선이 구역의 시작과 끝을 비교할수 있음을 알수있다. 1, 〔1 < n
BaekJoon(2839)::설탕 배달
문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제파악 : 설탕의 무게가 주어지고 2개의 봉지가 주어지어 더 적은 봉지로 나눌 수 있게한다. : 즉, 최소 봉지개수를 구해야한다. 문제해결 : 최대한 적은 봉지의 개수 > 우선 여러 해결방법중 'greedy algorithm'을 생각할 수 있다. : 선택은 5kg 그리고 3kg을 선택할 수 있다. 5kg을 선택시 이후 선택에 영향을 주지 않음을 통해 '탐욕스런 선택 조건이 만족 됨을 알수 있다.' 5kg부터 선택해나가다 3kg을 선택하여 전체 봉지의 갯수를 구할 수..
BaekJoon(2164)::카드2
문제 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제파악 : 카드가 쌓인 모양과 제거를 하는 방법을 보면 '큐'가 떠오른다. 카드를 쌓는다 : push 맨위의 카드를 제거한다 : pop 맨위 카드를 맨 아래로 옮긴다 : front데이터 push > pop 카드가 1장남을때까지 반복 문제풀이 : 큐는 제공하는 stl를 이용하며, 행동을 반복하는 조건을 적절하게 위치한다. 소스코드 #include #include #include using namespace std; int main() { cin.tie(NU..
BaekJoon(18258)::큐2
문제 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제파악 : 자료구조 'Queue'를 정확히 이해하고 해당 자료구조를 작성하고 요청하는 명령어를 작성할 수 있어야한다. [명령어] push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에..
BaekJoon(1037)::약수
문제 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 문제파악 : 진짜약수의 갯수, 모든 약수의 값이 주어짐 「약수란?」 : 두 정수 a, b에 대하여 b=ac를 만족하는 정수 가 존재한다면 a를 b의 약수라 한다. : 즉, 어떠한 수로 정수가 나누어떨어지는 것을 대하여 이르는 말. : 문제를 보면 자기와 1은 제외한다고 하였으니 자명약수를 제외한 고유약수중 자기 자신을 제외한 진약수가 주어짐을 알 수있다. 문제풀이 : 약수의 특징을 알면 가장 큰약수와 작은 약수의 곱이 해당 정수 N이 됨을 알수 있..