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

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

접근 바로 직전 문제와는 다르게 수열의 크기가 매우 커져서 2중 for문을 순환하는 알고리즘은 사용할 수 없다. 이전에 풀었던 '가장 긴 증가하는 부분 수열 2' 문제는 동일하게 수열의 크기가 매우 커서 dp 수열을 이분탐색하여 갱신하는 알고리즘을 사용하였는데, 이 방법을 발전시켜 이번 문제를 풀 수 있다. 2021.04.05 - [코딩/백준 (Python)] - 백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python) 백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python) 접근 가장 긴 증가하는 수열은 동적계획법에서 나왔던 문제이고, 그때도 굉장히 오래 고민했던 기억이 난다. 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열..

2021. 4. 25. 20:57
코딩/백준 (Python)

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

접근 이번 문제는 입력 받는 수열의 길이가 길지 않아 전체를 다 탐색하는 dp 알고리즘을 이용하였다. dp 알고리즘으로 길이만 구하는 문제: 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 접근 수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산 ca.ramel.be 이전 문제와는 다르게 해당 수열을 구해야 한다는 점이 다르다. 따라서 dp에 부분 수열의 길이만 저장하는 것이 아닌, 해당 길이의 부분 수열을 같이 ..

2021. 4. 25. 19:11
코딩/백준 (Python)

백준 18870번: 좌표 압축 (Python)

접근 좌표를 압축한 결과는 그 값보다 작은 '서로 다른 좌표의 개수'와 같다. 따라서 입력받은 좌표들을 set으로 바꾸어 중복을 제거해주고 정렬해주면 해당 좌표가 몇번째로 작은 좌표인지, 즉 해당 좌표보다 작은 좌표가 몇개인지를 확인할 수 있다. 인덱스를 딕셔너리 형태로 저장해주고, 각 좌표에 따라 불러옴으로써 문제를 해결할 수 있다. 코드 import sys n = int(sys.stdin.readline()) points = list(map(int, sys.stdin.readline().split())) points2 = list(sorted(set(points))) dic = {points2[i]: i for i in range(len(points2))} print(*[dic[i] for i in ..

2021. 4. 25. 18:40
코딩/백준 (Python)

백준 12852번: 1로 만들기 2 (Python)

접근 이전에 풀었던 1로 만들기 문제와 동일하게 dp(dynamic programing) 방법을 이용하여 풀 수 있는 문제였다. 1로 만들기 기본 문제: 2021.03.28 - [코딩/백준 (Python)] - 백준 1463번: 1로 만들기 (Python) 백준 1463번: 1로 만들기 (Python) 접근 단계별 이전 동적계획법 문제들과 유사한 문제였다. 2021.03.28 - [SW/백준 (Python)] - 백준 2579번: 계단 오르기 (Python) 백준 2579번: 계단 오르기 (Python) 접근 단계별 문제에서 동적 계획법 이전 문.. ca.ramel.be 기존 문제와 다른 점은 경로를 저장해주어야 한다는 점이다. 기존 코드 dp에 경로도 저장해 주었고, 경로를 표시해주는 코드도 추가하였다..

2021. 4. 25. 10:52
코딩/백준 (Python)

백준 1450번: 냅색문제 (Python)

접근 이 문제는 meet in the middle 이라는 알고리즘을 이용하여 푸는 문제이다. meet in the middle 알고리즘은 말그대로 한번에 연산하기 어려운 문제를 둘로 나누어 시간적인 단축을 꾀하는 알고리즘이다. 위 문제같은 경우 만약 주어진 n 이 30이라면, 부분 집합의 합은 각 원소가 있고 없고를 카운트하여 2 ^ 30의 경우의 수를 가지게 된다. 즉 2 ^ n 의 시간복잡도를 가지게 되는 것이다. 하지만 이를 반으로 나누어 2 ^ 15 정도만 되어도 기존에 비해 매우 할만해지는 숫자가 되기 때문에 meet in the middle 알고리즘을 사용하게 된다. 이 문제를 푸는 순서는 다음과 같다. weight 리스트를 반으로 나눈다. 보통 len(weight) // 2 를 기준으로 나누..

2021. 4. 24. 23:20
코딩/백준 (Python)

백준 1644번: 소수의 연속합 (Python)

접근 바로 이전에 풀었던 부분합 문제와 푸는 방식이 같았던 문제이다. 입력받은 n 까지의 소수를 모두 구한 후, 부분합에 사용했던 투포인터 알고리즘을 이용하여 부분합이 n과 일치할 때를 카운트하여 문제를 해결할 수 있다. 소수 구하기 참고 문제: 2021.03.25 - [코딩/백준 (Python)] - 백준 9020번: 골드바흐의 추측 (Python) 백준 9020번: 골드바흐의 추측 (Python) 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 ca.ramel.be 부분합 투포인터 알고리즘 문제: 2021.04.24 - [코딩/백준 (Pyt..

2021. 4. 24. 21:09
반응형