전체 글 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (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
코딩/백준 (Python)

백준 1806번: 부분합 (Python)

접근 이전 투포인터 알고리즘 문제들이 좌우 끝에서 가운데서 만날 때까지 연산했다면 이번 문제에서는 두 점이 0,0 으로 시작하여 마지막 점에 도달할 때까지 계산을 해주었다. 투포인터 알고리즘 설명 및 기본문제: 2021.04.24 - [코딩/백준 (Python)] - 백준 3273번: 두수의 합 (Python) 백준 3273번: 두수의 합 (Python) 접근 먼저 투포인터 알고리즘에 대해 알아보았다. 위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만 ca.ramel.be 두개의 점 left 와 right 이 각각 0, 0 에서 시작하여 left 에서 right 까지의 부분합이 s를 넘는지 체크하여 다음과 같이 계..

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

백준 2470번: 두 용액 (Python)

접근 투포인터 알고리즘을 이용하여 푸는 문제였다. 투포인터 알고리즘 설명 및 기본 문제: 2021.04.24 - [코딩/백준 (Python)] - 백준 3273번: 두수의 합 (Python) 백준 3273번: 두수의 합 (Python) 접근 먼저 투포인터 알고리즘에 대해 알아보았다. 위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만 ca.ramel.be 기존 투포인터 알고리즘과 동일하게 용액들을 오름차순으로 정렬한 후 탐색하되, 두 용액을 합한 특성값이 0보다 크면 right를 1 줄여주고 0보다 작으면 left를 1 키워주었다. 연산을 진행하는 동안 두 용액 특성 값의 절대값을 계속 갱신하면서 절대값이 작을때의 ..

2021. 4. 24. 18:44
코딩/백준 (Python)

백준 3273번: 두수의 합 (Python)

접근 먼저 투포인터 알고리즘에 대해 알아보았다. 위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만 이 경우 시간복잡도가 O(n^2) 이기 때문에 리스트의 데이터가 커지면 시간 초과가 발생할 확률이 높다. 이런 경우 투포인터 알고리즘을 이용할 수 있다. 투포인터 알고리즘은 다음과 같은 방식으로 작동한다. 리스트를 오름차순으로 정렬한다. left는 리스트의 왼쪽 끝, right는 리스트의 오른쪽 끝을 초기값으로 가진다. list[left] + list[right] 값이 원하는 수 x 보다 클 경우 right 값을 1 줄여준다. list[left] + list[right] 값이 원하는 수 x 보다 작을 경우 left 값..

2021. 4. 24. 15:18
반응형