프로그래밍(Basic)
[바미] Go - Heap 을 이용하여 문제를 풀어보자!
매일프로그래밍 이라는 곳에서 나왔던 문제를 풀어보려 합니다. 문제는 아래와 같습니다. 문제) 정수 배열(int array)과 정수 N이 주어지면, N번째로 큰 배열 원소를 찾으시오. 예제) Input : [-1, 3, -1, 5, 4], 2 Output : 4 Input : [2, 4, -2, -3, 8], 1 Output : 8 Input : [-5, 3, 1], 3 Output : -5 이 문제를 푸는 방법은 여러가지가 있겠지만 Input : [-1, 3, -1, 5, 4], 2 Output : 4 의 경우 가장 무식하게, 단순하게 푸는 방법은 배열 2개 짜리를 하나 만들고, 가장 큰 값을 앞에, 두번째로 큰 값을 뒤에 적어주는 방법입니다. 그래서 처음에 -1이 나왔고, 3이 있는데 3과 -1을 비교..
[바미] Go - Heap에 대해 알아보자2!
지난 시간에 최대 값과 최소 값을 빠르게 가져오기 위해 Heap을 사용한다고 했었고, Heap의 추가 방법, 삭제 방법에 대해 알아 보았습니다. 이 Heap을 Tree로 만들려고 하면 상당히 어렵습니다 부모와 자식간 Linked list로 연결되어 있기 때문에 각각 층간에 연결되어야 하기 때문에 보통 Heap의 같은 경우 Array를 많이 사용합니다. 이것을 Go에서는 Slice라고 합니다. 보통 맨 앞을 Root Node로 두는데 아래와 같이 Heap이 구성되어 있다고 가정할 때 이걸 배열로 표시를 하면 맨 앞이 Root니까 9인데 BFS하듯이 돈다고 생각 하면 됩니다. 그래서 아래와 같은 배열이 구성 됩니다. 9 7 8 3 4 6 7 그리고 그 다음에 추가되는 값은 빈 공간에 추가되고, 뺄 때는 맨 ..
[바미] Go - Heap에 대해 알아보자!
안녕하세요. 오늘은 Heap에 대해 알아보려 합니다. 그 전에 지난 번에 아래와 같은 Tree를 그렸는데 맨위의 root 값이 왜 5인지 궁금해 할 것입니다. 왜 가운데 값이 root에 들어갈까요? 생각해보면 1~10까지를 갖는 Tree가 있는데 아래와 같은 형태로 그려진다 했을 때 위와 같이 오른쪽으로만 이어진 Tree도 BST가 맞다. 자기 값보다 큰 값이 오른쪽이 들어가 있기 때문입니다. 그래서 1 ~ 10까지 Node를 집어 넣을 때 순서대로 집어 넣는다 할 때 위와 같이 한 줄로 나오게 됩니다. 반대로 10 ~ 1까지 거꾸로 집어넣으면 왼쪽으로만 값이 들어가질 것입니다. 당연히 위의 형태도 BST가 맞습니다. 하지만 BST의 장점이 어떤 값을 찾을 때 반절을 버리고 찾는다는 것에 있는데 위의 형..
[바미] Go - BTS가 아닌 BST에 대해 알아보자!
안녕하세요. 오늘은 이진트리에 대해 알아보고자 합니다. 위의 그림 같이 자식이 두 개 밖에 없는 것을 이진트리라고 합니다. 기존의 트리는 Type TreeNode struct { childs []*TreeNode } 형태로 슬라이스 형태로 가졌는데 이진트리는 자식이 두 개 밖에 없기 때문에 슬라이스 형태로 가질 필요가 없습니다. Type TreeNode Struct { left *TreeNode right *TreeNode } 이 부분을 코딩해보죠. package dataStruct type BinaryTreeNode struct { Val int left *BinaryTreeNode right *BinaryTreeNode } 이 부분을 먼저 짚고 가는 이유는 다음에 설명할 BST(Binary Searc..
[바미] Go - Tree BFS 와 Dijkstra에 대해 알아보자!
안녕하세요. 오늘은 Tree BFS 와 Dijkstra에 대해 알아보고자 합니다. 이번에 할 것은 Tree 순회 중에 너비 우선 탐색(BFS, Breadth-First Search)인데 옆에 부터 탐색한다는 것이다. 이렇게 구성되있을 때 탐색 순서는 1. 우선 Root인 1번부터 탐색하고, 2번으로 가서 너비로 가기 때문에 3번을 탐색합니다. 2. 3번 간 뒤에 옆이 없기 때문에 4, 5, 6, 7번을 탐색하게 됩니다. BFS는 큐로 이용해서 만들 수 있습니다. 큐로 이용한 BFS 순서는 아래와 같습니다. 마찬가지로 아까 했었던 Tree로 구성되어 있을 때 Root부터 큐에 넣는다. 그러면 1번이 들어가게 되고 1 바로 1번을 Pop한 뒤에 1번의 자식들을 모두 큐에 집어 넣습니다. 출력값 : 1- 2 ..
[바미] 자바스크립트 스코프에 대해 알아보자.
스코프란? 자바스크립트에서 스코프란 어떤 변수들에 접근할 수 있는지를 정의합니다. 스코프엔 두 가지 종류가 있습니다. 전역 스코프와 지역 스코프로 나뉩니다. 그럼 먼저 전역 스코프에 대해서 알아봅시다. 전역 스코프 전역 스코프는 변수가 함수 바깥이나 {}바깥에서 선언되었다면, 전역 스코프에 정의 됩니다. const globalVariable = 'variable' 위와같이 전역 변수를 선언한다면 코드 모든곳에서 globalVariable이라는 변수를 사용할 수 있습니다. 심지어 함수에서도 사용이 가능하죠 아래 예제를 보시죠 const hello = 'Hello Marcus' function marcusHello () { console.log(hello) } console.lo..
[바미] JAM Stack이란 무엇일까?
JAM Stack 개념 정리하기 SSR 도입위해 NextJS 를 검토하던중 JAM Stack 개념을 알게되어 이를 정리 해보고자 한다. JAMstack WTF JAM stack 은 Javascript, Api, Markup Stack 의 약자이다. 약자에서 알수 있듯 Javascript 와 API 그리고 Markup(HTML) 만으로 이루어진 웹의 구성을 이야기하는 것인데, 우리가 알고 있는 SPA 과는 비슷하지만 다르다. SPA (Single Page Application) 와 CSR (Client Side Rendering) 웹은 보통 완성된 Static HTML 와 CSS 를 네트워크로 전달 받아서, 화면을 보여준다. 서버가 동적으로 HTML을 생성할 수 있게 되면서 Server Side Rende..
[바미] Go - Tree에 대해 알아보자!
안녕하세요 오늘은 Tree에 대해 알아보려 합니다. Tree란 말 그대로 나무라는 의미인데 위 그림처럼 줄기가 있고, 가지가 뻗어 있고, 가지 끝에 나뭇잎이 달려있는 형태를 가지고 있는 자료구조 라고 해서 Tree라고 합니다. 하나에서 시작해서 여러 갈래로 나뉘어 가는 형태가 Tree입니다. Tree의 형태를 보면 나무를 뒤집어 놓은 형태인데 아래와 같습니다. 맨 위에서부터 시작하는데 맨 처음 시작하는 노드를 Root 노드(node)들과 노드들을 연결하는 하는 부분을 간선(edge) 각 간선 끝에는 노드가 연결 되어 있는데 이 노드를 자식노드(Child Node) 자식노드 상위에 있는 노드를 Parent Node 라고 합니다. 이건 상대적인 개념인데 Root 노드는 모든 노드의 항상 부모가 되고, 자식노..
[바미] Go - Packaging 과 Stack, Queue에 대해 알아보자!
안녕하세요. 오늘은 Go의 Packaging 과 Stack, Queue에 대해 알아보겠습니다. 패키지(Package)라는 것은 어떤 모듈, 기능 등을 묶어 놓은 것을 의미 합니다. Go 자체가 가지고 있는 "fmt"라는 패키지가 있는데 "format"의 약자인데 이것은 출력과 관련된 것들을 묶어놓은 것이고, "math"라는 패키지가 있는데 수학과 관련된 함수들을 묶어 놓은 패키지 입니다. 이런 관련된 기능들을 묶어 놓은 것을 패키지(Package)라고 합니다. 이전에 Linked List를 만들었었는데 그 외에도 Stack, Queue, Tree, Heap들을 하나의 패키지로 만들어서 dataStruct라는 것으로 만들어 늘려가볼까 합니다. 먼저 지난 시간에 만들었던 Linked List를 패키지로 분리..