본문 바로가기

알고리즘, 자료구조/알고리즘 문제10

[SW역량] 14501. 퇴사 N수가 작아서, 완전탐색으로 풀어도되고, 그렇지 않고 가능하다면 DP로 풀어도 되는 문제이다. 여러가지 DP 해법을 보다가, 가장 와 닿는 풀이방법을 찾았다. d[i] : i일로부터 N일까지 최대 수익 이라고 정하면, 식을 자연스럽게 세울 수 있다. d[i] = max(d[i+1], d[i + t[i]] + p[i]) 이제 d[i]를 solve(int i)라고 놓고, 리턴값을 d[i]으로 설정해서 풀어보자. 그렇다 Top-down 방식의 동적계획법이다. 기저 조건은, d[N + 1] = 0 d[N + 1 초과] = - INF 라는 것이다. 이것은 예제 하나를잡아 하나하나 대입해가면서, 마지막 조건을 생각하면 이해가 쉬운 편이다. Hint: 마지막 날의 t[i]가 1이라면, d[i + t[i]] + p[i.. 2019. 10. 19.
13460 구슬 탈출 2 삼성 SW 역량 문제. 방향이 4방향이니까, 한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다. 그래서 코드도 비슷하지만, 길어진 코드가 되었다. 총평 - 모든 경우의 수를 세는 dfs는 잘 구현했다. - dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자. - 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다. - 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다. - 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다. 이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다. #include int N, M; char a[.. 2019. 10. 6.
16236 아기상어 시뮬레이션 문제를 해결해보자. 맵이 주어지고, 탐색을 할 경우에 dfs를 쓸 것인지, bfs를 쓸 것인지 고민이 된다. bfs가 dfs를 아우르는 개념이라서 보통 bfs를 쓰면 되는데, 특히 최단경로 문제(가중치가 없을 때)일 때는 bfs를 써야한다. 이 때, visited[][] 대신, dist[][]를 이용하면서 최단경로도 저장하고, 방문했는지도 체크할 수 있다. 처음에 문제를 이해하느라, 시간을 많이 썼지만 차근차근 이해하고, 배운 개념을 써먹으면 문제가 풀린다. 시간복잡도는 모든 물고기 O(V)에 대해 한번 잡아먹을 때마다 다음 잡아먹을 물고기 모두를 탐색해야 하므로 O(|V| + |E|)가 걸린다. O((20 x 20) x (20 x 20 + 19 x 20 x 2) ) = 464,000이 걸린다.. 2019. 9. 29.
16234. 인구이동 삼성 SW역량 테스트 기출문제. BFS를 사용하는 완전탐색 문제이자, 주어진 규칙을 잘 구현하는 시뮬레이션 문제이다. 문제 그대로만 하면 된다. BFS의 결과로 최소 신장트리(Minimum spanning tree)가 나오는데, 그 트리가 바로 하나의 연합이다. 처음에 문제를 보고, 하루에 연합이 2개이면 인구이동도 2번인가 했었는데 아니었다. 하루에 인구이동이 일어났으면 연합의 개수에 상관없이 그냥 인구이동이 한번 추가 되는 것이다. 무튼, 연합이 만들어지면, 그 node들을 하나의 vector에 저장해놓고, 인구이동값을 각 node에 대입해주면 된다. 그래서 코드는 크게 bfs()와 immigrate()로 나뉜다. #include #include #include #include using namesp.. 2019. 9. 28.
17143. 낚시왕 시뮬레이션 문제. 처음엔 쉬울 줄 알았지만, 하나하나 구현하며 오류가 많아 실제로 푸는데는 꽤 오래걸렸다. 해결방법은 문제에 주어진 대로 코드를 쭉 구성해가면 된다. 우선, 시간복잡도를 계산했을 때, 0 낚시왕이 모든 열을 걸어가는 시간 O(N) 1 낚시하는 시간(모든 행을 살핌) O(N), 2 맵을 다시 만드는 시간 O(N^2), 3 모든 상어에 대해 O(N^2) 3-1 상어가 이동하는데 걸리는 시간 O(N) 따라서 최악은 O(N^4)이 걸린다. 100x100x100x100 = 1억이므로 시간 내에 해결이 가능하다고 생각했다. 상어가 있는 물을 w[101][101]로 만들고, 1. 낚시왕이 오른쪽으로 한 칸 이동한다. C(column)을 바꾸어가며, 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일.. 2019. 9. 24.
14889. 스타트와 링크 사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것.. 2019. 9. 21.
14888. 연산자 끼워넣기 같은 것을 포함한 순열이라는 느낌을 받고, 이를 구현해보려고 하다가, 잘 안되서 결국 못했다. 조합을 여러번 하는 것으로 구현해보려고 하다가, 너무 복잡해지는 감이있어서, 다시 완전탐색을 시도. 연산자는 최대 10개이고, 같은 연산자라도 다 다르다고 취급하고, 순열의 수를 생각해봤을 때, O(N!)의 시간복잡도를 가진다. 10! = 3,628,800 이므로 충분. 처음에는, 마지막 기저조건(return)에서 모든 결과값을 계산하는데 O(N)시간을 써먹어서 시간이 좀 느리게 나왔다. #include int N; int nums[12]; char opers[12]; int chk = 1 2019. 9. 19.
[SW Expert Academy] 1767. 프로세서 연결하기 DFS를 이용하지만, 조건이 덧붙여져있어서, return 되는 상황을 잘 생각해야하는 문제이다. 1) 전선이 연결된 코어 수는 최대가 되어야 하고, 2) 그 다음으로는, 전선 길이의 합이 최소가 되는 답을 찾으면 된다. 사실 이게 핵심이고, 나머지는 DFS이다. #include #include #include #include using namespace std; int N; int map_[12][12]; bool visited[12][12]; int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; vector cores; int core_num; int line_ans; void go(int startidx, int line_len, int core_cnt){ if (st.. 2019. 9. 18.
[SW] 8382 방향전환 쉬운 문제, 규칙을 찾는 문제. #include inline int abs(const int& a){ return a >= 0 ? a : -a; } int main() { int T; scanf("%d", &T); int x1, y1, x2, y2; for (int i=1; i ady) ans = 2 * ady; else ans = 2 * adx; int line = abs(adx - ady); if (line % 2) ans += 2 * line - 1; else ans += 2 * line; } printf("%d\n", ans); } return 0; } 2019. 9. 6.
[SW] 7732 시간 개념 인풋을 잘 나누어 받고, 자리수를 조정하여 계산할 수 있다면 쉬운 문제에 속한다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; string current, appointment; int ctime[3]; int atime[3]; int ans[3]; for (int i=1; i> current >> appointment; for (int j = 0, k = 0; j < 7; j += 3, ++k) { ctime[k] = stoi(current.substr(j, 2)); atime[k] = stoi(appointment.substr(j, 2)); .. 2019. 9. 5.
728x90