궤도

문제 풀이 DFS 또는 BFS로 정점 1과 연결된 정점의 수를 세면 된다. 난 그냥 편하게 DFS를 재귀함수로 구현했다. 소스코드 #include using namespace std; int matrix[101][101], cnt; bool visited[101] = {false}; //정점의 방문 여부 void dfs(int cur, int max) { //재귀함수로 구현 for (int i = 1; i > N >> M; for (int i = 0; i > first >> second; matrix[first][second] = 1; matrix[second][first] = 1; } visited[1] = true; dfs(1, N); cout

문제 풀이 그래프 탐색 방법에 속하는 DFS와 BFS를 구현하는 문제이다. DFS는 깊이 우선 탐색으로 보통 스택 또는 재귀로 구현한다. BFS는 너비 우선 탐색으로 보통 큐로 구현한다. BFS와 DFS의 그래프 순회 순서를 나타낸 그림이다. 대충 BFS는 왼쪽->오른쪽, DFS는 위->아래로 생각하면 된다. 소스코드 #include #include #include #include using namespace std; int matrix[1001][1001]; //정점 i와 j 사이에 간선이 존재하면 matrix[i][j]=1 bool visited[1001] = {false}; //정점의 방문 여부 void dfs(int start, int max) { //스택으로 구현, 재귀로 구현해도 됨 stack..

문제 풀이 이 문제의 시간 제한은 0.1초다. 그니까 입력이 들어오자마자 바로바로 출력을 내보내야 한다는 것이다. 입력을 받을 때를 제외하곤 단 하나의 for문도 쓸 수 없다. 그럼 도대체 제일 작은 값도 제일 큰 값도 아닌 중앙값을 바로바로 내보낼 것인가... 중앙값을 기준으로 그보다 작은 수는 최대 힙에 넣고 그보다 큰 수는 최소 힙에 넣는 것이다. 그렇다면 최대 힙의 top에는 중앙값보다 같거나 작은 수 중 가장 큰 수가, 최소 힙의 top에는 중앙값보다 같거나 큰 수 중 가장 작은 수가 올 것이다. 균형을 이루기 위해선 최대 힙과 최소 합의 원소의 갯수 차이가 0(원소의 총 갯수가 홀수)이거나 1(원소의 총 갯수가 짝수)이여야 한다. 만약 이 균형이 깨진다면 중앙값을 수정해야 한다. 위 상태에서 ..

문제 풀이 myunji.tistory.com/271 [백준] 11279번 : 최대 힙 문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe.. myunji.tistory.com myunji.tistory.com/272 [백준] 1927번 : 최소 힙 문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 ..

문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 그 반대인 greater로 바꿔주면 최소 힙이 되겠다. 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //greater면 min heap int N, x; cin>>N; for(int i=0;i>x; if(x==0){ if (pq.empty()) cout

문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //default : max heap i..

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이 문제랑 똑같이 접근할 것이다. 위 문제에서는 LIS 수열을 만들고, 새로운 입력에 대해 LIS 수열의 마지막 원소부터 0번째 원소까지 이동하며 하나하나 비교하며 원소가 들어갈 위치를 찾아줬다. 이 부분에 대한 시간 복잡도는 O(n)이다. 만약 새로운 입력의 위치를 찾아주는 과정을 이분 탐색으로 하면 시간 복잡도가 O(logn)이 될 것이다. 새..

문제 풀이 별별 뻘짓을 많이 했다... 일단 당연히 nxn의 배열을 실제로 저장한다거나, 배열 B를 만든다거나 하면 안된다. /* 생각(aka. 뻘짓) 일단 4x4의 행렬을 그려봤다. 그러다가 놀라운 사실을 하나 발견했다. i+j=2k(짝수라는 뜻)인 모든 A[i][j]에 대해 A[k][k]가 가장 크다는 것이었다. 그니까...4x4 행렬이 있다고 하자. A[2][2] = 4이다. i+j=4인 다른 A[i][j]를 보면, A[1][3] = 3, A[3][1] =3이 있다. 그래서 이걸 보고 left를 (1, 1), right를 (n, n)으로 한 뒤 그 둘의 mid를 구해서 계산하고 어쩌구...하는 식으로 했는데...망했다. */ 결국 검색을 했고 내 접근이 반은 맞고 반은 틀렸다는 것을 알았다. 반까지..