[이코테] 문제3 - 두 배열의 원소 교체(182p) (한줄평) 정렬만 할 줄 안다면 쉽게 해결할 수 있는 문제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 배열의 크기: n, swap 가능 횟수: k 라고 주어졌을 떄 A, B 2가지 배열의 원소를 각각 하나씩 swap하여 만들 수 있는 A의 원소 합의 최댓값을 구하는 문제다. A, B의 원소를 서로 바꿔 A의 원소 합이 최댓값이 되게 하려면 단순하게 A의 작은 수와 B의 큰수를 바꾸는 것을 최대 K번 반복하면 된다. 그러므로 A는 오름차순 정렬, B는 내림차순 정렬하여 0번부터 (k - 1)번 까지 값을 swap하면 된다. 여기서 중요 포인트는 A, B를 각각 정렬 해야함을 떠올리는 것이다. 단, A의 원소가 B의 원소보다 크거나 같으면 굳이 바..
[이코테] 문제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..
[이코테] 예제3 - 퀵정렬(Quick Sort)(168p) (한줄평) 예제 문제지만 quick sort가 익숙치 않아 복습이 꼭 필요!!! 풀이2는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, pivot과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다. (풀이1) 일반적인 코드 풀이 시간: 30분 이내 1) 문제 해결 아이디어 Pivot(기준)을 설정하여 정렬을 수행한 후 Pivot을 기준으로 왼쪽 리스트, 오른쪽 리스트에서 각각 정렬을 수행(왼쪽: pivot보다 작은 수들, 오른쪽: pivot보다 큰 수들) 1. 리스트의 원소가 1개인 경우 종료 2. Pivot(기..
[이코테] 예제2 - 삽입 정렬(Insertion Sort)(164p) 풀이 시간: 1) 문제 해결 아이디어 정렬된 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입 (첫번째 데이터는 정렬되어있다고 가정, 2번째 데이터부터 정렬 시작) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) 2) 소스코드 # 선택 정렬(Insertion Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] # 오름차순 정렬 # 1번 인덱스부터 시작 for i in range(1, len(array)): # 0 ~ i 인덱스 정렬 for j in range(i, 0, -1): # 현재값이 왼쪽값보다 크면 탈출 if array[j] > array[j - 1]: break # 현재값이 왼쪽..
[이코테] 예제1 - 선택 정렬(Selection Sort)(159p) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 (최솟값을 맨 앞에 있는 값과 바꾸고 그 다음 최솟값을 앞에서 2번째 값과 바꾸는 과정을 반복) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) swap: 리스트에서 두 변수의 위치를 변경하는 작업 파이썬에서는 간단하게 swap를 할 수 있음(tmp 사용할 필요X) arr = [1, 2, 3, 4, 5] # 0번째 & 1번째 값 서로 바꾸기 arr[0], arr[1] = arr[1], arr[0] 2) 소스코드 # 선택 정렬(Selection Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] #..
