[Do it 알고리즘 코딩 테스트] 3-1. 배열과 리스트

배열과 리스트

파이썬에서 배열과 리스트는 따로 구별하지 않지만 각각의 특징을 알아두면 좋다. 파이썬의 리스트는 두 자료구조의 특징을 모두 가지고 있다.

 

1️⃣ 배열

배열은 연속된 메모리 주소 공간에 값이 채워져 있는 자료구조다. 배열의 값을 인덱스로 참조할 수 있으며 선언된 자료형만 저장할 수 있다.

 

📍 주요 특징

• 인덱스로 값을 참조할 수 있다. => 참조 O(1)
• 삽입, 삭제가 오래 걸린다. (삽입하거나, 삭제한 뒤 근처의 데이터들을 모두 옮겨줘야 한다.) => 삽입, 삭제 O(N)
• 처음 선언할 때 크기가 정해지고 그 다음은 크기를 수정할 수 없다 

 

 

2️⃣ 리스트

값과 포인터를 묶은 노드를 포인터로 연결한 자료구조다.

 

📍 주요 특징

• 값을 참조할 땐 처음부터 참조해 포인터를 타고 가야 한다. => 참조 O(N)
• 연속된 주소 공간에 저장되지 않고 포인터로 저장하기 때문에 삽입 삭제가 빠르다 => O(1)
• 선언할 때 크기를 정하지 않아도 된다. 크기가 변하는 데이터를 다룰 때 적합하다.

 

💡 파이썬의 리스트

파이썬의 리스트는 배열과 리스트의 특징을 모두 가진다. 하지만 모든 작업의 시간복잡도가 O(1)로 해결되는 건 아니다. 파이썬의 리스트는 구조상 배열을 따라하고 있다. 그래서 삽입과 삭제 시 O(N)이 걸린다. (append, poplast 등 양 끝에 하는 메소드는 O(1)이지만 deque를 사용하는게 양쪽 다 할 수 있으니 효율적이다.) 다만 인덱스로 값을 참조할 때는 O(1)이다. 

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

 

 

 

숫자의 합 구하기

문제

N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.

출력

입력으로 주어진 숫자 N개의 합을 출력한다.

예제 입력 1 

1
1

예제 출력 1 

1

 

 

1️⃣ 분석

입력받은 숫자들을 리스트에 넣자. 인덱스로 참조하면 O(1)이다. 숫자가 최대 N개니 O(N)이 걸린다. N이 100이므로 안전하다.

 

2️⃣ 손으로 풀어보기

 

문자열만 이용해서 문제를 풀 수도 있지만, 알고리즘을 활용하는 의미가 없어진다.

 

3️⃣ 슈도 코드

 

처음에 숫자를 문자열로 입력 받아서 인덱싱을 통해 리스트에 넣는다고 생각했는데, 비효율적인 로직이다. 입력받은 문자를 한번에 리스트로 변환하면 된다.

numbers = list(input())

input 함수는 입력값을 문자열로 저장한다. list() 함수는 리스트 클래스의 생성자 함수를 이용하는 것이다.

 

📍리스트 생성자

생성자는 항목들과 그 순서가 iterable과 같은 리스트를 만듭니다. iterable은 시퀀스, 이터레이션을 지원하는 컨테이너, 이터레이터 객체가 될 수 있습니다. iterable이 이미 리스트라면, iterable[:]과 비슷하게 복사본을 만들어서 반환합니다. 예를 들어, list('abc')는 ['a', 'b', 'c']를 반환하고 list( (1, 2, 3) )는 [1, 2, 3]를 반환합니다. 인자가 주어지지 않으면, 생성자는 새로운 빈 리스트인 []을 만듭니다.

아직은 뭔지 모르겠으니 나중에 정리하자.

https://wikidocs.net/25#input

04-2 사용자 입출력

 

https://docs.python.org/ko/3.13/library/stdtypes.html#list

Built-in Types

 

4️⃣ 코드 구현하기

 

for문을 range를 통해 구현했는데 for i in numbers처럼 배열에 직접 원소를 꺼내는 코드가 더 효율적이다.

 

 

평균 구하기

문제

세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다.

예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다.

세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다.

출력

첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답이다.

예제 입력 1 

3
40 80 60

예제 출력 1 

75.0

 

 

1️⃣ 분석

 

평균을 구할 때 결합 법칙으로 식을 정리하면, 과목 점수를 다 더하고 평균을 구해도 된다. 과목 점수 합을 구하고, 최댓값을 구하고 평균을 구하자. 그리고 결합 법칙을 활용하면 마지막에 추가로 점수 수만큼 나눠야 한다!

 

2️⃣ 손으로 풀어보기

 

최댓값을 구할 때 max()를 쓸건지 코드로 구현할 건지 고민했는데 이참에 max()를 찾아보자.

📍max()
max(iterable, *, key=None)

