솔

지난번 랜선자르기와 비슷한 문제입니다. https://sol248.tistory.com/32 백준_1654_랜선자르기랜선의 개수와 필요한 랜선의 개수가 주어졌을 때 그 개수만큼 만들 수 있는 랜선의 최대 길이를 구하는 문제입니다.  초기 코드)#include void lan_cal(int lan_length[], int max, int lan_count, int lan_need);intsol248.tistory.com 이 문제와 같이 이분 탐색으로 문제를 풀어보겠습니다.  위 문제와 동일한 방식으로 풀었습니다. 전체 코드)#include int binary_search(int tree_need, int max, int min, int tree[], int size);int main(void){ in..

사람 명수를 의미하는 N 과몇 번째를 의미하는 K 를 입력받아서 요세푸스 순열을 구하는 문제입니다. 사람들이 둘러앉아있는 모양이기 때문에, 원형 큐의 성질을 이용하면 풀 수 있을 것이라는 생각이 듭니다. 그런데, 큐는 FIFO (먼저 들어간게 먼저 나오는 성질) 을 가지고 있지만,  이 문제에서는 K번째 사람을 제거해야 하므로, pop 함수를 조금 다르게 구현해야 할 것 같습니다.   POP 함수) 조건 1 : 큐의 모든 값이 빠져나가면 pop을 할 수 없다. 조건 2 : K번째 사람을 제거하려 했을 떄 그 자리가 이미 공석이라면, 공석이 아닐 때까지 이동한다. int pop(int n, int k){ int t = 0; t = queue[front]; queue[front] = 0; ..

랜선의 개수와 필요한 랜선의 개수가 주어졌을 때 그 개수만큼 만들 수 있는 랜선의 최대 길이를 구하는 문제입니다.  초기 코드)#include void lan_cal(int lan_length[], int max, int lan_count, int lan_need);int main(void){ int lan_count = 0, lan_need = 0; scanf("%d %d", &lan_count, &lan_need); int lan_length[lan_count]; int max = 0; for (int i = 0; i max) max = lan_length[i]; } lan_cal(lan_length, max, lan_count, lan_ne..

입력받은 m과 n 사이의 소수를 구하는 문제입니다. 소수란, 약수가 1과 자기 자신인 수를 뜻하죠. 가장 흔하게, 2부터 자기 자신-1 까지 나누어지는지 검사하여 소수인지 판별합니다. 하지만 문제에서 1백만까지 입력받을 수 있기 때문에 위의 방법대로라면, 시간이 너무 오래 걸립니다.   여기서 소수의 성질을 하나 더 알아야 합니다. 소수는 자기 자신의 제곱근 이하의 자연수 로 나누었을 때 1을 제외하고 나누어떨어지지 않습니다. ex) 16의 제곱은은 4이죠. 2 , 3 , 4 로 나누면 나누어 떨어지므로 소수가 아닙니다.53의 제곱근은 7.xx 이죠. 2 , 3 , 4 , 5 , 6 , 7 중 어떤 것으로도 나누어 떨어지지 않으므로 소수입니다. 이제 이 방식을 코드로 구현해 봅시다.  전체 코드)#inc..

쉬운 문제이지만, 처음 알게 된 지식이 있어 글을 적습니다. 여러분은 배열을 함수 내에서 선언하는 것과 함수 밖에서 선언하는 것의 차이를 아시나요?전역 변수 / 지역 변수 말고 다른 부분에서요.. 함수 내에서 선언하는 것은 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의 개수 또한 구할 수 있겠죠. 하지만,..