ORTHODOX

전략: 1. 에라토스테네스의 체를 이용하여 소수를 판정하는 con 함수를 정의 하고, 투 포인터 알고리즘을 이용하여 연속합의 경우의 수를 반환하는 primesum 함수를 정의를 하고 적절히 사용한다. 코드: #include using namespace std; vector v; int N; int Primesum(){ int si = v.size(), l = 0, r = 0, sum = 0, result=0; while(l=N){ sum-=v[l]; l++; } else if(r>=si){ break; } else{ sum+= v[r]; r++; } } return result; } int con(int num){ if(num%2==0){ return false; } for(int i = 3; i>N; ..

전략: 1. 투포인터 알고리즘을 사용하여 푼다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin>>N>>M; int arr[N]; for(int i= 0; i>arr[i]; } int l =0, r= 0, sum= 0, result = 0; while(l=M){ sum-=arr[l]; l++; } else if(r>=N){ break; } else{ sum+= arr[r]; r++; } } cout

안녕하세요 오늘은 중복 제외 정렬 문제를 풀어보겠습니다. 전략: 1. 먼저 정렬을 한 후, 출력할 때 전과 다른지 비교하여 같으면 출력하지 않고 같지 않으면 출력하고 x에 그 수를 대입한다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin>>N; vector v(N); for(int i =0; i>v[i]; } sort(v.begin(), v.end()); int x= -1001; for(int i= 0; i

안녕하세요 오늘은 동적 계획법 문제를 풀어볼 것입니다. 전략: 1. P(n)의 값을 n+1번째 원소로 하는 배열을 선언해주고, P(n) 함수를 선언해준다. 2. P(n) = P(n-2) + P(n-3)임을 이용하여 P(n)함수를 정의해준다. 코드: #include using namespace std; long long int arr[101] = {0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, }; long long int P(int n){ if(arr[n]){ return arr[n]; } else{ arr[n] = P(n-2) + P(n-3); return arr[n]; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); i..

안녕하세요 오늘은 dfs을 이용하여 n개중에 순서 상관있이 m개의 숫자를 뽑는 모든 경우의 수를 출력하는 문제를 풀겠습니다. 전략: 1. dfs라는 return 값이 없는 함수를 만들어주고 cnt를 매개변수로 받아줍니다. 2. 1부터 N까지 반복하는 반복문을 만듭니다. 그 뒤, visited[i]가 false이면 i를 방문한 적이 없는 것이므로, visited[i]를 방문상태, 즉 true로 바꾸고 arr[cnt] = i를 해줌으로 cnt번째로 출력할 값을 i로 설정합니다. 3. 그리고 dfs(cnt+1)을 해줍니다. 그 과정이 끝나면 다시 전 노드로 와야하므로 visited[i]를 false로 만듭니다. 코드: #include using namespace std; int arr[9] = {0, }; b..

안녕하세요 오늘은 이진탐색을 이용하여 문제를 풀어보겠습니다. 전략: 1. string, string 을 페어로 하는 pair를 타입으로 하는 v라는 vecotr를 만들고, string 타입으로 x, y를 입력 받아서 각각 v[i].first, v[i].second에 대입해주고 이진탐색을 위해 sort를 해준다. 2. string 타입의 x라는 변수를 입력받고, 이진탐색을 진행하여 만약 x와 v[mid].first가 같으면 v[mid].second를 출력한다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin>>N>>M; vector v(N); for(int i..

안녕하세요 오늘은 이진탐색으로 문제를 풀어보겠습니다. 전략: 1. see(보지 못한 사람), hear(듣지 못한 사람), result 라는 이름의 string 타입의 vector를 선언여 see와 hear를 구분하여 input을 받는다. 2. see를 탐색할 예정이기 때문에 see를 sort해준다. 어느 이진탐색과 탐색을 실행하고, hear[i]와 see[mid]가 같으면 그 값을 result 뒤에 넣어준다. 3. 최종적으로 result의 길이를 출력하고, sort하여 사전순으로 출력한다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin>>N>>M; vect..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 사진이 너무 길어질까봐 오늘은 링크를 남깁니다. 안녕하세요 오늘은 이분탐색을 이용하여 문제를 풀어보겠습니다. 전략: 1. string타입의 vector와 int, string을 페어로 하는 pair타입의 vector를 선언해주고, input을 받아줍니다. 2. p를 정렬해줌으로 문자열 순서대로 정렬합니다. 3. 만약 들어오는 것이 index이면, v[index]를 출력..

안녕하세요 오늘은 다이나믹 프로그래밍 및 브루트 포스를 이용한 문제를 풀어보도록 하겠습니다. 전략: 1. 범위가 50000까지이니까 길이 50001짜리 배열을 만들어서 동적 계획법을 이용할 준비를 한다. sq라는 함수를 이용하여 재귀를 구현할거다. 2. 만약 arr[a]가 존재를 하면, arr[a]를 return해줍니다. 그것이 아니면 arr[a]의 값을 집어넣어줘야하는데, 만약 a의 제곱근을 제곱한 값이 a와 같다면 arr[a]에 1을 대입해주고, 1을 반환해준다. 3. 그렇지 않다면 count라는 변수를 만들어서 1(arr[i*i]) + sq(a-temp)를 대입해준다. 그리고 min와 비교하여 더 작은 값을 min에 대입해준다. for문이 끝났을 때 min값을 arr[a]에 대입해준다. 코드: #i..

안녕하세요 오늘은 vector를 이용하여 집합을 구현해서 문제를 풀어보겠습니다. 전략: vector를 21의 길이로 만들어서 v[num]이 1이면 num이 있다고 생각하고, v[num]이 0이면 num이 없다고 생각하고 풀 면 쉽게 풀 수 있습니다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int M; cin>>M; vector v(21); for(int i = 0; i>x; if(x=="add"){ int num; cin>>num; v[num] = 1; } else if(x=="remove"){ int num; cin>>num; v[num] = 0; } else if(x==..