anonymous?

구간 합 알고리즘 사용 i~j 사이 합을 반복문을 사용할 때 시간복잡도는 O(n)인데, n이 클수록 시간복잡도가 커진다. 구간 합 알고리즘은 시간복잡도가 O(1) 먼저 현재 인덱스까지의 합을 sum[]에 저장한다. j-1까지의 총합 sum[j-1]에 j를 더하면 sum[j]이므로 sum[j] = sum[j-1] + arr[j] 만약 구간 [i,j]의 합을 구한다면 j까지의 합에서 i 이전까지의 합을 빼면 i부터 j까지의 합이므로 sum[j]-sum[i-1]으로 나타낼 수 있다. 계산의 편의를 위해 0번 인덱스는 0으로 초기화하고 사용하지 않고, 1번 인덱스부터 N까지 사용 #include #include #include using namespace std; int main(){ int N, M; scan..

PROGRAMMING/Algorithm 2023. 4. 11. 01:48

O(N) 문제 #include using namespace std; int main(int argc, char** argv) { unsigned long K, P, N; scanf("%u %u %u", &K, &P, &N); for(unsigned int i=0; i

PROGRAMMING/Algorithm 2023. 4. 8. 20:22

#include using namespace std; int main(int argc, char** argv) { unsigned int T; scanf("%d", &T); for(int i=0; i

PROGRAMMING/Algorithm 2023. 3. 28. 01:09

#include #include using namespace std; int main(int argc, char** argv) { string delim=":"; unsigned int result=0; for(int i=0; i> start >> end; int pos1=start.find_first_of(':'); int pos2=end.find_first_of(':'); int start1 = stoi(start.substr(0, pos1)); int start2 = stoi(start.substr(pos1+1)); int end1 = stoi(end.substr(0, pos2)); int end2= stoi(end.substr(pos2+1)); //printf("start1: %d start2: ..

PROGRAMMING/Algorithm 2023. 3. 28. 01:08

Overview Backtracking n-Queens 문제 Sum-of-Subset 문제 (부분집합의 합 구하기 문제) 그래프 색칠하기 문제 Hamiltonian Circuits Problem Monte Carlo 기법 (probabilistic Algorithm) Backtracking 1) Backtracking 노드의 유망성 점검 후 유망하지 않으면 부모로 되돌아가(backtracking) 다음 자식노드의 유망성 점검하여 문제의 답 찾는 기법 마디의 유망성 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다(non-promising)고 판단, 그렇지 않으면 유망하다(promising)고 판단 어떤 집합에서 특정 기준을 만족하도록 원소를 선택하는 문제 해결에 적합 예) n-Queens 문제 깊이 ..

PROGRAMMING/Algorithm 2022. 1. 8. 23:20

이전 내용 Greedy Algorithm 거스름돈 문제 최소비용 신장트리(MST, Minimum Spanning Tree) Prim 알고리즘 Kruskal 알고리즘 Greedy Algorithm (탐욕 알고리즘) 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다. 따라서 얻은 해답이 최적인지 검사하는 절차 필요 Greedy Algorithm 설계 1. 선정 과정 (selection procedure) 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함 2. 적정성 점검 (feasibility check) 새로 얻은 solution set이 적절한..

PROGRAMMING/Algorithm 2022. 1. 8. 21:09

Greedy Algorithm (탐욕 알고리즘) 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다. 따라서 얻은 해답이 최적인지 검사하는 절차 필요 Greedy Algorithm 설계 1. 선정 과정 (selection procedure) 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함 2. 적정성 점검 (feasibility check) 새로 얻은 solution set이 적절한지 결정 3. 해답 점검 (solution check) 새로 얻은 solution set이 최적의 해인지 결정 거스름돈 문제 1. 거스름돈 문제 문제: 동전의 개수가..

PROGRAMMING/Algorithm 2022. 1. 8. 18:06

💡 문제풀이 과정 sort 함수를 사용할 때 compare 함수를 사전 정렬이 되도록 구현해줬다. 💻 코드 #include using namespace std; bool compare(string x, string y){ return x > S; vector v; for(int i=0; i

PROGRAMMING/Algorithm 2021. 8. 30. 18:12

💡 문제풀이 과정 A + B나 C+D를 진행하거나 더할 때 int 범위를 벗어날 수 있기 때문에 출력 시 long long int형을 사용했다. 💻 코드 #include using namespace std; int main(){ string str; getline(cin, str); vector v; istringstream ss(str); string buffer; while(getline(ss, buffer, ' ')){ v.push_back(buffer); } printf("%lld\n", atoll((v[0] + v[1]).c_str()) + atoll((v[2] + v[3]).c_str())); } 📄 제출결과

PROGRAMMING/Algorithm 2021. 8. 30. 18:09

💡 문제풀이 과정 문자 + 13을 했을 때 아스키 코드의 대문자 범위를 벗어나거나, 소문자 범위를 벗어나는 경우에는 다시 A부터 또는 a부터 시작하도록 연산을 해줬다. 대문자 소문자에 따라 연산이 다르기 때문에 isupper, islower로 케이스를 나눠서 진행했다. 💻 코드 #include using namespace std; int main(){ string str; getline(cin, str); for(int i=0; i 90) str[i] = 65 + (str[i] + 13 - 90) - 1; else str[i] += 13; } else if(islower(str[i])){ if(str[i] + 13 > 122) str[i] = 97 + (str[i] + 13 - 122) - 1; else..

PROGRAMMING/Algorithm 2021. 8. 30. 18:06

💻 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); string str; cin >> str; printf("%d", str.length()); } 📄 제출결과

PROGRAMMING/Algorithm 2021. 8. 30. 18:02

💡 문제풀이 과정 getline 시 eof가 아닐 때까지 입력을 받고, 입력받는 스트링마다 isdigit, islower, isupper, isspace로 숫자, 소문자, 대문자, 공백 여부에 따라 카운팅을 진행했다. 입력받을 때 cin >> ws가 아닌 cin만 해야 제대로 공백이 카운트된다. 💻 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); string str; while(!getline(cin, str).eof()){ int c_lower=0, c_upper=0, c_num=0, c_space=0; for(char c: str){ if(isdigit(c)) c_num++; else if(is..

PROGRAMMING/Algorithm 2021. 8. 30. 18:00