[SCCC 스터디] 4일차 기초 자료구조

SCCC 스터디 4일차 1月 14日

오늘은 기초 자료구조에 대해 공부했다.

1. list

STL에 있는 list을 이용하여 구현해봤다. list를 이용한 문제가 잘 안나온다고 하는데 그렇게 어려운것도 아니고 간단한 자료구조이기도 하고 혹시 나오면 당황해서 못짜는 것보단 아는 것이 좋아 list를 이용해 백준에 있는 문제를 풀었다.

2. Graph

Graph를 인접행렬로 표현 할 수 있고, 인접리스트로 표현 가능하다. 각자의 장단점이 존재한다. 어느정도 작을땐 인접행렬을 이용해 문제를 풀어도 되고 좀 클땐 인접리스트가 효율적이다.

3. Tree

트리에 가장 큰 특징은 사이클이 없는 연결 그래프라는 점이다. 즉, Tree는 Graph의 일종이다. 

또한 트리는 정점이 n개가 있으면 간선은 n - 1개가 있다. (이를 만족하지 않는다면 트리가 아니다.)

1. 조세퍼스 문제 - ●●◐○○ 

2. 풍선 터트리기 - ●●◐○○

3. 키로거 -  ●●◐○○

4. 뱀 - ●●○○○

5. DFS와 BFS - ●◐○○○

6. 연결 요소의 개수 - ●●○○○ 

7.  적록색약 - ●●○○○

8. 오일러 회로 - (아직 못품)

9. 트리의 부모 찾기 - ●●●○○ 

10. 촌수계산 - ●●○○○

11. 트리 순회 - (아직 못품)

12. 양 구출 작전 - (아직 못품)

13. 단말 장점들의 거리 - (아직 못품)