Mate of Wind Mate of Wind

이번 겨울방학은 학교를 다니며 마지막 겨울방학이지만 딱히 특별한 감흥이 느껴지지는 않는다... 지난 학기 말에 랩실로부터 서버를 구축해 줄 수 있냐는 요청을 받고 학부연구생 신분으로 돈을 받으며 3달 동안 열심히 달려 이제야 결과물이 보이기 시작했다. 더불어 원래 방학게 공부하려 했던 자바도 많이 공부하고 이제 알고리즘 문제도 전부 자바로 풀 수 있는 정도까지는 온 것 같다. 사실 혼자 공부한 거보다 프로젝트를 진행하면서 에러 해결하느라고 찾아본 지식이 훨씬 방대한 것 같지만... 결과적으로 네트워크와 서버 통신에 대한 상당한 지식을 얻을 수 있었다. 이것도 시간 되면 정리해서 까먹지 말아야지. 2월이 지나갈수록 점점 데드라인은 다가오는데 뭔가 안된 게 엄청 많아 일이 갑자기 많아져 다른 공부고 뭐고 못..

이번 포스팅에서는 기수 정렬에 대해 알아보도록 하겠다. 기수 정렬은 시간복잡도가 가장 빠른 정렬방법으로 O(kn)의 시간복잡도를 가진다. 여기서 k는 정렬하고자 하는 숫자의 최대 자릿수이다. 만약 숫자의 범위가 999까지 라면 k=3인 것이다. 보통 시간복잡도를 쓸 때는 상수는 무시하는 것이 관례이다. n이 커질수록 상수가 의미가 없어지기 때문이다. 그런데 기수 정렬은 왜 상수를 표시해 놓았을까? 그것은 기수정렬에서는 자릿수가 가장 큰 변수 중 하나이기 때문이다. 만약 1~9까지의 수 10개와 1X10^99이라는 숫자가 하나 있다고 해 보자. 이 숫자들에 기수 정렬을 실시한다면 시간복잡도는 100이다. 저 큰 숫자만 없다면 시간복잡도는 1이다. 즉 자릿수에 따라 시간복잡도가 매우 유동적이므로 저렇게 표시..

이번 포스팅에서는 병합 정렬에 대해서 알아보겠다. 병합 정렬은 전체를 잘게 나누어 작은 조각끼리 먼저 정렬시키는 것을 반복해 결국 전체를 정렬하는 방법이다. 전문용어로는 분할 정복(Divide and Conquer)이라고 한다. 평균적인 시간복잡도는 O(nlogn)을 가진다. 문제를 풀 때 가끔 사용되고 특이하게도 지난번의 버블 정렬 문제인데 버블 정렬을 쓰면 안 되는 그 문제의 변형문제에 병합정렬이 사용된다. 이제 자세한 방법을 알아보자. 먼저 병합정렬을 하기 위해서는 전체를 가장 작은 단위로 나누어야 한다. 1개의 숫자만을 가지게 나누면 비교의 의미가 없어지니 2개씩 가지도록 나누자. 만약 홀수개라서 1개만 남으면 이번 단계에서는 그냥 놔두고 다음 단계에서 합치면 된다. 이제 2개씩 묶인 숫자들을 각..

이번 포스팅은 퀵 정렬의 변형 방법인 퀵 선택 정렬에 대해서 알아보도록 하겠다. 퀵 선택 정렬은 정렬한 수에서 K번째 숫자를 구할 때 유용하게 사용되는 정렬 알고리즘이다. 일반 정렬 방법으로 K번째 수를 찾으려면 모든 숫자를 정렬한 뒤에야 찾고자 하는 숫자를 찾을 수 있지만 퀵 선택 정렬을 이용하면 모든 숫자를 검색하지 않고 숫자를 찾을 수 있다. 퀵 정렬에서는 피벗을 설정하고 피벗 앞과 뒤를 나누어 정렬한다. 피벗의 앞쪽은 무조건 피벗보다 작고 뒤쪽은 피벗보다 크다. 만약 찾고자 하는 숫자 K의 인덱스가 피벗의 인덱스보다 크다면 피벗의 앞쪽을 정렬할 필요가 있을까? 이 생각을 이용한 것이 퀵 선택 정렬이다. 매번 피벗의 인덱스와 K의 인덱스를 비교해 K의 인덱스가 피벗의 인덱스보다 작다면 피벗의 앞쪽만..

