알고리즘 week_02

timtam·2021년 10월 17일
0

Algorithm

목록 보기
2/5

어레이

✅ 배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없다!
✅ 배열은 각 원소에 즉시 접근할 수 있다 numbers[0] 처럼!

  • 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다.
  • 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미한다.
    즉, O(1) 내에 접근할 수 있다고 말한다.

✅ 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.
최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가진다.
✅ 배열은 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조이다.

  • But python의 경우 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계했다!
  • python의 배열은 링크드 리스트로 쓸 수도 있고,배열로도 쓸 수 있게 만든 효율적인 자료구조다!

링크드리스트

✅ 링크드리스트는 크기가 정해지지 않은 데이터의 공간. 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있다!
✅ 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색.

  • 최악의 경우에는 모든 원소를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
  • 연결 고리를 포인터라 부르고, 각 원소를 노드라고 부름.

✅ 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됨.

  • 따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.
ArrayLinkedList
특정 원소 조회O(1)O(N)
중간에 삽입 삭제O(N)O(1)
데이터 추가데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리데이터에 접근하는 경우가 빈번하다면 Array를 사용하자삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

이진탐색

숫자의 범위는 1~100 중에 문제 출제자가 정한 숫자를 맞추는 알고리즘.
답안을 말하면 숫자를 맞추기 위해 UP을 해야하는지 Down을 해야하는지 알려준다.

알고리즘 관점으로 가장 효율적인 방법은
바로 범위의 절반인 50을 시도해보는 것!

대답이 UP 이라면 1~49 은 후보에서 없어지고
대답이 DOWN 이라면 51~100을 후보에서 없어지기 때문이다.

이 방법이 이진 탐색.

재귀함수

재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.
재귀 함수는 바로 자기 자신을 호출하는 함수.

몰랐던 개념

  • 숫자 내림 하는 방법 // 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있다.
   >>> print((4 + 5) / 2)
   4.5
   >>> print((4 + 5) // 2)
   4
  • 문자열 슬라이싱
>>>"가나다라마바사"[0:3]
'가나다'
>>>"가나다라마바사"[0:-2]
'가나다라마'
  • 정렬
    정렬하고 싶은 배열 뒤에 .sort() 함수만 호출하면 된다!
>>> array = [4, 1, 6, 2]
>>> array.sort()
>>> array
[1, 2, 4, 6]

# 참고로 한글도 정렬 가능!
>>> korean_array = ["라", "가", "다", "나"]
>>> korean_array.sort()
>>> korean_array
['가', '나', '다', '라']
  • set 자료형
>>>a = set([1,2,3,4,5])
>>>a
{1, 2, 3, 4, 5}
>>>b = {1,2,3}
>>>b
{1, 2, 3}

0개의 댓글