솔

드디어 백준을 풀기 시작한지 한달이 되었습니다!! 이전에 한두문제 풀었던 것을 제외하면 약 100문제 정도 풀었네요. 계정은 이전부터 있었지만, 이제야 처음으로 풀기 시작했네요.. 앞으로 정진하고자 기록합니다.

쉬운 문제이지만, 처음 알게 된 지식이 있어 글을 적습니다. 여러분은 배열을 함수 내에서 선언하는 것과 함수 밖에서 선언하는 것의 차이를 아시나요?전역 변수 / 지역 변수 말고 다른 부분에서요.. 함수 내에서 선언하는 것은 stack 영역에 할당하게 되고, 전역이나 static 으로 선언하는 경우는 data 영역에 할당하게 된다고 합니다. #include int main(void){ int result[20000001]; int n; scanf("%d", &n); int k; for (int i = 0; i 처음에 이렇게 작성하고 실행하는데 segmentation fault 가 계속 떠서 왜그런지 찾아보니까 지역변수에서 크기가 큰 배열을 생성하면 segmentation faul..

총 설탕 무게가 주어졌을 때, 3kg 봉지와 5kg 봉지를 각각 몇 개 사용하면 가장 적은 포대로 옮길 수 있는지 구하는 문제입니다. 입력받는 설탕의 무게를 n, 3kg 봉지의 개수를 x, 5kg 봉지의 개수를 y 라고 했을 때,3x + 5y = n 의 방정식을 풀면 됩니다. n은 주어졌기 때문에 x 와 y 에 하나씩 대입해가며 구하면 될 것 같습니다. 범위가 크지 않기 때문에 하나씩 대입해서 풀어도 상관 없을 것 같습니다.  전체 코드)#include int main(void){ int sugar = 0; scanf("%d", &sugar); int x = 0, y = 0; int check = 0; for (int x = 0; x  x와 y의 범위는 문제에서 주어진 조건에 ..

문제의 제목이 questack 이기 때문에 queue 와 stack 을 이용해 푸는 문제라고 착각하기 쉽습니다. 물론 그렇게 풀어도 되지만, 문제의 시간 제한이 1초이기 때문에, 최대한 시간이 적게 걸리는 방식으로 풀어야 합니다. 예제를 보며 작동 방식을 이해하면 어떤 식으로 풀어야 하는지 알 수 있습니다.   예제1번)문제에서 친절하게 각 상태에 대한 큐스택 내부를 차례차례 알려주었습니다. 입력 2번째 줄에서 i번 자료구조가 큐인지 스택인지 알려준 후, b를 입력받습니다. A배열0110[0][1][2][3] B배열1234[0][1][2][3]queuestackstackqueue 이런 식으로, A배열의 값에 따라 B배열에서 stack인지 queue인지 결정됩니다. 그 후, C 배열을 입력받아 하나씩 B에..

문제 설명에는 스택을 활용하는 문제라고 적혀있지만, 큐와 스택을 동시에 활용하면 더 좋을 것 같아서큐와 스택을 같이 활용하였습니다.     이 과정을 보시면, 왜 스택과 큐를 사용하는지 알 수 있습니다. 현재 줄 서있는 곳에서는, 먼저 줄 선 사람만 먼저 나갈 수 있습니다. ( 큐의 성질과 동일하죠.) 한 명씩만 설 수 있는 공간에서는, 나중에 들어온 사람만 먼저 나갈 수 있습니다. ( 스택의 성질과 동일합니다.)   문제 풀이)이 문제를 풀기 위해서는 다양한 예시를 살펴봐야 합니다. 문제에 나온 예시와 위 사진을 보면, 결과가 나올 때 가지는 공통점이 있습니다. 바로 현재 줄 서있는 곳에 사람이 없다는 점입니다. 그렇다면, 현재 줄 서있는 곳(큐) 가 빌 때까지 반복문을 돌리면 될 것 같습니다. 또 하..

저번에 큐를 이용한 문제와, 큐를 이용한 계수정렬 문제를 해결한 적이 있었죠.https://sol248.tistory.com/17 백준_10845_큐(queue)큐를 구현하는 문제입니다.   큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고sol248.tistory.comhttps://sol248.tistory.com/18 백준_2751_수정렬하기2_(radixSort)문제는 매우 단순합니다. N을 입력받아 N번 숫자를 입력받은 후 오름차순으로 정렬하는 문제입니다. 하지만 제한시간이 2초라는 점을 감안해야 할 것 같습니다. 시간이 짧으므로, 시간 복잡도sol248.tistory.com  이번엔 ..

팩토리얼에서 맨 뒤에서부터 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의 제곱이 계속 곱해지는 것을 확인할 수 있습니다.이 문제에서는 정사각형의 개수를 구하지 않기 떄문에 크게 상관은 없습니다(혹여 나중에 정사각형의 개수를 구할 일..