Cloud.log

정렬  ✔ list.sort() - 오름차순으로 정렬list = [3, 4, 2, 1, 5]list.sort()print(list)출력 결과[1, 2, 3, 4, 5]  ✔ list.sort(reverse = True) - 내림차순으로 정렬list = [3, 4, 2, 1, 5]list.sort(reverse=True)print(list)출력 결과[5, 4, 3, 2, 1]  ✔ sorted(list) - 오름차순으로 정렬list = [3, 4, 2, 1, 5]print(sorted(list))출력 결과[1, 2, 3, 4, 5]  ✔ sorted(list, reverse = True) - 내림차순으로 정렬list = ['A', 'B', 'C', 'D', 'E']print(sorted(list, reve..

➤ DP 알고리즘이란? 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하는 방식을 사용하여, 여러 번 반복되는 동일한 문제를 계산할 때의 비효율성을 방지하는 해결 방법이다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 위의 그림을 보면 같은 함수들이 여러번 호출되는 것을 볼 수 있다. 컴퓨터 상에서 연산을 할 때 같은 함수를 여러 번 호출하고 사용하다 보면 메모리 낭비가 되고, 연산 속도도 늘어나기 때문에 비효율적이다. 이러한 문제를 해결하기 위해서 사용하는 것이 동적 계획법이다. DP 알고리즘으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수..

에라토스테네스의 체란? 소수를 찾는 방법으로, 고대 그리스 수학자 에라토스테네스가 발견했다. 이 알고리즘을 사용하지 않고 단순히 소수를 구하려고 할 때 시간이 오래 걸리므로 소수를 구하고자 할 때 에라토스테네스의 체 알고리즘을 사용하는 것이 훨씬 효율적이다. Alogrithm 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색으로 표시) 자기 자신을 제외한 2의 배수를 모두 지운다. (선홍색으로 표시) 남아있는 수 가운데 2의 다음인 3은 소수이므로 오른쪽에 3을 쓴다. (초록색으로 표시) 자기 자신을 제외한 3의 배수를 모두 지운다. (연초록으로 표시) 위의 과정을 반복하면 구하고자 하는 구간의 ..

그래프 탐색(Graph Search) 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다. 단순히 그래프의 노드를 탐색하는 것으로 문제를 해결한다. 그래프 탐색에는 BFS/DFS가 있다. ✔ BFS(Breadth First Search) 정의 너비 우선 탐색이라는 뜻이고, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 아래의 그림을 보면서 쉽게 이해해보자. 위의 그림과 같이 6개의 노드와 5개의 간선(노드의 개수-1)이 있다. 노드 1번부터 시작해서 2번을 탐색하고 다음으로 4번 노드를 탐색하는 게 아닌 3번 먼저 탐색하는 것이다. 3번 옆에 아무것도 없으므로 다시 2번 노드로 돌아와서 2번 노드의 하위 노드 중 하나인 4번을 탐색한다. 4번을 끝냈으면 다..

그리디 알고리즘 정의 탐욕 혹은 욕심쟁이 알고리즘이라고도 하며, 탐욕이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 따로 알고리즘의 사용 방법을 알고 있어야 한다거나, 외워야 하는 건 없다. 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 대표적인 문제로는 거스름돈이 있다. 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JO..

1. 누적 합 알고리즘 정의 누적 합 혹은 부분 합 알고리즘은 말 그대로 구하고자 하는 구간의 누적된 합을 구하는 것이다. 예를 들어, 배열의 i ~ j 까지의 합을 구하고자 할 때 하나씩 더해가는 방식을 사용하는 경우에 최악의 경우 O(n^2) 시간복잡도가 생기기 때문에 메모리 낭비 혹은 시간이 오래 걸리는 문제가 발생한다. 이 문제를 해결 하기 위해서는 누적된 합을 구해 필요한 부분만 사용하고, O(N), O(1) 시간까지 단축시킬 수 있다. 2. 1차원 배열 인덱스 0 1 2 3 4 배열 10 20 30 40 50 누적 합 10 30 60 100 150 위 배열에서 인덱스 2번~4번 구간의 합을 구한다고 해보자. 4번 인덱스의 누적 합은 150(0번째~4번째 합)이다. 그러나 우리는 인덱스 2번부터..

Brute Force란? Brute : 신체적인 힘[폭력]에만 의존하는, 짐승같은 Force : 힘 Brute-Force : '온전히 힘으로만 모든 것을 다 해보겠다'라는 의미로 해석할 수 있다. ▷ 정리하면, 모든 경우의 수를 탐색하는 알고리즘이다. 그런 점에서 '완전 탐색 알고리즘'이라고도 한다. 특징 - 암호를 해킹할 때 주로 사용되었다. - 조합 가능한 모든 것을 하나씩 대입해 보는 방식이다. - 오래 걸리고 자원이 많이 들어가지만, 하나씩 다 해보기 때문에 100%의 정확도를 보장한다. ※ 코딩테스트에 단순히 이 알고리즘을 푸는 문제가 나오는 것이 아닌 모든 문제마다 부분적으로 필요할 수도 있다. 종류 선형 구조 : Sequential Search 비선형 구조 : Backtracking, DFS..