백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 11054번: 가장 긴 바이토닉 부분 수열 (Python)

접근 백준 단계별 문제에서 바로 이전 단계인 11053번 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 2021.03.28 - [SW/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 접근 수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산 ca.ramel.be 다만 다른 점은 증가하는 수열이 아닌 바이토닉 수열(의미는 문제 참조)이기 때문에 증가하다가 감소하는 수열이어야 한다. 이를 해결 하기 위해 앞에서 부터 증가하는 부분 수열을 구할 뿐 ..

2021. 3. 29. 00:16
코딩/백준 (Python)

백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

접근 수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산을 계속한다. 예를 들어 i 0 1 2 3 4 5 A 10 20 10 30 20 50 dp 1 i = 1 을 탐색할 때, A의 0 ~ i - 1 요소 중 A[1] = 20 보다 작은 요소는 [10]이고, 이 요소들 중 dp 값의 최대값은 10이 가진 1이므로 dp[1] 에는 1을 더하여 2를 입력해 준다. i 0 1 2 3 4 5 A 10 20 10 30 20 50 dp 1 2 i = 2 를 탐색할 때, A의 0 ~ i - 1 요소 중 A[2] = 10 보다 작은 요소는 없으므로 dp[2]에는 ..

2021. 3. 28. 23:33
코딩/백준 (Python)

백준 10844번: 쉬운 계단 수 (Python)

접근 백준 단계별 문제 동적 계산법을 착실히 풀어왔다면 쉽게 풀 수 있다. 2021.03.28 - [SW/백준 (Python)] - 백준 1463번: 1로 만들기 (Python) 백준 1463번: 1로 만들기 (Python) 접근 단계별 이전 동적계획법 문제들과 유사한 문제였다. 2021.03.28 - [SW/백준 (Python)] - 백준 2579번: 계단 오르기 (Python) 백준 2579번: 계단 오르기 (Python) 접근 단계별 문제에서 동적 계획법 이전 문.. ca.ramel.be 다음의 접근 방법을 이용하여 점화식을 만들면 쉽게 풀 수 있다. 길이가 N인 i로 끝나는 계단 수의 개수 = 길이가 N-1인 i-1로 끝나는 계단 수의 개수 + 길이가 N-1인 i+1로 끝나는 계단 수의 개수 코드..

2021. 3. 28. 21:54
코딩/백준 (Python)

백준 1932번: 정수 삼각형 (Python)

접근 백준 단계별 풀이 순서로 풀고 있다면 바로 이전 문제인 1149번: RGB 거리와 매우 유사하게 풀 수 있다. 2021.03.27 - [SW/백준 (Python)] - 백준 1149번: RGB 거리 (Python) 백준 1149번: RGB 거리 (Python) 접근 [0, 0, 0] 리스트 N + 1개를 요소로 갖는 리스트(코드에서는 min_price)를 작성하여, 각 요소를 다음과 같은 의미를 갖도록 채운다. min_price[i][j] = i 번째 집에 j를 선택했을 때 채색 비용의 최소값 ca.ramel.be 제시된 삼각형과 같은 모습을 한 리스트를 작성하여, 해당 칸에는 해당 칸까지의 길 중 최대값을 입력하는 방법으로 해결할 수 있다. 점화식은 아래와 같다. max_route[i][j] = ..

2021. 3. 28. 00:41
코딩/백준 (Python)

백준 1149번: RGB 거리 (Python)

접근 [0, 0, 0] 리스트 N + 1개를 요소로 갖는 리스트(코드에서는 min_price)를 작성하여, 각 요소를 다음과 같은 의미를 갖도록 채운다. min_price[i][j] = i 번째 집에 j를 선택했을 때 채색 비용의 최소값 즉, min_price[10][0] 요소는 10번째 집에 R 색을 선택했을 때의 채색 최소값을 가지게 된다. 이는 다음의 점화식을 통해 구현할 수 있다. min_price[i][0] = min(min_price[i - 1][1], min_price[i - 1][2]) + price[i][0] # price는 해당 집 하나를 채색하는 비용 리스트 min_price[i][1] = min(min_price[i - 1][0], min_price[i - 1][2]) + price..

2021. 3. 27. 23:44
코딩/백준 (Python)

백준 1904번: 01타일 (Python)

접근 N이 증가함에 따라 변화하는 타일 배열 수 N 타일 배열 배열 수 1 '1' 1 2 '11' '00' 2 3 '111' '100' '001' 3 4 '1111' '1100' '1001' '0011' '0000' 5 5 '11111' '11100' 11001' '10011' '00111' '10000' '00100' '00001' 8 6 '111111' '111100' '111001' '110011' '100111' '001111' '110000' '100100' '001100' '100001' '001001' '000011' '000000' 13 정말 신기하게도 피보나치 수열의 배열과 동일하게 증가하게 된다. 코드 n = int(input()) num = [0, 1, 2] if n > 2: num ..

2021. 3. 27. 04:24
반응형