hado-dev-log 📚

문제 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 함수를 작성해주세요. 제한 조건 ..

정렬(sort) 이란? 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업이다. 파이썬의 리스트를 이용하면 직접 정렬 알고리즘을 구현할 필요가 없다. 파이썬 내장 함수 sorted() 리스트에 쓸 수 있는 메서드 .sort() 정렬의 순서를 반대로하길 원할 때 인자로 reverse = True를 넣어준다. 문자열로 이루어진 리스트의 경우 정렬 순서는 사전순서(알파벳 순서)를 따른다. 문자열 길이가 긴 것이라고 해서 더 큰 것이 아니다. 문자열 길이 순서로 정렬하고 싶다면 정렬에 이용하는 키(key)를 지정해준다. L = ['abcd', 'xyz', 'spam'] # 문자열 길이로 정렬 sorted(L, key=lambda x: len(x)) L = [ {'name': 'john', 's..

선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말한다. 보통 프로그래밍에서 배열이라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는것을 뜻한다. python에서는 리스트라는 데이터형이 있다. 데이터를 늘어놓은 모양새를 말할 때는 배열(array), 파이썬의 데이터형을 가리킬 때에는 리스트(list)라는 용어를 사용하겠다. 리스트(배열) 연산 리스트의 길이와 관계 없이 빠르게 실행 결과를 보게되는 연산들 O(1) 원소 덧붙이기 : .append(덧붙일 원소) 끝에서 꺼내기 : .pop(꺼내는 원소 위치) 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 O(n) 원소 삽입하기 : .insert(원소의 위치, 삽입할 원소) 원소 삭제하기 : del(리스트이름[삭제할 원소의 인덱스]) 추..