WEEK02 개발일지

학습 내용

스택(Stack)

• 정의

  • LIFO(Last-In-First-Out) 방식으로 데이터를 저장하는 자료구조
  • 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조
  • 주로 재귀 알고리즘, 괄호 문제, 백트래킹 등에 사용

• 파이썬에서의 활용

  • list를 활용하여 스택을 구현
  • append()로 데이터 추가, pop()으로 데이터 삭제

• 느낀 점

  • 스택(FILO(First-In-Last-Out) -> 프링글스통)은 비교적 익숙해서 자료구조에 대해서는 쉽게 넘어갈 수 있었던 것 같습니다.(문제가 어려운 것을 별개..)

큐(Queue)

• 정의

  • 스택과는 반대로 FIFO(First-In-First-Out) 방식으로 데이터를 저장한다.
  • 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조

• 파이썬에서의 활용

  • list를 활용하여 큐를 구현
  • append()로 데이터 추가, pop(0)으로 데이터 삭제
  • collections 모듈의 deque를 사용하면 보다 효율적인 큐 구현 가능

• 느낀 점

  • 큐 역시 이전에 접해본 개념이라 이해하는 데 어려움이 없었습니다.
  • 파이썬에서는 list로 큐를 구현할 수 있지만, deque를 사용하면 더 효율적으로 구현할 수 있다는 점이 인상 깊었습니다.

우선순위 큐(Priority Queue)

• 정의

  • 우선순위가 높은 데이터가 먼저 나가는 자료구조
  • 다익스트라 알고리즘, 프림 알고리즘 등의 그래프 알고리즘에서 사용

• 파이썬에서의 활용

  • 파이썬에서는 heapq 써서 우선순위큐를 구현할 수 있다.
  • heappush()로 데이터 추가, heappop()으로 데이터 삭제
  • 기본적으로는 최소힙으로 구성이 되기 때문에 최대힙이 필요하다면 heappush()와 heappop()시에 각각 - 를 넣어줌으로서 간단히 구현할 수 있다.

• 느낀 점

  • 우선순위 큐는 heappop() 할 때마다 최소,최대힙에 따라 극값이 나오기 때문에 이를 어떻게 활용할지 문제의 의도를 잘 파악해야 할 것 같다고 생각했습니다.

그래프(Graph)

• 정의

  • 정점(Vertex)과 간선(Edge)로 이루어진 자료구조
  • 무방향 그래프와 방향 그래프로 나뉨

• 그래프 표현 방법

  • 인접 행렬: 2차원 배열로 그래프를 표현
  • 인접 리스트: 리스트를 사용하여 그래프를 표현

• 파이썬에서의 활용

  • 딕셔너리와 리스트를 활용하여 그래프 표현
  • 딕셔너리의 키를 정점으로, 값을 연결된 정점의 리스트로 표현

• 느낀 점

  • 그래프는 비선형 자료구조라서 이전에 배운 자료구조랑 다르게 코드에서 이해하기가 어려웠다.
  • 스패닝트리 관련해서 좀 더 공부해야할 것 같았다.(크루스칼, 프림 알고리즘 .. )

BFS(Breadth-First Search) - 너비 우선 탐색

• 정의

  • 그래프를 탐색하는 알고리즘 중 하나
  • 시작 정점에서 가까운 정점부터 차례대로 방문
  • 큐를 사용하여 구현

• BFS 활용 분야

  • 최단 경로 찾기,연결성 찾기 등

• 파이썬에서의 활용

  • deque를 사용하여 BFS 구현
  • 시작 정점을 큐에 넣고, 큐에서 정점을 하나씩 꺼내면서 연결된 정점들을 큐에 추가하는 방식으로 진행

• 느낀 점

  • BFS -> 큐를 사용해서 공부하는 방식

DFS(Depth-First Search) - 깊이 우선 탐색

• 정의

  • 그래프를 탐색하는 알고리즘 중 하나
  • 시작 정점에서 깊이 우선으로 탐색 진행
  • 스택 또는 재귀 함수를 사용하여 구현

• DFS 활용 분야

  • 사이클 검사, connected component 찾기, 위상 정렬 등

• 파이썬에서의 활용

  • 재귀 함수 또는 스택을 사용하여 DFS 구현
  • 시작 정점을 스택에 넣고, 스택에서 정점을 하나씩 꺼내면서 연결된 정점들을 스택에 추가하는 방식으로 진행

• 느낀 점

  • 재귀를 통해 구현하는 만큼 코드가 간단하고 직관적이어서 BFS에 비해서 좀 더 좋았던 것 같습니다.

전반적인 느낀 점

이번 주에는 그래프와 관련된 자료구조와 알고리즘을 집중적으로 공부하면서, 이제 정말 보면서도 이해하기 어려운 구간에 진입했구나라는 생각이 들었습니다. (특히 트리..)

하지만 위상 정렬을 한 두문제 풀었는데 진입차수 관리하는게 너무 이해가 잘 되지않아서 좀 더 DFS와 BFS에 집중했던 것 같은데, 알고리즘 주차 끝나도 스터디같이 꾸준히 공부할 수 있는 루트를 만들어서 보충해나가야할 것 같습니다.

다음 주 계획

• 그리디 알고리즘 학습
• 다이나믹 프로그래밍(Dynamic Programming) => DP 학습
• 메모이제이션(Memoization) 관련 기법 학습

3주차에는 문제가 많지 않아서 4주차 부터 들어가는 OS관련 과제들을 수행하기 위해 C언어를 기본적으로나마 다룰 줄 알아야한다고 하기 때문에 빠르게 문제를 풀고 학습 진도가 밀리지 않기 위해서 좀 C언어를 공부할 시간을 마련해야할 것 같습니다.