📌문제N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. 📌풀이N이 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘이나 O(N)을 보장하는 계수 정렬을 이용파이썬 기본 정렬 라이브러리도 가능학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬 수행 📌코드n = int(input())# N명의 학생정보를 입력받아 리스트에 저장array = []for i in range(n): input_data = input().split() # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 리스트에 저장 ar..
📌문제하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. 📌풀이파이썬이 기본 정렬 라이브러리 사용기본적인 정렬을 할 수 있는지 물어보는 문제 📌코드n = int(input())# N개의 정수를 입력받아 리스트에 저장array = []for i in range(n): array.append(int(input()))# 파이썬 기본 정렬 라이브러리로 정렬 수행array = sorted(array, reverse=True)# 정렬이 수행된 결과를 출력for i in array: print(i, end=" ") 내림차순 정렬을 할 경우 sorted 함수 인자에 r..
📌정렬 라이브러리 sorted(), sort()sorted() 함수최악의 경우에도 시간 복잡도 O(NlogN) 보장리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]result = sorted(array)print(result) sort() 함수리스트 변수 하나만 있을 때 내부 원소를 바로 정렬리스트 객체의 내장 함수별도의 정렬된 리스트를 반환하지 않음array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]array.sort()print(array) 📌sorted(), sort() 사용 시 key 매개변수key값으로는 하나의 함수가 들어가야..
📌heapq다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용파이썬의 힙은 최소 힙으로 구성(최소힙: 최상단 원소가 항상 가장 작은 원소)단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료 📌heapq 메서드heapq.heappush(): 힙에 원소 삽입heapq.heappop(): 힙에서 원소 꺼냄 📌힙 정렬을 heapq로 구현하는 코드import heapqdef heapsort(iterable): h = [] # 힙 result = [] # 결과 리스트 # 모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h,..
📌함수똑같은 코드가 반복적으로 사용되어야 할 때 함수를 사용함수를 작성할 때 함수 내부에서 사용되는 변수의 값을 전달받기 위해 매개변수 정의할 수 있음어떠한 값을 반환하고자 할 때는 return 사용매개변수나 return은 존재하지 않을 수도 있음(선택) 📌global 키워드함수 안에서 함수 밖의 변수 데이터를 변경해야 할 때 사용global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고 함수 바깥에 선언된 변수를 바로 참조a = 0def func(): global a a += 1for i in range(10): func()print(a) 📌람다 표현식함수를 매우 간단하게 작성하는 방법한 줄로 작성 가능def add(a, b): return a + b# 일..
📌리스트여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용파이썬의 리스트 자료형은 배열(Array)을 채택append(), remove() 등 메서드 지원 📌리스트 컴프리헨션리스트를 초기화하는 방법 중 하나대괄호 [] 안에 조건문과 반복문을 넣는 방식으로 리스트 초기화# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트array = [i for i in range(20) if i % 2 == 1]print(array) 2차원 리스트를 초기화할 때 효과적으로 사용# N x M 크기의 2차원 리스트 초기화n = 3m = 4array = [[0] * m for _ in range(3)]print(array) 📌언더바의 역할반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바 사용for ..
📌계수 정렬특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 정렬 알고리즘데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적 계수 정렬에서는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 함 선택, 삽입, 퀵 정렬처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아님 데이터의 크기가 제한되어 있다면 데이터 개수가 많더라도 빠르게 동작 정렬 방식1. 가장 작은 데이터부터 가장 큰 데이터까지 모두 담길 수 있도록 하나의 리스트를 생성2. 리스트의 모든 데이터가 0이 되도록 초기화3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증..
📌퀵 정렬가장 많이 사용되는 정렬 알고리즘기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작 피벗: 큰 수와 작은 수를 교환할 때 교환하기 위한 기준퀵 정렬을 수행하기 전 피벗을 어떻게 설정할 것인지 미리 명시 피벗을 설정하고 리스트를 분할하는 가장 대표적인 방식: 호어 분할 방식1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.3. 큰 데이터와 작은 데이터의 위치를 서로 교환하는 것을 반복한다.4. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 교환한다.5. 분할 완료: 피벗을 기준으로 피벗 왼쪽에는 피벗보다 작은 데이..
📌삽입 정렬특정한 데이터를 적절한 위치에 삽입삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 효율적선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸어서 비효율적 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정 삽입 정렬은 두 번째 데이터부터 시작, 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬(첫 번째 데이터는 이미 정렬이므로 N번이 아닌 N-1번) 📌삽입 정렬의 특징정렬이 이루어진 원소는 항상 오름차순 유지따라서 특정한 데이터가 삽입될 위치를 정할 때(삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이..
📌정렬특정한 기준에 따라 데이터를 순서대로 나열하는 것 📌선택 정렬데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복 매번 가장 작은 것을 선택한다 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬 완료마지막(N번째) 데이터는 가만히 두어도 이미 정렬된 상태 📌코드array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[..