꾸준합니다

병합 정렬 : 자르고 합치기

이번 포스팅에서는 Merge sort - 병합 정렬에 대해 알아보도록 하겠습니다. 1. 병합 정렬 (Merge Sort) 이란? 이름에서 알 수 있듯이 병합정렬은 주어진 자료구조를 여러 조각으로 자르고 다시 합쳐 나가는 과정에서 정렬을 하는 정렬입니다. 구현 방식은 일반적으로 재귀로 구현되며 분할정복 방식이라는 데서 Quick Sort와 유사한 면이 있어 자주 비교 대상이 되곤 합니다. 퀵 정렬 : Pivot 이번 포스팅에서는 정렬의 종류 중 하나인 퀵 정렬에 대해서 알아보겠습니다. 대다수의 정렬이 구현된 언어, 프레임워크 등에서 자료구조를 정렬할 때 퀵 정렬 로직을 사용하고 있습니다. 어떠 hy1as.tistory.com 2. 병합 정렬의 진행 자료 구조의 길이가 0 또는 1이면 이미 정렬 된것으로 봅..

Big-O Notation - 공간 복잡도

이번 포스팅에서는 공간 복잡도에 대해 이야기해보도록 하겠습니다. 1. 공간 복잡도란? 공간 복잡도는 해당 문제를 해결하기위해 얼마나 많은 공간(메모리)을 필요로 하느냐를 나타내는 척도입니다. 공간 복잡도 또한 시간복잡도와 같이 빅 오 표기법으로 표현 할 수 있습니다. 빅 오로 공간복잡도를 표현할 때 핵심 질문은 "데이터 원소가 N개 일 때 알고리즘은 메모리 단위를 얼마나 소모할까?"입니다. 아래의 코드를 한 번 보겠습니다. function makeUpperCase(array) { let newArray = []; for (let i = 0; i < array.length; i++) { newArray[i] = array[i].toUpperCase() } return newArray; } 위의 코드는 크기..

그래프 (3) : 가장 짧은 경로

이번 포스팅에서는 가중 그래프와 최단 거리 찾기에 자주 사용되는 알고리즘에 대해 알아보도록 하겠습니다. 1. 가중 그래프(Weighted graph) 란? 그래프에는 다양한 변형이 존재합니다. 그래프 간선에 정보를 추가하는 가중 그래프 역시 또 하나의 유용한 그래프 유형입니다. 위 그래프와 같이 간선에 비용, 거리 등을 데이터를 부여하여 사용됩니다. 코드로 구현한다면 아래와 같이 구현할 수 있습니다. class WeightedGraphVertex { data; // 배열 대신 해시 테이블 사용하여 가중치 삽입 adjacentVertices; constructor(data) { this.data = data; this.adjacentVertices = new Map() } addAdjacentVertex(..

그래프 (2) : 탐색의 방향?

그래프에서의 탐색은 우리가 일반적으로 알고 있는 자료구조에서 일반적으로 쓰이는 연산으로서의 의미 이외에도 여러 의미와 쓰임새를 가지고 있습니다. 이번 포스트에서는 그 의미와 쓰임새를 알아보고 탐색을 진행하는 방법에는 어떠한 것이 있는지 이야기해 보겠습니다. 1. 그래프에서의 탐색 그래프 용어에서 탐색은 몇가지 의미를 함축하고 있습니다. 단순한 의미로는 특정 정점(vertex)이 어디에 존재하는지 찾는 것입니다. 또 하나는 그래프 내에서 정점에 접근할 수 있을 때 그 정점과 연결된 또 다른 특정 정점을 찾는 것을 의미합니다. 경로(path)라는 용어는 그래프 용어로 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻합니다. 그래프의 탐색은 특정 정점 찾는 것 이외에도 두 정점이 서로 연결되어있는 상태인지 ..

그래프 (1) : SNS가 이거에요

이번 포스팅에서는 데이터 간의 관계에 특화된 자료구조인 그래프에 대해서 이야기해 보겠습니다. 1. 그래프란? 그래프는 관계를 표현하는데 특화된 자료구조로서 데이터 간 연결 상태를 쉽게 보여줍니다. 그래프에서는 각각의 구성 요소를 가리키는 단어가 존재합니다. 그래프의 노드를 정점(vertex), 그 정점을 연결하는 선을 간선(edge)라고 부릅니다. 간선으로 연결된 정점들은 서로 인접한다(adjacent)라고 말합니다. 그리고 인접한 정점들을 가리켜 이웃(neighbor)라고 부릅니다. 그래프에서는 다른 정점과 연결되지 않은 정점이 존재할 수 있습니다. 모든 정점이 연결되어있는 그래프를 가리켜 연결 그래프(connected graph)라고 부릅니다. 2. 방향 그래프 SNS를 예로 들어보면 A라는 사람이 ..

[boj] 1463. 1로 만들기

[boj] 1463. 1로 만들기 문제 링크 : https://www.acmicpc.net/problem/1463 사용 언어 : Node.js 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 1. 문제 분석 이번 문제는 주어진 연산을 이용해 1을 만드는 경우의 수중 연산의 횟수가 가장 적은 경우의 연산 횟수를 출력하는 문제입니다. 입..

일확천금의 꿈 - 1편 : 새로운 프로젝트를 시작합니다.

서론 안녕하세요. 얼마 전 고통의 나날이던 프리랜서 생활을 정리하고 다시 직장인으로 복귀하게 되었습니다. 직장인으로 돌아온 후 지독하게 시달리던 불면증과 안녕하고 스트레스가 사라지고 입맛이 싹 도는 중입니다. 하지만 마음의 평화도 잠시... 통장에 들어오는 월급의 소박함에 깊은 고민에 빠지게 되었습니다. 이러다 내 집 마련의 꿈은 손목터널 증후군으로 인해 손목 연골이 다 닳아 없어지고 난 후에야 가능하겠다는 생각에 정신이 아득해졌습니다. 결국 이러한 생각들은 근로소득만으로는 답이 없다는 생각으로 귀결되었고 그 결과 제2의 워뇨띠를 꿈꾸며 성공한 주식 투자자로 거듭나기로 결심했습니다. 참고로 저는 야수의 심장 + 귀가 얇음 환장의 콜라보로 인해 GME (-42%), EH (-51%) 로 돈을 삭제한 화려한..

[boj] 17299. 오등큰수

[boj] 17299. 오등큰수 문제 링크 : https://www.acmicpc.net/problem/17299 사용 언어 : Node.js 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 $ N $ 인 수열 $ A = A_1, A_2, ..., A_N $이 있다. 수열의 각 원소 $ A_i $에 대해서 오등큰수 $ NGF(i) $를 구하려고 한다. $ A_i $가 수열 $ A $에서 등장한 횟수를 $ F(A_i) $라고 했을 때, $ A_i $의 오등큰수는 오른쪽에 있으면서 수열 $ A $에서 등장한 횟수가 $ ..