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

백준 1956번: 운동 (Python, PyPy3)

접근 처음에는 접근을 플로이드 와샬 알고리즘을 이용하여 모든 정점 사이의 이동 시간을 작성하고, i에서 j, j에서 i로 가는 이동 시간의 합들을 구하여 그 최소값을 표시하는 식으로 했더니 Python에서는 시간초과, PyPy3에서는 통과되었다. 플로이드 와샬 알고리즘 참고 문제: 2021.04.21 - [코딩/백준 (Python)] - 백준 11404번: 플로이드 (Python) 백준 11404번: 플로이드 (Python) 접근 문제 풀이에 앞서 플로이드 와샬 알고리즘이 무엇인지 공부해보았다. 이전에 풀었던 다익스트라 알고리즘이 하나의 점에서 출발했을 때 모든 정점까지의 최단 경로를 구했다면, 플로이드 ca.ramel.be 코드를 약간 수정하여, 기존 플로이드 와샬 알고리즘 3중 순환에서 i != j ..

2021. 4. 23. 01:42
반응형