Cherry & Cherish

문제 : 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 접근 : count를 통해서 풀어보려고 했는데 시간초과가 나왔고, 연속하는 숫자를 세기 위해서 while 문을 추가로 만들어서 s(start)와 e(end)라는 투포인터를 만들어서 문제를 풀어봤다. 하지만 또 시간초과가 나왔다. 그래서 결국 문제에 대한 풀이를 찾아봤고, 파이썬 내장 모듈인 bisect에 대해서 알게 되었다. bisect는 파이썬에 내장되어있는 이진탐색 모듈이다. bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스, bisect_r..

문제 : 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 접근 : 제한 숫자가 크기 때문에 시간 초과가 어떻게 해도 난다. 이진 탐색을 활용해서 문제를 풀었다. 풀이 : import sys def binary_search (array, target, start, end): while start target : end = mid - 1 else : start = mid + 1 return None N = int(input()) arr = sorted(list(map(int, sys.stdin.readline().split()))) M = int(i..

순차탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. count()메서드를 이용할 때도 내부에서는 순차탐색이 수행된다. 또, 특정 값의 원소가 있는지 확인하는 모든 순간에 순차탐색이 사용되며, 구현도 간단하다. def sequential_search(n, target, array): for i in range(n): if array[i] == target : return i + 1 순차탐색은 데이터 정렬 여부와 관계 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다. 따라서, 데이터의 개수가 N개일 때, 비교 연산이 필요하므로 순차탐색의 최악의 경우 시간 복잡도는 O(N)이다. 1. 이진 탐색 개념 💡 이진 탐색 - 정렬이 끝난 데이터를 시작점..

문제 : 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 접근 : 이전에는 이 문제를 조합으로 풀어야 하는지 고민했었다. (당연히 시간 초과 나온다.) 시간 때문에 정렬로 풀려고 접근했고, 처음에는 numbers의 객체를 문자열로 바꾼 뒤에, arr.sort(key=lambda x: x, revers..

문제 : 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 접근 : lambda를 활용하면 아주 손쉽게 풀 수 있다. arr에 추가할때, 알아보기 쉽도록, 국어 영어, 수학, 이름 순서로 append 했다. key=lambda x : (-x[0], x[1], -x[2], x[3])로 설정함으로서, 국어는 감소하고 영어는 증가하고, 수학은 감소하고..

문제 : 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 접근 : lambda를 활용해서 첫 번째 인자인 나이만 정렬하도록 했다. 정렬 문제는 출력 시 타입을 잘 확인해야 한다. 답은 맞는데 type 때문에 실패 처리된 케이스가 있었다. 풀이 : import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(list(sys.stdin.readline().split())) arr.sort(key=lambda x: int(x[0])) for i in range(n): print(ar..

문제 : 퀵 정렬을 구현해 N개의 정수를 정렬해 리스트 A에 넣고, A[N//2]에 저장된 값을 출력하는 프로그램을 만드시오. 접근 : 퀵 정렬 알고리즘을 적용했다. 풀이 : def quick_sort(arr): if len(arr) pivot: high.append(num) else: equal.append(num) return quick_sort(low) + equal + quick_sort(high) T = int(input()) for tc in range(1, T+1): N = int(input()) arr = list(map(int, input().split())) ans = quick_sort(arr) print(f'#{tc} {ans[N//2]}') 사실, 정렬 라이브러리로 훨씬 간편하게 ..

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다. 정렬 알고리즘은 상당히 다양한 종류가 있고, 파이썬에서는 기본 정렬 라이브러리를 사용해서 효과적으로 정렬할 수 있다. 1. 선택 정렬 1-1. 선택 정렬 개념 💡 선택 정렬 - “가장 작은 것을 선택” 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 1-2. 선택 정렬 구현(Python) array = ..