xeros RSS FEED

알고리즘 중에서도 정렬과 탐색은 가장 많이 쓰이는 알고리즘중 하나이다. 

이 포스팅에선 코드적으로 구현이 꽤 간편하면서도 햇갈리는 버블 정렬(Bubble Sort) 선택 정렬(Selection Sort)

삽입정렬(Insertion Sort)을 정리해 보려한다.

우선 버블정렬은 c언어 기본문법서도 다룰 만큼 기초적인 정렬 알고리즘이다.

(윤성우의 열혈 자료구조 그림 10-1)

위의 그림에서부터 알수 있듯이 버블정렬은 두 인접한 데이터를 비교해가면서 정렬을 진행하는 방식이다.

위의 작업은 오름차순으로 정렬을 하는 과정으로 정렬의 우선순위가 가장 낮은 큰 값이 맨 뒤로 이동한다.

위와 같이 두번째, 세번째, 네번째 값들도 차례 대로 정렬을 해준다. 

다음은 버블정렬의 구현이다.

void BubbleSort(int arr[], int n)

{

int i, j;

int tmp;

for(i=0; i<n-1; i++)

{

for(j=0; j<(n-i)-1; j++)

{

if(arr[j]>arr[j+1])

{

tmp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = tmp;

}

}

}

}

버블 정렬의 빅오는 O(n^2) 이다. 상당히 좋지 않은 알고리즘에 속한다고 볼수 있다.

그 다음은 선택 정렬이다.

(윤성우 열혈 자료구조 그림 10-5)

위의 그림을 해석해보자면 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그자리에 있던 데이터는 빈 자리에 가져다 놓는것이다. 딱히 덧붙힐 설명도 없으므로 아래 구현을 참고하길 바란다.

void SelSort(int arr[], int n)

{

int i, j;

int idx;

int tmp;

for(i=0; i<n-1; i++)

{

idx = i;

for(j=i+1; j<n; j++)

{

if(arr[j]<arr[idx])

idx = j;

}

tmp = arr[i];

arr[i] = arr[idx];

arr[idx] = tmp;

}

}

선택 정렬의 빅오는 O(n)으로 버블정렬보다는 성능이 좋지만 여러 경우들을 고려하면 사실 둘은 비슷비슷하다.

마지막으로 삽입 정렬이다.

(윤성우 열혈 자료구조 그림 10-8)

그림을 보면 이해가 쉽게 되리라 생각된다. 첫 번째부터 차레대로 데이터를 비교하며 데이터를 옮겨준다 

단지 코드를 구현해줄때는 정렬이 되야 되는 곳 이후에 있는 데이터들은 뒤로 옮겨 주는 작업도 해줘야 된다.

다음은 삽입 정렬 코드이다.

void InsertSort(int arr[], int n)

{

int i, j;

int data;

for(i=1; i<n; i++)

{

data = arr[i];

for(j=i-1; j>=0; j--)

{

if(arr[j]>data)

arr[j+1] = arr[j];

else

break;

}

arr[j+1] = data;

}

}

빅오는 O(n^2)이므로 버블정렬과 같다. 좋은 알고리즘이라고 볼수는 없겠다.

자바스크립트 내장 함수중에 특정한 시간에 특정한 함수를 실행할 수 있게 해주는 타이머 함수가 있다.

setTimeout() 함수는 한 번만 실행하므로 주의할 사항이 없지만 setInterval() 함수는 지속적으로 실행하므로

지속적으로 컴퓨터의 자원을 소비할 위험이 있기 때문에 주의해야 한다.

// 공백+대문자 기능 없음

#include <stdio.h>

#include <string.h>

void findplace(char encrypt[], char plane[], int place[], int len)

{

int i, j;

for(i=0; i<len; i++)

{

for(j=0; j<53; j++)

{

if(encrypt[i] == plane[j])

{

place[i] = j;

}

}

}

}

int main(void)

{

int k;

char key[27];

char encrypt[80];

char plane[53] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

int place[80];

int len;

scanf("%s", key);

scanf("%s", encrypt);

len = strlen(encrypt);

findplace(encrypt, plane, place, len);

for(k=0; k<len; k++)

{

printf("%c", key[place[k]]);

}

return 0;

}

최근에 여러모로 바빠서 블로그 포스팅을 많이 못했는데..

시간을 내서 최근 있었던 일과 앞으로의 계획등을 정리해 보려 합니다.

1. 디미고 과제

디미고를 합격하고 약 2주동안은 보안공부를 거의 못했는데 과제량이 정말 많네요 ㅡ.ㅡ

12/30일 방학이 시작되고 나서 과제 때문에 보안공부를 못할 일은 없어졌지만 여전히 과제가 많은건 어쩔수 

없었읍니다.

2. 3박4일 서울

12월 27일날은 팀원들끼리 소소하게 모여서 세미나도 참석하고 SUA단체에서 뒷풀이도 갔었읍니다. 사실 세미나 자체는 그닥 재밌진 않았지만 뒷풀이는 재밌었던거 같네요. 

가려졌지만 하얀색 무늬가 있는 니트를 입고 있는게 나고 준오, 현종이형, 오현이형, 서울여대 분들 2명, 성우형, 문기님, 도원이형, 그리고 한분은 이름이..ㅠㅠ 이렇게 앉아서 얘기도 나누면서 저녁식사를 함께 했읍니다. 

세미나 뒷풀이가 끝나고 한아전으로가 새벽 4시에 시작하는 30c3 ctf를 풀기로 하였는데.. 

너무 어려워서 대회는 접어두고 그냥 잠을 잤읍니다.. 

다음날 팀원들이랑 점심식사를 하고 도원이형, 바현이형, 오현이형 나 이렇게 4이서 서코 구경을 갔습니다.

팀원들끼리 단체사진( 바현이형이 찍어주셧고 진혁이형은 찍기 싫다고 안찍으셧다는 ㅠㅠ)

서코는 항상 가보고 싶다고 생각은 했었는데 직접 가보니 그 경이로움은 말로 표현할 수가 없었읍니다.

실제로 팀형중 한명은 충격때문에 서코 구경내내 말을 못하셨다는..

잔나 코스프레

무슨 코스프레인진 모르겠지만 한컷

이 정도 일줄은 몰랐는데.. 사람 정말 많더군요.. 형들에 의하면 이번에는 엄청 조금 온거라고..ㄷㄷ

이런 경험들을 하고 다시 도원이형 성우형과 함께 성우형집으로 가서 밤을 보내고 다음날 버스를 타고 집으로 돌아왔습니다.

3. 향후 계획

이렇게 여러 경험들도 했고 다시 공부에 매진을 해야되는데 앞으로의 계획들을 나열해 보자면..

1) 여러 알고리즘 공부해보기 (Machine learning, MIC, Viterbi, Baum-Welch ..)

2) 리버싱공부 

3) 안드로이드 개발 프로젝트 (3개월)

4) ARM커널 소스 분석, Nexuiz 분석

5) 디미고 과제

크게 봤을때 이정도 되는거 같네요.

이번방학은 정말 후회없이 보내야 겠다고 매일 생각은 하고 있는데 정말 그랬으면 좋겟읍니다.

어찌됐든 요즘은 그렇게 큰 걱정거리도 없고 좋은듯 하네요ㅎ