패스트캠퍼스 챌린지 50일차

끝나지 않을것 같던 패스트 캠퍼스 챌린지가 이제 끝이 났다..

 

시작했을떄 완주 할 수 있을까라는 생각을 했지만 50일은 생각보다 짧았으며 습관을 기르기에 적합한 기간이라고 생각한다

 

집에 늦게들어갔을때 챌린지를 하지 못하는 그 불안감... ㅋㅋㅋ 그래도 어떻게 잘 해왔다

 

강의를 다 완주하여서 마지막으로 자료구조와 알고리즘 정리를 통해 기본 개념들을 한번 더 복습하는 시간을 가진다

 

 

자료구조

 1. 배열 (Array) : 같은 유형의 데이터를 여러개 넣어 관리하는 데이터구조

 

 2. 큐 (Queue) : 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (FIFO)

 

 3. 스택 (Stack) : 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO)

 

 4. 링크드 리스트 (Linked List)

  - 데이터와 다음 데이터의 주소를 저장하는 공간을 같이 저장하여 중간 데이터 삽입,삭제 시 데이터를 찾아갈 수 있다.

  - 데이터 저장 단위인 Node와 이전노드와 연결 정보를 가진 포인터로 구성

   4-1) 더블 링크드 리스트 (Double Linked List, 이중 연결 리스트)

    - 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

 

 5. 해쉬 테이블 (Hash Table) : Key에 데이터(Value)를 매핑할 수 있는 데이터 구조

   - 해쉬 함수를 통해 배열에 키에 대한 데이터를 저장한 후, Key를 통해 바로 데이터가 저장되어 있는 주소 조회

   - Key값이 중첩되어 Key값 충돌이 일어날 경우 Chaning, Linear Probing 기법을 통하여 해결

    5-1) Chaning 기법

     - 충돌이 일어날 경우, 링크드 리스트 자료구조를 사용하여, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜 저장

     5-2) Linear Probing 기법

     - 충돌이 일어날 경우, Hash Address의 다음 Address부터 맨 처음 나오는 빈공간에 저장

   

 6.트리 (Tree)

  - Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

  6-1) 이진 트리 (Binary Tree) : 노드의 최대 Branch가 2 인 트리 

  6-2) 이진 탐색 트리 (Binary Search Tree)

    : 왼쪽 노드는 현재 노드보다 작은 값, 오른쪽 노드는 현재 노드보다 큰 값을 만족하는 트리

  6-3) 신장 트리 (Spanning Tree)

    : 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프, 사이클이 존재하지 않는다.

 

 7. 힙 (Heap) : 데이터에서 최대값 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

  7-1) 완전 이진 트리 (Complete binary Tree)

   - 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

   - 최대값 또는 최소값을 빠르게 찾기 위해서 사용되는 자료구조

 

---

알고리즘

 1. 정렬

  1-1) 버블 정렬 

   - 인접한 두 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

  1-2) 선택 정렬

   - 주어진 데이터 중, 최소값을 찾아서 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다

   - 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

  1-3) 삽입 정렬

   - 두번째 인덱스부터 시작하며, 해당 인덱스 앞에 있는 데이터 부터 비교하여 더 작으면 해당 인덱스 앞으로 이동

  1-4) 병합 정렬

   - 문제를 작은 2개의 문제로 분리하고 각각을 해결한다음, 결과를 모아 문제를 해결하는 방법, 분할 정복 방법

  1-5) 퀵 정렬

   - 기준점(pivot)을 정한 후, 기준점 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성,

     각 왼쪽, 오른쪽은 재귀용법을 사용하여 다시 동일 함수를 호출하여 반복한다

   - 함수는 왼쪽 + 기준점 + 오른쪽을 리턴

 

 2. 재귀 호출

  - 함수 안에도 동일한 함수를 호출하는 형태

 

 3. 동적 계획법

   - 입력 크기가 작은 부분 문제들을 해결한 뒤, 해당 부분의 해(풀이)를 활용해서 보다 큰 부분 문제를 해결 후 ,

    최종적으로 전체 문제를 해결하는 알고리즘

  - Memooziation 기법 사용 : 프로그램 실행 시 이전에 사용했던 값을 기억하여 재 사용

 

 4. 분할 정복

  - 문제를 나눌 수 없을 떄 까지 나눈후, 각각 풀면서 합병하여 문제의 답을 찾는 알고리즘

  - 상위의 해답을 얻기 위해, 아래로 내려가며 하위의 해답을 구하는 방식

 

 5. 탐욕 알고리즘

  - 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘, 매순간 최적이라고 생각되는 경우를 선택

 

 6. 백트래킹

  - 제약 조건 만족 문제에서 해를 찾기 위한 전략

  - 해를 찾기 위해, 후보군에서 제약 조건을 점진적으로 체크 하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단

    되는 즉시 이 후보군은 체크를 하지 않는다는 표기를 하고, 다른 후보군으로 넘어가 최적의 해를 찾는 방법

 

 7. 탐색

  7-1) 순차 탐색

   - 데이터가 담겨 있는 리스트를 앞에서 부터 순차적으로 하나씩 비교하여 원하는 데이터를 찾는 알고리즘

  7-2) 이진 탐색

   - 탐색할 자료들을 둘로 나누어(이진) 해당 데이터가 있을만한 곳을 탐색하는 방법

 

 8. 그래프

  - 실제 세계의 현상이나 사물을 노드(정점,Vertex)와 간선(Edge)로 표현하기 위해 사용

  8-1) 너비 우선 탐색

   - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드를 먼저 순회, 형제노드 우선 순회

  8-2) 깊이 우선 탐색

   - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 형제들의 자식을 타고 내려가며 순회

 

 9. 최단 경로 알고리즘 

  - 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘

  - 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는것이 목적

  9-1) 다익스트라 알고리즘

   - 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제

   - 우선순위 큐를 사용하는 방식으로 설명, MinHeap방식을 활용하여 가장 짧은 거리를 가진 노드 정보 추출

 

 10. 최소 신장 트리 알고리즘 

  - 신장 트리 중, 간선의 가중치의 합이 최소인 신장트리

   10-1) 크루스칼 알고리즘

     - 간선이 가장 작은 순서대로 정렬한 후, 가장 작은 순서대로 선택하나 사이클이 발생하면 탈락

     - 시작 노드를 선택하지 않으며 가장 작은것을 먼저 선택한 후 작은 순서대로 계속 선택해 나아간다.

   10-2) 프림 알고리즘

     - 시작 노드를 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 노드를 선택하고,

        해당 노드에서 다시 최소 간선으로 연결된 정점을 선택하는 방식

     - 최소 신장트리를 확장해나가는 방식

 

학습 방법

 - 자료구조 유형과 알고리즘 문제를 이해하고 풀어야 한다. 코드를 작성하는 것 보다 문제를 먼저 이해하고

   사용할 변수 선언 및 유형 파악을 우선시 해야하며 여러가지 문제를 반복적으로 학습하는것이 유용하다

 

 

 

 

50일차 인증

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]