CS 3주차 발자국 및 미션

학습 내용 정리

컴퓨터 구조

명령어

• PC를 통해 명령어를 인출하면 우리는 스탭 카운터를 통해 명령어 한개의 세부단계를 파악할 수 있다.

• 예를 들어 ADD는 CO, MI -> RO, II, CE -> IO, MI -> RO, BI-> EO,AI, FI 로 총 5단계로 이루어진 걸 파악할 수 있다.

어셈블리어

• 기계어를 사람이 다루기 쉬운 언어체계로 만든 것으로 어셈블리어 명령줄은 기본적으로 RAM의 용량과 동일하다.

• 예를 들어 16Byte RAM이라면 16줄로 명령어와 데이터 영역을 나누어 작성해야 한다.

자료구조_알고리즘

- Trie

• HashTable를 활용한 자료구조로 검색엔진의 자동완성 기능을 구현할 때 사용한다.

• 최대 힙을 활용하여 검색 수가 많은 검색어부터 사용자에게 보이도록 만들 수 있다.

• 검색시 첫 글자가 HashTable의 Key값을 의미하며 테이블에 존재할 경우 연결된 노드로 계속이동하고

  
  특정 문자열("*")의 키값을 얻게 되면 종료되고 Words 리스트에 추가하는 방식이다.

- Graph

• 그래프는 트리보다 폭넓은 자료구조를 의미한다.

• 트리는 그래프에서 사이클을 제거하고 연결되지 않은 정점이 존재하지 않으며 계층 구조를 이룬 것을 말한다.

• 그래프는 무방향,방향 그래프로 나뉘고 둘의 차이점은 양방향,단방향의 차이이다.
  A-B 라고 하면 A와 B는 연결되어 있다. / A->B 라고 하면 A는 B와 연결되어 있지만 B는 A와 연결되지 않음

• 탐색에는 두가지 방법이 있으면 상황에 따라 선택하면 된다.

• 첫번째로 DFS로 깊이 우선 탐색이다.

• 한 노드를 기점으로 끝까지 탐색한다. 사이클이 형성되어 있을 경우 무한 반복하기 때문에 탐색한 노드는 무시한다.

• 두번째는 BFS로 너비 우선 탐색이다.

• 큐를 활용하여 인접한 정점을 모두 탐색하고 끝나면 큐에 있는 다음 정점의 간접정점을 모두 탐색하는 방식이다.

다익스트라 알고리즘

• 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 직통으로 가는 거리와 경유해서 가는 거리 중 짧은 거리를
  테이블에 등록하여 구하는 알고리즘이다. 조금 더 개량된 버전은 A* 알고리즘이 있다.
  라우팅 테이블이나 , 네비게이션, 게임 AI의 길찾기 알고리즘 등 많은 분야에서 활용된다.

   

프림 알고리즘

• 다익스트라 알고리즘과 유사하지만 모든 간선의 길이가 최단거리가 되도록 만드는 알고리즘이다.

• 경유해서 가는 거리를 계산에 포함하지 않고 직접적으로 연결되는 거리만 계산한다.

학습하면서 깨달은 점 , 느낀 점

• 세상에 많은 알고리즘들과 자료구조들이 있지만 그것들을 이해하기 위해 기초적인 부분을 많이 공부해야 겠다고 느꼈다.

• 특히 자료구조와 알고리즘을 단단하게 알고있다면 다른 프로그램들을 개발할 때 큰 힘이 될것 같다.

미션 과정 및 느낀점

• 마지막 허프만 코딩 미션이 어려웠다. 생각해야하는 부분이 많고 개념을 충분히 숙지해도 구현하는게 어려웠다.

• 이번 강의들을 통해 배운 내용들을 조금더 탄탄하게 만들 필요가 있다고 느꼈다.

• 앞으로 좋은 개발자가 되기 위해 열심히 공부해야 겠다.

스스로 칭찬

• 모든 과정을 모두 수료했다는 것에 대해 칭찬하고 싶다.