Beelog

programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제는 위와 같으며, 조합을 구해서 해결할 수 있는 문제였습니다. 1. 주어진 course 배열의 숫자만큼 코스 요리의 메뉴를 구성하기 때문에, course 배열을 반복하면서 몇개의 메뉴(A)로 코스를 결정할지 정하고 orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] course = [2, 3, 4] 2. 전체 주문 배열을 돌..

문제는 위와 같으며 책을 입력 받아 제목을 키로 하고 해당 책이 팔린 횟수를 값으로 하는 딕셔너리를 생성한 뒤, 먼저 횟수를 기준으로 정렬하고 횟수가 같으면 제목을 사전 순으로 정렬하여 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. 여기서는 기본적으로 제공되는 sorted 함수를 이용하여 문제를 해결하였는데 이 방식 말고 먼저 최대 값을 구한 뒤, 딕셔너리에서 값이 최대 값과 같은 키의 리스트를 생성하고 그 리스트를 정렬하는 방식으로도 문제를 해결할 수 있습니다. from sys import stdin n = int(stdin.readline()) books = dict() for _ in range(n): book = stdin.readline().strip() if book in boo..

문제는 위와 같으며 위 문제의 경우 데이터 개수가 최대 5,000,000 개이므로 NlogN 정렬 알고리즘을 통해 겨우 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin n, k = map(int, stdin.readline().split()) nums = list(map(int, stdin.readline().split())) nums.sort() print(nums[k - 1]) 병합 정렬을 직접 구현하여 문제를 푸는 경우는 제출할 때 pypy3 로 하면 좀 더 빠르게 계산되기 때문에 시간초과 에러를 해결할 수 있습니다. from sys import stdin # 병합 정렬 이용 def merge_sort(array): if len(array) == ..

문제는 위와 같으면 주어지는 수의 개수가 1,000,000 개까지 이므로 파이썬이 일반적으로 1초에 20,000,000 번의 연산을 수행한다고 할 때 NlogN 의 시간 복잡도를 가지는 정렬 알고리즘을 통해 문제를 해결할 수 있습니다. NlogN 의 시간 복잡도를 가지는 정렬 알고리즘은 병합 정렬, 퀵 정렬, 힙 정렬 등이 있으며 기본적으로 파이썬에 내장된 sort() 메소드 또한 NlogN 의 시간 복잡도를 가진다고 할 수 있습니다. 먼저, 파이썬에 내장된 함수를 사용하는 코드를 살펴보겠습니다. from sys import stdin n = int(stdin.readline()) nums = [int(stdin.readline()) for _ in range(n)] nums.sort() print("\..

문제는 위와 같으며 이 문제의 경우 계수 정렬 알고리즘을 사용하여 해결할 수 있습니다. 계수 정렬(Counting Sort) 알고리즘을 간략하게 살펴보면 배열의 인덱스 값을 특정한 데이터의 값으로 여기는 정렬 방법입니다. 배열의 크기는 데이터를 포함할 수 있도록 설정하고 해당 인덱스의 수가 등장한 횟수를 세는 방식입니다. 이 알고리즘은 주어지는 수는 많지만 수의 범위가 제한적일 때 효율적으로 사용할 수 있습니다. 파이썬 코드를 보면 다음과 같습니다. from sys import stdin n = int(stdin.readline()) nums = [0 for _ in range(10001)] # 배열의 크기는 10001 이고, 0으로 초기화 => [0] * 10001 로 써도 됨 for _ in rang..