wonseok.log wonseok.log

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

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