공부

취미는 JetBrains Academy

요즘 시간만 나면 하는 일은 JetBrains Academy에서 Topic을 공부하고 Notion에 정리하거나, Project를 진행하는 것이다.

매니저 역할이 어울릴 나이와 연차가 되었고, 실제로 회사에서의 역할도 매니저지만, 소프트웨어 개발과 관련된 모든 일을 내 손으로 직접할 수 있는 능력을 갖추겠다는 의지를 이어나가고 있다.

회사에서는 우선 매니저 역할에 충실해야 하므로, 집에서 육아를 하면서 틈틈히 JetBrains Academy를 통해 실무에 대한 아쉬움을 달래고 있다. 한 맺힌 사람처럼.

올해 상반기엔 3개의 트랙을 수료할 생각이다.

  • Java Backend Developer
  • Frontend Developer
  • Kotlin Developer

회사에서 함께 갖춘 기반 없이, 개인적으로 백지에서 개발을 시작하려면 아직 막막함이 느껴지지만, 끊임없이 빈 구멍을 메워나가다보면, 혼자서도 꽤 괜찮은 소프트웨어를 만들어 낼 수 있는 수준에 이를 수 있을 것으로 믿는다.

소프트웨어는 함께 개발하는 것이지만, 혼자서도 할 수 있다는 것을 스스로 확인하고 싶다. 그게 진짜 실력이 아닐까 싶다.

5년만에 다시 쓰는 Java (feat. JetBrains Academy)

내년에 새롭게 참여할 프로젝트에서 Java + Spring Boot 조합을 써야해서 급하게 공부를 하고 있다.

커리어를 돌아보면, Java로 가장 많은 코드를 작성한 것 같다. 그 다음은 Python.

마지막으로 Java를 사용한 건 2016년이니 정말 오랜만에 다시 Java를 쓰게 되었는데, 그새 버전은 8에서 17로 올라갔다.

Spring Boot는 이번이 처음이다.

어떻게 공부하면 좋을까 탐색하다 찾은 것은 JetBrains Academy.

Java Backend Developer Track을 진행 중인데, 프로젝트를 중심으로 이론, 연습문제, IDE를 연동한 실습이 제공된다.

프로젝트를 먼저 선택한 다음, 그 프로젝트를 소화하는데 필요한 Topic을 공부하는 방식이다.

이론 설명도 잘 되어 있어서, 기억이 가물가물하거나 잘 모르는 것은 꼼꼼히 읽고 이해하고 정리하고 문제를 풀어보는 식으로 제대로 공부하려고 애쓰고 있다.

그래서 진도가 무척 더디지만, 하나씩 제대로 해놓으면 나중에 충분한 보상을 받을 수 있을 것으로 믿는다.

MongoDB University 개발자 과정 수료

오늘 M220P를 끝으로 6개 강의로 구성된 MongoDB 개발자 과정을 모두 수료하였다.

긴 여정이었는데 실습이 지루함을 달래 주어서 지속할 수 있었다.

2021년은 NoSQL을 제대로 공부한 해로 기억해도 좋을 것 같다.

내년엔 AWS를 제대로 공부해보고 싶다.

MongoDB Certified Developer, Associate Level 시험 후기

2021년 10월 18일 시험을 보았고, 10월 22일에 합격 통보를 받았다.

9월 24일에 준비를 시작했지만, 대부분의 공부는 하계휴가기간(10/5~12)에 이루어졌다.

무료로 제공되는 온라인 강의만 충실히 소화하면 합격할 수 있다.

https://university.mongodb.com/

특정 프로그래밍 언어와 관련된 문제는 나오지 않으므로, M220 MongoDB for Developer 강의는 듣지 않아도 된다.

그래서 총 5개의 강의를 수강해야 하는데, 영어로 들어야하고, 실습문제도 쉽진 않아서 제대로 소화하려면 꽤 시간을 투자해야한다.

온라인 강의는 훌륭하다. 충실히 따라가면 MongoDB를 실무에서 활용하는데 필요한 기본기는 충분히 갖출 수 있다.

온라인 강의에 포함된 Quiz, Lab, Final Exam 대비 시험문제의 난이도는 낮다.

연습시험을 통해 문제 유형을 파악할 수 있다. 하나라도 틀리면 점수가 없는 모두 고르시오 문제가 많이 나오고, 시중에 구할 수 있는 덤프가 없기 때문에 정확히 이해하는 것이 중요하다.

