솔

https://www.acmicpc.net/problem/11689  문제자연수 n이 주어졌을 때, 1~n 의 자연수 중 n 과 서로소인 숫자의 개수를 구하는 문제이다. 접근 방법오일러 파이 함수를 이용해야 한다.이는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 계산하는 함수이므로 이 문제를 해결하기에 적합하다.따라서, n의 소인수만 찾으면 효율적으로 계산이 가능하다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.이렇게, 소수를 찾아서 순차적으로 p[i] = p[i] - (p[i]/2) 연산을 반복적으로 수행해주면 최종 결과는 오일러 피 함수의 결괏값이 배열에 남게 된다. 코드#include #include #include #include // 오일러 파이 함수 구현long long ..

https://www.acmicpc.net/problem/1016  문제 정의min 과 max 가 주어졌을 때, 제곱수로 나누어지지 않는 정수의 개수를 찾아야 한다. 예제 입력 1에서 min=1 , max=10 이 주어졌을 떄, 1보다 큰 제곱수(4,9)로 나누어지지 않는 정수의 개수는 1,2,3,5,6,7,10 으로 7개이다.  위 그림과 같이 2부터 제곱수가 max값을 넘기 전까지 제곱수로 나누어지는 수들을 하나씩 제거해주면 된다.  배열 초기화입력받은 min, max 값에 따라 범위를 설정해주고 배열을 초기화한다.long long range = max - min + 1;std::vector is_power(range, false);  제곱수로 나누어지는 수 순차적으로 탐색i^2 형태의 제곱수를 순회..

https://www.acmicpc.net/problem/1931  여러 시간대가 주어지고, 시간이 겹치지 않으면서 가능한 한 많은 회의실 사용 횟수를 구하려고 한다. 이를 구하기 위해서는, 가장 빨리 끝나는 회의를 찾고, 그 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 찾고, 이렇게 찾아나가면 될 것 같다. 위와 같이 회의 시간을 찾기 위해서는, 끝나는 시간을 기준으로 정렬되어 있어야 한다.  이를 위해 다음과 같은 구조체와 배열을 만들어 주고,이렇게 끝나는 시간을 기준으로 정렬해주는 cmp함수까지 완성해주면 준비는 끝났다.(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬)bool cmp(const t& a, const t& b) { if (a.eTime != b.eTime) return a..

https://www.acmicpc.net/problem/1300  이 문제를 풀 때 N의 최댓값이 10^5 이므로 이차원 배열(N x N)을 만들어 문제를 풀면 100억의 메모리가 필요하고, 10^10(log(10^10)) 의 시간이 필요한데 사실상 불가능하다.메모리O(N^2)시간O(N^2 log(N^2))  이 문제에서 요구하는 것은 "정렬된 배열에서 k번째로 작은 값"이다. 만약 어떤 값 x를 기준으로 배열(B) 에서 x 이하의 원소가 몇 개인지만 구하면  “x 이하가 k개 이상이면 → B[k]는 x 이하여야 함”“x 이하가 k개 미만이면 → B[k]는 x 보다 커야 함”위와 같은 기준을 얻을 수 있고, 이분탐색을 이용해 원하는 B[k]를 빠르게 구할 수 있다.   문제를 보면 이론상으론1 이지만,..

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; ..