솔

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

백준 1074번 문제입니다.    행렬에서 z모양으로 탐색하는 문제입니다. 이 문제는 입력받은 행(r)과 열(c)의 크기에 따라 위치를 판단할 수 있습니다. 위 행렬을 사분면 나누듯 4등분을 하며 재귀적으로 문제를 해결할 수 있을 것 같습니다. ( 입력받은 행과 열이 어디에 위치한지 찾고 또 4등분하고를 반복 )  코드)입력받은 행과 열이1.좌상단2.우상단3.좌하단4.우하단중 어디에 있는지 파악하고, 재귀를 이용하여 그 부분으로 다시한번 쪼개는 방식을 사용.(위치에 따라 return 할 떄 재귀함수에 더해지는 값이 달라지는 것 중요 -> 2의 거듭제곱을 이용하여 표현 가능)#include #include int Z(int n, int r, int c) { if (n == 0) return 0; int..

DFS ( 깊이 우선 탐색 ) 와BFS ( 너비 우선 탐색 ) 에 대한 문제입니다. DFS는 그래프가 있을 때 인접한 vertex중 값이 작은 것부터 깊게 탐색하는 것이고,BFS는 그래프가 있을 때 인접한 모든 vertex를 값이 작은 순으로 탐색하고 그 다음에 깊게 들어가는 방식입니다. 따라서,DFS는 Stack 혹은 재귀를 사용하여 구현할 수 있고 (LIFO)BFS는 Queue 를 사용하여 구현할 수 있습니다. (FIFO) 코드)main함수입니다.문제에 맞는 조건의 수를 입력받아 그래프를 만들고 탐색하도록 작동시킵니다.int main(void) { int N, M, V; std::cin >> N >> M >> V; AdjMatGraph m(N + 1); for (int i = 1; i > u ..

문자열을 n번 ,m번 입력받아서 겹치는 문자열과 그 개수를 출력하는 문제입니다. 단순하게 문자열을 입력받아서 하나하나씩 비교하게 되면 시간이 너무 오래걸려 시간 초과가 날 것입니다. 그렇다면 어떻게 해야할까요?? 해시를 기반으로 하는 탐색을 이용하면 됩니다. 해시는 고유값을 가지기에  데이터의 삽입, 삭제, 탐색 모두 평균적으로 O(1) 입니다. 이번에는 unordered_set 을 이용해보겠습니다. #include #include #include #include #include using namespace std;int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int n = 0, m = 0; cin >> n >> m; unordere..

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

숫자를 입력받아 모두 붙여서 그대로 쓴 뒤, 크기를 비교하는 문제입니다. 이 문제같은 경우, 노트에서도 볼 수 있듯, x와 y의 크기가 매우 클 수 있으므로 long long 타입을 써야 합니다.  저는 입력을 배열로 받은 뒤, 숫자들을 이어붙이기 위해 10의 거듭제곱을 곱해서 다른 배열에 넣어주었습니다.   코드)#include #include #include int main(void){ int N = 0; scanf("%d", &N); long long A[20] = {0}; long long B[20] = {0}; long long result_A[20] = {0}; long long result_B[20] = {0}; for (int i = 0; i = 0; ..

사람 명수를 의미하는 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; ..

스트레스를 계산해서 복통이 며칠동안 일어났는지 알아내는 문제입니다. 스트레스 값을 배열에 입력받은 뒤, 스트레스의 합을 나타내는 sum 변수를 이용해 문제를 풀었습니다.   전체 코드)#include int main(void){ int N = 0, M = 0; scanf("%d %d", &N, &M); int stress[N]; for (int i = 0; i = M) { stomach++; } else if (sum

랜선의 개수와 필요한 랜선의 개수가 주어졌을 때 그 개수만큼 만들 수 있는 랜선의 최대 길이를 구하는 문제입니다.  초기 코드)#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..