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

자료구조와 알고리즘 정리

 

자료구조

 • 배열 (Array)

   - 같은 유형의 데이터를 여러개 넣어 관리하는 데이터구조

 

 • 큐 (Queue)

  - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (FIFO)

 

 • 스택 (Stack)

  - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO)

 

 • 링크드 리스트 (Linked List)

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

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

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

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

 

 • 해쉬 테이블 (Hash Table)

   - Key에 데이터(Value)를 매핑할 수 있는 데이터 구조

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

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

    º Chaning 기법

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

   º Linear Probing 기법

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

   

 • 트리 (Tree)

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

  º 이진 트리 (Binary Tree)

   - 노드의 최대 Branch가 2 인 트리 

  º 이진 탐색 트리 (Binary Search Tree)

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

  º 신장 트리 (Spanning Tree)

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

 

 • 힙 (Heap)

  - 데이터에서 최대값 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

  º 완전 이진 트리 (Complete binary Tree)

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

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

 

알고리즘

 • 정렬

  º 버블 정렬 

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

  º 선택 정렬

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

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

  º 삽입 정렬

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

  º 병합 정렬

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

  º 퀵 정렬

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

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

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

 

 • 재귀 호출

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

 

 • 동적 계획법

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

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

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

 

 • 분할 정복

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

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

 

 • 탐욕 알고리즘

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

 

 • 백트래킹

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

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

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

 

 • 탐색

  º 순차 탐색

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

  º 이진 탐색

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

 

 • 그래프

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

  º 너비 우선 탐색

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

  º 깊이 우선 탐색

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

 

 • 최단 경로 알고리즘 

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

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

  º 다익스트라 알고리즘

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

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

 

 • 최소 신장 트리 알고리즘 

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

  º 크루스칼 알고리즘

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

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

  º 프림 알고리즘

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

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

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

 

학습 방법

 - 기본 자료구조, 알고리즘 반복 학습 후 각 알고리즘을 사용하는 유사한 코딩테스트 문제를 한꺼번에 묶어서 풀이 하라

 

해당 강의에서는 위와 적은 내용과 달리 전부 어떤 개념인지 다시 설명해주지는 않지만 본격적인 알고리즘 강의를 

듣기 위해 앞선 내용을 한번 훑는 시간을 가졌다. 

 

 

 

18일차 인증

 

 

 

 

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

https://bit.ly/37BpXiC

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