본문 바로가기

Algorithm/Programmers11

여행경로 - 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 2 해결방법 좀 더 신중히 고민하면 쉬운문제이다. 여벌 옷은 가지고 온 아이들은 수업에 참여 할 수 있다. 그래서 lost, reserve에서 같은 번호가 있다면 두 곳 모두에서 제거해주는 전처리가 필요하다. Time Complexity sort과정이 두번 있다. $$ O(2NlogN) $$ 전처리 과정은 reserve와 lost같은 것을 찾으므로 for문 2개로 돌아간다. $$ O(2N^{2}) $$ 마지막 계산 같다. $$ O(2N^{2}) $$ 따라서 $$ O(2NlogN + 4N^{2}) $$ 전체 소스 #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { sort(lost.be.. 2019. 5. 6.
단속카메라 - 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.
튜브의 소개팅 - level 4 해결방법 고려해야 변수는 y, x, d(거리)이다. 따라서 3차원 배열로 dp를 정의했다. ll dp[51][51][2510]; 점화식은 아래와 같이 된다. newy, newx는 다음번에 이동할 좌표를 의미한다. 다음 좌표는 해당 좌표의 +1이므로 d+1번째에 저장한다. 이전까지의 s + time_map[y][x]를 저장하면 된다. $$ dp[newy][newx][d+1] = min(dp[newy][newx][d+1], dp[y][x][d] + time_map[y][x]) $$ 당연히 수다시간은 제한이 있으므로 제한 시간 넘으면 못가게 해야 한다. if(dp[y][x][d] + time_map[y][x] 2019. 4. 14.
서울에서 경산까지 - level 4 해결방법 2차원 dp로 해결하였다. i는 도시, j는 시간을 의미한다. int dp[101][100010]; 점화식은 아래와 같다. k는 이전도시까지의 시간이다. 이전도시 시간과 + 현재도시 시간(걷는 방법과 자전거 2가지 모두)에 이전 도시까지 + k번째 기부금(걷는 방법과 자전거 2가지 모두)값의 넣는다. $$ dp[i][k + 현재도시 시간] = max(dp[i][k + 현재도시 시간], dp[i-1][k] + k번째 기부금) $$ 하지만, K(전체시간)을 넘으면 안되므로 예외처리를 해줘야 한다. if(k + travel[i][0] 2019. 4. 14.
GPS - level 4 해결방법 먼저 점화식을 세워보자! $$ dp[i][j] = min(dp[i][j], dp[i-1][here] + error) $$ 여기서 i는 시간을 의미하고, j는 각 노드를 의미한다. here은 j노드와 연결된 인접노드를 의미한다. dp[i][j]는 이전 시간 인접노드들의 에러들 중 최소를 + error(1 또는 0)을 의미한다. int dp[110][210]; // 시간과 노드로 구성된 dp int error = gps_log[i] == j ? 0 : 1; // gps_log[i]와 현재 노드가 같다면 0 아니면 1 초기화 과정이다. adj[i].clear()는 꼭 써주자! 아무래도 프로그래머스는 전역변수도 초기화가 안되는 모양이다. for(int i=0;i 2019. 4. 13.
단체사진 찍기 - Level 4 해결방법 경우의 수를 구하는 문제이다. 다행히 n의 최대크기가 8이므로 8! = 40,320개로 모든 경우의수를 세면서 풀 수 있는 문제이다. 이 문제를 풀면서 next_permutation이라는 함수를 새로 배웠다. 그 동안 재귀나 반복으로 풀었는데, 한결 쉬워질거 같다. 먼저 vector에다가 8개의 수를 모두 넣었다. 그리고 pos배열을 하나 만들어 해당 알파벳의 index번호를 넣었다. vector f = {&#39;A&#39;, &#39;C&#39;, &#39;F&#39;, &#39;J&#39;, &#39;M&#39;, &#39;N&#39;, &#39;R&#39;,&#39;T&#39;}; int pos[26]; 그 다음 do ~ while문을 통해 나오는 다음 경우의 수를 통해 문제의 조건과 일.. 2019. 4. 6.
게임 맵 최단거리 - Level 4 해결방법 문제는 (0,0)부터 (n-1, m-1)까지 가는 거리 중 최소값을 구하는 것이다. 이런 문제는 항상 BFS가 답이다! DFS로 구현해도 되지만 DFS의 TimeComplexity가 너무 크기 때문에 시간초과가 된다. 다익스크라 알고리즘도 BFS를 쓰는 이유로 사용되고 있다! 삼성에서 이런 문제가 출제되기도 하는데 무조건 BFS다! 나는 struct로 (y,x)위치와 거리가 있는 구조체를 만들었다. struct node { int y, x, d; node(int yy, int xx, int dd) : y(yy), x(xx), d(dd) {} node() {} }; 그 다음 BFS로 구현하였고 먼저 (n - 1, m - 1)도착한 거리를 answer에 대입하고 break해주었다. BFS는 먼저 도.. 2019. 4. 6.
쿠키 구입 - level 4 해결방법 이 문제는 두 아들에게 똑같은 쿠키를 줄 경우 가장 큰 쿠키의 개수를 구하는 문제이다. 아들 1에게는 N - M번째까지의 쿠키를 주었다면, 아들2에게는 M+1 - K번째까지의 쿠키를 준 쿠키가 같아야 되고 가장 큰 수를 return해야 된다. 까지의 배열에는 쿠키의 수가 임의의로 존재한다. 만약 이 문제를 경우의 수마다 합을 한다면 Time Compexity는 우주까지 간다. 그래서 배열을 이용해 M번째 까지의 합을 미리 저장해 놓는 것이 좋다. 만약 I - J까지의 합을 구하고 싶다면 J번째 합에서 I - 1번째의 합을 빼주면 된다. int sum[N+1]; for (int i = 0; i < cookie.size(); ++i) sum[i+1] = sum[i] + cookie[i]; 먼저 아들.. 2019. 4. 5.
도둑질 - level 4 해결방법 이 문제는 처음에 0번을 터는 수와 1번을 터는 수로 나눌 수 있다. 인접한 집을 털 수 없기 때문에 이전전 집과 현재와 이전 집중에 누가 큰지가 현재 값이 된다. $$ dp[0][i] = max(dp[0][i-1], dp[0][i-2] + money[i]) $$ $$ dp[1][i] = max(dp[0][i-1], do[0][i-2] + money[i]) $$ 위의 점화식을 보면 똑같이 보이겠지만 위에 점화식은 처음 집을 털 경우이므로 마지막집은 항상 털면 안되고, 아래 점화식은 2번째 집부터 털기 때문에 마지막집을 털어도 된다. 점화식을 통해 dp는 2 * 집의 수만큼 2차원 배열로 정의했다. int dp[2][1000001]; 아래는 초기화 코드이다. dp[0][1]에도 넣어준 이유는 반복.. 2019. 4. 5.

티스토리툴바