궤도

문제 풀이 myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제와 풀이가 동일하다. 오히려 이 문제는 연결된 배추의 그룹(?)수만 세면 되는거라 더 쉬운 셈이다. 소스코드 #include #include #include using namespace std; //범위 초과 때문에 상하좌우 한줄씩 추가 int matrix[52][52], M, N; pair dir[4] = {{-1, 0}, //상 {1, 0}, //하 {0, -1}..

문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 건 더이상 해당 root와 이어진 1이 없다는 뜻이니까 다시 새로운 1이 나올때까지 배열을 돌면 되겠다. 난 그냥 편하게 재귀함수 돌리려고 dfs로 했다. 그나저나 이런 문제를 풀땐 상하좌우로 이동하면서 풀어야 하는데.. 아무생각없이 상하좌우로 이동하다간 5x5배열에서 [-1][0]을 참조하거나 [6][2]를 참조하게 될 수도 있다. 이걸 해결하는 방법은 여러가지가 있지만 난 이렇게 상하좌우 테두리를 둘러주는 방법을 선호한다. 위아래 2줄씩 더 생긴다고 큰 일이 일어나진 않을테니까... 소스코드..

문제 풀이 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..