데이터구조와 알고리즘 1回_동적배열

データ構造とアルゴリズム

알고리즘은 교환학생가면 꼭 듣고싶었던 과목이었다. 

교환학생 자소서에서도 야심차게 썼었는데 진짜 들을 수 있을지 사실 잘 몰랐었는데ㅋㅋㅋㅋ

 나사가키 대학에서 마침 2학기에 과목이 개설되어있어서 들을 수 있었고

제일 잘하고 싶고 중요한 과목이기 때문에 블로그에 매회 공부했던 내용을 기록하기로 했다.

오래걸릴 수는 있지만 일본어도 함께 공부하기위해 일본어로도 작성하기로 했다.

오늘 까지 총 두번의 수업을 들었는데 일본에서 강의를 들으면서 느꼈던 점!

일단, 교수님이 젊다. 교수님이 젊다기 보다는 교수님들이 수업을 많이 하지는 않고 부교수라는

교수님 밑에서 연구하시는 분들이 계신데 그 분들도 수업을 꽤 많이 하시는 것 같았다. 

그리고 진짜 자세하게 천천히 설명해 주신다. 나는 유학생인데도 불구하고 한국에서 배웠을 때보다 이해가 잘될정도로

자세하게 알아들을 때까지 계속 똑같은말을 반복하시면서 설명하신다.

수업시간이 길긴 길다. 수업할 내용이 끝나더라도 시간이 다 될때까지 똑같은 내용을 또 반복하신다....ㅋㅋ

그리고 개인적으로 가장 좋았던 것이 교수님이 설명하시는 파워포인트 자료나 컴퓨터 화면이 내 앞에있는 개인컴퓨터에도 뜬다. 

그래서 멀리있는 사람도 안보여서 수업을 못들을 수 없도록,

이건 한국에도 다른대학교는 이렇게 할 수도 있지만 우리학교는 아니어서 이부분이 너무 좋았다.

단점은, 그래서 학생들이 최대한 뒤에서 수업을 들을려고 한다는 점..ㅋㅋㅋㅋ   

그리고 나가사키대학에서는 모든 수업을 리눅스로 진행한다. 무조건 리눅스로 해야한다.

리눅스는 동아리활동하면서 써봤지만 그래도 거의 무지랭이다.. 그래서 나도 첨부터 배운다 생각하고 공부했다.

좋은 경험인것 같다. 한국에서는 리눅스 잘 안쓰는데 여기서 같이 배우니까 좋았다><

1回 동적배열

＃알고리즘과 계산량_アルゴリズムと計算量

‡알고리즘이란?_アルゴリズムとは?

주어진 문제의 정확한 답을 구하기위한 '효율적인 방법'

-같은 문제를 해결해도 방법은 여러가지가 있다. 

-계산기에서 수행할 수 있는 방법만을 생각한다. 즉, 프로그래밍으로 쓸수 있는 것.

 「与えられた問題の正しい答えを求める ための“うまいやり方”」

–同じ問題を解くにも手順が複数ありうる。

–計算機で実行できる手順だけを考える。つまり, プログラムとして書けるものだけ。 

‡알고리즘의 예_アルゴリズムの例

CD가게에서 아르바이트를 하고있다.

서양음악CD가 100장이 들어왔다.

아티스트의 ABC순으로 선반에 넣고 싶다.

어떻게하면 빨리 일이 끝날까?

CD屋でバイトをしている。

洋楽のCDが100枚入荷した。

アーティスト名のABC順で棚に並べたい。

どうすれば早く仕事が終わる？

‡정렬_ソート

데이터의 집합을 일정한 규칙에따라 나열하기 위한 알고리즘.

-일정한 규칙의 숫자라면 값의 크고작은 순서, 문자열 알파벳순서 등.

-가까운 곳에서 정렬을 찾아보자.

データの集合を一定の規則に従って並 べかえるためのアルゴリズム 

– 一定の規則とは、数値なら値の大小の順、文字 列ならアルファベット順、など。 

– 身近なところでソートを探してみよう。

‡좋은 알고리즘이란?_良いアルゴリズムとは？

효율적인 알고리즘

-시간이 걸리지 않는다. (CD의 예: CD를 이동시키는 횟수)

-메모리가 들지않는다. (CD의 예: 필요한 작업 공간)

효율성이 좋은것을 어떻게 측정할까? 

効率が良いアルゴリズム 

