Algorithm

[백준 2533] 사회망 서비스(SNS) C++

2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #3 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 지난 포스팅 우수마을과 다르게 dp[now][0] -> 현재 친구가 얼리어답터가 아니라면 연결된 모든 친구는 얼리어답터여야 한다 이므로..

[백준 1949] 우수 마을 C++

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #2 [백준 15681] 트리와 쿼리 C++ 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1. hyeo-noo.tistory.com 이전 문제에서 아주 조금 개념이 추가된 트리 동적계획법 문제를 풀어보았다 만약 1번 ..

[백준 15681] 트리와 쿼리 C++

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #1 R이 트리의 기본 루트일 때 정점 U를 루트로 하는 Subtree에 속한 정점의 수를 출력 문제 이해를 위한 설명! 트리의 기본 루트는 5이다 사진에서 4를 루트로 하는 서브트리는 아래와 같다 그림과 같이 4를 루트로하는 서브트리의 정점은 1, 2, 3, 4 이다 (자신도 서브트리에 물론 포함) 트리의 리프노드 까지 가면 dp[now]를 반환한다(dp[i]의 초..

[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 돌대가리 건너기 다이나믹 프로그래밍 처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다.. 결국 어쩔 수 없이 구글을 참고했는데.. 단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다 dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수] 처음 dp배열을 -1로 초기화 시켜주고 현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..

[백준 1937] 욕심쟁이 판다 C++

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net DFS + DP dp[r][c]값 : 판다가 r, c에서 출발했을 때 최대로 살 수 있는 날을 저장 상하좌우로 움직이며 얻는 dp값들 중 최댓값을 현재 dp값으로 갱신한다 방문여부, 좌표별 최대 생존일의 메모이제이션을 통해 문제를 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

[백준 17136] 색종이 붙이기 C++

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹 연습하기 #3 삼성 A형 기출 문제 백트래킹을 효과적으로 적용하기 위해서 가장 큰 색종이 먼저 덮어줘야하는 그리디 기법이 사용되었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ..

[백준 2661] 좋은 수열 C++

2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 연습하기 #2 res : 지금까지 만들어진 수열 is_bad() 함수의 나쁜 수열 찾는 방법 ex1) res = 32121 start lo hi 0 32 121 1 21 21 -> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false ex2) res = 3212323 start lo hi 0 321 2323 1 212 323 2 12 323 3 23 23 -> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return f..

[백준 1759] 암호만들기 C++

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 연습하기 #1 Stack Permutation C++ 순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for hyeo-noo.tistory.com 이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다 추가된 조건들 암호를 이루는..

[백준 11404] 플로이드 C++

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최단경로 플로이드-와샬 알고리즘 11404문제 예제 입력의 그래프이다 숫자가 겹쳐보이는 이유는 1 4 1 , 1 4 2 처럼 1번에서 4번 노드로 가는 경우의 비용이 중복되어서 입력되기 때문이다 플로이드-와샬 알고리즘은 동적계획법을 활용한 알고리즘이다 그래서 임의의 vertax 에서 다른 vertax로 가는 모든 경우의 수를 조사해서 최소 비용을 구할 수 있다. 그리고 다익스트라 최단거리 알고리즘은 edge의 비용이 음수인 경우는 찾지 못하는 반면 플로이드-와샬 ..