Today I learned
2022/01/17
회고록
1/17
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
7장 배열
1. 이론
파이썬의 배열은 여러 원소를 하나의 묶음으로 관리하고 각 원소간에는 순서(order)가 존재하여 인덱스(Index)를 통해 접근하는 리스트로 파이썬에서는 리스트(list)와 튜플(tuple)이라는 두가지 타입이 있습니다. 통상 프로그래밍 언어에서 배열은 동일한 데이터 타입의 원소들로 구성되지만 파이썬에서는 각 원소의 데이터 타입이 동일하지 않아도 되고 심지어 다른 배열을 원소로 갖는 것도 허용 됩니다. 배열간의 비교는 동일 인덱스 끼리 각각 비교해 가는 방식으로 적용 됩니다.
■ 리스트(list)와 튜플(tuple)
리스트(list)는 [1, 2, 3] 형태로 정의하며 각 원소를 수정 할 수 있는 특성을 갖습니다. []는 빈 list를 의미 합니다.
b = [1,"aa",3,4,5]
type (b)
<type 'list'>
튜플(tuple)은 (1, 2, 3) 형태로 정의하며 한번 정의한 원소를 수정 할 수 없는 특성이 있습니다. 튜플 원소에 대한 수정 작업은 "TypeError: 'tuple' object does not support item assignment" 같은 오류를 발생시킵니다. 원소의 추가 및 삭제도 할 수 없습니다. ()는 빈 tuple을 의미한다. 주의할 점은 원소가 하나만 있는 tuple은 일반적인 괄호와 구분이 되지 않기 때문에 ('A',)와 같이 기술하면 tuple임을 명시할 수 있습니다. 원소를 교체하거나 추가 하는 등의 작업은 새로운 튜플을 생성하는 방법으로만 가능 합니다. 아래의 예에서는 첫원소를 대문자 'A'바꾼 새로운 배열로 교체 했습니다.
b = ( 1, "aa", [3, 4, 5], 6, 7)
type (b)
<type 'tuple'>
t = ('a', 'b', 'c', 'd', 'e')
t = ('A',) + t[1:]
t
('A', 'b', 'c', 'd', 'e')
배열 내부에 또다른 배열을 갖는 경우 해당 원소에 대한 접근은 b[2][0]같은 방식으로 인덱스를 지정 합니다. 파이썬에서 배열의 인덱스는 0부터 시작합니다. 배열 내부에 이미 정의한 다른 배열 변수를 포함시키면 포함된 배열을 참조하는 형태로 관리되어 포함된 배열을 수정하면 포함한 상위 배열도 같은 내용을 보게 됩니다. 아래 예제를 보면 a 배열이 b 배열을 포함했는데, b[2][0]을 'test'로 변경했을때 a배열에도 동일한 내용이 반영되는 것을 확인할 수 있습니다.
print b
(1, 'aa', [3, 4, 5], 6, 7)
print b[2]
[3, 4, 5]
print b[2][0]
3
a = [3, b, 'aaa']
print a
[3, (1, 'aa', [3, 4, 5], 6, 7), 'aaa']
b[2][0] = 'test'
print a
[3, (1, 'aa', ['test', 4, 5], 6, 7), 'aaa']
2. 문제
Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.
Example 1:
Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
Example 2:
Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.
Constraints:
1 <= n <= 10^4
nums.length == 2 * n
-10^4 <= nums[i] <= 10^4
https://leetcode.com/problems/array-partition-i/
3. MySol
def listPartition(list):
print('before sort : ' + str(list))
list.sort()
print('after sort : ' + str(list))
groupPartition=[]
result=0
for item in list:
print('popping list : '+ str(list))
temp = []
for i in range(0,2):
temp.append(list.pop(0))
groupPartition.append(temp)
for item in groupPartition:
result+=min(item)
return result
if __name__ == '__main__':
n = [1,4,3,2]
result = listPartition(n)
print('result : ' + str(result))
문제가 처음에 의미를 이해하기 어렵다.
배열의 요소를 2개씩 묶고, 각 요소의 최솟값을 더했을 경우 결과가 다르다는 사실을 먼저 인식하자
[1,2,3,4]
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4생각해보면 오름차순으로 정렬 후 2개씩 묶는 방법이 가장 큰 값을 구할 수 있는 방법이다.
4. 배운 점
- 반복문 연습
5. 총평
반복문 훈련
