Mate of Wind Mate of Wind

데이터베이스(Database): 간단하게는 '데이터의 집합'이라고 할 수 있다. 오라클에서는 데이터베이스를 '구조화된 정보 또는 데이터의 조직화된 모음'이라고 정의하고 있다. 핵심은 데이터가 있는 그대로가 아니라 가공되어서 저장된다는 것이다. DBMS(Database Management System): 한국어로는 데이터베이스 관리 시스템이다. 데이터베이스를 관리하고 운영하기 위한 소프트웨어이다. SQL을 이용해 데이터베이스에 접근하는 것도 DBMS를 통해 이루어진다. 여러 종류의 DBMS가 있는데 유명한 것으로는 오픈소스인 MySQL, PostgreSQL 등이 있고 상용으로는 Oracle, SQL Server등이 있다. DBMS는 5가지의 유형으로 분류할 수 있다. 계층형, 망형, 관계형, 객체지향형, ..

선택 정렬은 버블 정렬과 비슷하지만 약간 다른 정렬 방법이다. 버블 정렬과 마찬가지로 O(n^2)의 시간복잡도를 가지며 실제로 사용하는 일은 별로 없다. 하지만 이전 포스팅에서도 말했듯이 원리를 이해해야만 해결할 수 있는 문제가 나올 수 있으니 반드시 알아두어야 한다. 선택 정렬 선택 정렬은 정렬되지 않은 곳을 전부 조사하여 가장 작은 값을 찾은 후, 정렬되지 않은 곳의 맨 앞과 swap 하는 방법이다. 그림을 보자. 버블 정렬과 같은 예제이다. 다만 이번에는 먼저 배열 전체를 검사한 후, 가장 작은 값을 체크하였다. 그리고 정렬되지 않은 곳의 맨 앞과 swap 해주면 맨 앞에서부터 정렬이 이루어지는 모양이 된다. 첫 번째에서 1이 가장 작은 값이므로 원래 1의 index인 2와 맨 앞의 index인 0..

이번 포스팅에서는 O(n^2)의 시간복잡도를 가지는 버블 정렬을 알아보겠다. 버블 정렬은 그 자체로는 많이 사용되지 않지만 중간 과정을 묻는 문제가 존재한다. 다만 이때는 버블정렬을 사용해 풀면 시간초과가 나기 때문에(...) 다른 방법을 생각해야 한다. 뒤에서 살펴보겠다. 설명에 앞서 숫자는 배열에 저장되어 있다고 생각하겠다. 버블 정렬 버블 정렬은 배열 전체를 하나씩 살펴보며 현재 숫자와 다음 숫자를 비교해 가는 방법이다. 왼쪽부터 오른쪽으로 정렬이 진행되는 과정을 나타낸 것이다. 먼저 맨 아래부터 그 위의 숫자와 비교해 아래 숫자가 작으면 서로 바꾸어(swap) 작은 숫자를 위로 올라오게 한다. 첫 번째의 아래에서 2, 3번째인 3과 8이 두 번째 정렬에서는 자리가 바뀌어있는 것을 볼 수 있다. 이..

정렬은 주어진 숫자들을 오름차순이나 내림차순으로 재배열하는 것을 뜻한다. 알고리즘 문제를 풀다 보면 특정 정렬을 구현하는 문제도 매우 많은 편이고 실제로도 중요하다. 정렬방법은 크게 버블, 선택, 삽입, 퀵, 병합, 기수 정렬 이렇게 6가지로 분류할 수 있다. 물론 큰 개념만 그런 것이고 세부적으로는 다양한 변형들이 존재하고 문제를 풀 때에도 보통 변형해서 사용해야만 풀리는 경우가 많다. 그러면 어떤 정렬방법을 사용하는 것은 어떻게 결정하는가? 각 방법들은 일반적 성능, 점유 메모리, 특정 상황에서의 성능에 따라 알맞게 써야 한다. 성능은 정렬을 시행하는 데 걸리는 시간을 말하며 빅 오 표기법으로 표현한다. 일반적인 성능(평균 성능)은 랜덤한 숫자를 정렬할 때 모든 수를 정렬하는데 걸리는 시간을 말한다...

자바를 공부하기 시작하면 가장 먼저 보는 것이 자료형에 관한 것일 것이다. 자바는 많은 부분이 C언어와 유사하기 때문에 자료형도 많은 부분이 비슷하다. 자바는 기본적으로 8개의 자료형을 제공한다. 정수형 3개, 실수형 2개, 불리안 1개이다. 정수 타입 정수형은 byte, char, short, int, long 이렇게 5가지이다. 그런데 중간에 문자를 뜻하는 char가 껴있다. 처음에 이걸 보고 다소 이상하게 생각했지만 공부를 해 보니 왜 그런지 알 수 있었다. byte는 말 그대로 크기가 1바이트=8비트인 자료형이다. 자주 사용하지는 않지만 나는 아스키 코드를 다룰 때 강제 타입변환으로 사용한 기억이 있다. char을 제외한 숫자를 나타내는 자료형은 모두 signed(부호가 있는)이기 때문에 가장 앞..

스택(Stack)은 데이터 구조의 한 종류로 나중에 입력된 것이 먼저 출력된다(Last in First out => LIFO)는 특징을 가진 데이터 구조이다. 쉽게 생각하면 책을 위로 쌓다가 읽고 싶은 책이 아래에 있다면 위의 책들을 차례대로 치우고 원하는 책을 읽을 수 있는 것과 비슷하다. 책을 하나씩 쌓는(데이터를 입력하는) 행위를 push라고 하며 책을 하나씩 제거하는(데이터를 출력하는) 행위를 pop이라고 한다. 스택에 저장된 데이터를 읽을 때에는 맨 상단 스택의 데이터만 읽을 수 있기 때문에 상단의 스택이 중요하다. 이번에 만들어 볼 스택에서는 문자열을 입력받도록 하고 push, pop기능에 더해서 스택을 비우거나 완전히 삭제하는 기능을 만들어 보려고 한다. C언어에서 스택을 만드는 방법은 크게..