솔

팩토리얼에서 맨 뒤에서부터 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제입니다. 문제가 잘 이해가 안되실 수 있으니 (제가 그랬습니다..) 예시를 보여드리겠습니다. 더보기5! = 5*4*3*2*1 = 120 -> 1개 6! = 6*5*4*3*2*1 = 720 -> 1개 7! =  7*6*5*4*3*2*1 = 5040 -> 1개 8! =  8*7*6*5*4*3*2*1 = 40320 -> 1개 9! =  9*8*7*6*5*4*3*2*1 = 362880 -> 1개 10! = 10*9*8*7*6*5*4*3*2*1  = 3628800 -> 2개어떤 숫자의 맨 뒤에 0이 오기 위해서는 반드시 10이 곱해져야 합니다.10 = 2*5 이므로, 2와 5의 개수를 찾으면 0의 개수 또한 구할 수 있겠죠. 하지만,..

666이 포함된 숫자를 작은 순으로 나열하는 문제입니다. 이런 문제에는 두가지 선택지가 있습니다.1. 규칙을 찾아서 풀 것인가.2. 하나하나 나열해서 풀 것인가. 우선 규칙이 있나 찾아보기 위해 작은 수부터 나열해보겠습니다.더보기666 1666    2666    3666    4666    5666  6660    6661    6662    6663    6664    6665    6666    6667    6668    6669 7666    8666    9666    10666    11666    12666    13666    14666    15666 16660    16661    16662    16663    16664    16665    16666    16667    1666..

숫자를 정렬하는 간단한 문제처럼 보이지만, 메모리 제한이 8mb로 매우 작기 때문에 이때까지와는 다른 방식으로 풀어야 합니다. 입력을 보시면 데이터가 천만개 까지 들어올 수 있는데, int 형 1천만개를 배열에 넣으면 8mb를 넘어가기 때문에배열에 넣고 정렬하는 방밥은 쓰면 안됩니다. 이번에 써볼 정렬 방식은, 시간 복잡도가 작은 계수정렬(counting sort) 입니다.  계수정렬)계수 정렬이란, 비교 연산을 하지 않는 정렬 방식입니다. 배열 내에 특정한 값이 몇 번 등장했는지를 세서 정렬을 수행하는 방식이기 때문에 속도가 보장됩니다. 최악의 경우라도, 시간 복잡도가 O(n+k) 로 매우 작습니다. 아래 그림을 보며 어떻게 정렬되는지 확인해봅시다.   정렬 방식)다음과 같은 array1 배열이 있을 ..

