안녕~ 1년만에 다시 글 쓰는듯 하다...

작년에는 쓰다가 흐름이 끊어벼 버렸음..

다시 쓰게되는 이유는.. 이번년도에 저 과목을 들었고! 무엇보다 1주간은 할일이 없을듯 하기때문에 다시 쓰려고 해 ㅋㅋ

1. 소개

자료구조라는 말은 전산학을 전공 하는 게이나, 정보처리기사 또는 기능사 시험을 본 게이들은 익숙할거야

하지만 이제 막 처음 프로그래밍에 접했거나, 전산학과 거리가 멀거나, 컴맹들은 처음 듣는 용어 일거야..

자료구조는 영어로는 Data structure, 말그대로야..

보통 자료구조와 알고리즘은 같이 따라다니는데, 여기서는 자료구조만 할거임...

(알고리즘이 뭔지 모르는 게이를 위해서, 알고리즘은 어떠한 문제를 해결하기 위한 과정을 적어놓은 지침서라고 표현 할수 있음.)

자료구조 이 말을 풀어 쓰게 되면, 자료를 저장하고, 불러 오기 위한 데이터 집합의 모양 이라고 볼수 있어.

말만 들어서는 어렵지만, 전산학을 전공 하지 않아도 인류는 활자가 발명함에 따라 알게 모르게 자료구조를 사용하고 있지..

자 우리가 이제 공장 물류 창고를 운영한다고 생각을 해보자고?

공장에서 막 물건들이 생산되고 있어서, 물류 창고를 운영중인 우리는 그 물건들을 물류 창고에 집어 넣었어.

근데 창고에 물건을 집어 넣을때 물건을 창고에서 빠르게 찾기위해, 어떠한 규칙에 따라서 물건을 집어 넣겠지?

물건의 일련 번호 순서로 보관 한다던지, 물건의 품목에 따라 보관 한다던지 어떠한 규칙이 있겠지.

이 규칙에 따라 물건이 보관된 모양을 보고 자료구조라고 표현 할수 있겠어.

자 그럼 이제 컴퓨터 세계로 가보자, 우선 자기가 쓰는 컴퓨터의 하드디스크나 램용량을 확인해보자.

나는 24기가 램에, 640기가 하드디스크를 사용하고 있네.. (은근 슬쩍 자랑.. ㅎ)

보통 게이들은 4기가나 8기가의 메모리를 사용중이겠지..?

또한 저 하드디스크나 메모리에 어떠한 자료들이 저장 되어 있겠지. 그러니깐 사용한다고 나오니깐..

이제 이걸 실제 세계와 매칭을 시켜 보면

창고 = RAM, 하드디스크

물건을 저장하는 규칙 = 프로그램, 알고리즘

물건 = 데이터

이렇게 볼수 있지..?

"엥? 그럼 저거 배울 필요도 없는거 아니냐..?"라는 의문이 들거야...

나도 그런 의문이 들었지.. 하지만 컴퓨터라는 물건을 생각해보자.

사람은 아주 뛰어난 프로세서와 운영체제를 가지고 있어서 스스로 학습을 할수가 있다.

하지만 컴퓨터는 그런 능력이 없음 ㅠ..

컴퓨터는 졸라 멍청한 새끼인거임 ㅠㅠ 이걸 컴퓨터 아키텍쳐까지 배우면 "아.. 똥 멍청이 새끼를 200만원이나 주고 산거구나.."

이생각까지 들정도...

그래서 우리는 컴퓨터에게 우리가 알고있는 자료구조를 컴퓨터에게 정의를 내리고, 설계를 해줘야해..

또 자료구조가 중요한 이유는 자료구조를 잘 선택함으로 같은 사양의 컴퓨터일지라도 더 빠르게 프로그램을 만들수가 있어.

그래서 막 어떤게임은 사양이 낮아도 잘되는데, 어떤 게임은 사양이높아도 느리지.(이걸 자료구조 탓이라고 해야되나, 알고리즘 탓으로 해야되나... -_-)

(그리고 소위 말하는 발적화 여부가 여기서 결정이됨!)

하지만 모든 자료구조의 알고리즘은 마치 빛의 속도에 가까울순 있어도 빛보다 빠를순 없는것처럼, 어떤 알고리즘이라도, 일정 속도 이상으로 더이상 빨라지지 않는다.

지금 까지 개발된 자료구조들은 각각의 장단점이 있어서 프로그램을 설계할떄 잘 선택을 해야되.

어떤 자료구조 알고리즘은 속도가 빠른데, 메모리는 쳐묵쳐묵 하는경우가 있고, 어떤 알고리즘은 메모리를 조금 먹는데, 속도가 헬급으로 느린 경우가 있지..

2. 성능의 측정 기준

이 부분은 무려 거의 1년전에 배운 내용이라 틀릴수도 있으니 양해 바람 ㅋㅋ

알고리즘의 성능은 두가지로 분류되

컴파일때 걸리는 시간과 실행할때 걸리는 시간.

(컴파일 = 내가 컴퓨터에 지시를 내리기 위해, 지침서를 작성했는데, 이제 이걸 컴퓨터에게 알아 듣게 번역 해주는놈)

