알고리즘 17일차

문제 1

1. 문제

• 앞글자가 같은지 찾기 : prefix 찾기 문제

2. 접근법

• nested for loop : 실패

3. 서칭 결과

• sort()로 정렬 후 (리스트 안 요소들을 a~z 순으로 알아서 소팅 해줌) 문자 길이로 찾기

4. 코드

def get_prefix(strs):
  if len(strs) == 0:
    return ''
  # 먼저 해당 없는 길이 0인 배열 제외

  strs.sort()
  # 정렬
  shortest = strs[0]
  # 기준점 잡기
  prefix = ''
  # return 할 완성작 잡기

  for i in range(len(shortest)):
  # Range index
    if strs[len(strs)-1][i] == shortest[i]:
      prefix += strs[len(strs)-1][i]
  # 만일 값이 같다면 프레픽스에 하나씩 글자 추가
    else:
      break
  # 없으면 브레이크 걸기

  return prefix


print(get_prefix(['start', 'stair', 'step']))

어렵다. [][] 이 부분은 익숙치 않았다. 나중에 다시 풀어보기

문제 2

1. 문제

• 연속된 값 중 더했을 때 가장 큰 값을 리턴

2. 접근한 방법

• for loop 이용하여 전, 후값 더해서 0보다 큰지 작은지로 비교하려했으나 실패

3. 서칭 결과

• 단순히 for loop을 돈 뒤 양수인 것만 서로 다음 것을 더해주면 되었고 그 다음에 max 값을 찾아주면 되는 것이었다....

너무 어렵게 생각 말기.

4. 코드

def maxSubArray(nums):
    for i in range(1, len(nums)):
    # 1부터 len(num)까지
        if nums[i-1] > 0:
    # 만일 0보다 큰 요소가 있다면
            nums[i] += nums[i-1] 
    # 다음 요소와 더해준다.
    return max(nums)
    # 그 중 가장 큰 값
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

각종 정렬 참고 링크

참고 블로그

문제 3

1. 문제

선택정렬

2. 정답

def selectionSort(nums):
    for i in range(len(nums)-1):
      min_index = i
      for j in range(i+1, len(nums)):
        if nums[j] < nums[min_index]:
          min_index = j
      nums[i], nums[min_index] = nums[min_index], nums[i]
    return nums

print(selectionSort([2,4,7,5]))

피보나치처럼 약간 공식같다. 잘 알아두자.

문제 4

1. 문제

버블정렬 ; 선택정렬과 반대, nested for loop가 필요

2. 힌트

3. 정답

def bubbleSort(arr):
  for i in range(len(arr)-1, 0, -1):
    for j in range(i):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

print(bubbleSort([2, 1, 4, 6, 8, 3]))

문제 5

1. 문제

재귀함수(reverse 안 쓰고 재귀함수로 뒤집기)

2. 접근

• 재귀함수 이용하여 인덱스 번호 역순으로 만들고 join 하기

3. 정답

def reverseString(str):
  result = []
  for i in range(len(str)):
    result.append(str[len(str) - (i+1)])

  result = ''.join(result)

  return result
print(reverseString('hello'))

참고 링크