Programming [Python]/백준 알고리즘 솔루션 (409) 썸네일형 리스트형 #393 백준 파이썬 [2805] 나무 자르기 - 이분탐색 https://www.acmicpc.net/problem/2805 SOLUTION 이분탐색으로 풀 수 있는 문제다. 정답비율이 난리나 있는 이유는 (아마) 초보자들이 선뜻 덤볐다가 시간 초과 폭탄을 맞지 않았나 하는 생각이 든다ㅎㅎ(본인 포함) 이분탐색에 대한 정의를 알고 오길 추천한다. (https://claude-u.tistory.com/267) 알고리즘은 쉽다. 벌목 높이를 움직여 필요 나무 길이를 채우는지 보는 것이다. 1) 가장 짧은 길이 1을 start로, 나무 중 가장 긴 길이를 end로 둔다. 2) 이분탐색이 끝날 때까지 while 문을 돌린다. 3) mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼 총 어느정도 길이의 벌목된 나무가 나오나 살펴본다. 4-1) 벌목나무.. #392 백준 파이썬 [7579] 앱 - 냅색 알고리즘 https://www.acmicpc.net/problem/7579 SOLUTION 유명한 냅색 문제, 냅색 알고리즘이다. 간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 출처: 위키피디아 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem) 해당 문제는 0-1 배낭문제의 경우다. 이 문제는 .. #391 백준 파이썬 [17626] Four Squares https://www.acmicpc.net/problem/17626 SOLUTION 라그랑주의 네 제곱수 법칙의 증명은 참조 (https://ko.wikipedia.org/wiki/%EB%9D%BC%EA%B7%B8%EB%9E%91%EC%A3%BC_%EB%84%A4_%EC%A0%9C%EA%B3%B1%EC%88%98_%EC%A0%95%EB%A6%AC) 하지만 우리는 해당 식을 증명하고자 하는 게 아니기 때문에 3번의 for문을 통해서 제곱수들의 최소 개수를 추려내볼 수 있다. 큰 숫자부터 차례대로 모든 숫자를 대입해 보는 것. 그리고 다음 숫자로 넘어가는 것 단 시간을 빠르게 하기 위해 range를 적절하게 조정[A**0.5 ~ (A//4)**0.5]해준다. PYTHON CODE n = int(input().. #390 백준 파이썬 [1654] 랜선 자르기 - 이분탐색 https://www.acmicpc.net/problem/1654 SOLUTION 이분탐색으로 풀 수 있는 대표적인 알고리즘 문제다. 정답비율이 난리나 있는 이유는 (아마) 초보자들이 선뜻 덤볐다가 시간 초과 폭탄을 맞지 않았나 하는 생각이 든다ㅎㅎ(본인 포함) 이분탐색에 대한 정의를 알고 오길 추천한다. (https://claude-u.tistory.com/267) 알고리즘은 쉽다. 랜선의 길이를 움직여 랜선 개수를 채우는지 보는 것이다. 1) 가장 짧은 길이 1을 start로, 랜선 중 가장 긴 길이를 end로 둔다. 2) 이분탐색이 끝날 때까지 while 문을 돌린다. 3) mid를 start와 end의 중간으로 두고, 모든 랜선 값을 mid로 나누어 총 몇개의 랜선이 나오나 살펴본다. 4-1) 랜.. #389 백준 파이썬 [12738] 가장 긴 증가하는 부분 수열 3 - LIS https://www.acmicpc.net/problem/12738 SOLUTION 최장 증가 부분 수열 (LIS : Longest Increasing Subsequence)문제이다. 흔치 않게 나무위키에서 제대로 자세하게 설명이 나와있기에 첨부한다. https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2 간단하게 말하자면 먼저 답이될 수열을 dp = [] 로 정의한 뒤 for문으로 주어진 리스트 앞쪽부터 검사를 진행한다. if: 현재 값이 수열에서 가장 크다면 --> dp의 가장 뒤에 값을 추가 else: 아니라면 --> 자신보다 큰 수 중 최솟값과 대치(이진탐색 이.. #388 백준 파이썬 [12015] 가장 긴 증가하는 부분 수열 2 - LIS https://www.acmicpc.net/problem/12015 SOLUTION 최장 증가 부분 수열 (LIS : Longest Increasing Subsequence)문제이다. 흔치 않게 나무위키에서 제대로 자세하게 설명이 나와있기에 첨부한다. https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2 간단하게 말하자면 먼저 답이될 수열을 dp = [] 로 정의한 뒤 for문으로 주어진 리스트 앞쪽부터 검사를 진행한다. if: 현재 값이 수열에서 가장 크다면 --> dp의 가장 뒤에 값을 추가 else: 아니라면 --> 자신보다 큰 수 중 최솟값과 대치(이진탐색 이.. #387 백준 파이썬 [1264] 모음의 개수 https://www.acmicpc.net/problem/1264 PYTHON CODE string = input() vowel = 'AaEeIiOoUu' while string != '#': answer = 0 for i in string: if i in vowel: answer += 1 print(answer) string = input() #385 백준 파이썬 [385] 돌 게임 2 https://www.acmicpc.net/problem/9656 SOLUTION https://claude-u.tistory.com/325참조 이기고 지는 사람만 바꾸면 된다. PYTHON CODE n = int(input()) if n % 2 == 1: print('CY') else: print('SK') 이전 1 2 3 4 5 6 ··· 52 다음