MongoDB Korea의 프로모션을 활용해서 50% 할인받아 $75에 시험을 보았고, 합격했으니 환불 받을 예정이다.

객관적인 지표로서 자격증을 획득한 것도 의미가 있겠지만, MongoDB를 제대로 쓸 수 있게 된 것이 큰 소득이다. 그래서 주변 동료들에게 MongoDB 자격증 시험에 도전하는 것을 권하고 싶다.

Go언어로 구현한 Dijkstra 알고리즘

Go언어로 구현된 코드와 한글로 작성된 설명을 인터넷에서 찾기 힘들기에, Go언어를 공부하고 있는 누군가에게는 약간의 도움이 되길 바라며, Graph Search, Shortest Paths, and Data Structures 강의에서 프로그래밍 숙제로 구현했던 Dijkstra 알고리즘 코드를 공유해본다.

수준이 낮은 코드를 인터넷에 공유하는 것은 부끄러운 일이지만, 이정도 코드밖에 만들 수 없는 것이 현재 나의 실력이라는 것을 인정해야만 더 높은 수준으로 나아갈 수 있다고 믿기에, 앞으로도 기회가 닿는대로 Go언어로 작성된 코드와 시행착오를 공유해보고자 한다.

저장소: http://gogs.reshout.com/reshout/dijkstra-heap

소스트리 구조는 아래와 같다.

├── dijkstraData.txt
├── graph
│   ├── graph.go
│   └── graph_test.go
├── heap
│   ├── heap.go
│   └── heap_test.go
└── main.go

graph 패지와 heap 패키지는 알고리즘 구현에 필요한 자료구조를 별도의 패키지로 구현한 것인데, 유닛테스트 코드를 포함하며 100%에 가까운 커버리지를 확보하였다. 유닛테스트를 통해 확보한 자료구조의 완성도 덕분에 이를 활용한 알고리즘 코드를 완성한 후에는 한 번에 원하는 답을 얻을 수 있었다. Go언어는 소스코드와 같은 폴더에 유닛테스트 코드(e.g., graph_test.go)를 작성할 수 있어서 유닛테스트를 작성하는 습관을 들이는데 도움이 되는 것 같다.

$ go test -cover ./...
?       dijkstra-heap   [no test files]
ok      dijkstra-heap/graph     (cached)        coverage: 94.4% of statements
ok      dijkstra-heap/heap      (cached)        coverage: 97.3% of statements

main.go에 구현된 Dijkstra 알고리즘은 Dasgupta가 쓴 알고리즘 책 115쪽에 있는 pseudocode를 약간 변형한 것으로 다음과 같다.

func dijkstra(g *graph.Graph) {
	for _, u := range g.GetVertices() {
		u.Distance = maxInt
	}
	g.GetVertex(1).Distance = 0

	h := heap.NewHeap()
	for _, u := range g.GetVertices() {
		h.Push(u)
	}

	for !h.IsEmpty() {
		u := h.Pop().(*graph.Vertex)
		for _, edge := range u.OutgoingEdges {
			v := edge.Head
			if v.Distance > u.Distance+edge.Length {
				v.Distance = u.Distance + edge.Length
				h.Delete(v)
				h.Push(v)
			}
		}
	}
}

heap 패키지는 다른 프로젝트에서도 사용할 수 있도록 범용적인 인터페이스를 제공한다. 아래와 같이 Less 함수를 구현한 어떤 객체도 Push(obj Object), Pop() Object 할 수 있도록 하였다.

package heap

type Object interface {
	Less(obj Object) bool
}

graph 패키지는 heap 패키지에 의존적이다. Vertexheap에 넣어놓고 Distance 기준으로 최소값을 추출해야 하기 때문이다.

package graph

import "dijkstra-heap/heap"

type Vertex struct {
	Label         int
	Distance      int
	OutgoingEdges []*Edge
}

func (v *Vertex) Less(obj heap.Object) bool {
	return v.Distance < obj.(*Vertex).Distance
}

graph 패키지는 이 프로젝트 전용이다. 알고리즘에서 사용할 연산에 최적화된 실행시간을 제공하려면 내부 자료구조나 내부 알고리즘도 달라질 수 밖에 없다.

그래프를 구성하는 Vertex들과 Edge들을 저장하는 다양한 방법이 존재할 수 있다. Dijkstra 알고리즘에서는 Heap에서 꺼낸 Vertex에서 밖으로 연결된 Edge들을 탐색하는 경우가 많으므로 VertexOutgoingEdges를 갖도록 하였다.