iterable 에서 가장 큰 항목이나 두 개 이상의 인자 중 가장 큰 것을 돌려줍니다. 하나의 위치 인자가 제공되면, 그것은 이터러블 이어야 합니다. iterable에서 가장 큰 항목을 돌려줍니다. 두 개 이상의 위치 인자가 제공되면, 위치 인자 중 가장 큰 것을 돌려줍니다.선택적 키워드-전용 인자가 두 개 있습니다. key 인자는 list.sort() 에 사용되는 것처럼 단일 인자 순서 함수를 지정합니다. default 인자는 제공된 iterable이 비어있는 경우 돌려줄 객체를 지정합니다. iterable이 비어 있고 default 가 제공되지 않으면 ValueError 가 발생합니다.여러 항목이 최댓값이면, 함수는 처음 만난 항목을 돌려줍니다.

📍python max()에서 이터러블한 객체 값들이 모두 int여야 하나요?

아니요, 파이썬 max() 함수에서 이터러블 객체의 요소들이 모두 정수형일 필요는 없습니다. max() 함수는 다양한 데이터 타입을 비교할 수 있으며, 비교 가능한 자료형이면 모두 사용 가능합니다. 예를 들어, 문자열, 숫자, 리스트 등 다양한 객체를 포함하는 이터러블 객체도 max() 함수로 최대값을 구할 수 있습니다. 단, 비교 연산이 가능한 자료형이어야 합니다.

https://docs.python.org/ko/3.13/library/functions.html#max

Built-in Functions

arr = ['10', '3', '98']
print(max(arr))

# >>> 98

정수형이 아니라도 비교가능한 자료형이라면 max를 사용할 수 있다.

 

3️⃣ 슈도 코드

 

 

4️⃣ 실제 코드 작성

 

💡문자열로 max를 찾으면 틀리는 이유

n = input()
numbers = input().split()
M = max(numbers)
sum = 0

for i in numbers:
    sum += int(i)

average = sum / int(M) * 100 / int(n)
print(average)

이 코드로 처음에 작성했지만 계속 틀렸다. 그 이유는 numbers가 문자열을 값으로 가지고 있는 상황에서 max()를 사용했기 때문이다.

arr = ['3', '20', '10']
print(max(arr))

# >>> 3

문자열로 max를 할 경우 앞자리가 큰 수 문자열이 큰 문자열로 반환된다. 이래서 틀린거다. 이걸 막기 위해선 리스트 안의 수들을 전부 정수로 바꿔줘야 한다.

 

그럼 list(input().split())과 list(map(int, input().split()))은 무슨 차이가 있는걸까? map()과 split()을 찾아봐야 한다.

📍str.split(sep=None, maxsplit=-1)
split()은 string 클래스의 메소드다. sep를 delimeter(기준)으로 사용하여 자른 단어들을 담는 list를 반환한다. 문자열에서 단어들을 자르고 이를 리스트로 반환한다는 소리다. sep이 없다면 whitespace(빈칸)을 기준으로 해 단어들을 자르고 리스트를 반환한다. input()이 문자열 만들기 때문에 split을 사용할 수 있다.

 

📍map(function, iterable, *iterable)

Return an iterator that applies function to every item of iterable, yielding the results. If additional iterables  arguments are passed, function  must take that many arguments and is applied to the items from all iterables in parallel. With multiple iterables, the iterator stops when the shortest iterable is exhausted.

이터레이블 안에 있는 모든 이터레이터들에 함수를 적용하는 함수다.

list(map(int, input().split()))은 이렇게 동작한다.

1. input().split()으로 문자열을 whitespace(빈칸)으로 잘라서 나온 단어(자료형 : 문자열)들을 리스트로 만든다.
2. 리스트는 iterable로서 map()의 인자로 들어간다. iterable 안에 있는 모든 iterator들은 int()를 통해 int로 형 변환한다.
3. 그렇게서 나온 map iterable은 list()를 통해 다시 리스트로 변환된다.

nums = map(int, input().split())
print(type(nums))

# >>> map

list()에 iterable이 들어가면 이를 list iterable로 변환해준다. map 함수 반환값은 map iterable이므로 list()를 통해 이를 리스트로 변환해준다.

 

https://docs.python.org/ko/3.13/library/functions.html#map

Built-in Functions

 

https://docs.python.org/3.3/library/stdtypes.html

4. Built-in Types — Python 3.3.7 documentation

코드를 작성하면,

n = int(input())
nums = list(map(int, input().split()))
M = max(nums)
sum = 0

for i in nums:
    sum += i
    
average = sum / M * 100 / n
print(average)

n = int(input())
nums = list(map(int, input().split()))
M = max(nums)
sum = sum(nums)    
average = sum / M * 100 / n
print(average)

sum()도 iterable을 넣으면 전체 합을 반환한다.