반응형 실버314 [백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13. [백준] 9095번 - 1,2,3 더하기 (Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 메모이제이션을 좀 안다고 생각했는데 한 방 먹은 문제다. 1시간 동안 고민했는데 풀지 못했다. 알고 봤더니 1~3까지 숫자를 계산할 때 약간의 상상력을 보태야 하는데 그까지 생각이 미치지가 못했다. * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1) DP 테이블 정의 - DP테이블은 1,2,3의 합으로 조합할 수 있는 경우의 수를 가진다. - 정수 n은 < 11이므로 DP[10+1]로 구성해서 값을 미리 구한 다.. 2022. 9. 28. [백준] 1003번 - 피보나치 함수 (Java) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. DP 테이블의 성격 정의 - DP[N][2]로 생성해서 DP[i][0]에는 0의 출력 횟수, DP[i][1]에는 1의 출력 횟수를 저장한다. - N 2022. 9. 27. [백준] 1463번 - 1로 만들기 (Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1. 테이블 정의 DP[i] = 정수 i를 1로 만들때까지 걸리는 연산 횟수의 최소값 2. 점화식 찾기 DP[12]의 경우 a. 3으로 나눌 경우 -> DP[12] = DP[4] + 1 -> DP[x] = DP[x/3] + 1 b. 2로 나눌 경우 -> DP[12] = DP[6] + 1 -> DP[x] = DP[x/2] + 1 c. 1을 뺄경우 -> DP[12] = DP[11] + 1 .. 2022. 9. 26. [백준] 2606번 - 바이러스 (Java)(◎) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 컴퓨터 번호가 정점, 네트워크가 간선이다. 2. 바이러스가 감염되는 컴퓨터의 수는 간선을 통해 방문할 수 있는 정점의 수와 일치한다. 3. 1번 정점부터 dfs로 탐색을 해서 마지막에 카운팅한 수를 출력하면 된다. 4. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력이니까 1번 컴퓨터는 카운팅하면 안된다. 1. 인접배렬로 입력값을 저장하고, 배열번호는 정점의 번호와 동일하게 1~.. 2022. 8. 31. 이전 1 2 다음 반응형
