오늘 한 일👊

• 정보처리기사 실기 시험 공부
• graph, tree 공부 범위 정리
• 알고리즘 문제 풀이: 11724

Python 2차원 배열 출력

2차원 배열을 깔끔하게 확인하고 싶다면, * 연산자와 sep 옵션을 이용한다.

connection = [[0 for i in range(N)] for j in range(N)]
print(*connection, sep='\n')

'''
[0, 1, 0, 0, 1, 0]
[1, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
'''

Graph, Tree

이번 주차는 그래프를 공부하다보니, 내용이 무척 방대함이 와닿았다. 그래서 내가 어떤 부분을 공부해야할지 정리하는 것이 필요해서 알고리즘 책을 보고 정리해보았다. 정리하고보니 각 단원들 사이의 연관 관계도 보이고 공부 방향도 명확해졌다.

# 그래프
## 표현
ㄴ 인접 행렬
ㄴ 인접 리스트
ㄴ 인접 배열, 인접 해시테이블

## 탐색
ㄴ 너비 우선 탐색(BFS)
ㄴ 깊이 우선 탐색(DFS)

## 최소 신장 트리(Minimal Spanning Tree)
: cycle을 갖지 않은 그래프 중에 길이가 가장 짧은 점
ㄴ 프림 알고리즘: 모든 정점을 포함할 때까지 탐색한다.
ㄴ 크루스칼 알고리즘: 사이클을 만들지 않을 때 최소 비용간선을 하나씩 더해가면서 만든다.

## 위상 정렬(Topological Sorting)

## 최단 경로
ㄴ 다익스트라: 음의 가중치를 허용하지 않는다.
ㄴ 벨만포드: 음의 가중치가 존재한다.
ㄴ 모든쌍 최단 경로
ㄴ 사이클이 없는 그래프의 최단 경로
---
# 검색 트리
## 이진 검색 트리
ㄴ 검색
ㄴ 삽입(재귀, 비재귀)
ㄴ 삭제
## 레드블랙트리
ㄴ 삽입
ㄴ 삭제

## B트리
ㄴ 검색
ㄴ 삽입
ㄴ 삭제

## 다차원 검색 트리   
ㄴ KD-트리
ㄴ KDB-트리
ㄴ R-트리

문제 풀이

11724: 연결 요소의 개수

파이썬에서 인접 리스트 만드는 방법이 생각나지 않아 2차원 배열로 풀었다. python으로 하면 시간초과나서 pypy로 바꾸니 통과되었다.
그런데 pypy로 수정하는 것이 근본적인 해결책이 아닌 것 같아 친구랑 같이 linkedList로 수정했다. 그랬더니 python에서도 통과했다.
linkedlist 쓰는 방법은 무척 간단하다.

노드 사이의 관계를 2차원 배열에서 다음처럼 했다면,

connection = [[0 for i in range(N+1)] for j in range(N+1)]

빈 배열을 개수만큼 만들어서, index를 노드 value로 두고 해당하는 리스트에 노드와 연결된 value(즉 index)를 추가하는 것이다.

connection = [[] for i in range(N+1)]

내일은 이렇게 수정해봐야겠다.

내일 할 일🍅

• 이론 공부한 내역 velog에 업로드하기
• 알고리즘 문제 풀이

이번주는 저번주보다 체감상 내용이 익숙해서 공부하는게 덜 부담스럽다. 덕분에 내가 아는 것을 남에게 공유할 수 있어서 뿌듯하고, 공부 방향도 명확하며 내가 목표로 하는 구현 능력도 기를 수 있을 것 같다.