[프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 1,2,3강

1강 : 어서와! 자료구조와 알고리즘을 왜 배워야 하는지 알려줄게

• 파이썬 기본 자료구조 : str, list, dict, tuple, set, ...
• 자료구조를 왜 알아야할까?
  • 파이썬의 기본 자료구조보다 주어진 문제를 빠르게 행할 수 있는 다른 자료구조가 있기 때문 ⇒ 효율성
• 알고리즘이란?
  • 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
  • 선택시 최적의 해법이 (응용 종류와 범위에 따라) 다르기 때문에 자료구조 이해가 필요

 

2강 : 선형 배열

• 선형 배열(Linear Arrays)
  • List 활용
  • 보통 array는 같은 type의 데이터만 원소로 존재 가능 (But List는 다른 type의 원소도 가능)
  • 리스트(배열) 연산

  #List의 길이와 무관한 연관/상수시간=> O(1) ...big O
  List.append()
  List.pop() #끝에서 하나의 원소를 꺼냄(list도 변함)
  
  #List의 길이에 비례하는 연산/선형 시간=> O(n)
  List.insert(3,65) #List.insert(삽입할 위치, 삽입할 원소)
  del(List[2]) #2번 index의 원소를 삭제
  List.pop(2) #return 값이 List[2], 위 del 함수는 return 값이 List
  
  #원소 탐색=> 연산 시간 O(n)
  List.index('Cat')

• 정렬된 리스트에 원소 삽입

  def solution(L, x):
      idx = 0
      for i in range(len(L)):
          if(x>L[i]):
              idx+=1
      L.insert(idx,x)
      return L
  
  ###다른 풀이###
  def solution(L, x):
      L.append(x)
      L.sort()
      return L​

• 리스트에서 원소 찾아내기

  def solution(L, x):
      if x in L:
          answer = [ i if L[i]==x for i in range(len(L)) ]
      else:
          answer = [-1]
      return answer
  
  ###다른 풀이1###
  def solution(L, x):
      if x in L:
          return [i for i, y in enumerate(L) if y == x]
      else:
          return [-1]
  
  ###다른 풀이2###
  def solution(L, x):
      n = []
      index = 0   
      for i in range(len(L)):
          try:
              number = index
              index = L.index(x)
              n.append(index+number+i)
              L = L[index+1:]
          except:
              break
      if len(n)==0:
          answer = [-1]
      else: 
          answer = n
  
      return answer​

  • list.index(x[, start[, end]])
  • enumerate
    • 순서가 있는 자료형(list, set, tuple, dictionary, string)을 입력으로 받아 index 값을 포함하는 enumerate 객체를 리턴
    • 결과 ⇒ index : 값
    • 보통 for문과 함께 자주 사용

 

3강 : 배열 더 알아보기: 정렬과 탐색

• 배열의 정렬
  • sorted()
    • 내장 func. , 정렬된 새로운 list return
  • sort()
    • list의 method, 해당 list를 정렬

  sorted(L, reverse=True)
  L.sort(reverse=True)
  
  sorted(L, key=lambda x: len(x))
  sorted(L, key=lambda x: x['score'],reverse=True)
  

• 탐색 알고리즘
  • 선형 탐색(Linear Search)
    • 연산 시간 : O(n)
  • 이진 탐색(Binary Search)
    • 크기 순으로 나열된 list에서만 적용 가능
    • 한 번 비교가 일어날 때마다 list 반씩 줄임 (divide&conquer) ⇒ O(log n)

    lower = 0
    upper = len(L) -1
    idx = -1
    
    while lower<= upper:
    	middle = (lower + upper)//2
    	if L[middle]==target:
    	...
    	elif L[middle]<target:
    		lower = ...
    	else:
    		upper = ...
    

 

 

Reference

어서와! 자료구조와 알고리즘은 처음이지?