궤도

문제 풀이 문제 자체는 그냥 간단한 BFS였는데 그 과정이 너무 더럽다고 해야하나 짜증나게 한다고 해야하나 암튼 그랬다. D, S까지는 그렇다고 치고 L, R을 구현하는게 문제인데, 제일 먼저 생각난건 string이라 그걸로 했더니 tle가 났다. 그러다가 잘 생각해보니 이거 그냥 수학으로 되는 연산이었다...이것만 빨리 알아챘어도.. 소스코드 #include #include #include #include #include using namespace std; string bfs(int source, int target) { vector visited; visited.assign(10000, false); queue q; visited[source] = true; q.push(make_pair(sourc..

문제 풀이 min-heap과 max-heap을 하나씩 만들어두고 각 정수별 인덱스도 함께 저장해서 삭제 여부를 체크하면 풀릴 것이다... 하지만 뭔가 이걸보니 지금까지 미뤄뒀던 set을 써야할 때가 왔구나 싶었다... www.cplusplus.com/reference/set/set/?kw=set set - C++ Reference difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t www.cplusplus.com set은 입력되는 모든 값을 정렬된 상태(default : 오름차순)로 저장해주는 자료구조인데 그냥 set은 중복 저장이 불가능하고 mul..

문제 풀이 분할정복 문제다. 일단 그냥 판을 크게 4등분 한다면 1 2 3 4 이 순서로 방문해야 한다. 그러면 판을 계속 4등분 하면서 우리가 구하고자 하는 좌표가 존재하는 사분면만 탐색하면 될 것 같은데 함수에 들어갈 인자가 뭐가 있을까... 사람마다 다르겠지만 대충 이번에 탐색할 사분면을 A라고 하면 기본적으로 들어가는 N, r, c에 더해서 A의 가장 왼쪽 위 좌표와 해당 좌표를 방문하는 순서를 저장했다. 4등분 될 때마다 N은 1씩 줄어든다. N이 0이 될 때까지 탐색하면 될 것이다. 소스코드 #include #include #include #include using namespace std; int recurZ(int N, int r, int c, int num, pair p) { if (N ..

문제 풀이 할 것이 굉장히 많다... 일단 최대 입력을 보니 브루트포스로 각 섬을 연결하는 모든 다리를 찾아도 될 것 같았다. 그렇다면 각 섬을 연결하는 다리를 어떻게 찾을 것이냐가 문제인데... 각각의 섬을 구분해야 하니 섬마다 다른 숫자로 라벨링하기로 했다. myunji.tistory.com/355 [백준] 2146번 : 다리 만들기 문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 myunji.tistory.com 이 문제에서 섬을 구분했던 것과 같은 방법을 쓴다. 0 0 0 0 0 0 2 2 3 3 0 0 0 0 2 2 3 3 0..

문제 풀이 입력이 100,000개까지 들어올 수 있어서 행성 하나하나마다 모두 거리를 구하면 메모리 초과가 발생한다. 그렇다면 MST에 들어올 가능성이 있는 거리만 저장해야 하는데 그걸 도대체 어떻게 알까? 이 부분 때문에 힘들었다. 두 행성을 연결하는 비용을 살펴보자. 보통의 좌표간 거리 구하기 공식이 아니라 x, y, z 좌표의 차이의 절댓값 중 가장 작은 값을 터널 비용으로 한다고 적혀있다. 그럼 문제를 단순화 해서 x좌표만 존재한다고 하자. 그럼 당연히 예제 입력 1에 대한 MST는 (-1) - (10) - (11) - (14) - (19)로 20일 것이다. 그니까 만약에 최종적으로 x좌표의 차이의 절댓값을 MST의 간선으로 사용하게 된다면...그것은 (-1) - (10), (10) - (11),..

문제 풀이 myunji.tistory.com/370 이 문제에서 각 정점이 좌표로 표현되는 정도만 달라졌다고 생각할 수도 있지만...하나 더 생각할 것이 있다. 바로 이미 연결된 정점들이 주어진다는 것이다. 처음엔 초기 연결 정점들이 다 연결가능하겠거니 하고 코드를 작성했다가 아닐 수도 있단 것을 깨달았다. 그니까 간단하게 예를 들자면 4 2 1 1 3 1 2 3 4 3 1 4 4 1 이렇게 입력이 들어와서 이미 1-4를 연결했는데 4-1을 연결하려고 할 수도 있다는 뜻이다. 이 부분만 신경쓰면 크게 어려울건 없다. 소스코드 #include #include #include #include #include using namespace std; typedef pair pp; int v_cnt; //사용한 간..

문제 풀이 최소 신장 트리, 최소 스패닝 트리, MST 등등으로 불리는 문제다. 가중치가 있는 간선이 주어진 그래프가 있을 때 가중치의 합이 가장 작은 트리를 만드는 것인데 트리니까 당연히 사이클이 없을 것이고 정점의 수가 V일 때, 최종 간선의 수는 V-1이 될 것이다. 이러한 MST를 만드는 대표적인 알고리즘은 크루스칼과 프림이 있는데 크루스칼(kruskal)은 유니온 파인드를 이용해 푸는 알고리즘이고 프림은 다익스트라랑 비슷해보여서 많이들 헷갈리지만 아무튼 둘은 다른 알고리즘이다. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과..

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 코드를 작성하긴 했었다. 근데 이번 문제는 사이클이 생기는 지점을 정확히 찾아야 하기도 하고...해서 유니온 파인드로 풀 것이다. 달리말하면 4803번도 유니온 파인드로 풀 수 있단 뜻이다. 아무튼 유니온 파인드에서 사이클이 형성된다는 것을 알 수 있는 기점은 유니온 하려는 x와 y의 부모가 같을 때이다. 소스코드 #include #include using namespace std..