오늘 한 일✍️

• 정보처리기사 실기 시험
• 알고리즘 이론 공부(그래프)

그래프

이번 주차는 문제 풀이를 잘하는 것도 중요하지만, 그래프와 트리를 잘 이해하고 이를 응용해서 문제를 풀이하는 능력이 필요할 것 같다. 특히 이것을 무엇으로 구현하느냐에 따라 성능이 달라지기 때문에 적절한 자료형을 사용하는 것이 중요할 것이라 생각한다. 그래서 당장 문제를 푸는데에 집중하기보다 이론 공부를 함께 하면서 하고 있다.

그래서 내용들을 노션에 정리하면서 하고 있는데 내용이 좀 방대해서 여기서는 대략적인 내용만 작성하고 자세한 내용은 별도의 게시글을 작성하겠다.

그래프 구성

• 정점(Vertex): 대상이나 개체
• 간선(Edge): 이들 간의 관계

그래프 구분

• 유향 그래프(Directed Graph): 그래프의 방향을 가진 그래프
  - 트리도 유향 그래프 일종이다.
• 무향 그래프(Undirected Graph): 간선의 방향이 없는 그래프

그래프 표현

• 인접 행렬 이용
• 인접 리스트 이용
• 인접 배열 이용
• 인접 해시 테이블 이용

인접 행렬은 정점의 개수에 비해 간선의 개수가 매우 적다면, 특정 점만 1로 채워지고 나머지는 0이된다. 행렬을 만드는 것 자체가 n^2의 시간 복잡도이므로 무작정 사용하는 것은 좋지 않다.

배열 vs 해시 테이블

그래프 표현 방법 중에 인접 배열과 인접 해시테이블이 있다. 해시 테이블의 개념인 hash function을 거쳐서 인덱스를 생성해 배열의 해당 인덱스에 값을 저장하는 것은 알고 있다.
그런데 순간 배열과 해시 테이블이 어떤 용도로 사용되는지 와닿지 않았다.

그래서 토론글을 찾아보니
해시 테이블은 key값에 해당하는 데이터를 기억하기 위한 용도이다. 예를들어, 해시 테이블에서 Key 5에 해당하는 값이 있는가를 찾는다면 hash function을 거쳐서 해당하는 인덱스를 바로 찾을 수 있다.

반면 배열은 키가 없으니 처음부터 끝까지 확인해야 한다. 물론 배열의 5번째 줄에 저장된 값이 무엇인가요? 라는 것은 O(1)번에 찾을 수 있다.

개념 자체를 이해하기보다 왜 만들어졌는지, 어떤 차이가 있는지 함께 생각하면 좋을 것 같다.

벌써 월요일이다.
주말에 정처기 실기 시험이 있었다보니, 공부 흐름에 방해된다. 몰입을 방해하는 요소는 가급적 처내야겠다고 생각한다. 이번은 나의 실수였다.
그래도 근처에서 시험보고 친구랑 밥 먹고 왔다. 오랜만에 고등학교 친구를 만나니 무척이나 반가웠다. 나와 전혀 다른 분야라 개발 이야기를 하지 않아도 되어서 좋았다.😁
앞으로 오전, 오후, 저녁마다 할 일을 대략적으로 구분할 예정이다. 일단 오늘 해보고 후기를 작성하겠다.