분류 전체보기 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (Python)

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

접근 가장 긴 증가하는 수열은 동적계획법에서 나왔던 문제이고, 그때도 굉장히 오래 고민했던 기억이 난다. 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 접근 수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산 ca.ramel.be 이번 문제는 그와 같은 문제이긴 하지만 입력되는 수열의 크기가 훨씬 커서 동적계획법으로는 시간안에 풀 수 없다...고 하여 이분탐색 알고리즘을 이용해야 하는데, 사실 스스로 풀지 못하고..

2021. 4. 5. 19:52
코딩/백준 (Python)

백준 1300번: K번째 수 (Python)

접근 문제 설명에 '의외로 이분 탐색으로 풀 수 있는 놀라운 문제'라고 했는데 정말 신기하게 이분 탐색으로 풀 수 있었다. 이분 탐색 알고리즘으로 풀기 위해 고민을 좀 많이 하였다. 매 탐색 과정에서 cnt를 계산해 주는데, 이 cnt는 N * N 행렬의 각 행에서 mid 값보다 작은 수들의 개수를 의미한다. 물론 모든 행렬을 순환하면서 mid 값과 비교하지는 않고, min(n, mid // i) 수식을 이용하여 계산해주게 된다. 예를 들어 n이 3인 행렬에서 mid가 4일 경우, n값 3과 mid // i = 4 중 작은 값은 3이다. [1, 2, 3] 중 4보다 작은 값은 세개 모두 해당한다는 의미이다. 이런 식으로 계산하여 mid 값보다 작은 수들의 개수를 모두 구한 cnt와 target을 비교한다..

2021. 4. 5. 08:01
코딩/백준 (Python)

백준 2110번: 공유기 설치 (Python)

접근 이전 단계들에서 풀었던 이분탐색 알고리즘을 이용하여 풀 수 있는 문제고, 동일한 방식으로 탐색하면 된다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1654번: 랜선 자르기 (Python) 백준 1654번: 랜선 자르기 (Python) 접근 이분탐색 알고리즘을 이용한 문제였다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1920번: 수 찾기 (Python) 백준 1920번: 수 찾기 (Python) 접근 이분탐색 알고리즘을 이용하여 풀이를 하였다. 이분탐색.. ca.ramel.be 공유기 사이의 거리가 될 수 있는 값의 최소값은 1이고, 최대값은 (x[-1] - x[0]) // (c - 1) 이다. 예제 코드에서 주어진 집 좌표 [1, 2, 4, 8, 9] 에..

2021. 4. 5. 04:18
코딩/백준 (Python)

백준 2805번: 나무 자르기 (Python)

접근 이전 문제인 백준 1654번 랜선 자르기 문제와 매우 유사한 문제였고, 마찬가지로 비슷한 내용의 이분내용의 이분탐색 알고리즘을 이용하여 해결할 수 있었다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1654번: 랜선 자르기 (Python) 백준 1654번: 랜선 자르기 (Python) 접근 이분탐색 알고리즘을 이용한 문제였다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1920번: 수 찾기 (Python) 백준 1920번: 수 찾기 (Python) 접근 이분탐색 알고리즘을 이용하여 풀이를 하였다. 이분탐색.. ca.ramel.be 절단기가 자를 높이의 최소값, 최대값을 이용하여 최초 범위를 구하고, 이분탐색으로 높이를 탐색해가면서 잘려진 나무들의 길이 합이 목..

2021. 4. 5. 03:33
코딩/백준 (Python)

백준 1654번: 랜선 자르기 (Python)

접근 이분탐색 알고리즘을 이용한 문제였다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1920번: 수 찾기 (Python) 백준 1920번: 수 찾기 (Python) 접근 이분탐색 알고리즘을 이용하여 풀이를 하였다. 이분탐색 알고리즘은 오름차순으로 정렬된 리스트의 중간값과 찾고자 하는 값을 비교하여 중간값보다 찾고자 하는 값이 클 경우 중간값부 ca.ramel.be 가장 먼저 끈 길이 탐색의 범위를 정해주기 위해 끈 길이의 범위를 생각해보았다. 예를 들어 주어진 끈 중 가장 긴 끈을 목표 개수로 나눈 값이 끈이 될 수 있는 길이 중 최소값이며, 모든 끈을 더한 값을 목표 개수로 나눈 값(모든 끈을 남김 없이 효율적으로 썼을 때)이 끈이 될 수 있는 길이 중 최대값이다. 예를 들어 주어..

2021. 4. 5. 02:41
코딩/백준 (Python)

백준 10816번: 숫자 카드 2 -dictionary 이용 (Python)

접근 이전 글 같은 문제의 이분탐색 알고리즘을 이용한 해결에 이어, dictionary를 이용한 방법을 공부해 보았다. 2021.04.05 - [코딩/백준 (Python)] - 백준 10816번: 숫자 카드 2 -이분탐색 (Python) 백준 10816번: 숫자 카드 2 -이분탐색 (Python) 접근 굉장히 오랜 시간을 투자하여 푼 문제이다. 이분탐색 알고리즘을 이용하여 풀기 위해 최적화에 최선을 다하여 결국엔 제한 시간 내에 들어오는 코드를 작성하였다. 더 최적화시킬 방법을 ca.ramel.be 먼저 주어진 카드들을 한번 순회하면서 dictionary에 해당 카드가 몇장있는지를 저장하고, 찾아야하는 카드들을 순회하면서 해당 카드가 있는지, 몇개 있는지를 dictionary에서 찾아서 표시하는 방법이다..

2021. 4. 5. 01:37
반응형