CPython: python interpreter
오늘 이진 탐색으로 최대 길이나 거리를 찾는 방법을 구현해봤는데 그 방식이 투 포인터랑 비슷하다는 걸 복습조에서 투 포인터를 다시 공부하면서 알게됬다.
이진 탐색 또는 이진 검색이란?
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
이진 탐색으로 푼 부품 탐색
n = 5
n_list = [8, 3, 7, 9, 2]
m = 3
m_list = [5,7,9]
n_list.sort()
# [2, 3, 7, 8, 9]
def search(n_list, target):
low, high = 0, len(n_list)-1
mid = (high + low) // 2
if len(n_list) > 0:
if target == n_list[mid]:
print('yes', end=' ')
elif target > n_list[mid]:
return search(n_list[mid + 1 : high+1], target)
elif target < n_list[mid]:
return search(n_list[low : mid], target)
if target not in n_list:
print("no", end=' ')
for target in m_list:
search(n_list, target)투 포인터란?
왼쪽 포인터와 오른쪽 포인터의 합이 타켓보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식이다.
두 수의 합 문제로 본 투 포인터 사용법
left right
sum = left + right
sum > target: sum을 줄여야 한다. 그래서 right포인터를 왼쪽으로!
sum < target: sum을 키워야 한다. 그래서 left포인터를 오른쪽으로!
def two_sum(nums, target):
left, right = 0, len(nums)-1
while left<=right:
sum = nums[left]+nums[right]
if sum > target:
right -=1
elif sum < target:
left +=1
else:
print(left,right)투 포인터로 푼 부품 탐색
def check_item(nums, m_list):
for target in m_list:
l, r = 0, len(nums) - 1
while l <= r:
if target !=nums[l]:
l += 1
if target != nums[r]:
r -= 1
else:
print(target)
print('yes',end=' ')
break
if target not in nums:
print(target)
print('no', end=' ')
n = [8, 3, 7, 9, 2]
m_list = [5, 7, 9]
check_item(n, m_list)간단 근황
요 근래 들어서 TIL를 잘 작성 안 하고 있는데 블로그 작성하는 것도 좋지만 복습하는 시간도 많이 필요하다고 생각해서 시간 배분을 TIL에 덜 쓰고 있다.
저번 주 중간서부터 시도한 페어 프로그래밍이 나에게 잘 맞아떨어지는 것 같다. 알고리즘 1주차랑 2주차 초반 때는 아무리 홀로 개념공부를 하고 강의를 봐도 이해 안 가는 부분들이 많았다. 이해가 안 가니 일단 주어진 코드로 구현을 해보려고 해도 계속 오류가 나서 포기하고 간단한 유튜브 강의나 보고 있던 차였다. 현재 학습법이 나에게 안 맞는다는 걸 알게되고 페어 프로그래밍이란 학습 방법을 항해 매니저님께 건의하여 시도하게 되었다.
짝/페어 프로그래밍
나에게 있어선 알고리즘 주차가 페어 프로그래밍 이전과 이후로 나뉜다. 페어 프로그래밍의 좋은 점은 시작부터 짝과 같이 개념 공부, 문제 해석, 알고리즘 코드 짜기를 시도해 다른 사람들은 어떤 식으로 알고리즘을 이해하고 문제에 접근하는지 알 수 있다는 점이다. 그래서 알고리즘 완전 초보에 이해 안 가서 계속 헤매는 분들은 페어 프로그래밍 학습을 추천한다.
나는 페어 프로그래밍을 할 때 일단 짝과 같이 개념 공부를 먼저하고 자료구조 구현을 시도해보며 전체적인 자료구조 알고리즘을 익히는 공부 순서를 따르고 있다. 나는 학습형이라 이 방식이 나에게 잘 맞는다.
살짝 잡담일 수 있는데,몇 일전에 다른 분들과 대화하다가 프로그래머들은 두 가지 타입으로 (학습형과 야수형으로) 나뉜다는 걸 알게됬다.
학습형은 개념 하나를 100%이해하지 않으면 안 넘어가는 성격이라 공부 진도가 느리다. 그 대신 한 번 제대로 학습한 개념은 잘 알아서 쓸 수 있다.
1 0 0 0
0 0 1 0 <- 1(100%)씩 마스터한 개념들이 3개 있다.
1 0 0 0
--각 개념들을 마스터는 했지만 수가 적다--
야수형은 일단 개념을 30%-50% 이해하고 넘어가서 이것 시도해보고 저것 시도해보면서 진도가 빠르게 나간다. 그 대신 한 개념을 100% 학습하는게 학습형보다 느리다.
0.3 0.1 0.7
0.2 0.2 0.5 <- 개념들을 골고루 파서 대부분 연결시킬 수 있다.
0.4 0.4 0.2
말했듯이 난 학습형이라 이론이 탄탄하고 기본이 이해가 안 가면 전체적인 문제 해석이라던지 자료구조 구현이 어려울 때가 많다. 그래서 기본적인 내용들과 자료구조 구현에 시간을 많이 투자한다. 요즘 내 짝을 맡고 계신 분은 야수형이라 기본이 이해 안 가 꼬치꼬치 캐묻는 나 때문에 진이 빠지셨을 수도 있는데, 그래도 질문하고 나니까 실력이 훨씬 늘은 것 같다. 또, 페어 프로그래밍할 때 얼굴에 철판 깔고 모르는 건 모른다고 계속 이해될 때까지 물어보니 막힌 게 풀리고 진도가 나가서 너무 기쁘다. 원래 배울 때는 이기적으로 배우라고 했다
전에는 기본문제도 못 풀고 개념도 이해가 안 된게 느껴졌었는데, 페어 프로그래밍 하면서 기본문제와 심화문제 다 풀 수 있어서 좋았다. 또 같이 하면서 대화를 나누고 현재 코드가 어떻게 쓰이고 있는지를 일일히 이해하며 넘어가다보니 집중력도 많이 높아진 것 같다. 아무리 학자형이라도 미로 속에 갇힌 것 같이 진도가 안 나가면 집중이 안 된다. 그러니 야수형과 같이 짝을 하면서 진도를 그나마 빠르게 나갈 수 있는게 기쁘다.
내일까지 발표자료를 제출해야되서 빨리 DNS 공부를 마저 해야겠다.
