궤도

따라할거라면 글을 끝까지 읽고 따라하세요 VIVA 프로젝트를 보면... 이렇게 사진을 업로드해야 하는 부분이 있다. 그래서 S3 bucket을 사용하고 있었는데 https://victorydntmd.tistory.com/70 [Node.js] AWS(1) - S3 사용하기 ( aws-sdk, multer-s3 모듈 ) 2019. 08. 11 수정 1. AWS S3( Simple Storage Service )란? S3는 AWS의 스토리지 서비스로 구글 드라이브, 네이버 클라우드와 비슷한 개념입니다. 그런데 S3는 HTTP 프로토콜로 파일 업로드 및 다운로드가 가능하 victorydntmd.tistory.com 이것과 비슷한 블로그를 봤을 것이다. 왜 이 블로그가 아닐 것이라면 여길 봤다면 난 Access..

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