[이코테] 문제1 - 부품 찾기(197p) (한줄평) 집합을 이용하여 쉽게 풀 수 있었던 문제! 하지만 다른 풀이 방법으로도 풀어보는 것을 추천! 이 문제는 부품 목록 n개, 손님이 구매를 원하는 부품 m개가 있을 때, 손님이 요쳥한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력하는 문제다. 이진 탐색, 집합, 계수 정렬 3가지 방법으로 모두 효과적으로 풀 수 있는 문제다. (풀이1) 집합(set)을 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 단순히 특정 수가 있는지 여부를 검사하면 되기 때문에 부품목록(graph)를 집합으로 선언한다. Q. 리스트가 아닌 집합으로 선언한 이유는? 집합에서 in 연산의 시간복잡도가 O(1)이고 리스트에서 in 연산의 시간복잡도는..
[이코테] 문제2 - 성적인 낮은 순서로 학생 출력하기(180p) (한줄평) 파이썬 기본 정렬 라이브러리를 이용하면 쉽게 풀 수 있었던 기본 문제! (풀이1) 기본 정렬 라이브러리 사용 풀이 시간: 3분 이내 1) 문제 해결 아이디어 sort()의 key에 정렬 기준을 명시하면 정렬 기준대로 정렬을 할 수 있다. 2) 소스코드 n = int(input()) # 학생 수 arr = [input().split() for _ in range(n)] # n명의 학생정보 # 성적을 기준으로 오름차순 정렬 arr.sort(key=lambda x: x[1]) for student in arr: print(student[0], end= " ") # 이름 출력 (풀이2) 계수 정렬 풀이 시간: 15분 이내 1) 문제 해..
[이코테] 문제1 - 위에서 아래로(178p) (한줄평) 정렬 알고리즘 예제 문제 수준으로 여러가지 정렬 알고리즘을 연습해볼 수 있는 문제! 퀵 정렬만 조금 더 연습해보면 좋을 듯! 이 문제는 n개의 수가 주어지고 내림차순 정렬을 하는 문제다. 수의 개수가 500개 이하로 매우 적고 모든 수는 1이상 100,000이하로 어떠한 정렬 알고리즘을 사용해도 해결할 수 있다. (풀이1) 파이썬 기본 정렬 라이브러리 이용 풀이 시간: 3분 이내 1) 문제 해결 아이디어 가장 단순한 방법으로 sorted()를 이용하여 해결하였다. 2) 소스코드 n = int(input()) arr = [int(input()) for _ in range(n)] # n개의 수 # 1. 정렬 라이브러리(내림차순) #print(*sort..
[이코테] 예제4 - 계수 정렬(Counting Sort)(174p) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 떄만 사용할 수 있지만 매우 빠른 정렬 알고리즘(데이터의 개수: n, 최댓값: k) 평균 시간 복잡도: O(n + k) 공간 복잡도: O(n + k) 2) 소스코드 # 계수 정렬(Counting Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count = [0] * (max(array) + 1) # 모든 범위를 포함하는 리스트 # 오름차순 정렬 for i in array: count[i] += 1 for i in range(len(count)): for j in rang..
