퀴즈
퀴즈를 봤다. 총 5가지 문제가 출제 되었다.
1번 문제: 캐시 메모리와 지역성
1번 문제는 컴퓨터의 구조에 대한 문제였다. cpu와 주기억장치를 비롯한 구성요소의 속도 차에 의한 시스템 전체 성능에 대해 미치는 영향을 이해하고 있으면 풀 수 있는 문제였다. 하드웨어 컴포넌트는 개개인이 속도가 모두 다르다. 보통 크기가 클수록 느리다. 예를 들어 보조기억장치는 용량이 크기 때문에 데이터를 다루는 것이 느리지만 cpu와 주기억장치는 다루는 데이터의 크기가 작기 때문에 속도가 빠르다. 하지만 시스템 전체 성능은 관여하는 구성요소에 따라 결정된다. 프로그램의 경우 cpu와 메모리의 성능이다. cpu는 메모리보다 훨씬 빠르다. 따라서 이 둘의 속도 격차를 줄이는게 필요하다. 캐시 메모리는 cpu와 주기억장치를 중개해주는 컴포넌트다. cpu가 사용할 데이터와 연산결과를 임시로 보관해주기 때문에 cpu는 필요한 데이터를 빠르게 얻을 수 있고 주기억장치는 데이터를 전달할 시간을 얻게 된다.
2번 문제: DFS, BFS 의사코드 작성하기
그래프의 탐색이론에 대한 이해와 구현에 대한 문제였다. 다른 분야도 마찬가지지만 소프트웨어 분야는 개념을 아무리 이해해도 구현을 하지 못한다면 의미가 없다. 저번주 티타임 때도 코치님이 프로그램은 돌아갈 수 있어야만 의미가 있다고 하셨는데 요즘 더더욱 그 말의 의미를 느끼고 있다.
DFS는 그래프의 깊이우선탐색, BFS는 너비우선탐색이다. 시작노드에서 가장 먼 노드부터 탐색하면 깊이우선탐색이고 가장 가까운 노드부터 탐색하면 너비우선탐색이다. DFS는 스택과 어울리기 때문에 재귀함수를 통해 구현할 수 있고 BFS는 큐를 통해 구현할 수 있다. BFS를 통해 가중치가 없는 그래프에서 길찾기 문제를 해결할 수 있다.
3번 문제: 다익스트라 알고리즘의 메커니즘
하나의 시작점에서 다른 정점까지의 최소경로를 구하는 문제는 다익스트라 알고리즘을 통해 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘의 한 유형으로서 확인하는 노드에서 주변노드까지 가장 비용이 적은 간선을 택하여 최소 경로를 찾는다.
4번 문제: 프로세스와 스레드의 차이
프로세스와 스레드의 차이점에 대해 묻는 문제였다. 시간적 공유와 공간적 공유를 서술하고 프로그램에서 성능에 미치는 요소를 설명했다.
5번 문제: B-Tree 인덱스의 역할과 기능
B-Tree의 역할과 기능에 대해 묻는 문제였다.
자료구조와 알고리즘
시험이 끝나고 자료구조와 알고리즘 산매경이었다. 위에서 언급했다시피 프로그래머는 결국 구현이다. 아이디어를 구현할 수 있는 것이 프로그래머로서의 최소이다. 그런면에서 자료구조와 알고리즘은 아이디어의 구현을 하는데에 최소한의 연습이 된다.
우선순위 큐
다익스트라 알고리즘을 구현하기 위해서는 힙을 활용해야한다. 힙은 완전이진트리다. 완전이진트리는 리스트로 구현하는 방법과 우선순위 큐로 구현하는 방법이 있는데 후자가 시간복잡도가 평균적으로 낮아 성능이 더 좋다. 파이썬의 경우 리스트를 선언한 후에 heapify 메서드를 활용하여 힙으로 만들면 완전이진트리를 쉽게 구현할 수 있다. 완전이진트리의 부모-자식 노드는 인덱스관계를 통해 구할 수 있다.
우선순위 큐 정리
다익스트라 알고리즘
우선순위 큐를 정리한 후에 다익스트라 알고리즘을 구현했다. 다익스트라 알고리즘은 그래프, 시작점, 목표점을 입력받아 최소 경로 길이를 반환할 수 있다. 그래프는 인접리스트로 구현한다. 인접리스트는 인덱스 각각이 정점을 나타내고 인덱스마다 간선의 가중치와 연결된 정점을 표현한다. 우선순위 큐를 통해 간선들을 정렬하면 각각의 연결된 정점에 최소 가중치 간선을 택하여 정점 별 최소 길이 경로를 구할 수 있다.
다익스트라 알고리즘 정리