자료구조 - 2

크루스칼 알고리즘

• 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

이 알고리즘의 개념은 간선을 거리가 짧은 순서대로 포함시킨다는 개념을 적용한다.

이 부분에서 중요한점은 사이클 형성으 하지 않아야 된다는 점이다.

일단 간선들을 거리(비용)을 기준으로 오름차순으로 정렬을 한뒤
가장 적은 비용으로 모든 노드를 연결한다.

List

• 데이터가 순서대로 저장이 되며 중복을 허용한다!!

Array와 List는 거의 유사하다(중복허용, 값을 순서대로 저장)

이 두개의 차이점은 Array는 index가 중요하다

• 특정 위치는 바로 찾아갈수가 있다.

List는 index보다는 value의 다음 데이터가 중요하다.

• 데이터끼리 서로 연관관계를 가지고 있기 떄문에
• 데이터가 다음 데이터의 정보를 담고있다.

예를드면 List[2]의 값은 List[1]에대한 정보를 가지고있고
List[3]는 List[2]에 대한 정보를 가지고 있다.

다른 예시로는 원본 데이터를 수정하려고 하면
배열은 값을 덮어쓰기 하지만
List는 데이터를 덮어쓰지 않고 새로운 데이터를 만들어낸다.

• 기존 데이터는 옆으로 밀어낸다.

  삭제도 동일하게 적용

JS에서는 splice라는 함수를 통해서 List를 구현가능하다.

• Js에서는 배열이 리스트 역할을 한다.

해시테이블

• key와 value로 데이터를 저장하는 구조로 빠르게 데이터를 검색할 수 있는 구조이다.

해싱이라는 암호화를 통해서 데이터를 저장하는 방법이다.

해시테이블에서는 충돌이라는 것이 발생할수도 있는데 너무 심오한 내용이기 떄문에
아직은 학습을 하지 않겠다.

단순하게는 데이터를 키 + value로 저장을 한다고 생각하면 된다.

재귀함수

재귀함수와 메모리 사용량의 관계

• 우리가 아는 재귀함수는 함수내에서 자기 자신을 계속해서 호출 하는것이다.

하지만 우리는 효율적이고 메모리를 최대한 적게 사용하는 프로그래밍을 추구해야하는데 이렇게 자기 자신을 계속해서 호출하게 되면 시스템의 성능에 좋지가 않다.

• 추가로는 오버플로우를 일으킬 수가 있다.

오버 플로우 : 변수에 담을수 있는 값의 이상의 값을 담게 되었을떄

하지만 그럼에도 재귀함수를 사용하는 이유는 2가지 정도가 있다.
1. 가독성이 뛰어나다.
2. 변수 사용량을 줄일수 있다.

• 1 == 우리는 기본적으로 혼자서 작업을 하는것이 아니기 떄문에 가독성을 많이 챙겨가야한다.
  나의 코드를 다른사람이 보아도 이해할수가 있어야 하기 떄문에 가독성을 위해서 사용 한다.

• 2 == 변수에 잡히는 데이터의 양을 줄인다는 의미가 아니라 쓸데없는 변수선언을 줄임으로써 메모리를 줄이겠다는 의미와 상수로 만들어서 오류를 줄이겠다는 의미이다.

꼬리 재귀

• 위에서 말한 단점을 줄이기 위한 재귀를 말한다.
• 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태이다.

일반적인 재귀 함수는 return으로 자기 자신을 return 하게 된다.
그렇게 되면 함수가 계속 호출이 되면서 스텍창에 스텍이 계속 쌓이게 될것이다.

• 데이터가 쌓인다는 의미

하지만 중간 과정에 변수에 재귀하는 코드를 넣어준뒤 해당 변수를 return해주면 함수에서 추가 연산이 일어나지 않는다.

• 이러한 방법으로 스텍이 계속 쌓이는 재귀의 단점을 처리할수가 있다.
• 위에서 말한 방법을 코드로 구현한 것이다 [출력값은 동일하다]

함수를 호출하게 되면 스텍이 계속 쌓이게 되어서 시스템의 성능이 나빠지지만
곱하기2처럼 변수에 할당하고 변수를 return 해주면 시스템의 성능이 좋아진다.

하노이의 탑 재귀

• 우리가 알고 있는 하노이의 탑에 대한 내용이다.

음... 이부분에 대한 내용은 어떤걸 정리해야 할지를 모르겠다;;

조합 재귀 함수

• 팩토리얼 에 대한 내용이다.

nCr에 대한 내용으로 순서에 상관없이 특정 범위의 수에서 특정 갯수를 뽑아오는 경우의수?를 말한다.

이것을 재귀 함수를 통해서 구현을 할수 있다고 알고 있으면 될꺼 같다.