솔

https://www.acmicpc.net/problem/5430  뒤집기와 삭제(R과 D) 명령과 숫자 배열을 입력받은 뒤,명령에 따라 배열을 뒤집거나 삭제하는 문제이다.  이 문제를 보고 배열을 숫자만 입력받는게 아닌데 어떻게 처리해야하지?  라는 생각이 들었다. 생각을 하면서 두 가지 과정을 거치면 해결할 수 있을 것 같았다.1. 배열의 처음과 끝은 무조건 대괄호이므로 이를 먼저 제거한다.2. 문자열에서 쉼표를 찾아 쉼표 이전의 문자열을 숫자로 변환  아래 코드에서 tmp는 입력받은 배열을 저장한 string 이고, d는 int를 저장하는 deque이다.deque를 사용한 이유는 아래서. tmp = tmp.substr(1, tmp.size() - 2); //대괄호를 제거 size..

지난번 랜선자르기와 비슷한 문제입니다. 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..

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

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