wonseok.log wonseok.log

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 그래프를 구현할 수 있는지 확인하는 문제로 인접행렬이나 인접리스트를 통해 표현할 수 있습니다. 이 문제 같은 경우는 인접행렬보다 인접리스트로 풀 경우 시간복잡도가 낮습니다. O(N2) >n>>m; bool visit[1005]; fill(visit, visit+1005, false); for(int i=0;i>a>>b; vec[a].push_back(b); vec[b].push_back(a); }..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 이분탐색에서 찾아야 할 target 원소의 인덱스 중 가장 작은 값과 가장 큰 값을 찾아 빼는 값이 개수입니다. 직접 구현할 수 있지만, 헷갈릴 위험이 있기 때문에 STL 중 upper_bound와 lower_bound 값을 쓸 수 있습니다. #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); long long arr[100000]; int num; cin>>num; for(int i=0;i>arr[i]; } sort(arr, arr+num); int n; cin>>n; for(int i=0;i>ans; bool check = false; lo..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제는 간단하게 map, set STL을 사용해서 풀면 시간초과가 납니다. 이진탐색 트리로 삽입, 정렬 과정에서 시간이 더 걸려서 이진탐색과 시간복잡도는 O(logN)으로 같지만 느립니다. 이진탐색 코드를 아래와 같이 직접 구현해도 되지만, STL의 binary_search 함수를 사용하면 보다 편리합니다. c, c++ stream 동기화 끄는 코드와 버퍼 비워주는 코드도 있어야 시간초과가 나타나지 않습니다. #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int arr[100005]; int num; cin>>num; for(int i..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제를 그리디라고 오해하여 중량 대비 가치가 가장 큰 경우를 넣는다고 할 경우 예외가 발생하게 됩니다. 그리디가 아닌 DP로 해결해야 하면 DP로 유명한 0-1 knapsack 알고리즘입니다. D[i][w] : 현재 w 무게가 남은 상태에서 i번째 item선택까지 최대 가치 if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i번째 Item을 담을 수 있다면, i-1번째까지 Item을 담으면서 현재 담을 수 있는 무게가 w-w[i]만큼 남은 경웅의 최대 가치합에 i번째 Item의 가치를 합한 값과 D[i-1][w] 값 비교 else, D[i][w] = D[i-1][w] #include #..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 그리디 알고리즘을 사용해야 합니다. 예를 들어 로프 5개 중 3개로만 가지고 최대 중량을 구하는 문제라고 하면 중량이 무거운 순으로 정렬 후 최대로부터 3개의 로프를 사용하게 되고 3개 중 가장 작은 값에 곱하기 3을 해주면 됩니다. 즉, n개의 로프를 사용한다고 하면, n번째로 큰 값에 곱하기 n을 해줘야 합니다. #include #include using namespace std; int main(){ int num; cin>>num; int arr[100000]; for(int i=0;i>arr[i]; } sort(arr, arr+num); int result = 0; for(int i=0;i

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 그리디 알고리즘의 대표적인 문제입니다. 가장 많이 회의를 하기 위해서는 회의가 가장 먼저 끝나는 회의순으로 정렬 후 동일 시 먼저 시작하는 경우를 탐색하면 됩니다. #include #include #include #include using namespace std; bool cmp(pair& p1, pair& p2){ if(p1.second == p2.second){ return p1.firstnum; for(int i=0;i>a>>b; vec.push_back({a,b}); } sort(vec.begin(), vec.end(), cmp); int cnt = 1; int e = vec[0].second; for(int i=1;i=e){ e = ve..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS를 사용할 수 있지만 DP를 활용하여 공간복잡도를 줄일 수 있습니다. if i%2 != 0 && i%3 != 0, D[i] = D[i-1]+1 if i%2 == 0 && i%3 != 0, D[i] = min(D[i-1], D[i/2]) + 1 if i%2 == 0 && i%3 == 0, D[i] = min(D[i-1], D[i/2], D[i/3]) + 1 방법을 출력하기 위해서는 그 전 숫자를 담는 prev 배열을 만들어야 합니다. 10 => prev[10] = 9, prev[9] = 3, prev[3] = 1 #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 Prefix sum 구하기 문제입니다. DP를 사용하면 시간복잡도 O(N)에 구할 수 있습니다. D[i] = D[i-1] + D[i-2] +... +D[1] #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int arr[100000]={0}; int n,m; cin>>n>>m; for(int i=1;i>arr[i]; arr[i]+=arr[i-1]; } for(int i=0;i>a>>b; cout