본문 바로가기

전체 글115

분할 정복의 진정한 핵심은 정보 구축하기! (feat. 합병 정렬) 1. 합병 정렬(Merge Sort)이란? 정렬이란 임의의 데이터 배열을 일정한 규칙에 따라 배열하는 알고리즘을 말하며, 그 종류는 여러 가지가 있다. 기초 알고리즘 수업 시간에 다루는 정렬 알고리즘에는 "버블 정렬", "선택 정렬", "삽입 정렬", "합병 정렬", "퀵 정렬", ... 등이 있다. 이 중에서 버블과 선택, 그리고 삽입 정렬은 인간의 직관적인 정렬 방식을 그대로 프로그래밍 언어로 풀이한 것으로서, 사실상 컴퓨터 과학에서 다룰 가치가 전혀 없다. 데이터 개수(N)가 증가할수록 N의 제곱으로 처리량이 증가하기 때문이다. (여담이지만 직관적인 방식으로 알고리즘을 풀면 보통 쓸만한 알고리즘이 나오지 않는 것 같다.) 그러나 합병 정렬부터는 실질적으로 사용할 수 있다. 시간복잡도가 O(N log.. 2023. 10. 31.
그래프 알고리즘 구현과 간단한 순회 알고리즘 (javascript) class Graph { constructor() { this.adjacencyList = {}; }; /** * @param {string} vertex */ addVertex(vertex) { if ( this.hasThisVertex(vertex) ) return; this.adjacencyList[vertex] = []; }; removeVertex(vertex) { if (this.hasThisVertex(vertex)) { // 1) vertex 리스트 삭제 delete this.adjacencyList[vertex]; // 2) 이 vertext에 연결하고 있는 노드들의 리스트에서 원소 삭제 for (let key in this.adjacencyList) this.removeEdge(key,.. 2023. 10. 31.
알고리즘과 도메인 로직의 분리 (2023-10-30) 데이팅 앱에서 남녀간 매칭을 위해 사용하는 알고리즘 도구는 그래프. 그래프는 노드들 사이의 관계를 매핑하는데 사용된다. 범용 도구이며, 데이팅 앱과 같은 소프트웨어는 노드의 집합(남자와 여자)과 그 사이의 관계에 대한 제약을 통해 원하는 대로 그래프를 만들어 사용한다. 남자 집합의 노드와 여자 집합의 노드 사이의 연결을 최대한 많이 만드는 것이 핵심이며, 여기에 가중치가 고려된다. 이때 가중치 계산 방법은 알고리즘이라기보단, 도메인(domain) 로직에 가깝다. 남녀 사이의 좋은 매칭이 어떤지는 컴퓨터 과학자가 알 수는 없다. 컴퓨터 과학자는 다만 검증된 그래프 이론과 컴퓨팅 도구를 제공할 뿐이다. 알고리즘을 배운다고 해서 모든 도메인의 소프트웨어를 구현할 수 있는 것은 아니다. 알고리즘과는 별개로 도메.. 2023. 10. 31.
왜 자바는 모든 것을 class로 처리하려는 것일까? (주절주절) 공부하면서 느끼는 제 개인적인 생각과 감정입니다... 자바는 클래스에서 시작해서 클래스로 끝난다. 처음부터 객체지향 설계 언어를 목표로 만들어진 언어라 그런가 싶다. 하지만 본질적으로 서로 다른 존재인 데이터 구조와 객체가 동등한 문법에 의해 만들어지는 것이 뭔가 불편하게 느껴진다. 데이터구조는 C언어의 struct와 비슷하다. 말 그대로 다양한 데이터타입을 묶어 개발자가 새롭게 정의한 데이터 타입이다. 대표적인 예로 직교좌표계의 점, 2차원의 벡터를 들 수 있다. 객체는 객체지향에서 말하는 바로 그 객체다. 객체를 정의하기가 쉽지 않지만, 객체지향에서 객체는 특정한 일에 특화된 작은 모듈이라 할 수 있다. 이때 그 구현은 외부로 드러나지 않아야 한다. 이것이 캡슐화(Capsulation) 개념이다. 만.. 2023. 10. 30.

티스토리툴바