코딩테스트 준비 (48) 썸네일형 리스트형 백준 2581 소수 소인수분해 알고리즘 메모이제이션을 사용한 백준 2775번 유클리드 호제법 - 최대공약수 구하는 알고리즘, 최소공배수 def gcd(a, b): while b > 0: tmp = a a = b b = tmp % b return a 최소공배수는 두 수를 곱한 뒤 최대공약수로 나눠서 구할 수 있다. 예를 들어 18과 24의 최대공약수는 6이고 각각 6x3, 6x4로 나타낼 수 있다. 최소공배수는 6x3x4이므로, 18과 24를 곱한 뒤 최대공약수로 한 번 나눠주면 된다. def gcd(a, b): while b > 0: tmp = a a = b b = tmp % b return a 최소공배수 = a*b // gcd(a, b) 이진 탐색, 이진 탐색 트리. 이진 탐색 이진 탐색 = 반으로 쪼개면서 탐색하기. 시작점 인덱스, 끝점 인덱스를 입력 받아서 이 둘을 합쳐서 2로 나눈 값을 중간 값으로 설정한 후, 중간 값이 타겟 값보다 크면 중간값 이상의 값을 모두 버리고 중간값 이하 부분에서 똑같이 반복. 시간 복잡도는 O(logN). 탐색 범위가 2000만이 넘어가면 거의 무조건 이진 탐색을 써야한다고 보면 된다. 정말 중요한 코드이므로 꼭 암기해 두자!!!! ------------------------------------------------------------------------ 트리 자료구조 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베.. 정렬 알고리즘 1. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복. - 가장 원시적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택정렬 알고리즘이라고 한다. 선택 정렬의 시간 복잡도 선택 정렬은 n-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 따라서 약 n x (n + 1) / 2 번의 연산을 수행한다고 할 수 있다. - O(N**) = 매우 비효율적. 2. 삽입 정렬 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에.. 백준 9095번 1, 2, 3 더하기 백준 10828 스택 이전 1 2 3 4 5 6 다음