지난번 포스팅에 이어서 SELECT구문을 좀 더 살펴보자. 지난번과 같은 테이블 예제를 이용하겠다. ORDER BY 구문은 출력을 정렬해 주는 기능이라고 생각하면 된다. SELECT id FROM qwer ORDER BY age(ASC생략가능); SELECT id FROM qwer ORDER BY age DESC; SELECT id FROM qwer ORDER BY age DESC, phone ASC; 출력 idid abchig defdef higabc 사용법은 WHERE구문처럼 사용하면 되며 기본값은 오름차순 정렬인 ASC이다. 생략이 가능하며 내림차순 정렬을 원할 경우 DESC을 쓰면 된다. 만약 순서가 동일한 경우 다른 기준을 적용하고 싶다면 뒤에 조건을 하나 더 붙여주면 된다. 지금은 테이블에 동..

SQL을 공부하면서 배운 것들을 간단하게 정리할 것이다. 엄청 깊게 공부하지는 않을 거지만 기본적인 것들은 한 번씩 보고 넘어가려고 한다. 이번 포스팅에서는 가장 기포적인 명령어 SELECT를 알아보자. SQL에서 SELECT구문은 데이터베이스에서 데이터를 추출하는 명령어이다. 데이터를 가져와서 보여주기만 할 뿐 변경하지는 않으므로 데이터가 손상되지 않는다. 기본적으로 SELECT ~ FROM ~ WHERE 구문을 같이 사용하여 원하는 데이터를 추출한다. 예시를 위해 엑셀로 테이블을 하나 만들었다. 데이터베이스의 테이블은 이것과 똑같이 생겼다고 보면 된다 가장 먼저 사용할 데이터베이스를 선택해줘야 한다. 이때 USE구문을 이용한다. 데이터베이스이름이 exercise라면 USE exercise; 이러면 해..

이번 포스팅에서는 퀵 정렬에 대해 자세히 알아보자. 퀵 정렬은 실제로 많이 사용하는 정렬 방법이다. 평균 시간복잡도는 O(nlogn)을 가지며 최악의 경우 O(n^2)을 가진다. 실제 알고리즘 문제에서도 자주 나오고 퀵 정렬 자체가 나오기보다는 변형된 정렬을 사용하는 문제가 나온다. 자바의 기본 내장함수도 정렬 방식으로는 퀵 정렬을 사용할 정도로 많이 사용되는 정렬 방법이다. 퀵 정렬 퀵 정렬은 숫자들 중에서 기준값을 하나 정해(이 값을 피벗(pivot)이라고 한다) 이 기준값을 이용해 나머지 수를 정렬한 후 이 행동을 반복하는 형태이다. 그림을 보자. 가장 먼저 피벗을 정해야 한다. 보통은 맨 앞, 맨 뒤를 피벗으로 정한다. 그 이유는 그게 코딩하기 가장 쉬우니까... 그리고 피벗으로 선택한 숫자를 제..

이번에는 삽입 정렬에 대해 알아보자. 삽입 정렬은 앞에서부터 하나씩 정렬해 가는 방법이다. 모든 숫자에 대해서 실행해야 하기 때문에 시간복잡도는 O(n^2)을 가진다. 느린 정렬방법이지만 구현이 쉽다는 장점이 있다. 단순 비교가 대부분이기 때문이다. 삽입 정렬 그림을 봐보자. 처음에는 맨 앞부분 2개만을 비교한다. 2와 7을 비교해 작은 수를 앞으로 놓는다. 그리고 다음 숫자를 보고 이전에 정렬이 완료된 부분 어디에 끼워 넣어야 하는지 보면 된다. 물론 컴퓨터는 하나씩 비교해 가며 새로운 숫자가 어디에 위치해야 하는지 찾는다. 1은 2와 7 둘보다 작기 때문에 맨 앞에 들어가야 한다. 따라서 하나씩 swap을 해서 원하는 위치로 보내던지 LinkedList라면 앞에 끼워 넣고 뒤의 인덱스를 하나씩 더해줄..