graph.go의 전체 코드는 아래와 같다.

package graph

import "dijkstra-heap/heap"

type Vertex struct {
	Label         int
	Distance      int
	OutgoingEdges []*Edge
}

func (v *Vertex) Less(obj heap.Object) bool {
	return v.Distance < obj.(*Vertex).Distance
}

type Edge struct {
	Tail     *Vertex
	Head     *Vertex
	Length   int
	Explored bool
}

type Graph struct {
	vMap map[int]*Vertex
}

func NewGraph() *Graph {
	g := &Graph{}
	g.vMap = map[int]*Vertex{}
	return g
}

func (g *Graph) AddEdge(tailLabel int, headLabel int, len int) {
	tail := g.GetVertex(tailLabel)
	head := g.GetVertex(headLabel)
	edge := &Edge{tail, head, len, false}
	tail.OutgoingEdges = append(tail.OutgoingEdges, edge)
}

func (g *Graph) GetVertexCount() int {
	return len(g.vMap)
}

func (g *Graph) GetVertex(label int) *Vertex {
	key := label
	if _, exists := g.vMap[key]; !exists {
		g.vMap[key] = &Vertex{Label: label, OutgoingEdges: []*Edge{}}
	}
	return g.vMap[key]
}

func (g *Graph) GetVertices() []*Vertex {
	vertices := []*Vertex{}
	for label := range g.vMap {
		vertex := g.vMap[label]
		vertices = append(vertices, vertex)
	}
	return vertices
}

Dijkstra 알고리즘에서 사용하는 Heap은 중간 객체를 찾아서 삭제하거나 업데이트하는 인터페이스가 필요한데, Go언어에 내장된 container/heap 패키지에서 이를 제공하지 않아 직접 구현했다.

type Heap struct {
	objArr []Object
	objMap map[Object]int
}

내부 자료구조로 array를 사용해야만 Leaf 노드를 찾아 치환하거나 삭제하는 연산이 O(1)에 가능하다.

중간 객체를 삭제하기 위해선 먼저 트리 안에서 해당 객체를 찾아야 하는데, Binary Search Tree가 아니므로 최악의 경우 모든 노드를 다 찾아보아야 해서 실행시간은 최악의 경우 O(n)이 된다. 이렇게 되면 Heap을 사용해 실행시간을 O(m * n)에서 O(m * log n)으로 향상시키려는 시도가 무의미해진다.

객체의 위치를 O(1)에 찾을 수 있도록 Hash Table을 도입하여 객체가 추가되거나 삭제되거나 위치가 바뀔때마다 objMap을 업데이트하도록 하여, Delete(obj Object) bool의 실행시간을 O(log n)에 맞췄다.

heap.go의 전체 코드는 아래와 같다. 더 간결하게 짤 수도 있을텐데, 지금은 이정도가 내 수준인 것 같다. 좋은 코드를 많이 볼 필요가 있을 것 같다.

package heap

type Object interface {
	Less(obj Object) bool
}

type Heap struct {
	objArr []Object
	objMap map[Object]int
}

func NewHeap() *Heap {
	return &Heap{objArr: []Object{}, objMap: map[Object]int{}}
}

func (h *Heap) Push(obj Object) {
	idx := h.insertAsLeaf(obj)
	h.bubbleUp(idx)
}

func (h *Heap) Pop() Object {
	rootIdx := 0
	root := h.objArr[rootIdx]
	leafIdx := h.getLeafIndex()

	h.swap(rootIdx, leafIdx)
	h.deleteLeaf()
	if len(h.objArr) > 0 {
		h.bubbleDown(0)
	}

	return root
}

func (h *Heap) Delete(obj Object) bool {
	if len(h.objArr) <= 0 {
		return false
	}

	objectIdx := h.getObjectIndex(obj)
	if objectIdx == -1 {
		return false
	}
	leafIdx := h.getLeafIndex()

	h.swap(objectIdx, leafIdx)
	h.deleteLeaf()
	if objectIdx != leafIdx {
		h.bubbleDown(objectIdx)
	}

	return true
}

func (h *Heap) IsEmpty() bool {
	return len(h.objArr) == 0
}

func (h *Heap) getParentIndex(idx int) int {
	if idx == 0 {
		return -1
	}
	return (idx - 1) / 2
}

