Level 33 여행경로 - level 3 해결방법 dfs, bfs문제이고 솔직히 쉬운 문제였는데 오래걸렸다. 첫 번째는 문제에 대한 오해였다. 이 티켓을 사용해서 모든 도시를 다 방문해야만한다. 단순히 dfs를 통해서 사용하는 것이 아니라 실제 다 모든 도시 방문 && 모든 티켓 사용인지를 확인해줘야만 한다. 전체 소스 #include #include #include #include #include using namespace std; int T; vector v; vector dfs(string s, vector t, vector ans, int cnt) { ans.push_back(s); if (cnt == T) return ans; vector tmp; for (int i = 0; i < t.size(); ++i) { if (t[i][0].. 2019. 5. 8. 단속카메라 - level 3 해결방법 왜 2점 밖에 안주는지 모르겠지만 쉽지 않았다. 아이디어 위의 그림은 예시를 그림으로 한 것이다. 그림을 보면 알 수 있듯이 겹치는 것들 중 진출 좌표(r[i][1])이 가장 작은 것이 가장 많이 겹치게 할 수 있다. 하지만 안 겹치는 선은 안 겹치는 선들 중 가장 처음 것을 기준으로 다시 몇개 겹칠 수 있는지 계산하면 된다. 알고리즘 r[i][0], r[i][1] 오름차순으로 정렬 변수 end : i번째까지 중 가장 작은 r[i][1] $$ end\ =\ min(end,\ r[i][1]) $$ 만약 end < r[i][1]이면 answer증가시키고, end = r[i][1]해준다. $$ end\ =\ r[i][1] $$ Time Compexity 정렬은 O(NlogN)이고, 업데이트는 O(N).. 2019. 5. 6. 줄 서는 방법 - level 3 해결방법 쉬운듯 어려운 문제였다. 해결방법은 머리 속으로 바로 생각났는데 처음 구현해보는 알고리즘이라 고생을 많이 했다. 충분히 프로그래머스를 이용하여 코딩테스트를 보는 회사에서 나올 수 있는 문제라고 여겨진다. k번째의 경우의 수를 구하는 문제이다. 만약 아래와 같이 next_permutation으로 푼다면 효율성 테스트를 통과하지 못해 효율적인 방법을 생각해내야 한다. do { k--; if(k == 0) break; } while(next_permutation(answer.begin(), answer.end())); factorial을 이용하여 문제를 푼다면 더 빠르게 풀 수 있다. 예를 들어 보자! n = 10이라고 가정한다. 만약 첫 번째 자리수가 바뀌기 위해서는 k > 9! 하므로, k < 9.. 2019. 5. 4. 이전 1 다음
