Hello World

백준 2231 : 분해합 문제 링크 https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 문제 내용 (요약) 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구하는 프로그램을 작성하라. ex) 245의 분해합은 256(=245+2+4+5). 즉 245은 25..

백준 1568 : 새 문제 링크: https://www.acmicpc.net/problem/1568 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현�� www.acmicpc.net 문제 내용: (요약) 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 숫자 K를 노래할 때, K마리의 새가 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 다시 시작한다. 앉아있는 새 N마리가 주어질 때, 하나의 수를 노래하는데 1초가 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는가? Ide..

백준 10870 : 피보나치 수 5 문제 링크: https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 �� www.acmicpc.net 문제 내용 (요약) 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1일 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. Idea 이번 문제는 재귀 함수로 풀어보았다. 피보나치 수는 자신 앞의 두 수를 합한 값과 같다는 것을 이용하여 먼저 점화식을 작성한다. 이를 그대로 코드에 옮겨적으면 된다. ..

백준 10872 : 팩토리얼 문제 링크 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 내용 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. Idea 팩토리얼을 구하기 위해서는 두가지 방법이 있다. 반복문을 사용하여 N까지 곱하기 재귀함수를 사용하여 구하기 N!의 값은 N*(N-1)! 임을 이용하여 재귀 함수 수식을 작성한다. 재귀함수를 사용할 때는 아래와 같이 수식을 적어두고 코딩하면 편하다. Code 1) 재귀X 1 2 3 4 5 6 7 8 9 10 #include int main() { int N,..

Lower Bound와 Upper Bound 일종의 이분 탐색(binary search) 오름차순으로 정렬되어 있을 때를 가정한다. Lower Bound -정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lower_bound(int *arr, int key, int size) { int mid, left, right; left = 0; right = size - 1; while (left = key) right = mid; else left = mid + 1; } return right; } Colored by Color Scripter cs Upper Bound -정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는..

이분 탐색 Binary Search 이분 탐색의 개념과 특징 이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다. 기본 알고리즘 구간에 대해 중간값을 우선 검사한다. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1) 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1) 중간값과 같다면 종료 구간을 줄여가며 1~3을 반복한다. 예제 정렬된 배열에 대해 목표값 9를 찾고자 한다. Search 1. left = 0(인덱스 위치) right = 8 mid = (0+8)/2 = 4 >>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다. >>left = mid + 1 Search 2...

백준 1920 : 수 찾기 문제 링크: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 문제 내용: (요약) N개의 정수가 있을 때, M개의 수들이 주어지는데, 이 수들이 N개의 정수 안에 존재하는 지를 출력하시오. Idea: 좀 더 빠르게 목표 숫자를 찾기 위해 이분 탐색을 사용하였다. 배열 A를 정렬해준다.(stl : algorithm의 sort 사용) 이분 탐색을 통해 해당 숫자가 있는지를 검사..

백준 2577 : 숫자의 개수 문제 링크: https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 같거나 크고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 내용: 세 개의 자연수 A, B, C가 주어질 때 A*B*C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오. Idea: mod 10을 통해 일의 자리 숫자부터 계산해주고, 10으로 나눠준다. 이를 반복해준다. ※ mod 10 을 통해 해당 배열 인덱스에 접근할 수 있기 때문 Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

백준 2798 : 블랙잭 문제 링크 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net 문제 내용 (요약) N개의 카드 중 3개를 조합하여 M에 가장 가까운 숫자를 찾는 프로그램을 만들자.(단, M이상을 넘기면 안 된다.) Idea 순서에 상관없이 중복되지 않도록 카드 중 3개를 뽑는다. 카드가 N 개라면 경우의 수는 N * (N -1) * (N-2)이다. for문의 범위를 적절히 조절하도록 하자. Code 1 2 3 4 5 6 7 8 9 10 11 ..

백준 1475 : 방 번호 문제 링크 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 내용 (요약) 플라스틱 숫자 0~9를 한 세트로 판매한다. 방 번호가 주어졌을 때, 필요한 세트 개수의 최솟값을 출력하시오.(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) Idea 둘 중 높은 수가 최소 세트 개수 int (6과 9가 나온 개수+1) / 2 그 외 숫자들 중 가장 많이 나온 숫자의 출현 횟수 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..