JAEJAE imojeomo

그리디 알고리즘매 순간에 가장 최선의 선택을 해 답을 구하는 알고리즘조건: 매 순간에서의 최선의 선택 = 문제에서의 최적해접근 방식에 가까운 알고리즘임 그리디 알고리즘 사용 불가능한 경우 ❌ 매 순간에서의 최선의 선택 ≠ 문제의 최적해→ 수학적으로 접근하거나 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로 형 변환해서 사용

누적합 알고리즘DP 알고리즘에 속함전처리를 한 후에는 1차원・2차원 배열의 합을 𝑂(𝟏) 만에 구할 수 있는 알고리즘 1차원 배열에서 누적합음수 있어도 잘 동작함Dp 테이블 설계psum[n]: 1~n번째 원소까지의 합관계식psum[n] = psum[n-1] + arr[n]a부터 b까지 원소의 합을 구하는 방법psum[b] - psum[a-1] 2차원 배열에서 누적합2차원 배열의 세로 길이를 N, 가로 길이를 M이라고 할 때, 𝑂(𝑁𝑀) 의 전처리를 수행하면 됨DP 테이블 설계psun[n][m]: (1, 1)부터 (n, m)까지의 2차원 합관계식psum[n][m] = (psum[n][m-1] + psum[n-1][m] - psum[n-1][m-1]) + arr[n](sy, sx)부터 (ey, ex..