궤도

오늘은 이 그림에서 7번을 구현할 것이다. 먼저 시험지를 촬영해서 욜로에 보내면...욜로는 우리가 설정한 클래스의 객체를 찾아낸다. 그리고 제이슨 형태로 결과를 반환하는데 뭐... label : OOO recognition word : OOO w : OOO h : OOO x : OOO y : OOO 객체마다 이런식으로 반환한다. 직접 보여주면 좋겠지만 내 담당이 아니라 여기서 보여주기가 좀 그렇다 우리가 찾아야 하는 클래스는 문제번호, 페이지번호, 객관식 체크 정보, 주관식 답안 정보인데 다른건 다 잘 찾는데 객관식 체크 정보를 아직도 몇 개씩 빠뜨린다. 그래서 백엔드에서 보정해줘야 한다. 일단은 객관식을 다 찾았다는 아주 희망적인 가정을 하고 알고리즘을 짜보겠다. 우리의 테스트 셋이다. 앞서 말했지만 ..

문제 풀이 지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다. 처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다. 일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다. 그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면 이렇게 될 것이다. dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다. 당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다. 한편 예제 입력..

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