– 時間がかからない （CDの例：CDを移動させる回数）

– メモリを喰わない （CDの例：必要な作業スペース）

 効率の良さをどうやって測る？

‡계산량_計算量

시간계산량 (이 수업에서는 이부분을 생각한다)

-문제를 푸는 데 걸리는 단계 수. 사칙연산과 메모리엑세스 등의 횟수

공간계산량 (이 수업에서는 중요하게 다루지는 않는다.)

-메모리에 보관해야하는 데이터의 개수

時間計算量 （この授業ではこちらを考える） 

– 問題を解くのに要するステップ数 • 四則演算やメモリへのアクセスなどの回数 

空間計算量 （この授業ではこれが重要になるほど大きな問題は扱わない） 

– 問題を解くのに要する記憶容量

‡big_oh표기법_オーダ記法

𝑂(𝑓(𝑛))라고 쓴다.

𝑛은 데이터 수. 𝑓(𝑛)은 𝑛의 함수. 

예1) 𝑂(𝑛)일때, 단계수가 데이터 수에 비례

예2) 𝑂(𝑛²)일때, 단계수가 데이터수의 제곱에 비례

𝑂(𝑓(𝑛))という書き方をする。

𝑛はデータ数。𝑓(𝑛)は𝑛の関数。 

– 例1） 「時間計算量が𝑂(𝑛)」 ステップ数がデータ数 𝑛に比例 

– 例2） 「時間計算量が𝑂(𝑛²)」 ステップ数がデータ数の2乗に比例。

‡검색의 계산량_探索の計算量

n장의 CD에서 아티스트의 ABC순으로 제일 처음 것을 찾는 계산량

-무작위로 나열되어 있다면 : 𝑂(𝑛)

-ABC순으로 나열되어 있다면 : 𝑂(1)

-완전히 ABC순으로 나열되어 있지 않더라도 궁리를 하면 : 𝑂(log 𝑛)

𝑛枚のCDから、アーティスト名のABC順で一番最初 のものを見つける計算量

– バラバラに並んでいるなら：𝑂(𝑛)

– ABC順に並べてあるなら：𝑂(1)

– 完全にABC順に並べなくても工夫をすれば: 𝑂(log 𝑛)

‡정렬의 계산량_ソートの計算量

n장의 CD를 ABC순으로 정렬

•간단한 방법 

-ABC순서에서 첫 번째 CD를 찾아 왼쪽으로 가지고 온다.

-나머지에서 ABC순서에서 첫 번째 CD를 왼쪽으로 가지고 온다.

-다음 나머지가 1장이 될 때까지 반복한다.

이방법의 계산량은? _퀴즈

𝑛𝑛枚のCDをアーティスト名のABC順でソート 

•単純な方法 

-ABC順で最初のCDを探し、一番左にもってくる 

-残りからABC順で最初のCDを探し、一番左にもってくる 

-以下、残りが1枚になるまで繰り返し 

この方法の計算量は？ _小テスト

#데이터 구조_データ構造

‡데이터 구조란? _データ構造とは

데이터의 모임을 컴퓨터에서 효과적으로 다루기 위해 일정한 형식으로 체계적으로 정리할때의 형식이다.

「データの集まりを コンピュータの中で効果的に扱うため、 一定の形式に系統立てて格納するときの 形式のことである。」

‡테이터 구조의 예_データ構造の例

배열, 리스트, 2중트리

配列, リスト, ２分木

‡좋은 데이터구조란?_良いデータ構造とは？

좋은알고리즘을 가지고 있으면 좋은 데이터구조이다.

-좋은 데이터 구조를 사용하면 동일한 문제가 보다 효율적으로 풀린다.

良いアルゴリズムをもたらすデータ構造 

– 良いデータ構造を使うと、同じ問題がより効率よく 解けたりする。

‡포인터_ポインタ

기본적인 내용은 알고 있지만 포인터는 많이 헷갈리기 때문에 수업시간에 봤던 간단한 코드만 확인.

 실행결과_  

‡메모리 할당_メモリの割り当て

포인터는 메모리에서 자신이 사용하고 있는 위치를 가리키지 않으면 안된다.

-이미 선언한 변수의 주소는 괜찮다. (선언되었기때문에 사용해도 좋은 장소이기 때문)

-그렇지 않으면 메모리를 명시적으로 할당한다. ("이 크기만큼 메모리를 사용하세요"라고 명시적인 코드를 써야한다)

