본문 바로가기

백준23

[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.
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.
[백준] 15651 N과 M (4) - 중복조합 15650 N과 M (2)를 풀었다면, 정말 거저 먹는 문제이다! 시작하는 부분만 한 단계 낮추어, 중복이 가능하게 하면된다. 이것 역시 stack버전과, 그냥 배열을 쓴 버전 두가지를 참고하시라. #include int N, M; int a[10]; void repeated_combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15651 N과 M (3) - 중복순열 15650 N과 M (2)를 풀었다면 정말 쉽게 풀리는 문제이다. #include int N, M; char a[15]; void repeated_permutation(int depth){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] N과 M (2) - 조합 조합. depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다. 한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다. #include int N, M; int a[9]; void combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15649 N과 M (1) - 순열 단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다. 하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다. DFS는 그래프에서 깊이 우선 탐색을 의미하지만, 완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다. 백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다. 구현 코드 2개를 소개하고자 한다. #include using namespace std; int n, m; int a[8]; void swap_(int &a, int &b){ int temp = a; a = b; b = temp; } void rotateR(int start, int end){ int t.. 2019. 9. 19.
728x90

티스토리툴바