Computer Science

최악의 경우 $\Theta(n^2)$의 시간복잡도를 갖지만 $\Omicron(n\log n)$ 평균적으로 가장 좋은 성능을 보이고 구현이 쉬워 현업에서 가장 많이 쓰인다고 알려진 퀵 정렬을 알아보고 자바와 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 퀵 정렬 `퀵 정렬(quick sort)`은 병합 정렬 알고리즘과 비슷하게 입력을 나누어 각각에 대해 재귀적으로 정렬하는 알고리즘입니다. 퀵 정렬과 병합 정렬의 차이점은 크게 두 가지가 있습니다. 퀵 정렬은 병합 정렬과 달리 합치는 과정이 없고 입력을 항상 반씩 균등하게 나누지 않습니다. 퀵 정렬은 기준값정하고 기준값보다 큰 값들과 작은 값들로 입력을 분할합니다. 이때 기준값을 `피벗(pivot)`이라 합니다. - Pseudocode qui..

지금까지 기본적인 시간 복잡도가 $\Omicron(n^2)$인 정렬 알고리즘들을 알아봤습니다. 선택 정렬, 삽입 정렬, 버블 정렬은 모두 평균 $\Theta(n^2)$의 시간 복잡도를 가졌고 삽입정렬과 개선된 버블 정렬은 최선의 경우 $\Theta(n)$의 시간 복잡도를 가졌습니다. 이번에는 평균 $\Theta(n\log n)$의 시간 복잡도인 고급 정렬 알고리즘들에 대해 알아봅시다. 자료구조, 알고리즘 시리즈 모아보기 병합 정렬 `병합 정렬(merge sort)`은 입력을 반으로 나누어 각각 정렬한 뒤 합치는 재귀 알고리즘입니다. "정렬하는 방법이 반으로 나눈 뒤 각각 정렬하는거면 각각은 어떻게 정렬하라는 거지?" 싶을 수 있습니다. 재귀적으로 입력을 반으로 나눠 정렬하다보면 어느 순간 입력의 크기는 ..

