본문 바로가기
728x90
반응형

백준34

[백준/Python] 11722 가장 긴 감소하는 부분 수열 문제: https://www.acmicpc.net/problem/11722  사용 알고리즘: DP  수열 A 가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 문제 ex) A = {10, 30, 10, 20, ,20, 10} -> 30, 20, 10  입력수열 A 의 크기 N (1 수열 Ai (1   여기서 중요한 것은 부분 수열이 연속적일 필요가 없다는 것!-> 이중 for 문을 돌면서 현재 위치의 수와 (처음~현재 위치) 까지의 수들을 비교해서 현재 위치에서 가장 긴 감소하는 배열의 길이를 찾기 i 는 현재 위치, j 는 처음~현재 위치까지 수들을 비교하기 위한 인덱스 현재 위치를 고정시켜놓고 현재 위치까지 수열을 돌면서 현재 위치와 방문한 수열의 값을 비교for i in range(n): .. 2024. 7. 2.
[백준/Python] 11726 2*n 타일링 문제: https://www.acmicpc.net/problem/11726  사용 알고리즘: DP  2 * n  크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법의 수를 구하는 문제 -> 전형적인 DP 문제  주어진 직사각형을 채우기 위한 방법의 수를 구하기 위해 도미노를 쪼개어 생각해보자. 1 * 2 / 2 * 1 의 두 가지 타일로 주어진 직사각형의 가장 오른쪽 부분을 채우는 방법을 생각해보면 아래와 같이 2가지 방법이 있다. -> dp[n] = dp[n-1] + dp[n-2]  # 입력n = int(input())# dp 초기화, 인덱스 1 부터 사용할 것이기 때문에 1001 칸을 만들어줌dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1):.. 2024. 7. 2.
[백준/Python] 1912 연속합 문제: https://www.acmicpc.net/problem/1912  사용 알고리즘: DP  입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)둘째 줄에는 n개의 정수로 이루어진 수열 (수는 -1,000 보다 크거나 같고, 1,000보다 작거나 같은 정수  n 개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. (단 수는 한 개 이상 선택해야 함)-> 부분합을 구하는 문제로 전형적인 dp 문제! 만약 dp 로 풀지 않는다면 이중 for 문을 써서 모든 [a, b] 구간합을 다 구해서 확인해야 한다. 이중 for 문을 써서 완전 탐색을 한다면 O(n^2) 의 Big-O 시간을 가지게 되고 문제에서 주어진 n 의 최대 값이 10만 이.. 2024. 6. 23.
[백준/python] 15665 - N과 M (11) 문제: https://www.acmicpc.net/problem/15665  사용 알고리즘: DFS 깊이우선탐색, 재귀  이 문제를 읽었을 때 바로 DFS 가 떠올랐다. 우선 내려갈 수 있을만큼 내려갔다가 방문할 수 있는 곳을 방문하면서 출력하면 되겠다고 생각했다.   구현로직 1. M 개의 수열 -> 몇 개가 될지 모름 -> 재귀를 이용해 타고 내려가기2. 재귀가 끝나야 할 조건-> M 개의 수열이라고 했으니, 방문한 노드가 M 개가 되면 리턴3. 재귀를 마치고 재귀함수가 호출됐던 곳으로 돌아왔다면 방문할 수 있는 노드를 모두 방문한 것이므로 pop 으로 큐에서 제거4. for 문을 돌면서 다시 방문할 노드 탐색 import sysfrom collections import deque# 입력N, M = .. 2024. 6. 4.
728x90
반응형

티스토리툴바