이둘을 더해서 성능을 측정하는데, 솔직히 컴파일 시간은 프로그래머한테나 체감되는 시간이라 무시 해도되

왜냐하면 컴파일은 한번만 하면, 그다음부터는 코드가 수정되지 않는한 컴파일 할필요가 없거든!

그래서 주로 성능이 좋다고 말하는건, "exe를 실행하는데 얼마나 빨리 처리 되느냐" 이거지...

한가지더! 위에서 말했다 시피 자료구조나 알고리즘의 선택에 따라 성능이 차이가 난다고 했지?

그럼 그 성능을 지표로 표시 할 필요성이 생기지.

보통 대부분 전산학에서 사용하는 자료구조들은 60-70-80년대에 개발된 알고리즘들이라

그당시 컴퓨터에서는 매우 느려서 얼마나 빠른지 느릴지 체감이 될거야..

하지만 요즘은 좀 다른 상황이지..

전산학이나 컴퓨터 공학과 전공인 게이들은 교수들이 구현과제를 낼때, 한번씩은 정렬 알고리즘을 사용할텐데

지금 까지 알려진 정렬 알고리즘중 가장 느린 정렬 알고리즘을 사용해도 느리다는 느낌이 안들정도로 빠른 컴퓨터를 사용하고 있지.

(그래도 알고리즘 자체를 수행하는데 걸리는 시간은 그 알고리즘을 사용하는 모든 기능의 성능에 영향을 주지...)

그래서 시간으로 표시하기에는 절대적이지가 않아.

그래서 알고리즘의 성능은 과정 하나를 거치는데 1초라는 시간이 걸린다고 가정을 하고, 총 몇번의 과정을 거쳤는가로 성능을 표시하지

마치 내가 학교에서 집으로 가는데, 걷는 속도는 그날그날 컨디션에 다르지만,

내가 집으로 갈때, PC방과 편의점을 거친다면 총 학교와 집을 포함에서 4번의 과정이 걸리지만, 내가 바로 집까지 간다하면 2번의 과정이 걸리는것 같은거야.

보통 성능을 나타낼때 Big-O표기법을 사용해. (Big-O가 평균이였던가..? 무튼 최소 최대 평균중 하나임.. ㅇㅇ)

Big-O 표기법은 O(1), O(N), O(logN), O(N^2)등등이런식으로 표기되..

O(1) = 데이터의 크기가 무엇이든간에 1초가 걸린다.

O(N) = N개의 데이터에 한에서, 걸리는 속도는 N에 비례한다.

O(logN) = N개의 데이터에 한에서, 걸리는 속도는 logN에 비례한다.(컴퓨터에서 밑이 없는 log는 밑이 2인 log로 가정함)

O(N^2) = N개의 데이터에 한에서, 걸리는 속도는 N제곱에 비례한다.

또한 어떠한 알고리즘을 step(과정)의 갯수를 세다보면 N(데이터수)에 대한 다차식이 나오게 되는데

그때 Big-O 표기법으로 나타내려면 다차식중 차수가 가장 높은 항만 넣으면됨.

솔직히 가장 큰 차수를 가진놈이 영향력이 크니깐 나머지는 무시! 하는거임.

자 예를 들어 보자, 버블 정렬을 하고 변수에 대입을 하는 코드를 작성해서 평가 해보자.

0 숫자들 집합 A{}, 변수 F = 0

1 변수 X는 0부터 N까지 반복됨 (X = 0, 1, ..,N-1, N), 그리고 아래의 과정을 수행.

2    변수 Y는 0부터 N까지 반복됨(Y = 0, 1, ..., N-1, N), 그리고 아래의 과정을 수행.

3       A의 X번째원소가 A의 Y번째원소보다 크면, X번째와 Y번째와 자리 교체

4    Y끝

5 X끝

6 F에 1 대입.

뭐 어렵지만, 정렬 알고리즘중 bogo-sort같은 ㅄ같은 알고리즘을 제외 하고 제일 쉬운 알고리즘이다.

그리고 실제로 어떻게 구현되는지는 아직은 몰라도 되니깐..

1번째 라인을 보자! 뭔지는 모르겠는데, X가 0부터 N번까지 반복을 한다.

2번째 라인을 보자. X가 한번 반복 할때 마다 Y는 0부터 N번까지 반복을 한다.

 X가 하나 증가 하는 과정을 거치게 될때 마다, Y는 0부터 N번까지 반복하는 과정을 거치게됨.

6번 라인을 보자 F에 1을 대입한다. 여기서 1번의 과정이 거치게됨.

그럼 전체적으로 N번의 과정 * N번의 과정에 대입을 하게 되는 1개의 과정을 거치게 되겠지?

이걸 식으로 나타내게 되면, f(n) = N^2 + 1이라는 식이 나오게되.

이걸 빅O표기법으로 나타내면 O(N^2)으로 나타낼수 있고!

빅오 표기법에 대해서 자세한건 https://mirror.enha.kr/wiki/Big-O

(일부러 엔하로 가져옴.. 너희들의 시간을 가져가겠어!)

하.. 원랜 자료구조의 종류중 하나까지 할라 그랬는데 시간이 없는관계로.. ㅂㅂ