3장 파이썬
1 리스트 컴프리헨션(list comprehension)
- 예시1
list(map(lambda x:x+10, [1,2,3]))- 예시2
[n*2 for n in range(1, 10+1) if n % 2==1]- 사용하지 않는 다면
a=[]
for n in range(1, 10+1):
if n % 2 == 1:
a.append(n*2)
a- 예시3
a={key:value for key, value in original.items()}- 예시4
- 최대한 표현식이 두 개가 넘지 않도록
str1 ="ajdASD"
import re
[
str1[i:i+2].lower() for i in range(len(str1)-1)
if re.findall('[a-z]{2}', str1[i:i+2].lower())
]
결과: ['aj', 'jd', 'da', 'as', 'sd']5장 리스트, 딕셔너리
1 에러 예외 처리
- IndexError: 인덱스가 리스트의 길이를 넘어설 때 발생
- 해결책: try 구문으로 에러에 대한 예외 처리 진행
try:
print(a[9])
except IndexError:
print('존재하지 않는 인덱스')
---2 딕셔너리
- 값 선언하기
a=dict()
a={'k1':'v1', 'k2':'v2'}
a['k3']='v3' # 별도로 값을 선언해서 넣어줌
a
>>> {'k1':'v1', 'k2':'v2', 'k3':'v3'}6장 문자열 조작
1 팰린드롬 여부 확인
팰린드롬: 앞뒤가 똑같은 단어나 문장, 뒤짚어도 같은 말이 되는 단어 또는 문장
- 방법1: 리스트로 변환
def isPalindrom(s):
strs=[]
for char in s:
if char.isalnum():
strs.append(char.lower())
while len(strs)>1:
if strs.pop(0) != strs.pop(): # 하나씩 빼면서 일치 여부를 확인
return False
return True # 모두다 통과한 경우 True를 반환
s="race a car"
isPalindrom(s)
>>> False- 방법2: 데크 자료형을 이용한 최적화 데크
def isPalindrome(s):
# 자료형 데크로 선언
strs : Deque = collections.deque()
for char in s:
if char.isalnum():
strs.append(char.lower())
while len(strs)>1:
if strs.popleft() != strs.pop(): # .popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
return False
return True- 방법3: 슬라이싱 사용
def isPalindrome(s):
s=s.lower()
# 정규식으로 불필요한 문자 필터링
s=re.sub('[^a-z0-9]','',s)
return s==s[::-1]문자열 슬라이싱
- s='안녕하세요'
- s[-1] == 요
- s[:-3] == 안녕(뒤에서 3개 글자 앞까지)
- s[-3:] == 하세요(뒤에서 3번째 문자부터 마지막까지)
- s[::1] == 안녕하세요(기본값)
- s[::-1] == 요세하녕안(뒤짚어줌)
- s[::2] == 안하요(2칸씩 앞으로 이동)
2 문자열 뒤집기
- 방법1: 투 포인터를 이용한 스왑
- 2개의 포인터를 이용해 범위를 조정해가며 풀이하는 방식
def reverseString(s):
left, right = 0, len(s)-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -=1
return s
s=['h','e','l']
reverseString(s)
>>> ['l', 'e', 'h']- 방법2: 파이썬 다운 방식
def reverseString(s):
s.reverse()
return s- 방법3: 슬라이싱
- 이때, 's=s[::-1]' 시행시 오류(p.146)
def reverseString(s):
s[:] = s[::-1]
return s3 로그파일 재정렬
def reorderLogFiles(logs):
letters, digits = [], []
for log in logs:
if log.split()[1].isdigit():
digits.append(log)
else:
letters.append(log)
# 2개의 키를 람다 표현식으로 정렬
letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
digits.sort(key=lambda x: (x.split()[1:], x.split()[0]))
return letters + digits
logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
reorderedLogs = reorderLogFiles(logs)
print(reorderedLogs)
>>>['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig2 3 6', 'dig1 8 1 5 1']2개의 키를 람다 표현식으로 정렬하는 방법
- sorted(s) 사용시 ['1A', '1B', '2A', '4C']
s= ['2A', '1B', '4C', '1A'] s.sort(key=lambda x:(x.split()[1], x.split()[0])) s >> ['1A', '2A', '1B', '4C']
sorted()의 key 옵션
- 예시 1
c=['ccc', 'aaaa', 'd', 'bb'] sorted(c, key=len) >> ['d', 'bb', 'ccc', 'aaaa']
- 예시 2
a= ['cde', 'cfc', 'abc'] def fn(s): return s[0], s[-1] # 첫 문자열과 마지막 문자열 순으로 정렬 print(sorted(a, key=fn)) >> ['abc', 'cfc', 'cde']
- 예시2-1 람다로
sorted(a, key=lambda s: (s[0], s[-1]))
4 가장 흔한 단어
- 금지된 단어 제외, 가장 흔하게 등장하는 단어 출력하기
- 방법 1 리스트 컴프리헨션, Counter 객체 사용
- \w: 단어 문자(Word character)
- => 해당 정규식은, 단어 문자가 아닌 모든 문자를 공백으로 치환하는 역할
- counts.most_common(1)까지 시행하면 [('ball', 2)]를 출력 => [0][0]을 이용해서 첫 번째 인덱스의 키를 출력 !
import re
from collections import Counter
def mostCommonWord(para, banned):
words= [word for word in re.sub(r'[^\w]', ' ', para)
.lower().split()
if word not in banned]
counts = collections.Counter(words)
return counts.most_common(1)[0][0]
mostCommonWord("bob hit a ball, the hit BALL flew far after it was hit", ['hit'])
>>> 'ball'5 그룹 애너그램
- 애너그램: 일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 과정
- 방법 1 정렬하여 딕셔너리에 추가
- .defaultdict(list): 존재하지 않는 키를 삽입하려 하는 경우 keyerror가 발생해, 에러가 나지 않도록 디폴트를 생성=> 매번 키 존재 여부를 체크하지 않고 비교 구문을 생략해 간결하게 구성할 수 있게 됨
from collections import Counter
def groupAnagrams(strs):
anagrams = collections.defaultdict(list)
for word in strs:
anagrams[''.join(sorted(word))].append(word)
return anagrams.values()
groupAnagrams(['eat','tea','tan','ate','nat','bat'])
>>> dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])6 가장 긴 팰린드롬 부분 문자열
팰린드롬: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열
- 방법 1 중앙을 중심으로 확장하는 풀이
def longestPalindrome(s):
# 팰린드롬 판별 및 투 포인터 확장
def expand(left:int, right:int):
while left >= 0 and right <= len(s) and s[left] == s[right-1]:
left -= 1
right += 1
return s[left +1:right-1]
# 해당 사항이 없을 때 빠르게 리턴
if len(s) < 2 or s == s[::-1]: # 길이가 2보다 짧거나, 뒤짚었을때 원래 같은 경우
return s
result = ''
# 슬라이딩 윈도우 우측으로 이동
for i in range(len(s)-1):
result = max(result,
expand(i, i+1),
expand(i, i+2),
key=len)
return result
longestPalindrome('babad')
>>> 'bab'3부. 선형 자료 구조
7장 배열
배열: 값 또는 변수 엘리먼트의 집합으로 구성된 구조, 하나 이상의 인덱스 또는 키로 식별
- 자료구조
- 1) 메모리 공간 기반의 연속 방식,
- 2) 포인터 기반의 연결 방식(8장 연결리스트)
추상자료형(ADT)의 실제 구현 대부분은 배열, 연결 리스트를 기반
-
예) 스택 -> 연결 리스트로 구현, 큐 -> 배열로 구현 (반대도 가능)
-
배열: 고정된 크기만큼의 연속된 메모리 할당
- 파이썬의 리스트 = 동적 배열 자료형(크기를 지정하지 않고 자동으로 리사이징하는 배열)
7 두 수의 합
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스 리턴하기
- 방법 1 브루트 포스로 계산
- 브루트 포스: 무차별 대입 방식
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
return [i, j]
twoSum([2,7,11,15],9)
>>> [0,1]- 방법 2 in을 이용한 탐색
def twoSum(nums, target):
for i, n in enumerate(nums):
complement = target -n
if complement in nums[i+1:]:
return nums.index(n), nums[i+1:].index(complement)+(i+1)
twoSum([2,7,11,15],9)
>>> (0,1)- 방법 3 첫번째 수를 뺸 결과 키 조희
def twoSum(nums, target):
nums_map = {}
# 키와 값을 바꿔서 딕셔너리로 저장
for i, num in enumerate(nums):
nums_map[num] = i
# 타겟에서 첫 번째 수를 뺸 결과를 키로 조회
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target-num]:
return nums.index(num), nums_map[target-num]- 방법 4 조회 구조 개선
def twoSum(nums, target):
nums_map ={}
# 하나의 for문으로 통합
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target-num], i]
nums_map[num] = i- 방법 5 투 포인터 이용
- 투 포인터: 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식
- 이 문제는 입력값인 nums가 정렬된 상태가 아니어서 -> 인덱스 엉망이 되고 결론적으로는 틀린 풀이 !
def twoSum(nums, target):
left, right = 0, len(nums)-1
while not left == right:
# 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
if nums[left] + nums[right] < target:
left +=1
# 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
elif nums[left] + nums[right] > target:
right -= 1
else:
return left, right8 빗물 트래핑
높이를 입력 받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하기
- 방법 1 투 포인터를 최대로 이동
- 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으며 -> 왼, 오른쪽을 가르는 장벽 역할을 함
- 목표: 가장 높이가 높은 막대, 즉 '최대'지점에서 좌우 포인터가 서로 만나면서 O(n) 풀이가 가능해짐
def trap(height):
if not height:
return 0
volume = 0
left, right = 0, len(height)-1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max),max(height[right], right_max)
# 더 높은 쪽을 향해 투 포인터 이동
if left_max <= right_max:
volume += left_max - height[left]
left += 1 # 오른쪽이 크다면, 왼쪽으로 이동
else:
volume += right_max - height[right]
right -= 1 # 오른쪽이 이동
return volume
trap([0,1,0,2,1,0,1,3,2,1,2,1])
>>> 5- 방법2 스택 쌓기
- 스택에 쌓아 나가면서 현재 높이가 이전 높이보다 높을 때, 즉 꺾이는 부분 변곡점을 기준으로 격차만큼 물 높이 채우기
- 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전과의 차이만큼 물 높이를 채워감
def trap(height):
stack = []
volume = 0
for i in range(len(height)):
# 변곡점을 만나는 경우
while stack and height[i] > height[stack[-1]]:
# 스택에서 꺼낸다
top = stack.pop()
if not len(stack):
break
# 이전과의 차이만큼 물 높이 처리
distance = i - stack[-1] -1
waters = min(height[i], height[stack[-1]])-height[top]
volume += distance * waters
stack.append(i)
return volume9 세 수의 합
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트 출력하기
- 방법 1 브루트 포스로 계산
- 브루트 포스: 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법\
- 타임아웃으로 문제 풀이 실패 가능성 있음
def threeSum(nums):
results = []
nums.sort()
# 브루트 포스 n^3 반복
for i in range(len(nums)-2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)-1):
if j>i+1 and nums[j] == nums[j-1]:
continue
for k in range(j+1, len(nums)):
if k>j+1 and nums[k] == nums[k-1]:
continue
if nums[i] + nums[j] + nums[k] == 0:
results.append((nums[i], nums[j], nums[k]))
return results
threeSum([-1,0,1,2,-1,-4])- 방법 2
def threeSum(nums):
results = []
nums.sort()
for i in range(len(nums)-2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i-1]:
continue
# 간격을 좁혀가며 합 sum 계산
left, right = i+1, len(nums)-1
while left < right:
sum=nums[i]+nums[left]+nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
# sum=0인 경우이므로 정답 및 스킵 처리
results.append((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return results10 배열 파티션 1
n개의 페어를 이용한 min(a,b)의 합을 만들 수 있는 가장 큰 수를 출력하라
- 방법 1 오름차순 풀이
- 페어의 min()을 합산했을 때 최대를 만들자 !
- 결국 min()이 되도록 커야 한다
- 페어의 min()을 합산했을 때 최대를 만들자 !
def arrayPairSum(nums):
sum = 0
pair =[]
nums.sort()
for n in nums:
# 앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair) == 2:
sum += min(pair)
pair= []
return sum- 방법2 짝수 번째 값 계산
- 일일이 min()을 구하지 않고 짝수번째 값 더하기
- 짝수번째에 정렬된 상태에서는 항상 작은 값이 위치하기 때문
def arrayPairSum(nums):
sum=0
nums.sort()
for i, n in enumerate(nums):
# 짝수번째 값의 합 계산
if i % 2 == 0:
sum += n
return sum- 방법 3 파이썬다운 방식
- [::2]로 두 칸씩 건너뛰어서 짝수 번째 계산하기
def arrayPairSum(nums):
return sum(sorted(nums)[::2])11 자신을 제외한 배열의 곱
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라(나눗셈을 하지 말고 풀이하라)
- 방법 1 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
def productExceptSelf(nums):
out=[]
p=1
# 왼쪽 곱셈
for i in range(0, len(nums)):
out.append(p)
p=p*nums[i]
p=1
# 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
for i in range(len(nums)-1,0-1, -1):
out[i]=out[i]*p
p=p*nums[i]
return out12 주식을 사고팔기 가장 좋은 시점
한 번의 거래로 낼 수 있는 최대 이익 산출하기
- 방법 1 브루트 포스로 계산
- 타임아웃으로 풀이 불가
def maxProfit(prices):
max_price = 0
for i, price in enumerate(prices):
for j in range(i, len(prices)):
max_price=max(prices[j]-price, max_price)
return max_price
maxProfit([7,1,5,3,6,4])- 방법2 저점과 현재 값과의 차이 계산
import sys
def maxProfit(prices):
profit = 0
min_price = sys.maxsize
# 최소값과 최대값을 계속 갱신
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price-min_price)
return profit파이썬 최대 최소 지정하기
mx=-sys.maxsize mn=sys.maxsize # 무한대 지정 mx = float('-inf') mn = float('inf
8장 연결리스트
13 팰린드롬 연결 리스트
파이썬 리스트 노드
- 방법 1 리스트 변환
9장 스택, 큐
연결리스트를 이용한 스택 ADT 구현
class Node:
def __init__(self, item, next):
self.item = item # 노드의 값
self.next = next # 다음 노드를 가리키는 포인터
class Stack:
def __init__(self):
self.last=None
def push(self, item): # 연결리스트에 요소 추가하면서 가장 마지막 값을 next로 지정, 포인터인 last는 가장 마지막으로 이동
self.last = Node(item, self.last)
def pop(self): # 가장 마지막 아이템 꺼내고, last 포인터를 한 칸 앞으로 전진(이전에 추가된 값을 가리키게)
item = self.last.item
self.last = self.last.next
return item- 직접 넣어서 확인 해보기
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)- 결과 보기
for _ in range(5):
print(stack.pop())20 유효한 괄호
괄호로 된 입력값이 올바른지 판별하기
1 스택 일치 여부 판별
(, [, {는 스택에 push하고 스택에서 pop한 결과가 ),},]를 만났을 때 일치하는지 확인하기
매핑 테이블을 만들고 테이블에 존재하지 않으면 푸시하고 팝했을 때 결과가 일치하지 않으면 False를 리턴하도록 구현
pop은 가장 최근에 삽입된 요소를 제거함
def isValid(s)-> bool:
stack = []
table= {
')':'(',
'}':'{',
']':'[',
}
# 스택 이용 예외 처리 및 일치 여부 판별
for char in s:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0
isValid('(}')
>>> False21 중복 문자 제거
중복된 문자를 제외하고 사전식 순서로 나열하기
1 재귀를 이용한 분리
사전식 순서: 사전에서 가장 먼저 찾을 수 있는 순서
def removeDuplicateLetters(s):
#집합으로 정렬
for char in sorted(set(s)):
suffix = s[s.index(char):]
# 전체 집합과 접미사 집합이 일치할 때 분리 진행
if set(s) == set(suffix):
return char + removeDuplicateLetters(suffix.replace(char,''))
return ''
removeDuplicateLetters('cbacdcbc')
>>> 'acdb'2 스택을 이용한 문자 제거
def removeDuplicateLetters(s):
counter, seen, stack = Counter(s), set(), []
for char in s:
counter[char] -= 1
if char in seen:
continue
# 뒤에 붙일 문자가 남아 있다면 스택에서 제거
while stack and char < stack[-1] and counter[stack[-1]]>0:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)- 사용하기
from collections import Counter
removeDuplicateLetters('cbacdcbc')22 일일 온도
매일의 화씨 온도 리스트를 입력 받아서 더 따뜻한 날씨를 위해서 며칠을 기다려야 하는지 출력하기
1 스택 값 비교
def dailyTemperatures(T):
answer = [0]*len(T)
stack = []
for i, cur in enumerate(T):
# 현재 온도가 스택 값보다 높다면 정답 처리
while stack and cur > T[stack[-1]]:
last = stack.pop()
answer[last]=i-last
stack.append(i)
return answer
dailyTemperatures([73,74,75,71,69,72,76,73])
>>> [1, 1, 4, 2, 1, 1, 0, 0]23 큐를 이용한 스택 구현
1 push() 할 때 큐를 이용해 재정렬
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self, x):
self.q.append(x)
# 요소 삽입 후 맨 앞에 두는 상태로 재정렬
for _ in range(len(self.q)-1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 024 스택을 이용한 큐 구현
1 스택 2개 사용
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self, x):
self.input.append(x)
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
# output이 없으면 모두 재입력
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]
def empty(self):
return self.input == [] and self.output == []25 원형 큐 디자인
1 배열을 이용한 풀이
원형 큐: INFO구조
class MyCircularQueue:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0
# enQueue(): 리어 포인트 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 +1) % self.maxlen
return True
else
return False
# deQueue(): 프론트 포인터 이동
def deQueue(self) -> bool:
if self.q[self.p1] is None:
return False #이미 내보낼것이 없는 상태 ->False
else:
self.q[self.p1] = None #삭제
self.p1 = (self.p1+1) % self.maxlen
return True
def Front(self) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self) -> int:
return -1 if self.q[self.p2 -1] is None else self.q[self.p2 -1]
def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None10 데크, 우선순위 큐
데크: 더블 엔디드 큐, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)
- 양쪽에서 삭제, 삽입 모두 가능
- 스택, 큐의 특징 모두 가짐
- 이중 연결 리스트로 구현시 좋은 성과 발휘
