궤도

문제 풀이 https://myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제를 응용한 것이다. 두 용액이면 투포인터를 쓰면 될 것인데 3개라 어떻게 할지 고민됐다. 근데 그냥 용액 하나를 고정하고 투포인터를 돌리면 되는 것이었다. 이렇게 초록색을 고정하고 빨간색과 파란색 포인터를 움직이자 N개의 용액이 있을때 초록색 포인터는 0~N-3번 용액까지 움직일 수 있다. 소스코드 #include #include #include #include #inc..

문제 풀이 위상정렬 문제다. m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com 이 분께서 시간 복잡도까지 포함해서 잘 정리해 주셨다. 각 빌딩의 건설 시간을 저장할 벡터와 이 빌딩을 건설하기까지의 시간까지를 저장할 벡터를 각각 만들었다. 두번째 벡터를 갱신하는 과정에서 실수가 있었는데 처음엔 더이상 부모 정점이 없어 큐에 삽입이 가능한 시점에만 갱신을 했다. 그리고 '입력 예제 1'의 두번째 테스트케이스에서 19라는 결과가 나와서 그림을 그려보니 어디가 문제였는지 이해됐다. 건설에 걸리는 총 시간은 ..

문제 풀이 보통의 최단거리는 다익스트라 알고리즘을 사용하지만 간선의 가중치가 음수인 경우 다익스트라를 무한루프에 빠질 수 있다. 어떤 경우에 그렇게 되는지는 내가 설명하긴 귀찮고 구글에 자료가 많으니 검색해보면 될 것이다. 아무튼 그럴때 쓰는 방법이 벨만-포드 알고리즘인데 정점을 기준으로 최단거리를 갱신해 나가는 다익스트라와 달리 이건 간선을 기준으로 최단거리를 갱신한다. 정점 A, B, C가 있다고 하자. 정점의 개수 V는 3이다. 아무리 멀리 돌아가도 최단경로라면 (V-1)개의 간선을 지날 것이다. A-B-C인 경우 A-C로 가는 경로에 간선이 2개 있는 것처럼 말이다. 만약 V개의 간선을 지나서 갈 수 있는 최단경로라면? 이건 음의 사이클이 발생한 것이다. 그러므로 일단 V-1번동안 간선을 살펴보며..

문제 풀이 처음에는 이 문제가 당연히 플로이드-워셜 문제인 줄 알았다... 실제로 그걸로 풀었더니 맞기도 했고... 근데 다익스트라 문제라는 것이다...! 난 이해가 되지 않았다. 다익스트라는 하나의 시작점에서 모든 정점과의 거리를 구하는 SSP 알고리즘인데 이 문제는 모든 사람에 대해 도착지점 하나에 대한 거리를 구해야 하기 때문이다... 굳이 모든 정점에 대해 하나하나 다익스트라를 돌리느니 플로이드-워셜이 낫지 않나 했는데 다익스트라 2번으로 해결할 수 있는 방법이 있었다. jow1025.tistory.com/114 [백준 1238] 파티 문제출처: https://www.acmicpc.net/problem/1238 풀이 출발->거쳐서->도착 의 패턴이 보여서 플로이드와샬 알고리즘이 끌리는데, 정점의 ..

문제 풀이 처음에는 각 사람들의 연결관계를 그래프로 만들어서 dfs했는데 생각해보니 정답을 맞고 보니 유니온 파인드로도 풀 수 있단걸 깨달아서 유니온 파인드로도 풀었다. 두 풀이 모두 중요한 부분은 모든 파티 정보를 고려해서 연결되어 있는 사람들을 전부 찾아야 한다는 것이다. 소스코드 - dfs #include #include using namespace std; vector isLie; //이 사람에게 거짓말을 할 수 있나? vector party_info; //파티 정보 vector graph; //연결 정보 void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크 isLie[cur] = false; for (int i = 0; i < graph[cur].size(); i++) { i..

문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순위 때문에 좀 헤맸다. 처음엔 단순히 '상-좌-우-하'의 순서로 탐색하면 되겠거니 했는데 '예제 입력 4'에서 틀린 답이 나왔다. 그래서 최단 경로에 위치한 모든 물고기들을 찾은 뒤, 그 물고기들 중에서 가장 우선순위가 높은 물고기를 찾는 방법으로 코드를 다시 작성했다. 소스코드 #include #include #include #include #include using namespace std; vector board; int shark_size = 2; //상어의 크기 int fish_cnt, result; //..

문제 풀이 문제 자체는 그냥 간단한 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..