wonseok.log wonseok.log

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제를 3중 for문을 사용하면 합을 구하고 합이 존재하는지 판단하여 시간복잡도가 O(N4)이기 때문에 시간초과가 발생하게 됩니다. 마지막 합이 존재하는지를 이분탐색을 사용하더라도 시간복잡도가 O(N3logN)이라서 시간초과가 불가피합니다. 문제를 해결하기 위해서는 이분탐색을 사용하되, 새로운 기법을 활용해야 합니다. 즉 2개의 숫자의 합을 하나의 배열을 만듭니다. 이 때의 시간복잡도는 O(N2)입니다. 이후 처음 배열의 두 개의 차이가 2개의 숫자의 합 배열에 존재하는지 확인하면 됩니다. O(N2logN)으로 해결할 수 있습니다. ex) a1+a2+a3 = a4 ->, a4 - a3 = a1+a2 #include #include #includ..

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제는 이분탐색을 활용한 Parametric Search 알고리즘을 사용해야 합니다. 1부터 최대 길이를 양쪽으로 하여 절반씩 길이일 경우에 원하는 랜선의 갯수가 되는지 확인하여 s와 e를 조정합니다. #include #include #include using namespace std; int main(){ int n,k; cin>>n>>k; int arr[10000]; for(int i=0;i>arr[i]; } long long s = 1; long long e = 1; for(int i=1;i

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 처음 생각했을 때 정렬 후 map을 통해 중복제거하고 값을 key로 0부터 하나씩 담기는 count를 value로 하여 추가한 풀이를 작성하였습니다. 이렇게 하면 map은 insert의 시간복잡도는 O(logN), 이후 정렬에 대한 시간복잡도 O(NlogN)이 걸려 전체 수에 대해서 탐색할 때의 시간복잡도는 O(N2logN)입니다. 다음 풀이는 무조건 시간초과가 나타나게 되는데 map이 아닌 unordered_map을 사용하면 이진 검색 트리가 아닌 해쉬 테이블로 구현이 되어 O(1)만에 통과할 수 있습니다. #include #include #include #include using namespace std; int main(){ int arr[1..

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 다음 문제는 이분탐색으로도 해결할 수 있습니다. 해당 수열을 정렬 후 처음 인덱스부터 끝까지 탐색을 하되 해당 인덱스의 값보다 M이 큰 값을 이분탐색을 하여 삽입할 인덱스를 찾을 수 있습니다. 즉, 정렬을 무너뜨리지 않고 해당 값을 추가할 인덱스(lower_bound)를 반환합니다. 하지만, 투 포인터 라는 알고리즘을 사용해서 풀이를 하려고 합니다. 이 문제에서 투 포인터를 사용하면 정렬할 때 O(NlogN)과 수를 고르는 방법 O(N)으로 시간복잡도는 O(NlogN)이 됩니다. #include #include #include using namespace std; int main(){ int arr[100000]; int n,m; cin>>n>>m..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 처음 문제를 보면 떠오르는 풀이는 O(n2)방법으로 2중 for문으로 전체 탐색하면서 비교하는 방법입니다. 하지만, 이 문제는 경우의 수가 1,000,000이기 때문에 당연히 시간초과가 날 것이라고 생각해야합니다. stack을 활용하면 O(n)으로 풀이가 가능합니다. #include #include #include using namespace std; int main() { // your code goes here int num; cin>>num; vector vec; for(int i=0;i>n; vec.push_back(n); } stack s; for(int i=vec.size()-1;i>0;i--){ s.push(vec[i]); } int ..

이 글은 c++로 풀이를 작성하였습니다. 문제 풀이 BFS를 활용하는 문제인데 2차원이 아닌 1차원으로 작성하면 됩니다. #include #include using namespace std; int arr[100005]; int main(){ int n,k; cin>>n>>k; queue q; arr[n] = 1; q.push(n); while(!q.empty()){ int cur = q.front(); if(cur == k) break; q.pop(); if(cur>0 && arr[cur-1] == 0){ q.push(cur-1); arr[cur-1] = arr[cur]+1; } if(cur

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS 활용하는 문제로 불에 시작점에서 BFS를 돌린 후 지훈이를 BFS를 진행하여 불이 먼저 확산된 경우 진행할 수 없도록 합니다. 주의해야할 점은 2가지로 불이 여러 개 존재할 수 있다는 점과, 불이 없을 수도 있다는 점입니다. 즉, 불이 여러 개 존재는 BFS를 똑같이 해도 괜찮지만, 불이 없는 경우에는 불이 이동한 거리 배열은 초기화인 상태 그래도 있습니다. #include #include #include #include using namespace std; int n,m; int arr[1000][1000]; int fdist[1000][1000]; int jdist[1000][1000]; int dir[4][2] = {{0,1},{1,0..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 시작점이 여러 개 있는 BFS 문제로 BFS에 대한 특징이 제대로 있어야 합니다. BFS는 큐에 처음 시작점을 한 개 담았다면, 이 문제는 시작점이 여러 개 있으면 여러 개를 하나의 큐에 담기만 하면 됩니다. 큐에서 front에 해당되는 시작점에서 BFS를 진행하게 되고 특정 영역은 여러 시작점 중 처음 방문할 때가 최단 거리입니다. #include #include #include using namespace std; int n,m; int arr[1000][1000]; int dist[1000][1000]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y, int x){ return..