JAEJAE imojeomo

백준 2579. 계단 오르기 - 실버III문제 설명계단 규칙1. 한번에 1개 or 2개2. 연속된 3개 밟을 수 없음. 단, 시작 계단 포함 X3. 마지막 계단 꼭 밟기⟹ 점수 최대값?  * 주의 1처음 3칸에 대한 초기화 먼저 해야함! (계단이 3개 밖에 없을 경우 고려!)dp[1]의 최대 → 그냥 계단 1칸dp[2]의 최대 → 계단 1칸 + 계단 2칸dp[3]의 최대 → max(③ + ②, ③ + ①) * 주의 2이 문제는 계단의 크기가 한정되어 있었음(301개 최대)! 그래서 리스트의 크기를 N개(실제론 (n+1)로 구현)로 설정하면 런타임에러가 뜸!→ 301이 더 작으니깐 주어진 조건 그냥 쓰자~파이썬 코드N = int(input())stairs = [0] * 301for i in range(1,..

그리디 알고리즘매 순간에 가장 최선의 선택을 해 답을 구하는 알고리즘조건: 매 순간에서의 최선의 선택 = 문제에서의 최적해접근 방식에 가까운 알고리즘임 그리디 알고리즘 사용 불가능한 경우 ❌ 매 순간에서의 최선의 선택 ≠ 문제의 최적해→ 수학적으로 접근하거나 DP(시간복잡도가 𝚶❨𝚴❩임)를 이용 실제 문제에서 그리디 알고리즘매 순간에서의 최선의 선택 = 문제의 최적해 를 만족하는지 판단할 것때에 따라, 위의 조건이 만족하도록 문제를 재해석 하는 능력도 필요만약, 재해석을 해도 그리디를 적용할 수 없다면 다른 풀이를 떠올려야 함(브루트포스 or DP or 수학)Tip! 정렬과 그리디는 함께 사용되는 경우가 많음

정렬 알고리즘어떤 기준에 대해 우선 순위가 높은 순서로 원소를 재배치(오름차순, 내림차순 etc.)오름차순: 작은 순으로 정렬(ex: 1, 2, 3)내림차순: 큰 순으로 정렬(ex: 3, 2, 1) 종류𝑶(𝑵²): 선택, 삽입, 버블𝑶(𝑵⦁𝑙𝑜𝑔𝑵): 병합, 퀵파이썬 정렬함수는 병합 정렬함수 기반으로 함 파이썬에서 정렬함수sort() 함수: 리스트에서만 사용 가능sorted() 함수: iterable한 모든 것(순서가 있는 것)에 사용 가능기본으로 오름차순 정렬임리스트로 형 변환할 수 있는 객체면 sorted()함수 사용 가능딕셔너리를 리스트로 형 변환하면 키만 담김문자열도 sorted()함수 사용 정렬 가능(이때, 문자열은 아스키코드 기준으로 정렬됨)reverse 옵션을 False로 설정..

브루트 포스 알고리즘모든 경우를 살펴보는 알고리즘100% 정답을 도출해내지만 수행시간이 오래걸림 브루트 포스 알고리즘 사용 가능한 경우 ⭕️조건 수가 작은 경우(시간 초과가 나지 않을 정도로) 브루트 포스 알고리즘 사용 불가한 경우 ❌조건으로 걸린 수의 크기가 너무 큰 경우 (예: 1,000,000 이하의 자연수의 소수 개수 출력)𝑶(𝑵²) 풀이를 사용하면 약 1조 번의 연산이 필요하므로 시간 초과가 남대응: 여러 수에 대한 소수를 판별해야 하는 경우, 에라토스테네스의 체 알고리즘 이용에라토스테네스의 체 알고리즘: 𝑶(𝑵 𝑙𝑜𝑔(𝑙𝑜𝑔𝑵)최악의 경우인 𝑵 = 1,000,000 인 경우에도 약 500만 번의 연산 내에 문제 해결 가능 실제 문제에서 브루트 포스 적용대부분의 문제에서 사..

순열 알고리즘순열은 순서 있음 → check배열(원소의 사용 여부 나타냄)필요파이썬 Permutations 함수파이썬 itertools 모듈에 포함된 함수이며 순열을 생성해주는 함수Permutations(arr, num)arr: 배열Num: 뽑을 개수(안써주면 배열의 크기만큼 선택하게 됨)반환값은 모든 순열을 담은 객체를 반환하여 list로 형 변환해서 사용 조합 알고리즘N개의 원소 중에서 r개를 뽑는 모든 경우레 대해 살펴보는 알고리즘파이썬 combinations 라이브러리파이썬 itertools 모듈에 포함된 함수이며 조합을 생성해주는 함수Combinations(arr, num)arr: 배열Num: 뽑을 개수반환값은 모든 조합을 담은 객체를 반환하여 list로 형 변환해서 사용