위의 그림과 같은 과정을 n번 거쳤을 때 점의 개수를 구하는 문제입니다. 이런 문제는 규칙을 찾아야 하니 규칙이 뭔지 알아보도록 하죠. 정사각형의 개수점의 개수초기 상태14    (2^2)1번째49    (3^2)2번째1625    (5^2)3번째6481    (9^2)4번째256349    (17^2)5번째10241089    (33^2) 문제에서는 15번째까지 입력받을 수 있지만, 거기까지 구해보는 것은 숫자가 너무 크기도 하고,이정도까지만 봐도 규칙을 찾을 수 있기에 5번째까지만 구해보겠습니다. 규칙이 보이시니요? 우선 정사각형의 개수는 2의 제곱이 계속 곱해지는 것을 확인할 수 있습니다.이 문제에서는 정사각형의 개수를 구하지 않기 떄문에 크게 상관은 없습니다(혹여 나중에 정사각형의 개수를 구할 일..

최소공배수를 구하는 문제입니다. 중학교 때 배웠던 소인수분해를 기억하시나요? 만약 8과 16이라는 두 수가 주어졌을 때, 소인수분해를 통해 최대공약수와 최소공배수를 구할 수 있습니다.아래의 표는 소인수분해의 과정을 나타낸 것입니다.2816248224 12 여기서 좌측의 노란색 배경 숫자들을 곱하면 최대공약수, 최대공약수에 초록 배경 숫자들까지 곱해주면 최소공배수를 구할 수 있습니다. 8과 16의 최대공약수는 2*2*2 = 8 이 되겠고,최소공배수는 2*2*2*1*2 = 16 이 되겠죠. 소인수분해의 과정만 코드로 구현한다면, 이 문제를 해결할 수 있습니다.  최대공약수,최소공배수 구하는 함수)int common(int a, int b){ int divisor = 1; for (int i = 2..

문제는 매우 단순합니다. N을 입력받아 N번 숫자를 입력받은 후 오름차순으로 정렬하는 문제입니다. 하지만 제한시간이 2초라는 점을 감안해야 할 것 같습니다. 시간이 짧으므로, 시간 복잡도가 작은 기수 정렬 (radix sort) 를 활용해 문제를 풀어보겠습니다. https://sol248.tistory.com/17 백준_10845_큐(queue)큐를 구현하는 문제입니다.   큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고sol248.tistory.com바로 이전에 큐 문제를 푼 적이 있습니다. 이 문제도 원형 큐를 이용한 기수정렬로 풀 것이기에, 큐에 대해 모르시는 분은 10845_큐 문제를 ..

큐를 구현하는 문제입니다.   큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고 있죠. ( 스택에 대해서는 추후에 정리해보겠습니다 ) 큐에서 front와 rear은 데이터의 시작과 끝 위치를 나타냅니다. rear을 이용해 가장 나중에 최근에 데이터에 접근할 수 있고, front를 통해 가장 나중에 들어간 데이터에 접근할 수 있습니다.   큐의 종류)1. 선형 큐(Linear Queue) : 가장 기본적인 막대기 형태의 큐. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다. 2. 원형 큐(Circular Queue) : 선형 큐의 단점..

규칙이 있는 아파트 문제입니다. a층의 b 호에 살기 위해서는 a-1층의 1호~b호 까지의 사람의 합 만큼 사람을 데려와야 한다는 규칙이 있습니다. 처음에는 반복문을 통해 시그마를 구현하고 하나하나 다 더해서 풀어야 하나 생각을 했지만 더 간단한 방법이 있었습니다. 아파트를 표로 구현해보았습니다.아래 표에서 규칙을 찾으면, 문제를 쉽게 풀 수 있을 것 같습니다.2층1명4명10명20명35명56명84명120명165명1층1명3명6명10명15명21명28명36명45명0층1명2명3명4명5명6명7명8명9명 __1호__2호__3호__4호__5호__6호__7호__8호__9호 규칙이 보이시나요?? 해당 호수에 몇명이 살고 있는지 구하기 위해서는, 같은 층의 이전 호수와, 바로 아래층의 같은 호수에 살고 있는 사람 수를 더..

달팽이가 올라가는데 며칠이 걸리는지 구하는 문제입니다. 조건은 고려하지 않고 문제만 보면 쉬워보여서 바로 코드를 짜보았습니다. #include int main(void){ int A, B, V; scanf("%d %d %d", &A, &B, &V); int i = 1; int height = 0; int count = 0; while (i) { height = height + A; count++; if (height >= V) { break; } height = height - B; } printf("%d\n", count); return 0;}  단순히 다..

팰린드롬에 대한 문제입니다. 문제에 나와있다시피, radar 와 sees 같이 뒤에서부터 읽어도 똑같다면 그 단어는 팰린드롬입니다. 숫자도 마찬가지로, 121 이나 12421 같이 뒤에서부터 읽어도 똑같으면 팰린드롬수 입니다. 숫자를 입력받아 팰린드롬수인지 아닌지 판별하는 프로그램을 작성해 봅시다.   1. 0이 입력될 때까지 종료되지 않아야 하므로 무한루프에 0이 입력되면 종료되도록 하는 조건을 넣습니다. while (1){ scanf("%d", &num); if (num == 0) // num이 0이면 종료 { return 0; }}   2. 입력받은 num의 자리수를 세고, number 배열에는 그대로, check 배열에는 역순으로 넣습니다. (비교하기 쉽도록 배열..