그 유명한 버블 정렬에 대해 알아보고 C++, 자바, 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 버블 정렬 `버블 정렬(bubble sort)`은 선택 정렬처럼 가장 큰 원소를 끝으로 옮기는 작업을 반복하는 알고리즘입니다. 선택 정렬이 큰 값을 콕 찍어서 옯겼다면 버블 정렬은 한쪽 끝에서 긁어 올라가며 더 큰 값만 가지고 올라가는 방식입니다. 이렇게 논리적으로 아래에서부터 수면 위로 올라가는 모습을 컴퓨터 과학에서는 버블링이라고 합니다. DOM트리에서 일어나는 이벤트 버블링도 아래에서 위로 올라가는 의미의 버블링이죠. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 버블 정렬 알고리즘은 다음과 같습니다. bubbleSort(A[], n){ for( last ← n d..

정렬 알고리즘 중 삽입 정렬을 알아보고 C++, 자바, 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 삽입 정렬 `삽입 정렬(insertion sort)`은 정렬된 부분을 하나씩 확장해 가며 모든 수열을 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 삽입 정렬 알고리즘은 다음과 같습니다. insertionSort(A[], n){ for( last ← 2 to n ) A[1 ⋯ last] 에 A[last]가 들어갈 곳을 찾아 넣는다; } 구체화하면 아래와 같습니다. insertionSort(A[], n){ for( last ← 2 to n ){ newElement ← A[last]; // 추가할 요소 i ← last-1; // newElement와..

정렬 알고리즘에서 가장 기본이 되는 선택 정렬을 알아보고 C++, 자바 그리고 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 선택 정렬 `선택 정렬(selection sort)`은 정렬할 수열에서 가장 큰 값(혹은 가장 작은 값)을 선택해 한쪽 끝으로 옮기는 행위를 반복하여 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 선택 정렬 알고리즘은 다음과 같습니다. selectionSort(A[], n){ for( last ← n downto 2 ){ A[1 ⋯ last] 중 가장 큰 수 A[k]를 찾는다; A[k] ↔︎ A[last]; } } 조금 더 구체화하면 아래와 같습니다. selectionSort(A[], n){ for( last ← n dow..

저번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 표현하는 점근적 표기법에 대해 알아봤습니다. 이번 글에서는 구조가 복잡한 재귀 알고리즘의 시간 복잡도를 어떻게 계산하는지 살펴봅시다. 자료구조, 알고리즘 시리즈 모아보기 재귀 알고리즘 `재귀 알고리즘`은 어떤 문제를 해결할 때 크기가 더 작은 동일한 문제를 해결해 얻은 답을 이용하는 알고리즘입니다. 말로 풀어 설명하는 것보다 직접 보는 게 더 이해가 쉬우실 겁니다. 대표적으로 팩토리얼과 피보나치 수열이 있습니다. 1. 팩토리얼 더보기 입력 n이 주어졌을 때 $n!$을 계산하는 함수를 $f_{actorial}(n)$이라고 합시다. $$\begin{align*}f_{actorial}(5)&=5\times f_{actorial}(4)\\&=5\times4\..

알고리즘의 성능과 효율성을 판단할 때 주로 시간 복잡도를 가장 중요하게 생각합니다. 이번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 단순화하여 표현하는 점근적 표기법(빅 오, 리틀 오, 빅 세타, 빅 오메가, 리틀 오메가)에 대해 알아보겠습니다. 자료구조, 알고리즘 시리즈 모아보기 시간 복잡도(Time Complexity) 알고리즘의 복잡성(효율성 혹은 성능)은 알고리즘 수행에 소모되는 자원의 양으로 판단됩니다. 여기서 자원은 소요 시간, 메모리, 통신대역 등이 될 수 있지만 가장 중요하게 생각되는 판단 기준은 소요 시간입니다. 메모리는 돈으로 어느 정도 해결 할 수 있지만 시간은 돈으로 살 수 없으니까요. 알고리즘의 시간 복잡도(소요 시간)는 입력 크기에 대한 함수로 표현할 수 있습니다. 아래 코..

프레임워크를 사용하거나 공부하다 보면 의존성 주입, 제어의 역전과 같은 말을 많이 접하게 됩니다. 대충 이런 뜻이겠거니 하며 짐작은 가지만 정확히 무엇을 말하는지 모르겠습니다. 이번 글에서는 의존성 주입이 무엇인지 왜 이런 개념들이 등장했고 왜 사용하는지 알아보겠습니다. 의존성 의존성 주입을 알아보기 전에 먼저 의존성에 대해 알아봅시다. 프로그래밍에서 `의존성(Dependency)`는 변경 혹은 에러로부터 영향을 받는다는 의미로 이해할 수 있습니다. 즉, "A가 B에 대한 의존성을 갖는다."라는 말은 A가 B의 변경 혹은 에러로부터 영향을 받는다는 의미로 받아들일 수 있습니다. 예시 1 - 의존성 아주 간단한 예시를 들어보겠습니다. 사람이 음료수를 먹는 예시입니다. 이 글은 아래 예시 코드를 고쳐가며 설..

이번 글에서는 싱글톤 패턴이 무엇인지와 장단점을 알아보고 자바로 싱글톤 패턴을 구현하는 방법들을 살펴봅니다. 싱글톤이란? 싱글톤 패턴(Singleton Pattern)은 클래스의 인스턴스가 오직 하나만 생성되도록 보장하는 패턴입니다. 여러 개의 인스턴스를 생성하지 않고 처음 생성된 하나의 인스턴스를 공유하여 사용하기 때문에 메모리를 절약하고 성능을 향상할 수 있습니다. 데이터베이스의 커넥션 풀, 스레드 풀, 로깅, 캐시등 I/O 바운드 작업과 프로그램 전역에서 공유되는 자원을 관리할 때 주로 사용됩니다. 장단점 장점 1. 인스턴스 생성 비용과 메모리 절약 싱글톤 패턴은 인스턴스를 중복으로 생성하지 않고 한번 생성된 인스턴스를 여러 모듈에서 공유하여 사용하기 때문에 인스턴스 생성 비용과 메모리를 절약할 수..

MySQL에서 localhost와 socket file! 데이터베이스 에러 프로그램을 만들 때 데이터베이스가 가장 말썽인 것 같다. 설계, 에러 등에서 시간을 많이 쓰게 된다. cloer chat프로젝트 중 잘 작동하다가 에러가 발생했다. Error: connect ECONNREFUSED ::1:3306 데이터베이스에 연결이 안되는 에러인데 간단한 실수부터 방법으로 발생하는 에러다. 단순 실수로 발생한 에러가 아니고 몰랐던 부분이어서 정리하려 한다. 내 경우 MySQL 공식문서에서 답을 찾았다. https://dev.mysql.com/doc/refman/8.0/en/can-not-connect-to-server.html MySQL에서 localhost localhost는 루프백 호스팅으로 본인의 컴퓨터..