![]()
많은 프로그래밍 언어가 나머지 연산자를 제공합니다. 하지만 언어마다 결과가 다를 때가 있습니다. C언어, Java, Python, Javascript 네 가지 언어에 대해 나머지 연산자를 비교해 봅시다. 모듈러 위키 백과를 보면 `모듈러 산술(Modular Arithmetic)`를 다음과 같이 정의합니다. 💡 모듈러 산술 혹은 합동 산술은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 임의의 정수 $a, b$가 있을 때, 정수 $n$에 대해 $a=b+kn$을 만족시키는 정수 $k$가 존재한다면 $a$와 $b$는 같은 동치류에 속하고 $n$에 대해 합동이라고 합니다. 기호로는 다음과 같이 씁니다. $a\equiv b\space(\text{mod}\space n)$ $n=3$일 때 ..
![]()
스택과 비교해 보며 큐 자료 구조에 대해 알아봅시다. 이번 글에서는 java로 `양방향 큐(deque)`를 `이중 연결 리스트(doubly linked list)`로 구현합니다. 자료구조, 알고리즘 시리즈 모아보기 큐 `큐(queue)`는 이름 그대로 줄 서는 것과 같습니다.(줄 서 있는 것을 미국에서는 line이라고 하지만 영국에서는 queue라고 합니다.) 줄을 설 때를 생각해 보면 먼저 온 사람이 먼저 원하는 것을 얻습니다. 늦게 온 사람은 늦게 얻죠. 이런 구조를 `FIFO(First In First Out)`이라 합니다. - 연산 큐 또한 스택과 마찬가지로 `추상 자료 유형(Abstract Data Type)`으로 연산(행위)으로 정의됩니다. enqueue: 새로운 요소를 자료 구조에 추가 de..
![]()
스택 자료구조에 대해 알아보고 java로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 스택 `스택(stack)`은 이름 그대로 자료를 쌓아 놨다고 생각하는 `추상 자료 유형(Abstract Data Type)`입니다. 흔히 프링글스, 팬케이크로 예시를 듭니다. 가장 마지막에 프링글스 통에 넣은 프링글스 칩, 가장 마지막에 쌓은 팬케이크는 바로 먹을 수 있지만 가장 예전에 넣은(처음 넣은) 것은 꺼내기 힘듭니다. 스택은 위 예시와 같이 마지막에 넣은 것이 처음으로 나오는 `LIFO(Last In First Out)`구조로 최신 순으로 자료에 접근이 가능합니다. - 연산 스택은 추상 자료 유형으로 다음과 같은 연산(행위)으로 정의됩니다. 스택은 크게 push와 pop이라는 두 개의 연산으로 정의됩니다..
![]()
연결 리스트의 가장 기본이 되는 단일 연결 리스트로 연결 리스트를 이해해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 연결 리스트 `연결 리스트(linked list)`는 데이터와 다음 데이터의 위치를 함께 저장하여 데이터들을 체인처럼 연결하는 자료 구조입니다. 여기서 저장되는 자료의 단위(데이터와 다음 자료의 위치를 묶은 구조체)를 `노드(node)`라고 부릅니다. 다시 말하면 연결 리스트는 데이터와 다음 노드의 참조값을 갖는 노드들로 연결된 자료 구조입니다. 연결 리스트는 연결되는 방법에 따라 `단일 연결 리스트(singly linked list)`, `이중 연결 리스트(doubly linked list)`, `다중 연결 리스트(multi-linked list)`, `원형 연결 리스트(circular..
![]()
최악의 경우 $\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와..
![]()
이번 글에서는 잘 사용하면 복잡한 연산을 쉽고 빠르게 처리할 수 있는 비트 연산과 시프트 연산을 알아보고 Java로 실습해 보겠습니다. 비트 연산 `비트 연산(bitwise operation)`은 이진수에 대해 비트 단위로 적용되는 연산입니다. 비트 연산자에는 논리 연산에서 사용되는 논리합(OR), 논리곱(AND), 배타적 논리곱(XOR), 부정(NOT)이 있습니다. 많은 프로그래밍 언어에서 `비트 연산자`로 &(AND), |(OR), ^(XOR), ~(NOT)을 사용합니다. `비트 연산의 진리표`는 논리 연산의 진리표에서 True와 False를 1과 0으로 바꾸면 됩니다. 진리표는 아래와 같습니다. AND(&) OR(|) XOR(^) NOT(~) 1 & 1 1 1 | 1 1 1 ^ 1 0 ~1 0 1 ..
![]()
정렬 알고리즘에서 가장 기본이 되는 선택 정렬을 알아보고 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..
![]()
이번 글에서는 싱글톤 패턴이 무엇인지와 장단점을 알아보고 자바로 싱글톤 패턴을 구현하는 방법들을 살펴봅니다. 싱글톤이란? 싱글톤 패턴(Singleton Pattern)은 클래스의 인스턴스가 오직 하나만 생성되도록 보장하는 패턴입니다. 여러 개의 인스턴스를 생성하지 않고 처음 생성된 하나의 인스턴스를 공유하여 사용하기 때문에 메모리를 절약하고 성능을 향상할 수 있습니다. 데이터베이스의 커넥션 풀, 스레드 풀, 로깅, 캐시등 I/O 바운드 작업과 프로그램 전역에서 공유되는 자원을 관리할 때 주로 사용됩니다. 장단점 장점 1. 인스턴스 생성 비용과 메모리 절약 싱글톤 패턴은 인스턴스를 중복으로 생성하지 않고 한번 생성된 인스턴스를 여러 모듈에서 공유하여 사용하기 때문에 인스턴스 생성 비용과 메모리를 절약할 수..
