📌문제동빈이네 전자매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 📌풀이다량의 데이터 검색은 이진 탐색 알고리즘을 이용해 효과적으로 처리 N개의 부품을 번호 기준으로 정렬이후 M개의 찾고자 하는 부품이 정렬한 리스트에 존재하는지 확인 이진 탐색은 정렬 되어 있어야만 사용 가능 📌코드def binary_search(array, target, start, end): while start target: en..
📌이진 탐색배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘배열이 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징 위치를 나타내는 변수 3개 사용시작점, 끝점, 중간점 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾음 한번 확인할 때마다 확인하는 원소가 절반씩 줄어든다는 점에서 시간 복잡도 O(logN) 📌재귀 함수로 구현한 이진 탐색def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if ar..
📌문제동빈이는 두 개의 배열 A, B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.N, K 그리고 배열 A, B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최대값을 출력하는 프로그램을 작성하시오. 📌풀이배열 A에서 가장 작은 원소를 골라서 배열 B에서 가장 큰 원소와 교체단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 함이 ..
📌문제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씩 증..