[Programmers-python algorithm] - 1,2강

Data Structure and Algorithm

Algorithm 이란?

• 사전적 정의 : 어떤 문제를 해경하기 위한 절차, 방법, 명령어들의 집합
• programming : 주어진 문제를 해결하기 위한 자료구조와 연산 방법에 대한 선택.
• 자료구조를 배워야 하는 이유 : 문제를 파악하고 내가 사용한 자료구조가 어떤 성질이여야 하는지 알아야 하기 때문

Linear Array

1) Array와 List

• Arrya : 원소들을 순서대로 늘어놓는 것.
• List : data type이 다른 원소들 사용 가능.

2) Python List에 활용할 수 있는 연산들

• 실행시간이 list 길이에 독립적인 연산들 O(1)
  • .append() : 맨 끝에 원소를 덧붙인다.
  • .pop() : 맨 끝의 원소 하나를 꺼내고 꺼낸 것을 출력한다. (When index is out of range, it returns index Error)
  • List의 길이와 실행시간이 비례한 연산들 O(n)
    • insert(indes,element): 원소 삽입하기
      • 삽입 할 위치인 index에 기존의 element들을 한 칸씩 땡기고 그 곳게 삽입하므로, 실행 시간기 list 길이와 비례한다.
    • del(elememt)
      • 원소 삭제 후 elements를 한 칸씩 당기고 마지막 element를 삭제한다.
    • 추가 다른 연산
      • index(element) -> index 출력
      • Time complexity : O(n) --> 각 리스트의 원소들을 비교해야하기 때문.
        • list.remove(index) , del list, list.pop()의 차이점
          (1) list.remove : 첫 번째로 matching 되는 원소를 제거한다.

      myList=[1,2,3,2]
      myList.remove(2)
      myList
      #index가 2인 3이 삭제된다 결과 : [1,2,2]
      

      
                    (2) del myList[index]
      

      myList=[1,2,3,2]
      del myList[2]
      myList
      #[1,2,2]​

      
                   (3)list.pop(index)
      

      myList=[4,3,5]
      myList.pop(1)
      #2
      myList
      [4,5]​

  3) Practice 문제
  • Practice 1
    List 에서 특정 워가 있는 모든 index를 구하려 list로 반환하라.
    • index() 메서드를 사용하여 해당 value가 있는 index를 구하고, slice를 이용하여 처음 구한 index 제외한 list로 초기화한다.
    • append() 메서드를 사용하여 출력 할 list의 끝에 추가한다.
      구현한 코드는 아래의 링크에서 확인이 가능하다.
      findindex.py
  • Practice 2
    크기에 따라 정령되어있는 list에 원소를 삽입하라.
    • 반복문을 사용하여 insert 메서드로 삽입한다.
    • 조건문에서 value가 list 내의 원소들보다 클 경우 마지막에 삽입하는 조건을 먼저 넣어준다.
      addNewelemTolist.py