파이썬 2일차!
미팅하고 나면 항상 커피가 식어있다...ㅠㅠ
따뜻한 아메리카노 먹고싶어요.
이론 📝
자료구조 : 논리적인 관계로 이루어진 데이터 구성
리스트, 문자열은 비슷하게 처리가 가능하다.
리스트와 튜플이 쓸 수 있는 함수가 차이가 있다
튜플도 인덱스가 있다. 리스트보다 차지하는 메모리가 적다.
튜플: 원소의 값을 변경할 수 없는 리스트
💡 검색 알고리즘
📌 선형검색
나열되어 있는 데이터를 순차적으로 검색
맨 처음 배열부터 검색을 시작해서 데이터를 찾는다.
최악의 시나리오 : 데이터가 가장 마지막에 있는 것
⭐배열의 길이가 길어지는 만큼 검색 시간이 길어진다
📌 보초법
선형검색 과정에서 판단식을 줄이기 위하여 사용하는 방법
마지막 인덱스에 찾으려는 값을 추가해서 검색 과정을 간략화
(즉, 리스트 마지막에 특정값을 추가해서 자료구조를 새로 만듦.)
특정값을 마지막 전에 찾으면 검색성공,
마지막에서 찾으면 검색실패⭐ 선형 검색을 도와주는 방법
📌 이진검색
⭐정렬된 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색
1) 배열 인덱스의 중앙에 있는 값을 검사.
2) 이 값이 찾는 키 값과 일치하는지 확인.
3) 만약 키 값보다 작다면 배열의 앞 부분을,
3-1) 크다면 배열의 뒷 부분을 생각 X
4) 나머지 부분에 대해서만 검색을 시도
+++
lst = [None] * num
파이썬은 동적 배열을 생성하기 때문에 원소수를 맞춰 리스트 선언을 하지 않으면 내부 구현로직상 메모리가 많이 든다.
미니실습 📌
미니실습 1
원소의 최솟값 구하기
def min_of(data):
min_num = data[0]
for i in range(1, len(data)):
if data[i] < min_num:
min_num = data[i]
return min_num미니실습 2
리스트 입력받고 역순 출력
print('주의: "End"를 입력하면 원소 입력을 종료합니다.')
i = 0
x = []
while True:
s = input(f'x[{i}]값을 입력하세요.: ')
if s == 'End':
break
x.append(int(s))
i += 1
i = len(x)-1
print("list reverse")
for item in x[::-1]:
print(f'x[{i}] = {item}')
i -= 1미니실습 3
선형 검색 While 문을 사용하는 경우와 보초법을 사용하는 경우에 각각 if 조건문 실행 횟수 출력
선형검색 while문
def seq_search(data, key):
i = 0
cnt = 0
while True:
cnt += 1
if i == len(data): #못 찾음
return -1, cnt
cnt += 1
if data[i] == key: #찾음
return i, cnt
i += 1보초법
def seq_search_sentinel(data, key):
a = data.copy()
a.append(key)
i = 0
cnt = 0
while True:
cnt += 1
if a[i] == key:
break
i += 1
return (-1, cnt) if i == len(data) else (i, cnt)if문은 무조건 실행되니까 그 전에 cnt 넣어주기
횟수가 절반으로 줄어든다.
if문 하나 더 쓰고 덜 쓰고의 차이인듯??
📎 if - else : one line code
💡 결과 = A if 조건 else B
2개 이상의 변수 return 시 튜플로 데이터 묶어주기
💡 결과 = A if 조건 else B if 조건 else C
중첩해서는 이렇게 사용
실습 📌
실습 1
문제보고 바로 생각난 풀이
data = list(range(2,1001))
answer = []
for item in data:
flag = 0
for i in range(2,int(item**(1/2))+1):
if item % i == 0:
flag = 1
break
if flag == 0:
answer.append(item)
print(answer)data가 커지면 에라토스테네스의 체 알고리즘이 효율적
but, N의 크기만큼 리스트 할당해야 하니 메모리는 비효율적
📎 에라토스테네스의 체 알고리즘
- 2부터 N까지 존재하는 모든 자연수를 나열한다.
- 나열된 숫자 중에서 가장 작은 수를 x로 지정한다.
- 나열된 숫자 중에서 x의 배수를 모두 제거한다. (이때, x는 제거하지 않는다)
- 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.
실습 2
리스트 역순 출력
# 입력 파트
data = list(map(int,input("space로 분리하여 입력하세요. : ").split(" ")))
# 1
data.sort(reverse=True)
print(data)
#2
for item in x[::-1]:
print(f'{item}',end=" ")
#3
def reverse_list(a):
n = len(a)
for i in range(n // 2):
a[i], a[n-1-i] = a[n-1-i], a[i]
return a
answer = reverse_list(data)
print(answer)실습 3
이진검색 사용
# 입력 파트
print("리스트의 원소들을 space로 분리하여 입력하세요.")
x = list(map(int,input().split(" ")))
num = int(input('검색할 값을 입력하세요. : '))
# 이진검색 함수 파트
def bin_search(a, key):
a.sort()
pl = 0
pr = len(a)-1
while pl<=pr :
pc = (pl + pr) // 2 # 중앙값
if a[pc] == key: #중앙값이 key면 바로 리턴
return pc
elif a[pc] < key: #작으면 큰 쪽으로
pl = pc + 1
else: #크면 작은 쪽으로
pr = pc - 1
return -1 #그래서 없다고 리턴
# 출력 파트
index = bin_search(x, num)
if index == -1:
print(f'검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 a[{index}]에 있습니다.')실습 4
# 입력 파트
data = list(map(int,input("space로 분리하여 입력하세요.: ").split(" ")))
# 1
print(f'최대값 인덱스는 {data.index(max(data))}이고, 최대값은 {max(data)} 입니다.')
#2
def max_of(a):
maximum = a[0]
for i in range(1, len(a)):
if a[i] > maximum:
maximum = a[i]
return maximum
print(f'최대값 인덱스는 {data.index(max_of(data))}이고, 최대값은 {max_of(data)} 입니다.')추가실습 📌
추가실습 0
백준 10871번 : X보다 작은 수
N, X = map(int, input().split()) # N, X 를 입력받음
data = list(map(int, input().split(" "))) # 리스트를 입력받음
answer = []
for item in data:
if item < X :
answer.append(item)
print(*answer)📎 Asterisk(*)
💡 Unpacking
괄호 안에 있던 데이터들을 풀어 각각으로 만들어 준다.
💡 가변인자 *args, **kwargs
들어오는 인자의 개수를 모른다거나,
그 어떤 인자라도 모두 받아서 처리를 해야 할 때 사용
위치에 따라 정해지는 인자인 'positional arguments'는 *로 사용
키워드(=이름)을 갖는 인자인 'keyword arguments'는 **로 사용
kwargs는 함수를 호출할 때 key 통해 값을 주어야한다.
추가실습 1
프로그래머스 : 로또의 최고 순위와 최저 순위
내 코드
def solution(lottos, win_nums):
prize_lst = [6,6,5,4,3,2,1] #idx: 맞은 개수, value: 등수
lst = [item for item in lottos if item != 0] #0을 다 제거
cnt_0 = 6 - len(lst) #0의 개수
cnt_min = 0
for item in lst:
if item in win_nums:
cnt_min += 1 #최저 등수
return [prize_lst[cnt_0 + cnt_min],prize_lst[cnt_min]].count()를 쓰면 리스트 컴프리헨션으로 0의 개수를 세지 않아도 된다.
def solution(lottos, win_nums):
rank=[6,6,5,4,3,2,1]
cnt_0 = lottos.count(0)
ans = 0
for x in win_nums:
if x in lottos:
ans += 1
return rank[cnt_0 + ans],rank[ans]그냥 한 줄로 써버리기
딕셔러니랑 set 쓸 생각은 했는데 &를 생각 못 해서 여기까지 도달하진 못했다.
def solution(lottos, win_nums):
rank = {0: 6,1: 6,2: 5,3: 4,4: 3,5: 2,6: 1}
return [rank[len(set(lottos) & set(win_nums)) + lottos.count(0)], rank[len(set(lottos) & set(win_nums))]]추가실습 2
프로그래머스 : 없는 숫자 더하기
내 코드
def solution(numbers):
lst = list(range(1,10))
answer = list(set(lst) - set(numbers))
return sum(answer)천잰가?
def solution(numbers):
return 45 - sum(numbers)추가실습 3
def solution(store, customer):
answer = []
for item in customer:
if item in store:
answer.append('yes')
else:
answer.append('no')
return answer추가실습 4
프로그래머스 : N개의 최소공배수
내 코드
def lcm(a, b):
for i in range(max(a, b), (a * b) + 1):
if i % a == 0 and i % b == 0:
return i
def solution(arr):
start = arr[0]
arr = arr[1:]
for item in arr:
lcm_num = lcm(start,item)
start = lcm_num
return startmath나 기타 라이브러리를 쓰지 않도록 했다.
근데 이랬는데 코테에서 다 써도 되는 거 아님?
그럼 빡치는데;
추가실습 5
프로그래머스 : 최고의 집합
와;; 천재신가?
📎 곱이 가장 큰 합
💡 도출하기 위해서는 모두 공평하게 값을 나눠준 상태에서 나머지를 각각 1씩 더해주는것이 가장 크다는 아이디어
def solution(n, s):
if n > s:
return [-1]
x,y = divmod(s,n) #나머지를 1씩 더해주기 위해 divmod
answer = [x] * n #몫을 n개의 자연수가 되도록 곱합
for i in range(y): #나머지 만큼
answer[i] += 1 #값에 더해줌
return sorted(answer)추가실습 6
프로그래머스 : 제일 작은 수 제거하기
def solution(arr):
arr.remove(min(arr))
if len(arr)==0:
arr.append(-1)
return arr추가실습 7
프로그래머스 : 같은 숫자는 싫어
내 코드
def solution(arr):
answer = []
answer.append(arr[0]) #빈건 안되니 무조건 넣고
arr = arr[1:]
idx = 0
for item in arr:
if answer[idx] == item:
continue
answer.append(item)
idx += 1
return answer처음은 answer[-1:]하면 빈 리스트이고
[i]는 [arr[0]]과 같다.
answer[-1:]가 리스트로 리턴해서 [i]를 쓴 거다.
그래서 항상 answer의 끝 원소를 가져와서 arr에서 나오는 원소들과 비교.
같으면 continue 되어서 append없이 다음 반복을 시작한다.
이 방법이 되게 좋네...
def solution(arr):
answer = []
for i in arr:
if answer[-1:] == [i]: continue
answer.append(i)
return answer
