본문 바로가기

알고리즘, 자료구조55

[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.
[백준] 15663. N과 M(9) N과 M문제 중에 이 문제만 정답률이 47%로 낮다. 낮은 이유가 있었다. 중복되는 것에 대해서 트릭이 필요했다. 두 가지 방법을 소개한다. 수열 인덱스를 골라 나갈 것인데 예를 들어 4개중 2개를 골라보자. 4 2 9 7 9 1 2번 예제이다. 0 1 0 2 0 3 1 0 1 2 1 3 2 0 2 1 2 3 3 0 3 1 3 2 이 될것이다. 우선 v에 입력을 순서대로 저장하면 1 7 9 9 가 될 것인데, 저 순서대로 출력한다면, 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 이렇게 될 것이다. 중복되는 수열이 많다. 이것을 제거하는 방법은 해당 depth에서 새로운 인덱스를 고르기전에(for문전에) 이전 값을 기억하는 변수를 만드는 것이다.(before) 따라.. 2019. 10. 19.
[GCD 알고리즘] 최대공약수 알고리즘 GCD 알고리즘 GCD(Greatest Common Divider, 최대공약수)를 구하는 방법 중 하나로 유클리드 호제법(유클리드 알고리즘, Euclidean algorithm)이 있습니다. 유클리드 호제법은 간단합니다. a, b의 최대 공약수를 (a, b)라고 정의하면 다음과 같은 관계가 성립합니다. $$ \begin{align}(a, b) = (b, r) \newline &where, a \geq b, 0 \leq r < b\end{align} $$ 단, a, b는 정수이고, a를 b로 나눈 나머지는 r 입니다. 증명은 비교적 간단하지만, 수식이 조금 복잡할 수 있습니다. 따라서 최대한 핵심 수식만 쓰고, 나머지는 말로 풀었습니다. 증명은 다음과 같습니다. 1) $$ (a, b) = d, a = d .. 2019. 10. 18.
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.
[최단경로] 다익스트라(Dijstra) 알고리즘 30. 최단 경로 알고리즘 BFS와 구현방법이 상당히 비슷하다. 다익스트라 알고리즘 다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다. d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다. 아이디어는 BFS와 비슷한데, 가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다. 매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다. 이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다! 그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다. 이렇게 해서 직접 코드를 .. 2019. 9. 27.
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.
728x90