2주차 WIL

2주차 항해에서는 알고리즘, 자료구조를 학습했다.
학습한 언어는 파이썬이다.
우선, 선형 자료구조의 학습에서는
배열, 연결리스트, 스택, 큐를 학습했는데

스택과 큐

스택과 큐의 자료구조를 구현해봤다.
선입후출/ 선입선출의 자료구조다 정도만 알고 있었는데,
직접 구현해보니 좀더 자료구조의 특징이 이해가 됬다.
스택은 배열을, 큐는 deque를 이용해 구현해 봤다.
둘의 공통점은 각각 pop(),popleft()때 시간복잡도 O(1)을 가진다는 것이다.

• 큐와 스택을 사용하면 효율적인 작업은 아래와 같다.
  -스택
• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.

-큐

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

dfs / bfs

-그래프를 탐색하는 방법이다.

bfs

깊이 우선 탐색. 최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동한다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
   -스택을 이용해 구현

dfs

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
-큐를 이용해 구현