rainyCode rainyCode

#골드5 백준 12865번 문제는 정말 유명한 알고리즘인 knapsack 알고리즘의 대표문제이다. knapsack 알고리즘은 쪼갤 수 있냐 없냐에 따라 두 가지로 나뉘는데 만약 쪼갤 수 없다면, brute force와 dynamic programming으로 풀 수 있다. 그러나 brute force 방법은 시간복잡도가 O(2^n)만큼 잡아먹어서 n이 크다면 극악의 시간복잡도이다. 그래서 웬만한 ps에는 쓰이지 않을 것이다. 반면에 dp는 중첩 for문으로 이차원 배열을 사용하기 때문에 O(n^2)으로 쓸만하다. 추가적으로 만약 쪼갤 수 있는 knapsack 문제이면 greedy하게 해결도 가능하다. 이 방법은 다른 포스팅에서 다뤄보겠다. 문제 링크 https://www.acmicpc.net/problem..

#골드4 백준 9663번 문제는 백트래킹의 대표 문제인데, 백트래킹을 돌 조건식만 잘 세울 수 있다면 문제없이 풀 수 있을 것이다. 자네, 체스를 좀 해보았는가..? 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 이 문제의 핵심은 두 개이다. 1. 같은 행에는 퀸 1개만 놓을 수 있다는 것 2. 두 개의 퀸이 대각선에 존재하는지 체크하는 식이다. 같은 행에 퀸은 한개만 존재하기 때문에, col이라는 배열에서 i번째 원소의 값은 NxN 체스..

#백준 15654번 N과 M(5) 백준 15654번 문제는 백트래킹 개념과 dfs 개념만 알고 있으면 쉽게 해결할 수 있는 문제이다. 바로 전에 N과 M(4)를 풀고와서 혼자 힘으로 해결할 수 있었다. 개꿀! 문제 링크 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 이 문제에 대한 자세한 플로우는 비슷한 문제인 N과 M(4)에 흐름을 자세히 설명해 생략하겠다. https://rainycode.tistory.com/entry/..

#백준 15652번 N과 M(4) 백준 15652번 문제는 문제도 간단해서 언뜻 보기에는 쉬워 보이지만 백트래킹, 재귀에 관한 개념이 제대로 잡혀 있지 않다면 본인처럼 헤맬 수 있다. 문제 링크 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 dfs 함수는 재귀함수이고, 두 개의 파라미터를 가진다. num과 k인데, num은 1~N까지 숫자, 즉 출력되는 숫자라고 생각하면 된다. 그리고 변수 k는 배열의 길이이다. 배열의 길이를 파라..

🥇문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📎알고리즘 난이도: Gold3 그냥 다익스트라를 사용했다면 실버 난이도였겠지만 골드 문제답게 경로 출력을 추가로 시켜서 난이도가 확 올라간 모습이다. 기본적으로 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 이용해 주면 된다. 시간 복잡도를 O(N^2)에서 O(NlogN)으로 줄이기 위해 우선순위 큐(파이썬에서는 heapq)를 사용해 주었다. 쉽게 ..

문제링크 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 알고리즘 시작점이 주어지고 다른 노드까지의 최단거리를 주는 문제는 다익스트라 알고리즘의 정석이라고 할 수 있다. 간선의 가중치가 모두 양수이기 때문에 다익스트라 알고리즘을 사용할 수 있고, 만약 가중치에 음수가 포함된다면 밸만포드(Bellman-Ford) 알고리즘을 사용해야할 것이다. 다익스트라 알고리즘도 우선순위 큐를 사용하면 시간복잡도를 O(Nlo..

문제링크 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 알고리즘 이 문제를 보고 처음부터 BFS로 풀어야지~ 하고 생각하지 못한다면 나처럼 많이 헤맬 것이다. 재귀로 처음에 풀다가 recursion 에러가 왕창 나버렸다 일반적인 BFS 함수를 만들어주고 deque로 구현하는 습관을 들이자. popleft()는 list의 pop()보다 실행속도가 훨씬 빠르다. 추가적으로, 이번에 공부한 플로이드-..

백준 1932번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 이 문제는 규칙이 눈에 보여서 어떻게 코드로 잘 정리하냐가 관건인 문제 같다. 문제 링크 알고리즘 최댓값의 경로를 파악해야 하는데 dfs 같이 모든 경로를 탐색해 버리면 n이 최대 500개라 해보진 않았지만 분명 시간 초과가 날 것 같아, 위에서 부터 한번에 돌면서 최댓값을 찾는 dp를 이용해야된 다. dp 이중배열을 선언해 dp[i][j]라 하면, 위에서 부터 i번째 층에 왼쪽부터 j번째 값의 최댓값을 저장한다고 하자. 지금부터 dp배열의 값들을 구해볼 것이다. 우선 삼..