hado-dev-log 📚

알고리즘들 중에는, 재귀 알고리즘이라고 불리는 것이 있다. 이것은 알고리즘의 이름이 아니라 성질이다. 주어진 문제가 있을 때 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법이다. 재귀함수 (recursive functions)란 ? 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것으로 생각보다 많은 종류의 문제가 재귀적으로 해결이 가능하다. # n! 팩토리알 def what(n): if n = 2 재귀함수 작성 연습을 의도한 것이므로, 재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다. def fibonacci(x): if x==0: return 0 elif x==1: retur..

병합정렬도 대표적인 '분할 정복' 방법을 채택한 알고리즘 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다. 퀵정렬은 피벗값에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있는데 병합정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다. 일단 반으로 나누고 나중에 합쳐서 정렬하자 병합정렬은 항상 반으로 나누기 때문에 피벗값이 따로 없다. 반으로 쪼개기 때문에 항상 logN을 보장한다. 합칠때는 2의 배수만큼 합친다. # 병합 정렬 (Merge sort) # 정렬배열은 반드시 전역 변수로 선언해줘야한다. (추가적인 배열) sortedArr = [] def merge(arr, start, middle, end): # start : m , end : n..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터가 커지면 사용하기가 어려운 알고리즘이다. 그래서 더욱 빠른 정렬알고리즘이 사용될 필요가 있다. 퀵 정렬 알고리즘은 대표적인 '분할 정렬' 알고리즘으로 평균속도가 O(N * logN)이다. 퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다. 일반적으로 퀵정렬에서는 기준값이 있다. 이를 피벗(Pivot)이라 한다. 보통 가장 앞에 있는 값을 피벗값으로 사용한다. 3 7 8 1 5 9 6 10 2 4 -> 3 2 8 1 5 9 6 10 7 4 ..

각 숫자를 적절한 위치에 삽입시킨다. 다른 정렬 박식들은 무조건 위치를 바꾸는 방식이었다면 삽입정렬은 필요할 때만 위치를 바꾸게 된다. 파이썬 코드 # 삽입 정렬 (Insertion Sort) def insertion_sort(arr): for i in range(len(arr)-1): # 현재 정렬할 원소를 선택해서 적절한 위치에 삽입할 수 있도록 j = i while arr[j] > arr[j + 1]: temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp j = j-1 return arr test = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] print("정렬된 데이터 : {}".format(insertion_sort(test))) 멈출 포인트를..

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다. 버블정렬은 구현은 쉽지만 효율성이 가장 떨어지는 알고리즘이다 파이썬 코드 # 버블정렬 (Bubble Sort) def bubble_sort(arr): # for문 배열의 크기만큼 반복 0부터 len(arr)미만까지 for i in range(len(arr)): for j in range(0, len(arr)-1-i): if arr[j] > arr[j+1]: # 두개의 값 바꾸기 temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp return arr test = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] print("선택 정렬된 데이터 : {}".format(bubble_sort(test))) 시간복잡도..

가장 작은 것을 선택해서 제일 앞으로 보낸다. 다음 10개의 수를 오름 차순으로 정렬해보자 1 10 5 8 7 6 4 3 2 9 가장 작은 숫자 1은 가장 앞쪽에 있으니 정렬이 된 것 1 10 5 8 7 6 4 3 2 9 -> 1 2 5 8 7 6 4 3 10 9 1을 제외하고 나머지 중에서 가장 작은 숫자 2를 가장 앞에 있는 10과 바꾼다. 1 2 5 8 7 6 4 3 10 9 -> 1 2 3 8 7 6 4 5 10 9 그 다음 가장 작은 숫자 3을 가장 앞의 숫자 5와 바꾼다. 이런 식으로 정렬을 하는 것이 선택정렬 파이썬 코드 # 선택정렬 (Selection Sort) # i와 j는 배열에 원소들을 반복적으로 탐색하기 위해 사용 # min 최소값 의미 # index 가장 작은 원소가 존재하는 위치..

문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한 조건 ..