오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!
문제를 풀 때 문제마다 최적의 해법은 서로 다릅니다. 그리고 같은 문제를 풀어도 어떠한 자료구조와 알고리즘을 사용하느냐에 따라 활용되는 저장공간과 수행되는 시간이 달라집니다.
그러므로 문제의 특성을 이해하여 자원을 효율적으로 활용(저장, 삭제, 검색 등)하면서 효과적인 방법으로 문제를 풀어내야 합니다.
배열은 원소들을 순서대로 늘어놓은 것을 말합니다. 파이썬에서는 List로 구현할 수 있습니다.
>>> L = ['Bob', 'Cat', 'Spam', 'Programmers']
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
.append()
: 현재 List의 끝(마지막)에 원소 x를 덧붙이는 연산입니다..pop()
: 현재 List의 끝(마지막) 원소를 반환하고 삭제합니다.>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L.append('illstandtall')
>>> L
['Bob', 'Cat', 'Spam', 'Programmers', 'illstandtall']
>>> L.pop()
'illstandtall'
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
.insert(n, x)
: 현재 List의 n번째에 x 원소를 추가하는 연산입니다.del(L[n])
: 리스트 L의 n번째 원소를 삭제합니다..pop(n)
: 현재 List의 n번째 원소를 반환하고 삭제합니다.위의 연산들은 원소를 추가/삭제하는 시간 외에 리스트의 크기를 조정하는 시간이 추가됩니다. 그러므로 리스트가 길면 길수록 시간이 오래 걸립니다.
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L.insert(2, 'data')
>>> L
['Bob', 'Cat', 'data', 'Spam', 'Programmers']
>>> del(L[3])
>>> L
['Bob', 'Cat', 'data', 'Programmers']
>>> L.pop(0)
'Bob'
>>> L
['Cat', 'data', 'Programmers']
sorted(L)
: 리스트 L을 오름차순으로 정렬하여 반환합니다. (문자열은 알파벳순).sort()
: 현재 List를 오름차순으로 정렬합니다. (문자열은 알파벳순)reverse=
: 내림차순으로 정렬하고 싶을 때 사용합니다.key=
: 다른 기준으로 정렬할 때 사용합니다.>>> L1 = [3, 2, 4, 5, 1]
>>> L1
[3, 2, 4, 5, 1]
>>> sorted(L1)
[1, 2, 3, 4, 5]
>>> L2 = [3, 2, 4, 5, 1]
>>> L2.sort()
>>> L2
[1, 2, 3, 4, 5]
>>> L2.sort(reverse=True)
>>> L2
[5, 4, 3, 2, 1]
>>> L3 = ['Bob', 'Cat', 'Spam', 'Programmers']
>>> L3
['Bob', 'Cat', 'Spam', 'Programmers']
>>> L3.sort(key=lambda x: len(x)) # 문자열의 길이를 기준으로 정렬하기
>>> L3
['Bob', 'Cat', 'Spam', 'Programmers']
# binary search algorithm
while left <= right:
mid = (left + right) // 2
if L[mid] == x:
answer = mid
break
elif x < L[mid]:
right = mid - 1
else:
left = mid + 1
- 1부터 50까지의 합을 구할 때, 1부터 49까지의 합에 50을 더해 문제를 풀 수 있습니다.
- 1부터 49까지의 합을 구할 때, 1부터 48까지의 합에 49를 더해 문제를 풀 수 있습니다.
- 1부터 48까지의 합을 구할 때, 1에 부터 47까지의 합에 48을 더해 문제를 풀 수 있습니다.
- 1부터 47까지의 합을 구할 때, 1에 부터 46까지의 합에 47을 더해 문제를 풀 수 있습니다.
중략...
# recursion
def sum(n):
return sum(n-1) + n
# recursion
def sum(n):
if n == 1: # Base case / trivial case
return 1
else:
return sum(n-1) + n
# recursive -> iterative
def sum(n):
res = 0
for i in range(n):
res += i
return res
# recursive
def binary_search(L, x, left, right):
if right > left:
return -1
else:
mid = (left + right) // 2
if x == L[mid]:
return mid
elif x < L[mid]:
return binary_search(L, x, left, mid-1)
else:
return binary_search(L, x, mid+1, right)
이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.