algorithm quiz
-
[프로그래머스] Skill Treesalgorithm quiz 2019. 4. 14. 19:12
skill trees문제 설명선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.제..
-
[백준][1309] 동물원algorithm quiz 2018. 6. 1. 16:40
문제 : https://www.acmicpc.net/problem/1309 알고리즘 : DP자료구조 : 2차원 배열푸는 데 걸린 시간 : 30분~1시간?시간복잡도 : O(N) 2 X n 일 때 n번째 우리에 사자가 위치하는 경우에 따른 2X(n-1)번째는 다음과 같다. n번째 줄에 사자는 아예 없거나, 왼쪽에만 있거나, 오른쪽에만 있을 수 있다. 이 세가지의 경우의 수를 dp[n][0], dp[n][1], dp[n][2]라고 할 때 dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] dp[n][1] = dp[n-1][0] + dp[n-1][2] dp[n][2] = dp[n-1][0] + dp[n-1][1] 이다. 처음에는 사자가 1,2,3...n마리일 때 각각의 경우의 ..
-
[백준][11057] 오르막 수algorithm quiz 2018. 5. 30. 14:52
알고리즘 : DP 자료구조 : 2차원 배열 시간복잡도 : O(N * (10 + 9 + 8 + ....1)) = O(N) 푸는 데 걸린 시간 : 1시간 arr[N+1][10] 배열에서 arr[i][j]는 i번째에 j라는 수가 왔을 때 만들 수 있는 오르막 수의 갯수다. arr[1][j]는 자릿 수가 1인 오르막수의 갯수다. 따라서 arr[1][0], arr[1][1]...arr[1][9] 는 모두 1이다. (20~21라인 코드) arr[i+1][j]는 i번째 수가 0부터 9일 때 만들 수 있는 오르막 수의 갯수를 나타내는데, 오르막 수는 이전 숫자보다 같거나 큰 숫자만 허용하므로 i+1번째 수는 i번째 수가 0일 때 0, i번째 수가 1일 때 0,1 i번째 수가 2일 때 0,1,2 ... i번째 수가 9일..
-
[백준][1722] 순열과 순서algorithm quiz 2018. 5. 19. 18:31
문제 : https://www.acmicpc.net/problem/1722 1번 문제는 c++ STL의 next_permutation()을 사용했으나, cnt를 순차증가시키면서 비교하느라 최악 시간복잡도가 O(N!) 으로 나와서 틀린것으로 보인다. 2번 문제는 그럭저럭 푼거 같은데.. 백준 강의 다시봐야겠다. 문제 미해결. #include #include #include using namespace std; int factorial(int n){ if(n==0) return 0; int result = 1; for(int i=1; i>N; int pNum; cin >> pNum; int k; vector v; vector input; for(int i=1; i> k; int cnt = 0; do{ if(..
-
[백준][11048] 이동하기algorithm quiz 2018. 5. 9. 18:40
문제 : https://www.acmicpc.net/problem/11048 자료구조 : 행렬알고리즘 : DP시간복잡도 : O(3N) = O(N)푸는 데 걸린시간 : 1시간 10분 2차원 행렬을 사용하는 DP문제.(x, y)기준 (x, y-1), (x-1, y-1), (x-1, y)에 위치한 숫자들 중 최댓값을 (x, y)에 더한다. import java.util.Scanner; class Candy{ int x; int y; int num; Candy(int x, int y, int num){ this.x = x; this.y = y; this.num = num; } } public class Problem11048 { public static int N,M; public static Candy dp[..
-
[백준][1520] 내리막길algorithm quiz 2018. 5. 7. 15:54
문제 : https://www.acmicpc.net/problem/1520자료구조 : 스택, 인접행렬 알고리즘 : DFS + DP공간복잡도 : O(M*N) 시간복잡도 : O(M*N + E(num이 인접한 칸보다 작은 경우)) 푸는 데 걸린 시간 : 2시간 이상, 미해결 후 구글 검색 bottom-up 방식으로 mat[M][N]을 구하려고 했으나, mat(i-1, j), mat(j+1, j), mat(i, j+1), mat(i, j-1) 이 DFS를 재귀호출하면 먼저 호출된 쪽에서 visited를 갱신하므로 다른 곳에서 인접한 칸을 검사할 수 없는 문제가 발생한다. top-down으로 (M, N)에서 (1,1)을 향해 역순으로 경로의 수를 세야한다. import java.util.Scanner; class..
-
[백준][7569] 토마토algorithm quiz 2018. 5. 4. 13:39
문제 : https://www.acmicpc.net/problem/7569 "며칠이 지나면 모든 토마토가 익는지" = 숫자가 1인 정점에서 숫자가 0인 모든 정점으로 향하는 모든 최단경로들 중에서의 최댓값. 자료구조 : 3차원 행렬, 큐알고리즘 : BFS푸는 데 걸린 시간 : 1~2시간공간복잡도 : O(n) . X, Y, H의 범위는 1부터 100까지이므로 100^3 = 10^6. (4 * 5 +1)byte X 10^6 = 최대 21 메가바이트.시간복잡도 : O(n). 1초에 1억번 연산이 가능하다고 가정할 때 10^6 = 100만 연산도 가능. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Vert..