ポインタは、メモリ上で自分が使って構わない 場所を指していないといけない 。

– すでに宣言した変数のアドレスは、大丈夫 。(宣言済みのため、使っていい場所だから) 

– そうでなければ、メモリを明示的に割り当てる (「このサイズ分だけメモリを使わせてください」と明示的 にコードに書く必要がある)

#동적배열_動的配列

배열의 크기를 변경하고싶을 때 쓴다.

-포인터로 선언

-malloc()으로 메모리 할당

-realloc()으로 크기 변경

                                                                  int *a; 

                                                                  a = (int *) malloc(sizeof(int) * 100); 

                                                                  a = (int *) realloc(a, sizeof(int) * 200);

配列のサイズを変更したい場合に使う

 – ポインタとして宣言 

– malloc()でメモリを割り当てる 

– realloc()でサイズを変更する

‡‡‡第1回課題‡‡‡

사용자가 double형의 데이터를 차례로 입력.

그 데이터를 배열에 저장.

0이 입력되면 데이터 입력 종료.

(전부 몇개가 입력될지 모르게하고 반드시 동적배열을 사용)

배열에 저장된 값에 대해 다음을 요구(최대값, 최소값, 평균, 표준편차)

malloc_.c

처음엔 그냥 처음이라서 당황스러웠다. 문제가 일본어로 되있으니까 이걸 어떻게 해석해야될지부터 생각이 안나서 머리가 새하얘졌다.

처음에는 그냥 동적배열만들어서 입력받을 때마다 계속 크기를 늘리면서 받는거까지만 하는 줄 알고 제출했는데

교수님이 내과제를 보고 당황하시더니ㅋㅋㅋㅋ밑에 최대값, 최소값어쩌고 더 해야된다고 하셨다.

그제서야 문제를 사진찍어서 번역을 해야지 생각하고 번역하니까 그제서야 이해하고 다시했다ㅠㅠ 언어의 장벽

표준편차를 계산할때 math.h 를 추가해서 sqrt를 써야되는데 그걸 쓰니까 실행이안됬다. 

오류가 생각이안나....ㅜㅜㅜ나중에 학교실습실 가서 다시 해보고 기록해야겠다.

암튼 안되서 막 구글링했는데 다 일본어....답답....학생들도 이제 다 빠지고 나 혼자 남아서ㅜㅜ 계속 찾았다.

아, 그리고 이 학교 좋은점이 컴퓨터 실습실이 24시간이다. 밤새도록 거기서 과제할 수 있는 특권ㅎ 변명도 못한다.

계속계속 찾다가 컴파일을 다르게 하는 어떤글을 봤다.

이때까지는 gcc -o malloc malloc.c  이런식으로 컴파일하고 ./malloc 으로 실행했었는데

거기서는 gcc malloc.c -lm 으로하고  ./a.out 으로 실행하길래 따라 해봤더니 됬다!

./a.out은 교수님이 gcc 파일명.c 로 컴파일할때 실행하는 걸 봐서 알아서 다행히 글을 보고 일본어 몰라도 바로 이해할 수 있었다ㅜㅠ

진짜 리눅스 아얘모르니까 수업을 잘 들어야겠다ㅜㅜ

-lm에 대해서 모르겠어서 검색했는데 난 똥손인가...못찾겠어서 동아리선배한테 물어봤다ㅎㅎ바로나옴...어이가 없네...

참고→http://temp123.tistory.com/33

동일한 gcc 컴파일 명령어 뒤에 -lm을 추가함으로써 해결할 수 있다. 

gcc 컴파일러는 디폴트로 mathematical 라이브러리를 링크할 당시 포함시키지 않는다고 한다. 

따라서 -lm 명령어를 통해 추가해줘야 한다.

라고한다ㅎㅎ 추가적인 설명으로 리눅스 gcc컴파일 옵션.

참고→http://jangpd007.tistory.com/220

여기서 [as 옵션] 에서 보면 

3) -l[패스] 옵션: include 디렉토리를 지정한다. 어셈블리 소스 내에서 사용된 inlcude 지정자가 지정하는 헤더파일을 찾고자할 때 사용한다.

라고 해서 -lm에서 l은 헤더파일을 찾는 옵션이고 m은 mathematical을 의미하는 것이다.

즉, math.h 헤더파일을 불러온다는 말이다.

교훈 : 구글링실력을 키우자