func (h *Heap) getLeftChildIndex(idx int) int {
	leftChildIdx := 2*(idx+1) - 1
	if len(h.objArr) <= leftChildIdx {
		return -1
	}
	return leftChildIdx
}

func (h *Heap) getRightChildIndex(idx int) int {
	rightChildIndex := 2*(idx+1) + 1 - 1
	if len(h.objArr) <= rightChildIndex {
		return -1
	}
	return rightChildIndex
}

func (h *Heap) getLeafIndex() int {
	return len(h.objArr) - 1
}

func (h *Heap) getObjectIndex(obj Object) int {
	idx, exists := h.objMap[obj]
	if !exists {
		return -1
	}
	return idx
}

func (h *Heap) insertAsLeaf(obj Object) int {
	h.objArr = append(h.objArr, obj)
	idx := len(h.objArr) - 1
	h.objMap[obj] = idx
	return idx
}

func (h *Heap) deleteLeaf() {
	leafIdx := h.getLeafIndex()
	leafObj := h.objArr[leafIdx]
	delete(h.objMap, leafObj)
	h.objArr = h.objArr[:leafIdx]
}

func (h *Heap) swap(idx1 int, idx2 int) {
	h.objArr[idx1], h.objArr[idx2] = h.objArr[idx2], h.objArr[idx1]
	h.objMap[h.objArr[idx1]] = idx1
	h.objMap[h.objArr[idx2]] = idx2
}

func (h *Heap) bubbleUp(idx int) {
	pIdx := h.getParentIndex(idx)
	if pIdx == -1 {
		return
	}
	pObj := h.objArr[pIdx]
	obj := h.objArr[idx]
	if obj.Less(pObj) {
		h.swap(pIdx, idx)
		h.bubbleUp(pIdx)
	}
}

func (h *Heap) bubbleDown(idx int) {
	node := h.objArr[idx]
	leftIdx := h.getLeftChildIndex(idx)
	leftLess := (leftIdx != -1 && h.objArr[leftIdx].Less(node))
	rightIdx := h.getRightChildIndex(idx)
	rightLess := (rightIdx != -1 && h.objArr[rightIdx].Less(node))

	if leftLess && rightLess {
		if h.objArr[leftIdx].Less(h.objArr[rightIdx]) {
			h.swap(idx, leftIdx)
			h.bubbleDown(leftIdx)
		} else {
			h.swap(idx, rightIdx)
			h.bubbleDown(rightIdx)
		}
	} else if leftLess {
		h.swap(idx, leftIdx)
		h.bubbleDown(leftIdx)
	} else if rightLess {
		h.swap(idx, rightIdx)
		h.bubbleDown(rightIdx)
	}
}

유닛테스트는 집요할 수록 좋다. 아래는 heap_test.go의 전체 코드다.

package heap

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

type testObject struct {
	key int
}

func (t testObject) Less(obj Object) bool {
	return t.key < obj.(testObject).key
}

func TestHeap(t *testing.T) {
	h := NewHeap()
	assert.True(t, h.IsEmpty())
	h.Push(testObject{11})
	h.Push(testObject{12})
	h.Push(testObject{13})
	h.Push(testObject{6})
	h.Push(testObject{8})
	h.Push(testObject{20})
	h.Push(testObject{15})
	h.Push(testObject{10})
	h.Push(testObject{5})
	h.Push(testObject{3})
	assert.False(t, h.IsEmpty())
	assert.False(t, h.Delete(testObject{100}))
	assert.Equal(t, 3, h.Pop().(testObject).key)
	assert.True(t, h.Delete(testObject{10}))
	assert.True(t, h.Delete(testObject{6}))
	assert.Equal(t, 5, h.Pop().(testObject).key)
	assert.Equal(t, 8, h.Pop().(testObject).key)
	assert.Equal(t, 11, h.Pop().(testObject).key)
	assert.Equal(t, 12, h.Pop().(testObject).key)
	assert.Equal(t, 13, h.Pop().(testObject).key)
	assert.Equal(t, 15, h.Pop().(testObject).key)
	assert.Equal(t, 20, h.Pop().(testObject).key)
	assert.False(t, h.Delete(testObject{20}))
	assert.True(t, h.IsEmpty())
}

소프트웨어를 설계하거나 코드를 작성할 때면, optimal solution을 가진 신이 등장해서 피드백을 주면 좋겠다는 생각을 하게 된다. 신은 아니더라도 나보다 나은 누군가가 이 코드를 보고 문제점, 개선점을 알려 주었으면 하는 바램이다.