TIL_230323-0324

3월 23일 (목)

• 알고리즘 : 그리디 문제 풀이, 알고리즘 문제 풀이 리뷰
• CS 스터디 : 자료구조 공부
• 프로젝트 브랜치 정리

 

3월 24일 (금)

• 알고리즘 : 구현 문제 풀이, 알고리즘 문제 풀이 리뷰
• 디자인 패턴 랜덤 손코딩 복습

---

📝배운 내용 간단 요약

1️⃣ 비선형 자료 구조 : 그래프

정점과 간선으로 이루어진 집합

정점 (Vertex, Node, V or U)

• 어떤 위치, 어떠한 지점
• 인접 정점 - 간선에 의해 직접 연결된 정점

간선 (Edge)

• 정점과 정점을 잇는 선
• 무방향 vs 방향 간선
• 차수(degree) - 무방향 그래프에서 하나의 정점에서 인접한 정점 수
• 진출/진입 차수 - 어떤 정점에서 나가는/들어오는 간선의 수
• 가중치(weight) - 간선 사이의 이동 값

그래프 저장 방법

• 인접 행렬 : 정점, 간선 관계를 2차원 행렬로 표현, V*V 공간 복잡도
• 인접 리스트 : 정점, 간선을 2차원 ArrayList로 표현, 차수의 합이 공간 복잡도

 

2️⃣ 비선형 자료 구조 : 트리

• Directed Acyclic Graph(방향성이 있는 비순환 그래프)의 한 종류
• 한 개의 루트 노드. 부모, 자식 관계.
• 노드가 N개인 트리는 항상 N-1개의 간선
• 임의의 두 노드 사이의 경로는 유일무이.
• 깊이(depth) - 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
• 높이 - 루트노드부터 리프 노드까지 거리 중 가장 긴 거리

 

 

참고 자료

주홍철, <면접을 위한 cs 전공지식 노트>, 길벗, 2022