무엇을 배웠나?
-
자료구조란 : 논리적인 관계를 통해 데이터를 모아놓은 구조
데이터의 특성에 따라 알맞는 자료구조를 선택할 수 있어야 한다. -
리스트 : 타 언어의 배열(array)에 해당하는 가장 기본적인 자료구조
-
튜플 : 값을 변경할 수 없는 리스트
메소드 등이 적게 들어있기 때문에 메모리를 적게 사용한다는 장점이 있다.
단순히 데이터를 전달하는 역할을 할 때 튜플을 사용하는 것이 메모리 측면에서 유리하다. -
리스트와 for loop
리스트를 직접 for loop에 넣어 인덱스 순서로 반복을 할 수 있고,enumerate함수를 통해 인덱스와 값을 한 번에 가져와 사용할 수 있다. -
리스트를 활용한 기초적인 알고리즘 : 리스트의 최대값, 최소값 구하기, 리스트 뒤집기
항상
reverse메소드를 사용했는데 배열의 크기가 n일 때n//2번의 교환으로 배열을 뒤집을 수 있다는 점을 새로 배웠다.
-
검색 알고리즘 : 원하는 값을 가진 원소를 찾아내는 알고리즘
-
선형 검색 : 리스트 구조에서 활용할 수 있는 가장 기본적인 검색, 0번 인덱스부터 배열의 끝까지 원하는 값을 찾을 때 까지 순차적으로 탐색한다.
-
보초법 : 선형 검색을 보완하는 방법으로, 조건 검사 비용을 줄인다.
기존 방법 : 검색값이 맞는지 확인하는 조건 + 배열의 끝인지 확인하는 조건 (최대 2n번)
보초법 : 검색값을 배열에 끝에 삽입하고, 검색값이 맞을 때만 배열의 끝인지 확인 (최대 n+1번) -
이진검색 : 데이터가 오름차순이나 내림차순으로 정렬되어있어야 적용이 가능하다.
방법 (오름차순 기준)
left 포인터와 right 포인터를 이용하고, mid 포인터는(left + right) // 2가 된다.
- mid 포인터의 값과 검색할 값을 비교한다.
- (a) mid 값보다 검색 값이 크다면 우리가 찾는 값은 mid보다 오른쪽에 있다는 뜻이 된다. -> left 를 mid+1로 옮긴다.
(b) mid 값보다 검색 값이 작다면 우리가 찾는 값은 mid보다 왼쪽에 있다는 뜻이 된다. -> right 를 mid-1로 옮긴다.- 검색 값을 찾을 때까지 1~2를 반복한다.
- 더이상 검색 가능한 범위가 없다면 left가 right보다 오른쪽에 위치하게 된다. 이때 검색 실패를 출력하고 반복을 빠져나온다.
새롭게 알게된 것
remove
- 리스트의 메소드 중 사용해보지 않았던
remove를 알게 되었다.
list.remove(value)로 리스트에서 value를 찾아 그 첫 인덱스를 반환한다. 찾는 값이 없다면ValueError가 발생한다.
iterator
for loop에는 range, 리스트, 문자열 등을 담을 수 있다.
정확히 말하자면 for loop에는 iterable를 담을 수 있다.
iterable는 '반복할 수 있는'이라는 뜻으로, 말그대로 반복이 가능한 객체를 의미한다.
iterable객체를 for loop에 넣으면 안에 있는 모든 요소를 하나씩 꺼내어(가능하면 순차적으로) 반복을 진행할 수 있다.
iterable에는 iter, dict, set, str, bytes, tuple, range 등이 해당한다.
만약 어떤 객체가 iterable인지 확인하고 싶다면 다음의 코드를 사용하면 된다.
# iterable 확인 방법
import collections.abc
object = [1, 3, 5, 7]
isinstance(var_list, collections.Iterable)
# True면 iterable, False면 Iterable이 아님기타
실습 풀이
최고의 집합
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12938
def solution(n, s):
answer = []
for i in range(n, 0, -1):
num = s // i
if num == 0:
return [-1]
answer.append(num)
s -= num
return answer기존에 풀어보지 못했던 문제 유형이었다.
어떻게 해야 곱셈값이 최고가 되는 집합이 나올지 고민하다보니 집합의 최소값을 최대화 하면 된다는 것을 발견할 수 있었다.
예를 들어 n=4, s=17이라면 {5, 4, 4, 4}가 최고의 집합이 되는데,
17//4 = 4 -> 13//3 = 4 -> 9//2 = 4 -> 5//1 = 5 이런식으로 집합을 구할 수 있다.
만약 s//n = 0 이라면 집합의 최소값이 0이되야한다는 뜻이므로 불가능을 출력하면 된다.
