wonseok.log wonseok.log

이 글은 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..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS 특징 중 하나는 탐색하는 영역을 최소한의 거리로 탐색한다는 특징이 있습니다. 따라서 BFS 알고리즘으로 원하는 공간을 처음으로 탐색했던 시간이 최단거리 입니다. #include #include #include #include #include using namespace std; int n,m; int arr[100][100]; int dist[100][100]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y,int x){ return 0m; for(int i=0;i>s; for(int j=0;j

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS를 활용하는 문제로 배열의 모든 지역에서 BFS를 실행합니다. 처음 BFS에서 실행하여 탐색하지 않은 지역에서 다시 BFS를 실행하여 그림의 갯수를 파악합니다. 그림의 최대 크기는 BFS를 실행하면서 큐에서 pop한 갯수를 세어 비교합니다. #include #include #include using namespace std; int n,m; int arr[500][500]; bool visit[500][500]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y,int x){ return 0m; for(int i=0;iarr[i][j]; } } int cnt = 0; int ans..

이 글은 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..