ㅇㅇ

우분투, 파이썬, 텐서플로우, 넘파이, 도커, 통계, 컴퓨터구조 등 회사일을 하면서 얻은 모든 지식을 여기다가 정리한다.

Ubuntu 명령어 모음

:

du -sh * # 현재 폴더 용량 확인

FDISK

:

mount

:

달린 device list보는 법

parted -l

fdisk -l

mkdir /home/id/data

mount /dev/sdc1 /home/id/data

즉 폴더만들고 parted -l로 새로 단 장비의 device 이름(sda,sda,sdc)를 보고 그 내부에 partition번호(1,2,3,...)을 보고 해당 partition을 지정한 폴더(/home/id/data)에 mount시킨다. 

Vim 명령어 모음

정규표현식 모음

Discard Data or Fix Data

Feature Engineering은 다음으로 구성되어 있다.

feature selection, feature extraction, feature scaling, create new feature

No Free Lunch Theorem In Machine Learning

:데이터에 대한 어떠한 가설도 없다면, 어떤 모델을 다른 모델보다 더 좋아할 이유가 없다. 따라서 데이터에 대한 도메인 지식이 반드시 필요하다는 것.

Dropout시

tf.placeholder_with_default쓰기(값 안넘기면 default값(1로 두고)을 사용함으로써 test할 때랑 train할 떄 구분 지어줌)

SVM(Support Vector Machine)

:데이터를 뿌려놓고 확률을 생각하지 않고 decision boundary를 구하는 방법

decision boundary를 margin(decision boundary과 가장 가까운 점(a training instance)과의 거리)이 크게 찾고 싶은 것

decision boundary를 support하는 vector를 찾는 것이 목표(결국 너비가 가장 큰 road에 걸려져있는 vectors를 support vector라 한다.)

wx+b가 양수가 나오면 w방향으로의 점들임(w는 평면의 법선벡터)

confidence level = y_i(wx_i+b), y_i는 positive case에 1, negative case에 -1을 assign, 이렇게 함으로써 모든 training instances에 대해 confidence level은 항상 양수

confidence level이 최대가 되게하는 (w,b)를 찾는게 목표(임의의 training instance에 대해 모두다 wx+b=0인 평면에 정사영 시킨 벡터로 벡터를 분리해서 보면 바로 이해가 됨)

x_0와 decision boundary와의 거리는 (wx_0+b)/||w||가 된다. 

만약 decision boundary가 존재한다면, 그리고 그때 support vectors를 wx_1+b = a, wx_2 + b = -a라 하자. (a는 임의의 양수)

그럼 다음과 같은 optimization problem이 된다.

max over (w,b) 2a/||w|| s.t. (wx_j+b)y_j >= a for all j in training instance

a를 편의상 1로 두고 역수취해 min 문제로 바꾸면

min over (w,b) ||w|| s.t. (wx_j+b)y_j >= 1 for all j in training instance

즉 quadratic programming(w의 크기->2차)

Hard margin SVM이란, 어떠한 error case도 허용하지 않는 것

Soft margin SVM이란, error case에 penality를 줌(즉 허용하되 penalty를 부여, decision boundary와 떨어진 거리에 비례하게 혹은 error case의 개수만 고려)

Hard margin SVM은 현실에서 구현이 힘듦(대개는 에러가 생김), Hard나 Soft모두 linear decision boundary를 찾는게 목표, 어쨌든 선형 decision boundary를 찾아야하는데 error case가 생긴다면 Soft margin SVM써야함

Kernel Trick을 이용하면 Hard Margin이면서 nonlinear decision boundary를 찾을 수가 있음.(데이터의 원래 차원에선 nonlinear이지만, feature mapping에 의한 차원 확장 공간에선 linear decision boundary임)

Soft margin SVM에서 

penalty상수에다가 error case 개수를 min에 추가하는 방법이 있을 수 있다. 이건, 모든 error case가 동등하게 penalty줘야하는 경우

penalty상수에다가 support vector를 넘어서는 순간부터 penality를 주는 형태가 있다.

전자는 0/1 loss(decision boundary를 넘어서는 순간부터 error줌), 후자는 hinge loss(decision boundary를 넘지 않았어도 support vector를 넘어서면 penalty 부과)

0/1 loss인 경우가 잘 쓰이지 않는 2가지 이유, 형평성문제(아주 틀린놈이랑 조금 틀린놈이랑 같은 취급), quadratic programming 구현이 어려움

후자에서 hinge loss인 경우 optimization problem은 다음과 같다.

min over (w,b) (||w||+C*sum over all j ξ_j s.t. y_j(wx_j+b) >= 1- ξ_j and ξ_j >=0 for all j in training instances.

(여기서 1-ξ_j를 이해하는게 관건, 원래는 >=1이었는데, >=1-ξ_j란 원래 있어야할 >=1영역보다 떨어진 정도를 1-ξ_j 로 나타낸 것)

후자는 Quadratic Programming이 쉽게 풀림 ξ_j를 slack variable(부가변수)라 한다.

Constraints를 Soften했다고 해서 Soft margin SVM이라 하는 것

Kernel Trick이란, 다른 차원으로 보내서 내적으로 정의되어있지만, 다른 차원으로 보내는 feature mapping function을 구하지말고 구하는 방법을 가리킨다. lagrange multiplier를 구하는 dual

https://www.youtube.com/watch?v=dP9CDyR0L3E

이거부터 보면서 마무리 정리하면 됨

Quadratic Programming

:다변수, 차수는 최대 2차인 함수를 max/min optimization, constraint는 1차로 표현되는 형태릐 문제를 가리킨다.

nonlinear programming의 대표적인 예

Quadratic Residue

:이차잉여를 배우는 이유는 정수계수정수방정식을 풀 때 그냥 풀기는 어려워서 합동식으로 범위를 제한하고 Chinese Remainder Theorem를 써서 구하는게 큰 그림. 이를 위해 일차, 이차 등 합동방정식을 해결먼저하는게 필요하고 그 때 이차잉여, 르장드르 기호 도입 등이 필요함

Decision Tree

:

n:features 총 개수

m:training instances의 총 개수

Parameters(scikit learn기준)

max_depth:tree의 depth의 상한을 설정

presort:학습이전에 데이터를 sort를 먼저 할 지를 정한다. m이 천단위로 적을 땐 True, 만단위이상일 땐 False하는 것이 학습 속도에 도움이 된다.

criterion:gini or entropy, cost function을 계산하여 feature를 greedy하게 나눌 때, impurity를 gini value를 쓸 지 entropy를 쓸 지 정한다. gini와 entropy가 성능 차이가 뚜렷하지 않으므로 계산이 빠른 gini가 default, 두개가 만들어낸 tree가 다를 때를 보면은 gini가 the most frequent class를 독자적인 branch로 두는 경향이 있고 entropy는 balanced tree를 만들어 낸다.

min_samples_split:leaf가 아닌 node가 split될 후보가 되기위한 최소 samples개수, 즉 만약 node_k가 samples가 153인데 min_samples_split가 160이면 학습시 node_k에서 쪼개는 것은 더이상 생각 안함

min_samples_leaf:leaf가 가질 수 있는 최대 samples 개수, 만약 node_k가 samples=7이고 쪼개지면 1과 6으로 쪼개지는 상황인데 min_samples_leaf가 2이면 1<2이므로 쪼개지지 않게 함

max_leaf_nodes:leaf의 최대개수 상한

max_features:학습시 각 node에서 feature를 고르는데 feature 고려 후보 개수 상한, 즉 max_features=5이고 모든 feature개수가 50일 때, 각 node에서 50개 중 임의의 5개의 feature만 택해서 greedy하게 best feature, threshold를 찾아낸다. 적을수록 regularize하는 것이고 overfit risk 낮춤

splitter:각 node에서 greedy하게 택한 best feature를 쓸지, 아니면 random하게 feature택하고 threshold만 적절하게 학습으로 찾을 지 선택

학습과정

:

Cost(feature_name, threshold_value) = left_ratio * left_impurity + right_ratio * right_impurity 가 최소가 되게하는 feature_name과 threshold_value를 택한다. 

즉 the purest subsets(weighted by their size)가 되게끔

이후 각 node마다 위의 과정을 반복하여서 feature_name과 threshold_value를 차례로 설정해나간다. 더이상 training instance가 나눠지지 않을때까지 나누거나 max_depth로 설정한 값까지 나눈다. 즉 greedy하게 학습한다.

greedy하기 때문에 optimal solution인지는 알 수가 없다. optimal solution을 찾는 것은 NP-Complete로 알려져 있으며 O(exp(m))로 알려져 있다. 

regression의 경우

Cost(feature_name, threshold_value) = left_ratio * left_variance + right_ratio * right_variance 가 최소가 되게하는 feature_name과 threshold_value를 택한다.

여기서 left_variance란, left에 속하게 되는 instances의 y값의 편차를 가리킨다.

학습할 때의 계산복잡도는 O(n*m*log(m))이다.

restriction없이 그냥 decision tree를 학습한 후에 모든 children nodes가 leaf인 node중에서 chi-square test using p-value 해서 null hypothesis:이 node를 children과 두는게 성능 향상되는게 우연이다, 라고 둔 확률이 일정 threshold(hyperparameter)보다 크면 accept하고 node의 children를 삭제하는 형태의 constraint를 두기도 한다. pruning(가지치기)라고 한다.

학습후

:

각 node는 다음의 데이터를 갖는다. 

feature_i criteria, ex) length > 0.2, 통과되면 왼쪽 node로 감

gini value(1 - (a_1/samples)^2 - (a_2/samples)^2....), 즉 작을수록 좋고, impurity를 measure하는 metric중 1가지 or entropy (parameter인 criterion을 default가 gini)

(entropy는 각 class의 training instance분포를 기준으로 구함, training instance가 0인 class는 summand로 넣지 않음)

samples(통과된 training instance의 개수), 

value=[a_1,a_2,...a_class개수]로 각 training instances의 class별 개수, 

class(이 node에 있으면 predict한 class값)

tree_clf.predict_proba("feature value list")를 통해 임의의 instance(feature value list로 실현된)를 입력하면

instance가 도착한 node의 samples와 value를 이용하여 instance가 어떤 class인지 predict한 값과, 그 class일 확률을 계산한다.

그 class일 확률 및 다른 class일 확률은 samples와 value를 이용하여 a_1/samples, a_2/samples,...를 통해 계산한다. 즉 training instances들의 그 node에 분포한 확률을 뱉는 것일 뿐. 즉 test instance의 feature값이 무엇이든, 같은 node에 도착하면 class distribution은 같게 나온다.

predict할 때의 계산 복잡도는 O(log(m))이다. Worst case는 O(m), 즉 모든 leaf가 training instance를 1개씩만 갖는 상황. (꼭 한개의 node에 여러 samples가 있을 필요가 없음, 특정 class의 samples가 다 있어야 하는 것도 아님)

따라서 아무리 많은 training instance로 학습하였어도, prediction은 빠르다.

특징

:

데이터 전처리를 거의 필요로 하지 않는다. scaling, centering따위 필요하지 않음

nonparametric(parameter가 없다는 뜻이 아니라, 있지만, 학습 이전에 정하지 않는 다는 의미), 따라서 overfit위험이 크므로 max_depth같은걸 지정함

regularization은 hyperparameter(max*을 줄이거나 min*을 늘리거나 하여 overfit 예방)

decision tree는 기준을 orthogonal하게 잡아버림, 따라서 rotation된 data에 대해선 generalization performance가 약함->PCA쓰고 decision tree쓰면 해결됨

학습데이터의 small variance이 학습된 decision tree 모양을 크게 바꿀 수 있음->instable

scikit-learn의 경우 decision tree를 학습시킬 때마다 (max_features같은게 설정되어 있다면)같은 training data set이어도 다른 모델들이 나올 수 있다. 왜냐하면 random하게 feature를 택하기 때문->instable

이러한 instable문제 때문에 random forest(decision tree의 bagging version)이 등장함

Random Forest

:

Autoencoder

:input, hidden layers, output으로 구성

데이터의 효과적인 표현(coding)을 learning

대개는 더 작은 사이즈로 dimensionality reduction

알아서 적절한 features만 뽑아낼 것(without label and domain knowledge)

->Autoencoder

사용하는 곳

-feature detectors, feature extraction, dimensionality reduction

-generative model

Autoencoder가 단순히 identity가 아닌 이유

-사이즈를 줄여나간 latent feature space

-변형된 Autoencoders(input은 with noise, output은 without noise)

구성

encoder=recognition network

decoder=generative network

output=reconstructions

loss=reconstruction loss

internal representation=latent feature

internal representation < input

이 때 undercomplete autoencoder라 한다

Simple Autoencoder(즉 layer가 가장 적게)에서 

activation function을 안쓰면 PCA와 같다.

Deep Autoencoder

주의사항:너무 딥하게 만들면, 모든 training instance마다 1개의 숫자로 대응시켜버려서

training accuracy는 좋지만 generalize는 못할 수가 있음

전략1:Tying Weights

transpose를 활용하여 같은 weight를 둠으로써 학습할 weight개수를 낮추고 deep하게 가능

fully_connected쓰지말고 직접 행렬을 정의하는게 이때는 훨씬 간결하다

이 때 주의사항

weights1과 weights2만 regularizer에 넣고

weights3과 weights4는 넣으면 안됨

bias는 tied도 regul도 안했음

전략2:한번에 한개의 autoencoder학습시키기

매우 deep한 autoencoder에서 유용하다(효율적인 학습)

즉 한번에 2개의 weight와 2개의 bias를 학습시키자.(그동안 나머지 weight와 bias는 고정)

이때 phrase가 증가함에 따라 input을 매번계산하지않게 하기 위해

값을 저장해두고 쓰기

Visualizing Features

방법1: layer에서 각 뉴런마다 가장 값이 높게 나오는 training instance찾기, 이 때 layer가 top에 있을 때가 효율적임, lower에 있을 때는 매우 추상적이고 값도 적을 가능성이 높다. 예를 들면 first neuron이 가장 높은 값이 있을 때, 그 때의 training instance가 고양이 사진이라면 다른 고양이 사진에서도 first neuron값이 높게 나올 것이다.

방법2:각 뉴런마다 직전 웨이트값을 transpose하여 plot해보기, weight값의 크기를 통해 그 뉴런이 어떤 feature를 찾으려는지 시각화됨

방법3:임의의 랜덤 input(image)를 넣고 내가 관심있는 neuron이 좀 더 activate하게되게 이미지를 수정해나가기(backpropagation)

(Classification의 pretraining 으로 사용할 경우, 그냥 Classification의 성능을 볼 수도 있다.)

Regularization implement example

:

regularizer = tf.contrib.layers.l2_regularizer(l2_reg)

initializer = tf.contrib.layers.variance_scaling_initializer()

X = tf.placeholder(tf.float32, shape=[None, n_inputs])

weights1_init = initializer([n_inputs, n_hidden1])

weights2_init = initializer([n_hidden1, n_hidden2])

weights1 = tf.Variable(weights1_init, dtype=tf.float32, name="weights1")

weights2 = tf.Variable(weights2_init, dtype=tf.float32, name="weights2")

weights3 = tf.transpose(weights2, name="weights3") # tied weights

weights4 = tf.transpose(weights1, name="weights4") # tied weights

biases1 = tf.Variable(tf.zeros(n_hidden1), name="biases1")

biases2 = tf.Variable(tf.zeros(n_hidden2), name="biases2")

biases3 = tf.Variable(tf.zeros(n_hidden3), name="biases3")

biases4 = tf.Variable(tf.zeros(n_outputs), name="biases4")

hidden1 = activation(tf.matmul(X, weights1) + biases1)

hidden2 = activation(tf.matmul(hidden1, weights2) + biases2)

hidden3 = activation(tf.matmul(hidden2, weights3) + biases3)

outputs = tf.matmul(hidden3, weights4) + biases4

reconstruction_loss = tf.reduce_mean(tf.square(outputs - X))

reg_loss = regularizer(weights1) + regularizer(weights2)

loss = reconstruction_loss + reg_loss

Tensorboard

:

now = datetime.utcnow().strftime("%Y%m%d%H%M%S")

root_logdir = "tf_logs"

logdir = "{}/run-{}/".format(root_logdir, now)

mse_summary = tf.summary.scalar('MSE', mse)

file_writer = tf.summary.FileWriter(logdir, tf.get_default_graph())

이렇게 학습시마다 다른 텐서보드를 얻기위해 폴더명에 실행시간을 추가시켜버리는 테크닉가능

summary_str = mse_summary.eval(feed_dict={X: X_batch, y: y_batch})

step = epoch * n_batches + batch_index

file_writer.add_summary(summary_str, step)

이렇게 텐서보드에 표현하고 싶은 필요한 스칼라값을 (학습중에서도 생기는,배치나 에퐄사이에)추가하여 학습, 그러면 events파일로서 저장되어 텐서보드에 표현가능

ROC(Receiver Operating characteristic curve)와 AUC(Area Under Curve)

:

False Positive란 예측값이 Positive인데 틀린(False) case, 즉 실제론 Negative인데 Positive라고 예측한 경우, Type I error

False Negative란 예측값이 Negative인데 틀린(False) case, 즉 실제론 Positive인데 Negative라고 예측한 경우, Type II error

False Positive Rate란 FP/N, 즉 실제 Negative에서 False Positve의 비율, 낮을수록 Negative인 것을 Negative라고 잘 판단

True Positive Rate란 TP/P, 즉 실제 Positive에서 True Positive의 비율, Recall이라고도 불리며 높을 수록 Positive인 것을 Positive라고 잘 판단

ROC란 어떤 binary classifier의 threshold를 다양하게 하여 x축을 FPR, y축을 TPR으로 하여 그린 곡선이다. 해석은 다음과 같다.

-[0,1]x[0,1]에서 그린 곡선이다.

-y=x위의 점인 경우 accuracy가 50%이다.(단 FPR=TPR=0.9인 경우랑 FPR=TPR=0.1인 경우 전자는 그래도 Positive인 것을 Positive라 판단하는 성능은 좋으며, 후자는 Negative인 것을 Negative로 판단하는 성능은 좋음)

-같은 binary classification문제에서 2개의 모델을 threshold를 다양하게하여 ROC curve를 각각 그려 2개를 그린다. 이 때 두 모델중 어느 것이 성능이 더 좋은 지를 판단하는 것을 AUC를 사용하여 구한다. (즉 2개 모델에서 threshold를 뭘하든 모델자체의 성능을 평가하기 위함)

-(FPR, TPR)=(0.9, 0.1)인 경우 엄청 성능이 낮음, random보다도 성능이 낮은 경우

-AUC가 높다->(FPR,TPR)이 좌측 상단에 있다->Better Case->즉 2모델 중 AUC가 높은게 Better Case(threshold가 존재)한다.

-실제로 어떤 threshold hold를 쓸 지는 TPR와 FPR중 무엇이 더 중요한지(즉 Problem마다 다름)를 생각하고 정한다.

Ridge, Lasso, L1, L2, regularization

:

ridge regression이란 bias말고 weight를 l2 norm구해서 l2 norm자체를 loss에 추가한 것

lasso regression이란 bias말고 weight를 l1 norm구해서 l1 norm 자체를 loss에 추가한 것

lasso는 여러 feature중 의미없는 feature를 걸러내는 데 사용

ridge는 weight의 절댓값을 줄임으로써 모델의 generalization의 성능을 끌어올리고자 하는 것

특히 training data가 적을 때 사용

Docker

:

장점

-용량 줄이기. 가상머신은 운영체제를 하나 새로 까니까 용량이 더 든다.

-빠르다. 가상머신은 CPU를 쪼개서 쓰므로 느릴 수 밖에 없다. 프로세스 차원으로 격리시켜 사용하는 도커는 OS를 분리하진 않으므로 기존 자원을 그대로 사용하므로 빠르다.

-

특징

-리눅스 전용

-sudo로만 실행가능, 매번 sudo쓰기 싫으면 sudo usermod -aG docker egoing을 실행시켜 현재 계정을 도커계정에 추가시키면 된다.

-image와 container로 구성, image란 실행파일과 라이브러리의 총합, container란 image를 실행해둔 상태를 가리킨다.

설치하기

-sudo wget -qO- https://get.docker.com/ | sh

사용하기

어떠한 패키지를 사용하는데에 있어서 그것을 일일이 다 설치하기보단 그것을 미리 설치해둔 좀 더 큰 이미지를 받아 실행시킴으로써 패키지 관리자를 사용할 수가 있다.

-우분투 이미지 다운받아 실행하기

push

ex)docker push ~~~~

자기가 만든 이미지를 서버로 공유하는 것

docker와 dochub와의 관계는 git과 github와 비슷하다.

pull

ex)docker pull ubuntu:14.04

우분투 14.04 패키지 시스템이 구성된 이미지를 받아온다.

우분투의 커널을 제외한 모든 리눅스 배포판이 이미지안에 포함되어있다.

ex)docker pull nginx:latest

이처럼 버전을 latest라 두면 가장 최신버전의 이미지를 받아온다.

images

ex)docker images

현재 docker가 갖고 있는 이미지의 리스트를 반환한다.

search

ex)docker search ubuntu

현재 dochub에 있는 ubuntu가 포함된 이미지 리스트를 반환한다.

결과 리스트에서 앞에 아이디가 적혀져있지 않은 것은 도커에서 지원하는 공식 이미지들이다.

하지만 결과 리스트가 너무 많아서, docker.com에서 browse 탭에서 ubuntu라 검색하면 Tags에 버전들 목록이 있으며 그것을 참고해서 docker pull ubuntu:14.04 같이 입력하여 사용하면 된다.

run

ex)docker run -i -t ubuntu:14.04 /bin/bash

설치된 이미지를 통해 container를 실행시키고 들어가는 명령어

/bin/bash를 쳐줌으로써 이미지에 있던 bash파일을 실행하면서 container를 실행

docker는 기본적으로 실행할 메인 실행파일(현재는 /bin/bash)을 함께 실행시켜야 container가 유지되고, 이것을 종료함으로써 container를 종료한다.

-i:interactive환경을 제공

-t:가상터미널환경을 제공

이후 container 내에서 어떠한 패키지들을 설치하면 그것은 원래 운영체제에서는 설치되지않고 container 내에서만 설치가 된다. 마찬가지로 기존 운영체제에 설치된 패키지를 container 내에서 사용할 수가 없다. 완전 독립

ex)docker run -i -t --name bg ubuntu:14.04 /bin/bash

--name을 통해 container의 이름을 붙여 실행시킬 수 있으며, 이는 후에 container를 재실행하기 쉽게 만든다. 만약 name을 지정하지 않았다면 docker가 알아서 이름을 만든다.

container내에서의 패키지 설치 및 사용 등은 container-level에서 독립적이다. 즉 하나의 image로 여러개의 container를 만들어서 사용할 수가 있으며 각개의 container는 독립적으로 운용된다.

ex)docker run -d --name hello-nginx nginx:latest

-d:detached, 백그라운드로 실행, 그렇다보니 bash같은 실행파일을 지정해주지 않아도 된다.

start

ex)docker start "container id"

ex)docker start "container name"

ex)docker start bg

container의 id나 name을 이용하여 container를 실행시킨다. 이 경우 container가 실행되지만 안으로 들어가지는 않는 상태가 된다.

attach

ex)docker attach "container name"

start로 실행시켰던 container로 들어가는 명령어

ps

ex)docker ps

현재 실행중인 container 목록이 나온다.

ex)docker ps -a

과거에 종료했던 container까지도 포함해서 목록이 나온다.

ex)docker container rm "container id"

docker rmi "image_name" 했을 때 특정 container가 사용중이므로 삭제가 안될 때가 있다. 그 때 docker ps해도 container가 켜지지 않았음에도 에러가 날 때가 있는데, 그땐 docker ps -a로 과거 container history를 본 다음에, 확실히 container를 제거해줘야한다. 그때 docker container rm "container_id"가 필요하다.

ctrl+p+q

container 내에서 container를 종료시키지 않고 빠져나오는 명령어

만약 container를 종료시키면서 빠져나오고 싶다면 exit 혹은 ctrl+d를 써서 bash를 꺼주면 된다.

stop

ex)docker stop "container name"

container밖에서 현재 실행 중인 container를 종료시키고 싶을 때 사용하는 명령어

rm

ex)docker rm "container name"

특정 container가 관심없어서 지우고 싶을 때 사용

rmi

ex)docker rmi "image name"

docker가 갖고 있던 image중에서 image를 삭제하는 명령어

exec

ex)docker exec "container name" touch /hello.txt # touch란 파일 만들기 명령어이다.

밖에서 container의 우분투에서 명령을 실행시킬 수가 있다.

commit

ex)docker commit "container id" "image name"

만든 container를 image로 뜨는 명령어이다.

nvidia-docker2설치과정

$ curl -s -L https://nvidia.github.io/nvidia-docker/gpgkey | \

  sudo apt-key add -

$ distribution=$(. /etc/os-release;echo $ID$VERSION_ID)

$ curl -s -L https://nvidia.github.io/nvidia-docker/$distribution/nvidia-docker.list | \

  sudo tee /etc/apt/sources.list.d/nvidia-docker.list

$ sudo apt-get update

$ sudo apt-get install -y nvidia-docker2

$ sudo docker pull nvidia/cuda:10.0-cudnn7-runtime-ubuntu16.04

$ sudo systemctl daemon-reload

$ sudo systemctl restart docker

cp

ex)docker cp "host파일경로" "container name":"container 내부경로" # host->container 파일복사

ex)docker cp "container name":"container 내부경로" "host파일경로" # container->host 파일복사

ex)docker cp docker-cp-test anchore:test

참고자료

http://pyrasis.com/docker.html

https://opentutorials.org/course/128/8657

https://nicewoong.github.io/development/2018/03/06/docker-commit-container/

https://hiseon.me/2018/02/19/install-docker/

https://github.com/NVIDIA/nvidia-docker/issues/838

Git

:

버전관리 시스템 중 하나(version control system)

파일이름을 바꾸지 않으면서도 버전관리, 즉 변경사항을 관리한다.

게다가 backup, recovery, collaboration(다른 사람과 협업) 등이 가능

설치방법

:

sudo apt-get install git

or

sudo yum install git

git init

ex)git init

프로젝트 폴더 내에서 실행하면 이 폴더를 버전관리를 하겠다고 git에게 알려주는 명령어

이후 프로젝트 폴더 내에 .git이란 폴더가 생기고 여기에 모든 작업 내역들이 저장된다.

git status

ex)git status

버전관리를 하겠다고한 폴더내에서 실행하면 현재 폴더 내에 파일들의 status를 알려준다.

git add "file명"

ex)git add f1.txt

git에게 파일을 관리(track)하라고 명령하는 명령어

git init하고나서 이후에 새로 추가된 파일들에게 주로 필요하며, init된 폴더내에 있다고해서 버전관리가 다 필요한 파일들이 아니기때문에, 새로 만들때마다 git add해주어야 한다.

최초 track을 하기 위해서도 git add를 쓰지만, 이후 파일을 수정하고나서 git status하고나면 "modified"가 나오는데, 이때 바로 git commit하여 새버전을 만드는게 안된다.

이때 새 버전을 만들때도 git add "file명" 해주어야 한다.

즉, git add는 1. track(변경이 된건지 아닌건지), 2. make new version, 2가지를 위함에 필요하다.

즉, git은 내가 commit하고 싶은 파일만 등록해서 commit할 수 있게 add를 둔 것, add를 통해서 stage(commit 대기파일들)에 파일을 등록시킨다.

작성자 profile 등록

git config --global user.name bg

git config --global user.name bg@gmail.com

이렇게 함으로써 버전에 작성자 profile을 등록할 수 있다.

git commit

실행하게되면 stage(commit 대기파일들)에 있는 것을 commit한다.

git status한 내용들이 하단에 주석으로 깔리고 상단에는 버전메시지를 입력하게끔 vim으로 .git/COMMIT_EDITMSG파일이 열린다.

버전메시지(commit message)란, 새 버전의 유의미한 변화를 적어주면 된다.

이후 commit하여 생성된 버전이 저장되는 곳을 repository라 한다.

git log

버전메시지들의 log가 남는다. 버전 작성자의 profile과 버전을 만든 data도 출력한다. 그리고 각 commit의 id도 출력한다.

git log -p

버전메시지들의 log와 함께 각 버전마다 직전버전과의 변화를 출력한다. 

기본적으로 버전관리라함은 git init한 폴더 자체를 1개의 버전으로 보기 때문에, 각 버전마다 새로생긴 파일, 수정된 파일 등의 변화를 볼 수가 있다.

git log "commit id"

해당 commit id의 이전 log만 출력한다.

git diff "commit id1".."commit id2"

commit id1과 commit id2 사이의 log -p만 출력, -는 commit id1의 내용, +는 commit id2의 내용을 출력한다.

git diff

작업한 변경사항들을 보여준다. 대개는 commit하기전에 확인차원에서 써본다. add하기 전의 파일들의 수정사항들을 확인하는 것이다. add한 파일들의 수정사항들은 나오지 않는다.

git reset

(버전을 되돌리는 방법이므로, 주의해서 사용해야함, 프로젝트 폴더 전체를 백업떠두고 하는 걸 추천)

git revert

Python3

:

sudo apt-get install python3-pip

pip3 freeze > requirements.txt

pip3 install -r requirements.txt

Numpy

:

Clustering

:

결과에 따른 종류:

Hard clustering:각 instance가 단일 cluster에 속하는 경우

Soft clustering:각 instance가 각 cluster에 속하는 정도를 나타낸 경우

알고리즘에 따른 종류:

K-means clustering:

n개의 instance를 m(<=n)개의 cluster에 속하게끔 분류를 한다. 이 때 C_1, C_2, ..., C_m개의 cluster에 속하는 instances의 평균을 μ1,μ2,...,μm이라 할 때 C_k에 속하는 임의의 instance와 평균사이의 거리제곱의 합이 최소가 되게하는 C_1,C_2,...,C_m을 설정하는 것을 목표로 한다. 방법은 Assignment Step과 Update Step을 반복적으로 시행하여 얻는다. 

먼저 initial values of means를 설정한다. 이후 Assignment(각 점마다 가장 가까운 mean의 cluster에 배정), Update(각 cluster의 새 mean을 구함)

이후 Assignment를 하여도 변함이 없을 때 종료한다. 

특징:

거리(distance)함수를 L2 외 다른 것을 씀으로써 변형 K-means clustering이 가능

만들어진 cluster가 convex하지 않으면 clustering이 실패하거나 means가 엉뚱한 값이 될 수가 있다.

초기 mean 설정에 대한 여러 방법들이 존재

최적 cluster 개수 k를 설정하는 여러 방법들이 존재(거리제곱의 합이 최소 중에 최소가 되는 k 선택, 물론 k=n이면 0이 되지만, k<<n인 k 중에서 거리제곱의 합이 급격히 변화하는 k를 택하거나, silhouette(각 점(i)마다 cluster 내의 다른 점들과의 평균거리(a(i))와 다른 cluster 각각의 평균거리(즉 다른 cluster 내의 점들과의 거리의 평균)의 최솟값 (b(i))를 구한다. 이렇게 각 데이터 i마다 a(i), b(i)를 바탕으로 silhouette score s(i)를 구하고 s(i)의 값에 따라 i가 cluster에 잘 배정됐는지를 해석한다. wiki에서 silhouette clustering을 검색, s(i)값이 높을 수록 좋으며, cluster 개수 k를 증가시키며 평균 silhouette score값이 최대가 되는 k를 택한다. 혹은 이전의 거리제곱의 합이 최소인 것과 동시에 silhouette score를 각 군집마다 결과를 내서 함께 고려하여 k를 결정하기도 한다. Calinski-Harabasz index(군집간 산포와 군집내 산포의 비율을 이용, https://scikit-learn.org/stable/modules/clustering.html#calinski-harabaz-index 참고)를 이용하여 k를 결정하기도 함(물론 silhouette, 거리제곱합 등도 함께 이용)

DBSCAN(Density-Based Spatial Clustering of Applications with Noise):

특징:

non-convex 문제를 해결할 수 있음

k를 먼저 선언하지 않아도 된다.

Ensemble

:

이론 배경은 Law of large number에 있다.

Pandas

:

국내

서울

-난지도

전라도

-장도(섬)(보성군 벌교읍)

-전라우수영(해남)

-낙안읍성(순천)

-선암사(순천)

-진도(4월에 바닷길 축제)

-

국외

싱가폴에서의 크리스마스? 더운 크리스마스?

1. 

목표는 아래의 모든 머신기구들 max중량, 셋트당 10~20, 4셋트채우기

1일차

체프:65

팩머:20

숄프:40

렉익:35

레프:80

케프다:20

2일차

체프:75

팩머:20

숄프:40

레프:100

렉익:40

로프다:10

케프다:X

3일차

체프:75

팩머:20

숄프:50

렉익:X

레프:100

로프다:12.5

케프다:X

4일차

체프:80

팩머:25

숄프:50

렉익:45

레프:110

로프다:15

케프다:X

for tensorflow 1.x 1080ti

[install graphic drivers]

$ sudo add-apt-repository ppa:graphics-drivers/ppa

$ sudo apt-get update

$ sudo apt-get install nvidia-390

$ sudo reboot

[check]

nvidia-smi

[install cuda]

sudo sh cuda_8.0.61_375.26_linux.run

### cuda 9.0으로 수정해서 깔아야함

Do you accept the previously read EULA?

accept/decline/quit: accept

Install NVIDIA Accelerated Graphics Driver for Linux?

(y)es/(n)o/(q)uit: n

Install the CUDA 9.0 Toolkit?  

(y)es/(n)o/(q)uit: y

Enter Toolkit Location  

 [ default is /usr/local/cuda-8.0 ]: 

Do you want to install a symbolic link at /usr/local/cuda?  

(y)es/(n)o/(q)uit: y

Install the CUDA 8.0 Samples?  

(y)es/(n)o/(q)uit: n

Enter CUDA Samples Location  

 [ default is /home/your_id ]: 

[set env]

$ echo -e "\n## CUDA and cuDNN paths"  >> ~/.bashrc

$ echo 'export PATH=/usr/local/cuda-9.0/bin:${PATH}' >> ~/.bashrc

$ echo 'export LD_LIBRARY_PATH=/usr/local/cuda-9.0/lib64:${LD_LIBRARY_PATH}' >> ~/.bashrc

$ source ~/.bashrc

[check]

$ nvcc --version

nvcc: NVIDIA (R) Cuda compiler driver

Copyright (c) 2005-2016 NVIDIA Corporation

Built on Tue_Jan_10_13:22:03_CST_2017

Cuda compilation tools, release 8.0, V8.0.61

[install cudnn]

### cuda 9.0에 맞게 깔아야

이후 pip를 install한 다음에

sudo pip install tensorflow

sudo pip install tensorflow-gpu

sudo pip3 install tensorflow

sudo pip3 install tensorflow-gpu

ubuntu 18.04사용하면서

python3에서 tensorflow를 불러오는게 안될 수 있음

이때 오류에 나온 pip.py인가를 띄워서 __internal을 추가하는거였나...(체크필요)

*우분투

GPU사용현황

-nvidia-smi

deb파일 설치 과정

-

home에서 vim .bashrc

-기본적인 환경변수들 지정가능, 우분투 기본 옵션 할당하는 것 인듯?

파일권한변경

-chmod 755 파일명

*파이썬

list합치기

-list1 + list2

FLAG사용하는 이유

-FLAG에 새로운 값 넣으면서 실행가능, 작성시 default값 줄 수 있음

-try, except, else, finally, pass, raise, 

몇가지 필요한 습관

-None이 return시 raise를 써서 에러, 주석, 처리해주어야 함(if none:)

-Naming Rule

-파일명은 소문자

-Class은 대문자로 시작

-상수는 올 대문자

-_Private 함수는 _로 시작

-Public함수는 그냥 시작

-하드코딩 금지(최대한 빨간글자 줄이기)

-가능한 요소들은 최대한 클래스화

-모든 함수, 클래스에 정해진 형식의 주석 삽입

-외부 설정파일은 하나로 공유

-중복 코드 금지

-긴 코드 최대한 모듈화

-테스트용 코드는 반드시 분리

-최대한 자주 Git활용

-getter, setter in python(인자 여부로 구분가능)

-Issue Tracking 남기기, 항상 Issue가 생기면 먼저 Trello같은 곳에 남기고, 해결되어도 issue 지우지말고 남겨두기

-모든 python process 종료, pkill -9 python

-pyc만들기, import py_compile 이후 py_compile.compile(file), pyc로 만들 file.py를 입력하면, 실행한 폴더에 __pycache__ 폴더가 새로 생기며 거기에 pyc생김

-//은 몫, %은 나머지, /은 나누기(정수로가 아니라 그냥 나누기 연산, 예를 들면 10/4 = 2.5)

-

*numpy관련

np.array(list, dtype= ) # list 를 np array 클래스로 만듦

np.array[np.array([2,1])] 이렇게 np.array에 np.array를 넣어서(index) 해당 index의 값과 순서를 고려해서 array를 slicing 및 수정 가능

np.array[2:23]으로 slicing도 가능

np.arange(10) # 0부터 시작해 10이전까지 등차가 1인 np array를 출력

np.arange(3, 21, 2) # 3부터 시작해서 등차가 2이고 21이전까지 등차수열 np array를 출력

np.random.permutation(np.array) # np.array를 임의로 섞어 은 np.array를 출력

*Tensorflow

tf.Variable

tf.constant

tf.placeholder

3개의 구분

Variable은 Variable

나머지 둘은 tensor

Variable은 학습하여 얻은 행렬 및 값에 쓰임, 왜냐하면 저장 및 복구가 가능

constant는 w2v.npy불러와서 쓰이듯 고정값으로만 씀

placeholder는 같은 연산, 행위를 반복하되 변수를 바꿔서 넣어야할 때 쓰임, 따라서 입력벡터, 라벨링벡터 등에 쓰임

tf.one_hot(indices, depth, on_value, off_value, axis, dtype, name) # depth길이 만큼의 벡터들로 index에 해당하는 위치에 on_value, 아닌 위치엔 off_value를 넣는 벡터들을 출력

tf.Session() # tensorflow 연산들을 실행하기 위한 클래스

with tf.device(장치명): # 특정 작업을 특정 device에 배치

tf.ConfigProto(...)

  device_count = {'GPU' :0} # 지정한 장치(GPU/CPU)의 사용할 최대 개수 정하기

  log_device_placement = T/F # 연산이나 텐서가 어떤 device를 쓰는 지 log해줌

  gpu_options.allow_growth = T/F # 필요한 만큼만 GPU메모리 할당 하였다가 이후 더 필요하면 증가, 하지만 증가된게 줄어들진 않음

  gpu_options.per_process_gpu_memory_fraction = 0~1 # GPU의 메모리의 일정 부분만 할당

  allow_soft_placement = T/F # 명시된 device가 없어서 작동안될 시에 tensorflow가 자동으로 존재하는 device중 선택

tf.nn.embedding_lookup

tf.nn.bidirectional_dynamic_rnn

tf.contrib.rnn.BasicLSTMCell

tf.contrib.rnn.DropoutWrapper

tf.contrib.rnn.MultiRNNCell

tf.concat

*git

git clone -b name url

-복사하라(clone), -b(branch하나파서), name란 브랜치로, url의 파일을

git add main.py

-git이 변경사항을 알아처먹을 파일 지정

git status

-내가 수정한 내용들을 알려줌

git config

??

git commit -m "[TST] commit test"

-commit하라, -m(message)를 던지겠다, [xxx]에 대한 규칙은 git.md참고

git push

-git웹사이트에 commit 내용 반영

주기동:주간기술동향, 정보통신기술진흥센터

180704 주기동

블록체인 기반의 탈중앙화 사례분석

단계별 제공가치 및 내용

1단계, 공유성, 모든 노드(사용자) 간에 정보를 공유함

2단계, 투명성, 정보 공유로 인해서, 숨기는 항목이 거의 사라짐

2단계, 무결성, '증명 알고리즘' 사용에 의해 공유 정보의 무결성 보장

3단계, 신뢰성, 믿을 수 있는 정보 공유로 노드 사이에 신뢰가 형성됨

4단계, 탈중앙화, 중개 비용 감소, 공유 비용 절감, 개인 권리 강화

GPS 전파교란 동향 및 대응 기술

GPS란, 위성항법시스템(Navigation Satellite System)중 Global, Regional 두가지로 분류할 수가 있는데, Global 중에서도 미국의 Global Positioning System을 GPS라 한다.

GPS 위성에서 송신하는 송출 신호의 세기는 25W로 강한 수준이지만, 지상까지의 거리가 멀어서, 약 20,000km, 지상에서의 수신 신호세기는 휴대전화 최소 수신 전력의 1/300 수준인 -160dBW로 약하다.

교란방법으로 잡음기법(위성 신호보다 40dB 이상의 강한 잡음 신호를 방출하여 수신기가 GPS 신호를 제대로 수신하지 못하게 방해하는 기법)과 기만기법(Meaconing(재머가 위성항법 신호를 수신하여 일정시간 동안 지연시킨 후 재방출하여 근처의 수신기로 하여금 재머 위치를 자신의 현 위치로 착각하게 만드는 방법)과 Spoofing(위성항법 정보를 열어서 내부 정보를 다른 정보로 조작하여 재방출함으로써 수신기로 하여금 재머가 보낸 엉뚱한 위치를 자신의 현 위치로 착각하게 만드는 방법))이 있다.

ICT로 고도화된 월드컵, 실시간 전술 변화 지원과 비디오 판정 도입

트래킹 시스템, 각 팀에 태블릿2개, 선수와 공의 위치 데이터, 각 선수의 달리기 속도, 패스와 압박, 태클 등의 통계데이터 제공 및 경기 영상 전달(30초 정도 딜레이)

VAR(Video Assistant Referee)

제2회 스타트업 월드컵

1위, 류코 랩스, 암 환자의 백혈구 수치를 신체에 의료 기기를 삽입하지 않는 비침습적 방법으로 모니터링하는 기술

2위, 플리토, 실시간 소셜 번역 앱

공동 3위, 스트랩, 시각장애인 지원 웨어러블 기기

공동 3위, 월박스, 전기자동차의 충전 효율 향상 기술

심사기준:임팩트가 강한 하나의 제품을 보유하고 있는가, 이미 사업화가 진행되어 어느 정도의 매출이 있는지

아마존의 인공지능 개발 플랫폼 개방을 통한 AI 생태계 확대 전략

2018년 5월 인공지능 알렉사 활용 앱 플랫폼인 스킬(Skill)에 유료 앱 등록을 모든 개발자에게 오픈함으로써 아마존의 음성 인공지능 생태계가 폭발적으로 확대될 것으로 예상

유어 보이스(Υοur Voice)라는 화자인식 기능도 개방함

이를 통해 하드웨어 제조사들에게 자사의 제품에 알렉사를 쉽게 탑재할 수 있는 기회를 제공, 인공지능 스피커 에코의 가치 상승, 많은 IoT상품들의 출현

Kohler의 Numi라는 인공지능 변, 음성명령에 따라 커버여닫기, 비데 강도 조절, 음악 재생, 물사용량 통계 등 가능

180711 주기동

인공지능의 창업 분야와 기회

1. 인공지능 기반 커머스에서 찾는 창업의 기회, Curation Commerce, 인공지능 기반의 맞춤형 추천, 개인화, 고객들의 특성, 과거 구매 내역 등 기반, Amazon Go는 무인 매장, 소비자는 스마트폰에 앱을 내려 받은 후, 매장에 들어가 계싼대에 줄을 설 필요 없이 원하는 상품을 들고 나오기만 하면 된다. 수백 대의 카메라와 센서들이 소비자가 어떤 물건을 골랐는지 자동으로 인식하고 연결된 신용카드로 결제까지 완료하기 때문

2. 미래 인공지능 챗봇에서 찾는 창업의 기회, 챗봇 자체를 서비스의 중심으로 이끌어가고 싶다면, Nadia와 같이 인간의 감정을 어루만져 줄 수 있는 친구 서비스로 가야한다. 혹은 B2B 형태의 창업으로 다른 서비스에 도움을 주는 형태로 가야한다. 챗봇 비즈니스를 시작할 땐 챗센터(chat Center), 즉 고객이 묻는 채팅 질문에 사람이 직접 대응하는 시스템을 동시에 운영해야 한다. 초기 오픈 단계에서는 90%에 가까운 예외사항들이 발생하고 이러한 예외사항에 대한 데이터를 빠르게 수집하여 적용해야 한다.

3. 인공지능 통번역에서 찾는 창업의 기회

4. 헬스케어 IoT와 인공지능의 결합에서 찾는 창업의 기회, 문신, 렌즈 형태의 센서들이 등장, 정신과 치료는 매일매일 환자의 상태를 파악해야만 좀 더 정밀하고 정확한 진료 가능, 챗봇을 통해 하루3번 상담, 구글 컨택트 렌즈를 통해 당뇨 진단도 가능, 

5. 패션과 인공지능의 결합에서 찾는 창업의 기회, 3D 패션 분야 가상현실을 통해 원단의 재질과 물리적 특성을 구현해 실물같은 옷을 보여줄 수 있다. 옷(티셔츠)에 센서를 달아 VR성능을 키우기도 가능, 자켓에 센서를 달아 스마트폰 제어가능(주요 수요층이 자전거로 출퇴하는 사람)

6. 인공지능 서비스 로봇에서 찾는 창업의 기회, 인공지능 면접관 서비스, 지원자의 얼굴 표정, 음성 등을 모니터링해서 지원자의 성향과 업무 능력 파악, 명품 진위여부 서비스도 가능(Entrupy가 개발한)

7. 가정용 로봇에서 찾는 인공지능 기술창업의 기회, 감정 표현, 소통, 개인 비서, 가전기기 제어, 집안 모니터링, 음악 스트리밍, 영화 재생, 교육(아이들의 질문에 대답과 재미있을만한 이야기를 들려주고 농담도 건넴), 약먹을 시간 알려주기, 담당 의사와 화상통신, 

7가지의 공통점은, '개인화'

IBM 왓슨, 구글 등의 원천 기술을 사용할 것을 추천하며, 대신 자신의 전문 분야(domain)에 노력을 쏟기를 바란다.

기업에서 사용되는 전력의 100%를 재생에너지로 충당하자는 'RE 100' 캠페인에 참여하는 글로벌 대기업들이 늘어나고 있음. (Renewable Energy)

구글 액션 카메라 '클립스clips', 가족이나 애완동물 등을 가르쳐두면, 그 인물을 중심으로 촬영, 미소 혹은 춤, 포옹 등을 스스로 파악해 사진작가처럼 비디오 및 사진을 찍음, 피사체와 1~2미터 거리가 적절, 최고의 씬 6초 정도 클립을 찍음, 

AI 민족주의 우려, 미-중 위주로 AI기술이 집중 발전하여 유전국/비유전국 처럼 지정학 요소가 될 수 있다.

180718 주기동

DQN(Deep Q-network)을 자율주행자동차에 적용하는 시도들이 있었지만 성공하지는 못하였다. 그 이유는 DQN은 ATARI 게임처럼 불연속적인 행동을 처리하는 조작이 간단한 문제에 적합하기 때문이다. 또한 DQN은 시뮬레이션 크기를 조금만 키워도 현재의 컴퓨터 계산 용량으로 처리할 수 없는 "차원의 저주"라는 컴퓨팅 자원의 한계도 가지고 있다. Deep Deterministic Policy Gradient, DDPG가 최근에 개발되었다. 연속적인 행동을 제어할 수 있다.

강화학습 기반 자율주행차량의 제어를 위해서 DQN을 적용하면, 차량의 3가지 행동 즉, 브레이크, 핸들, 가속페달의 값이 연속적이라서 계싼량이 기하급수적으로 증가하여 차원의 저주 문제에 봉착한다.

2017년 7월에는 일본 유명 영어학습 서비스 회사인 '이온(AEON)'이 영어학습용 가상현실 콘텐츠 "영어로 대접 가이드"를 출시하고 이를 애플리케이션으로 제공하여 스마트폰용 HMD를 사용하여 VR형태로 학습이 가능하도록 하였다. 즉, 단어와 예문을 사전 학습하고 대화 상대가 나타나면 배운 것을 토대로 대화를 이어나가는 방식으로 학습, 답변에 따라 달라지는 스토리텔링 콘텐츠를 VR기술을 활용하여 서비스하고 있다.

180725 주기동

딥러닝 기법을 이용한 인공지능 기반의 소비자 선호도 분석 시스템(짬뽕라면 A,B의 고객들의 리뷰를 통해 선호도 및 특성 조사를 딥러닝 기법을 이용하였을 때와 대면 조사(관능평가)의 성능 비교 및 장점이 있다.)

대면 조사의 단점:

-표본 집단의 구성 문제

-사이즈 증가에 따른 비용 문제

-취향 평가를 위한 적합한 질문 만드는 과정 및 평가를 위한 툴만드는 게 어려움

딥러닝 결과가 실제 대면조사와 비슷하게 나옴

허마시엔셩, new retail, 

new retail전략은 2016년 10월 마윈 회장이 제시한 것으로, 온 오프라인의 벽을 허무는 onmi channel 소매와 스마트 물류를 융합한 미래형 소비유통 모델이며, ICT를 활용하여 공급망을 혁신하고 빅데이터 분석에 따라 소비자의 요구를 만족시킨다는 것이 핵심

특히 육류, 야채 등의 코너에서 정확한 수요 예측을 통해 당일 생산과 당일 판매를 함으로써 최고의 신선도를 추구하는 것이 특징

육류와 야채 등 신선식품의 수요를 높은 정확도로 예측하고 당일 판매의 신뢰성을 보장할 수 있는 것은 철저한 고객 데이터 분석과 상품 추적 시스템을 활용하고 있기 때문

회원제를 택함, 반드시 스마트폰 전용 앱이 깔려야 쇼핑가능, 알리페이를 사용해야함, 이를 통해 방문 내역, 구매 내역 데이터 축적

전체 고객 ID를 부여하고 모든 판매 기록을 사용자마다 분석하여서 POS(계산대) 데이터 분석보다 정확도 높일 수 있음

스마트폰 앱으로 상품 포장과 가격표에 붙어있는 바코드 및 QR코드를 읽으면 상품에 관한 설명을 얻을 수 있음(생산지, 수확일, 가공일, 매장까지의 배송내역 등) 심지어 물고기 한마리마다 QR코드가 붙어있음

구매 후 현장에서 즉석 조리가 가능, 고객이 해산물을 수조에서 꺼내 결제한 다음, 조리 카운터에서 조리법과 양념을 지정하면 매장 내 상주 요리사가 즉석에서 요리를 해옴, 이걸 grocery + restaurant = grocerant라 한다. (미국, 유럽, 중국에서 유행)

스마트폰으로 주문하고 배송 받는 것이 가능, 30분 내에 배송해줌, 매장에서 대략 3km 이내 거리인 경우, 앱으로 매장에 있는 상품을 주문하면 30분 이내에 받을 수 있으며, 주문이 들어가면 점원이 매장에서 상품을 선택하고 허마시엔셩의 오토바이 퀵서비스를 이용해 배송함

경쟁업체 7Fresh는 허마시엔셩과 유사하되, 차별성으로는 고객을 자동으로 따라다니는 무인 자율 주행 쇼핑 카트, 셀프 계산대에서 얼굴 인식 인증 결제 도입 등이 있음

showrooming족, 즉 매장에서는 상품만 체크하고 실제 구매는 인터넷에서 하는 사람들, 쇼루밍 족을 위해 매장에는 재고가 있지만 쇼핑몰 사이트에서는 품절인 상품이 있다면 그 사실이 가격표에 표시되게하여 낭패를 보지않게 해주며, 각 가격표는 온라인과 연동하여 온라인 쇼핑몰의 가격과 실시간 연동되어 있다.

유튜버들의 축제, 비드콘(VidCon)

유튜버는 동영상 UCC(User Created Contents) 사이트인 유튜브에서 인기를 얻고 있고 영향력이 있는 인플루언서(influencer)들을 총칭하는 말

2018년 축제에 어린이와 청소년, 그리고 여성참가자가 많음

주최하는 곳은 유튜브나 모회사인 구글이 아니라, 컨퍼런스 이름과 같은 비드콘이라는 기업이고 올해로 9번째 행사를 주최함

안내 로봇, 아이들의 집단 괴롭힘을 피할 방법 학습

아이들의 경우 로봇의 길을 비켜달란 부탁에 무시하거나 여러 명의 어린이가 로봇을 둘러싸고 발로 차거나 공을 던지는 등의 폭력적 행동을 보이기도 함

이를 해결하기 위해 아이들의 행동 패턴 및 폭력 행위 모델을 포함한 시뮬레이션 학습용 알고리즘 '회피 기동 시스템(Escape Maneuver System)을 개발함

알고리즘의 핵심은 폭력이 발생할 가능성이 높은 상황이라고 판단되면, 로봇이 원래의 경로를 변경하거나 목적지를 변경하도록 하는 것임(사람과 조우했을 때, 상호작용 시간, 인구 밀도, 1.4m 이하의 사람이 있는지 등을 감지하며, 위험이 감지될 경우 1.4m 이하의 사람들로부터 달아나 키가 큰 사람의 그룹이나 인구밀도가 높은 장소로 이동함)

날짜+영어표현

주말에 총정리

(내일은 켜자마자영단어에있는거 옮기기)

cortically

sensualism

phubbing

coital

assertive

supine

panacea

kindergartener

gossamer

meridian

voiceover

devolve

heist

dachshund

cynic

live a decadent life

make biased calls

swoon

humongous

arable

agnostic

pawn off

fine-grained

circumplex

latch

in hidsight

fete

fiddle

melt away

window pane

polysemy

invariably

syntactical

cold start

legend

granularity

factoid

multiple hops

prune

downstream

grid-search

out of the box

nil

hapax legomenon

gestapo

scaffold

mescaline

ad hoc

topical

leapfrog effect

tendril

tush

shook(shake)

cheek

drool

lightsaber

faint

mermaid

bang(앞머리)

jack o lantern(할로윈 호박)

I pity the fool(난 그 어리석은 놈을 동정하지(나에게 잘못한 그새끼 걸리면 뒈진다 류의 catchphrase))

I forgot my combination(combination은 열쇠 비밀번호)

late pass(초중고딩들 지각사유서)

killer handshake(악수할때 특이하게 하는 방법 중 하나)

electives(선택과목들)

emasculate(무기력하게 느끼게 만들다)

giggly(낄낄거리는)

imputation

futuristic

WBS(Work Breakdown Structure, 소프트웨어 공학 쪽 용어)

SOW(Statement of Work, Scope of Work)

IR(Investor Relations)

PR(Public Relations)

HIS(Hospital Information System)

EMR(Electronic Medical Record)

PHR(Personal Health Record)

replenishment

rosary

faint music

chit chat

dork

tantalize

kindred spirits

wrecks it for me

RV(recreational vehicle)

play dead

admission by that name

cog in a network

barrel of a gun

wasp

feisty

dysfunctional family

acrimonious

extubate

right wing extremist

huckleberry

cock a gun

splinter

leg up

sea change

use it or lose it

intrepid

collar

anaphora

fleece

surf and turf

snippet

wide berth

irons in the fire

bipolar

머신러닝 기본 정리(각 키워드 핵심 내용 말할 수 있어야)

Learning, cost-sensitive learning, 

Inference

open-set protocol/closed-set protocol

hard (negative) mining

Logistic Regression

Naive Bayes

holdout method(non-exhaustive), k-fold cross-validation(non-exhaustive), leave p out cross validation(exhaustive), stratification, 

DB(Data Base), ElasticSearch, 

NLP(Natural Language Processing), LSI(Latent Semantic Indexing), LDA(Latent Dirichlet Allocation), CBOW(Continuous Bag Of Words), Skip-gram(Hiererchical Softmax, Negative Sampling, Subsampling frequent words), FastText(Subword-Information Skip-Gram), IF-IDF, Skip-thought, Co-occurence matrix

(Directed/Undirected)Graphical Model, CRF(Conditional Random Field), HMM(Hidden Markov Method), 

Generative/Discriminative Model

Kernel Method(Positive-Definite Kernel, RKHS(Reproducing Kernel Hilbert Space), Representer Theorem)

Production Quantization

SIFT(Scale-Invariant Feature Transform)

Deep Residual Learning

k-means clustering

k-nearest neighbors

instance-based, model-based,

GAN(Generative Adversarial Network), 

Robo-Advisor

Deep Taylor Decomposition

self-attentive sentence embedding

EM algorithm

Gibbs Sampling

topic model에서의 perplexity, coherence

ReLU, Swish, 

learning rate, iteration, batch size, epoch

batch/standard gradient descent, stochastic gradient descent, mini-batch gradient descent

batch normalization??

unsupervised learning, supervised learning, semi-supervised learning(PU learning)

macro-averaging, micro-averaging,

uniform distribution

hypergeometric(N개 중 M개가 빨간거, K개를 뽑는데 빨간것의 개수가 x일 확률, 정상/불량으로도 가능)

bernoulli(1번 시도 중 성공(x=1)확률)

binomial(N번 시도 중 x번 성공할 확률)

negative binomial(K번째 성공까지 시도한 횟수가 x번일 확률)

geometric(1번째 성공까지 시도한 횟수가 x일 확률)

poisson(주어진 시간 구간 동안 사건이 일어난 횟수)

gamma(sub:chi-squared with degree p of freedom, exponential, related:Weibull, inverse-gamma)

Normal(related:lognormal, cauchy)

(beta부터정리)

Kuller Leibler Divergence(DL(P||Q))

Frobenius norm

textual entailment

self-attention

scikit-learn tokenizer

Pearson Correlation Coefficient, Spearman's Correlation Coefficient

Deep Taylor Decomposition

A Structured Self-attentive Sentence Embedding

논문정리

2018, Multi-task learning for author profiling with Hierarchical Features

내용:

character-level feature representation, 한 word w당, char sequence얻고, 각 char마다 one-hot encoding한 다음에 weight W 곱, 이후 각 char마다 얻어진 representation을 LSTM1 input으로 사용, 이후 각 char마다 얻어진 LSTM hidden state 중 마지막 char에 해당하는 state를 word의 representation으로 보고, 각 word의 representation들을 다시 LSTM2에 넣고 LSTM2의 마지막 word에 해당하는 hidden state를 non-linear layer 하나 통과 시킨 것을 document의 character-level feature로 사용(T-dim)

word-level feature representation, 한 document x당, 여러 filter, 여러 window size로 CNN을 돌려 여러 features를 얻은 다음 max-over-time pooling사용하여 얻은 것을 fully connected non-linear layer 통과시킨 것을 document의 word-level feature로 사용(T-dim)

topic-level feature representation, 구축한 LDA를 바탕으로, 한 document의 topic distribution을 non-linear layer 통과시킨 것은 document의 topic-level feature로 사용(T-dim)

이후 3개의 representations을 pointwise multiplication한 결과를 softmax에 넣어 classification(남자/여자, 나이, job), multi-task

학습은 cross-entropy 함수를 각 task마다 L_age, L_gender, L_job 설정한 뒤, L=L_age + L_gender + L_job한 L을 minimize하게 learning

의의:

topic level representation없이 했을 때가 성능이 가장 떨어짐, 따라서 topic level feature의 영향력이 크다

multimodal, early fusion을 사용한 것이고, pointwise multiplication이용

2015, A Review and Meta-Analysis of Multimodal Affect Detection Systems

핵심:

MM과 UM의 90가지 결과들을 비교해서, 언제 MM쓰는게 좋은지 안좋은지 분석

Research Questions:

2015년 당시 MM의 trends?(training data로 뭘 쓰는지, fusion은 어케하는지, 등)

MM을 써서 나타난 효과가 무엇인지?

시스템레벨로봤을 때, MM의 구체적형태를 보고 accuracies를 predict할 순 없는지

결론:

MM쓰면 modest하게 improvement가 보통 있더라

왜 modest정도밖에 안되냐?

multimodal data를 활용을 덜해서? 

multimodal model이 덜 complicated해서?

애초에 애매하게정의된 emotion이라는 것에 대한 연구가 부족해서?

recommendations for future work

1. 높은 정확도의 nonauthentic context, person dependent 보다는 naturalistic context의 낮은 정확도가 훨씬 값어치가 있다.

2. 아무리 좋은 결과라도 비교가 없으면 덜 중요해진다.

3. 혼동 및 좌절 같은 감정에 대한 탐색해보기

4. model-fusion with time-varying relationships among different modalities

5. crowd-sourcing 혹은 적은 annotated data만으로도 가능한 semisupervised learning 이용

2018, Multimodal Machine Learning:A Survey and Taxonomy

2018, Efficient Large-Scale Multi-Modal Classification

2017, Deep Multimodal Learning, A survey on recent advanced and trends

2018, Deep Imbalanced Learning for Face Recognition and Attribute Prediction

2018, Recent Trends in Deep Learning Based Natural Language Processing

2017, A Structured Self-attentive Sentence Embedding

2017, Distance measures in author profiling

2018, Emphasizing personal information for Author Profiling_ New approaches for term selection and weighting

2009, LDA를 이용한 대용량 블로그 문서 처리

총 데이터 개수 1000

A인 경우 20

B인 경우 980

따라서 Event Rate(A) = 2%

이럴 때 쓸 수 있는 방법이 무엇이 있을까?

1. Data level에서

Random Under-Sampling

:B를 다 쓰는게 아니라, 비복원으로 몇개만 뽑아쓰기(ex:10%), 

A인 경우 20

B인 경우 98

Event Rate(A) = 20/118 = 17%

장점:데이터를 적게 사용하므로 run time과 storage prob을 improve

단점:

정보 손실

10%만 뽑은 98개가 980개를 대표하지 않은 biased sample이 될 수도 있다.

Random Over-Sampling

:A를 다 복사해서 쓰기(ex 20배)

A인 경우 400

B인 경우 980

Event Rate(A) = 400/1380 = 28.9%

장점:

정보 손실이 없다

Random Under-Sampling보다 성능이 좋을 때가 많다

단점:overfitting이 일어날 확률이 높아짐

Cluster-Based Over Sampling

:A를 KNN, B를 KNN 각각 clustering한 다음에 each cluster of A의 개수가 다 같게 oversampled, each cluster of B의 개수가 다같게, A의 size와 B의 size가 같게 oversampled한다.

장점:each cluster의 크기가 다를 때 좋음

단점:overfitting이 일어날 확률이 높아짐

Informed Over Sampling:Synthetic Minority Over-sampling technique(SMOTE)

:A에서 몇개를 뽑아 사용하되, 걔를 완전히 복사하기보다 Synthetic Instance(합성 유사 사례)를 만들어 사용한다.

장점:

Random Over-sampling할 때 생기는 overfitting 문제를 완화시킨다.

정보 손실이 적음

단점:

Synthetic Instance를 만들 때 다른 class와 overlapping할 것을 고려하지않고 진행될 때가 생겨서 overlapping가능성이 더 늘어난다.

데이터가 high dimensional인 경우 효과적이지 못하다

Modified Synthetic Minority Over-Sampling Technique(MSMOTE)

:A에서 몇개를 뽑아 Safe samples/Border samples/Noise samples로 분류한다. (Safe는 classifier의 성능을 높혀줄, Noise는 classifier의 성능을 낮게만드는, Border는 Safe와 Noise에 넣기 애매한 놈들), 이후 synthetic Instance를 만든 다음에 Safe sample은 kNN중 택해 사용하고, Border Sample은 가장 가까운 것만 synthetic으로, Noise sample의 경우에선 뽑지 않는 방법을 이용한다.

2. Algorithmic Ensemble Techniques

Bagging Based

:전체 데이터에서 복원추출로 Sample을 N개 만들고, 각 Sample마다 Classifier를 만들어서, Classifier를 10개 사용한 Classifier를 만드는 것이다.

장점:

Stability와 accuracy 상승

variance를 낮춤

overfitting 가능성 낮춤

misclassification rate를 낮춤

noisy data인 경우 boosting보다 성능 좋음

단점:각각의 classifier들이 성능이 어느정도 괜찮아야만 효과가 있음

1. [내 집 짓기] 내 손으로 내 집 짓기 꿈 실현 …황토·볏짚·소금집…자연에 한발 더

http://news.mk.co.kr/newsRead.php?year=2012&no=351879

2. 전국흙집짓기운동본부

http://ecovillage.or.kr/index.php?mm_code=166&sm_code=180

3. [동영상] 목조주택 시공과정 기초공사부터 완공까지

http://www.archros.net/woodenhouse_building_process/

4. 와타나베의 건물탐방

https://www.youtube.com/watch?v=uezuzEQYj7w&list=PLwmX4V11kWD5hajwQX79VdTMvVqH--rrM

5. 윤세상의 집짓는 이야기

https://m.blog.naver.com/PostList.nhn?blogId=dabinyss

시공사도 건축가도 안 알려주는 건축주만이 알려줄 수 있는 집짓기 진실

와타나베의 건물탐방

아파트에서 살았던 기억은 꿈에 안 나오지만, 단독주택에서 살았던 기억은 꿈에 나온다고 한다.

32평형 아파트의 실사용 면적은 25평 정도인 데 반해, 단독 주택은 분양면적이 실사용면적과 동일했다.

건축주가 가장 빠지기 쉬운 오류는 시공에 대한 지식이 해박해야 시공자에게 당하지 않는다고 생각하는 것이다. ... 건축주가 시공상의 잘못된 점을 하나하나 찾고 따지는 데 에너지를 쓰는 것보다 스위치나 조명의 위치, 타일 등 내가 지금 선택해야할 것에 집중하는 것이 좋은 집을 만드는 지름길이다.

건축주로서 어떠한 책을 먼저 읽는 것이 좋을까? 가장 먼저 읽어야할 책은 '집에 대한 철학을 담은 책'이다. 그 이유는 살고 싶은 집이 어떠한 집인지에 관한 확고한 생각이 있어야 성공한 건축주가 될 수 있기 때문이다. 

공간만으로도 인간의 감정에 직접적인 영향을 미친다. ... 살던 집에서 생각의 틀이 만들어진다고 했다. ... 천장이 30cm 높아지면 창의적 문제 해결 능력이 2배 높아진다고 한다. ... 이렇게 천장의 높낮이와 빛이 들어오는 양에 따라 완전히 다른 분위기와 감정을 느낄 수 있다. 

같은 건축가에게 설계를 맡겼더라도 건축주에 따라 집의 퀄리티가 매우 달라질 수 있다. ... 사람, 특히 자신과 가족에게 이로운 공간인지를 판단할 수 있는 능력을 말한다. ... 명작 주택들은 사진으로 봤던 것과 실제로 가서 느껴지는 것들이 완전히 달랐다.

건축 작품 감상법

1. 건축 작품이 앉혀진 대지를 둘러본다. 해가 떠있는 위치, 대지의 크기, 어떠한 방향으로 어떻게 앉혀 있는지를 파악한다.

2. 건축물의 외관을 한바퀴 돌며 감상한다. 외장재는 어떤 재료인지, 색은 어떠한지를 보고 그 색이 나의 취향에 맞는지를 본다.

3. 현관부터 주방과 거실과 각 방의 동선과 거리, 관계성을 직접 걸어 다녀보고 발걸음을 재어본다. 실제로 산다고 생각해보고 시뮬레이션을 해본다. 예를 들면 아침에 일어나 씻고 주방과 식당에 가 밥을 먹고 밖으로 나가는 동선, 빨래를 해 널고 개서 옷장에 집어넣는 동선 등을 공간별로 돌아다니면서 직접 경험하는 것이다.

4. 층고와 폭 등의 치수는 어느 정도가 좋은 지를 본다. 

5. 내부 각 공간에서 창으로 보이는 풍경, 시간대별로 들어오는 빛을 체감해 본다. ... 아침, 오후, 노을이 질 무렵 등 세 가지 시간대를 모두 볼 수 있으면 가장 좋다.

6. 인테리어 자재의 색과 마감 방식, 가구 및 액세서리의 형태와 종류를 본다. 바닥재, 벽의 색상, 타일의 종류, 가구, 조명, 손잡이, 수전, 스위치 등 내부 마감의 디테일을 관찰해 보는 것이 필요하다. 

이렇게 하면 건축가에게 무엇을 요청해야 할지 알 수 있고 건축가가 이야기하고 제시하는 공간을 이해하는 데 큰 도움이 된다. ... '로망'인 공간은 굳이 넣어봤자 그만큼 자주 사용하기 어렵다. 지하를 파서 영화관을 만들면 평생 영화관에서 신작 영화를 볼 수 있을 만큼 이상의 돈이 들어간다. 수영장 또한 개인이 관리하기 여간 까다롭지 않아 인근 풀빌라나 워터파크에 가는 것이 훨씬 나을 수 있다.

2018.03.29

Question:

자연수 n을 입력받아, n의 각 자릿수의 합을 출력하게 하세요. Ex) n=123이면 출력값은 1+2+3=6

import java.util.*;

public class Solution {

    public static int solution(int n) {

        int answer = 0;

        int tmp;

        int c = (int) Math.log10(n);

        for (int j = 1 ; j<=c+1 ; j++) {

            tmp = n%10;

            answer += tmp;

            n = n/10;

        }

        return answer;

    }

    public static void main(String args[]) {

    System.out.println("n의 각자릿수의 합은 : " + Solution.solution(123));

    }

}

혹은

import java.util.*;

public class Solution {

    public static int solution(int n) {

        if (n == 0) {

         return 0;

        }

        else {

     return n%10 + solution((n - n%10)/10);

     }

    }

    public static void main(String args[]) {

     System.out.println("n의 각자릿수의 합은 : " + Solution.solution(123));

    }

}

알 수 있었던 점:

1. 메소드를 static으로 선언하면 객체생성없이 사용할 수 있다.

2. (int) double하면 double의 정수부분만 남게 된다.(-2.3은 -2로, 2.3은 2로)

3. main함수는 반드시 static void가 붙는다. static은 JVM에서 main함수를 찾기 위함이고, void는 프로그램 끝으론 그 출력값을 사용하지 않으므로

4. tmp는 사실상 필요없고 answer += n%10;해도 됐었다.

5. 자연수의 자릿수를 알아내는 데에 로그(log)를 사용하지 않고도 가능한 방법으로는

String[] arr = Integer.toString(n).split(""); // 즉 n을 str으로 만들었다가 그것을 split해서 str 배열로 만들어서 arr의 length를 세기

String nStr = String.valueOf(n); // n을 str으로 만들어서 str의 length를 세기, 이후 Integer.parseInt사용해서 str을 int로

6. main함수의 위치는 가독성을 위해 제일 하단에 둔다. 클래스 내에 어디다 두든 상관은 없음

7. 모든 반복문은 순환문(recursion)으로 바꿀 수 있다. 순환문으로도 써보았다.

2018.03.30

Question:

길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.

1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.

import java.util.*;

public class Solution {

   public static boolean solution(int[] arr) {

      boolean answer = true;

      Arrays.sort(arr);

      answer = Solution.src(arr, arr.length);

      return answer;

   }

   public static boolean src(int[] arr, int i) {

      if(i==0) {

         return true;

      }

      else {

         if(Arrays.binarySearch(arr, i) < 0) {

            return false;

         }

         else

            i -= 1;

            return true&Solution.src(arr, i);

      }

   }

   public static void main(String args[]) {

      int[] a= {1,2,4,5};

      System.out.println(Solution.solution(a));

   }

}

혹은

import java.util.*;

class Solution {

    public boolean solution(int[] arr) {

        boolean answer = true;

        Arrays.sort(arr);

        if (arr[0]==1 && arr[arr.length-1]==arr.length)

            answer=true;

        else

            answer=false;

        return answer;

    }

}

혹은

(sort를 쓰지않고)

import java.util.*;

class Solution {

    public boolean solution(int[] arr) {      

        int k = arr.length;

        int[] temp_arr = new int[k+1];

        for(int i = 0 ; i<arr.length ; i++) { 

            if(arr[i]>arr.length) {

               return false;

            }

            else {

                temp_arr[arr[i]]++;

            }

        }

        for(int j =1 ; j<=arr.length ; j++) {

            if (temp_arr[j] != 1)

                return false;

        }

        return true;

    }

}

알 수 있었던 점:

1. 만약 필요조건인, int[] arr의 각 정수의 모든 합 == (arr.length*(arr.length+1))/2 를 넣어서할 수도 있지만, 그렇게 효율성이 늘어나는건 아닌듯 하다.

2. Arrays.binarSearch(arr, int k), k가 arr에 없을 때 음수가 나오며 어떤 음수가 나오는 지도 알 수 있었다. 

예를 들면 {1,2,3,4}와 k=6이라면, k가 1보다 왼쪽인 수면 -1, 1과 2사이 수면 -2, 2와 3사이 수면 -3, 3과 4사이수면 -4, 4초과이면 -5

3. 첫번째 방법은 sort에 binarySearch까지 반복으로 쓰니까, 효율성이 굉장히 떨어져서 통과하지 못했다.

4. 재귀함수를 쓰게되면, 함수호출이 잦아지고, 그럼 효율성이 떨어진다고한다. 아직까진 구체적인 그 의미를 모르겠다. 함수호출시 컴퓨터의 자원이 어떻게 쓰이는 지를 모르기 때문이다.

5. 마지막으로 가장 최적화시킨 방법, index를 활용하는 방법이다. 배열의 index에 자연수를 포함하므로, for문을 2번 써서 가능했다.

6. 기본적으로 Arrays.sort(arr)는 input array의 size에 따라 size가 적을 땐 Insertion Sort, 클 땐 Merge Sort를 사용한다. 각각의 방법을 공부해야할 필요가 있다.

2018.03.31

Question:

(1) 임의의 자연수n에 대해 n을 소인수분해하는 알고리즘을 조사하여라.

(2) 완전수 구하기. 자연수 n을 input으로 넣고, 그것보다 같거나 작은 자연수 중에서 완전수들을 output으로

https://www.alpertron.com.ar/ECM.HTM // elliptic curve method와 self-initializing quadratic sieve를 써서 계산해주는 웹사이트

speaker independent:training이 필요없는 음성인식

speaker dependent:training을 필요로하고 그럼 정확도가 더 올라가는 음성인식

DTW(Dynamic Time Warping)

LPC(Linear Predictive Coding)

Cepstrum

HMM(Hidden Markov Model)

n-gram language model

back-off model(multiple length n-gram model)

maximum likelihood estimation

generative model:(input,output)의 joint distribution을 모델링하고 goal로 삼는 방법

discriminative mode:(output|input)의 conditional distribution을 모델링하고 goal로 삼는 방법

feedforward ANN

RNN

LSTM(Long short-term memory)

vanishing gradient problem이 없으며

discrete time steps의 수천번 이전의 내용을 기억하는 효과가 있어서 speech recognition에 유용

acoustic model:audio signal과 phonemes(음소)사이의 관계를 밝히는 모델링

language model:words의 sequence에 해당하는 distribution model

In the long history of speech recognition, both shallow form and deep form (e.g. recurrent nets) of artificial neural networks had been explored for many years during 1980s, 1990s and a few years into the 2000s.[47][48][49] But these methods never won over the non-uniform internal-handcrafting Gaussian mixture model/Hidden Markov model (GMM-HMM) technology based on generative models of speech trained discriminatively.

GMM(Gaussian mixture model)

TDNN(Time Delay Neural Networks)

Autoencoder

RNN-CTC model

LAS(Listen, Attend and Spell, Attention-based ASR model)

LSD(Latent Sequence Decomposition)

WLAS(Watch, Listen, Attend and Spell)

MD-LSTEM(2D-LSTM, Multidimensional LSTM)

일단 머신런이에 싹다 넣고 다 이해되면 정리

시간 복잡도(time complexity)

실행 시간은 실행환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등)

따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트

연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현

데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐

최악의 경우의 시간 복잡도 (worse-case analysis)

평균 시간 복잡도 (average-case analysis)

점근적 분석(Asymptotic analysis)

데이터의 개수 n->inf일 때 수행시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법

유일한 분석법도 아니고 가장 좋은 분석법도 아니지만, 상대적으로 간단하고 알고리즘의 실행환경에 비의존적이어서 많이 사용됨

가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다.

Ο 표기법은 upper bound를 표현

Ω 표기법은 lower bound를 표현

Θ 표기법은 upper and lower bound를 표현

이진 검색(Binary Search)와 정렬(Sort)

이진 검색

오름차순으로 미리 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 

중앙값을 선택하여 target과 맞는지 비교후

맞으면 끝

중앙값>target이면 중앙값을 새로운 최댓값으로 택한다.

중앙값<target이면 중앙값을 새로운 최솟값으로 택한다.

정렬된 리스트에만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다 Ο(log_2 (n))

순차 검색과 비교하면 순차 검색은 Ο(n)으로 이진 검색이 훨씬 빠르다.

정렬

버블 정렬 혹은 거품 정렬(bubble sort)

가장 왼쪽(l)과 인접한 오른쪽(r)과 비교후 l>r이면 l<->r

이후 2번째 원소와 3번째 원소를 비교후 같은 방법

한차례 지나고나서 다시 또 한다. (다만 첫포문을 마치고나면 가장 오른쪽엔 가장 큰것이 이미 와있으므로 두번째 포문부터는 n-1까지만 하면된다.)

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)

삽입 정렬(Insertion sort)

index 1의 데이터를 0과 비교해 제자리에 둔다

index 2의 데이터를 0과 1과 비교해 제자리에 둔다.

...

index k의 데이터를 0~k-1까지의 데이터와 비교해 제자리(맞는 자리에) 둔다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)이다.

기타 정렬

퀵소트(quicksort)

합병(merger sort)

힙(heap sort)

등이 있다.

*code review부터 다시보고 정리

순환(Recursion)

순환(재귀함수)이란, 자기 자신을 호출하는 함수(메소드)를 가리킨다.

순환이 무한루프에 빠지지 않기 위한 조건이 있다.

적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. 이것을 base case라 한다. 

recursion을 반복하다보면 결국 base case로 수렴하게 recursive case를 둬야 한다.

가능하면 암시적(implict) 매개변수를 명시적(explicit)매개변수로 표현하라.

예제)(Hello를 n번 출력하는 형태)

public class Code02 { 

public static void main(String [] args) {

int n = 4;

func(n);

}

public static void func(int k) {

if (k<=0)  // base case

return;

else {

System.out.println("Hello");

func(k-1);  //recursive case

}

}

}

예제)(n까지의 합을 출력하는 형태)

public class Code03 {

public static void main(String [] args) {

int result = func(4);

}

public static int func(int n) {

if (n==0)

return 0;

else

return n + func(n-1);

}

}

예제)(실수 x의 n승 구하기)

public static double power(double x, int n) {

if (n==0)

return 1;

else

return x*power(x, n-1);

}

예제(피보나치 수열 구하기)

public int fibonacci(int) {

if (n<2)

return n; // f_0 =0, f_1 =1인 피보나치의 경우

else 

return fibonacci(n-1) + fibonacci(n-2);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 예제)

public static double gcd(int m, int n) {

if (m<n) {

int tmp = m;

m = n;

n = tmp; // swap m and n(즉 항상 first argument가 더 크거나 같게)

}

if (m%n == 0)

return n;

else 

return gcd(n, m%n);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 더 간단한 예제)

public static int gcd(int p, int q) {

if ( q==0 )

return p;

else

return gcd(q, p%q);

}

수학함수뿐 아니라 다른 많은 문제들을 순환을 이용하여 해결할 수 있다. 특히 for문, while문을 대신할 수 있다.

순환<->반복문(즉 모든 반복문도 순환으로 만들 수 있다.)

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

하지만 함수 호출에 따른 오버해드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등), 즉 순환은 프로그래밍 실행 속도에 단점이 있긴 있다.

예제(문자열의 길이 계산)

public static int length(String str) {

if (str.equals(""))

return 0;

else

return 1 + length(str.substring(1));  // str.substring(1)이란 str의 첫번째 문자를 제거한 substring을 가리킨다.

}

예제(문자열의 출력)

public static void printChars(String str) {

if (str.length() == 0)

return;

else {

System.out.print(str.charAt(0)); // str.charAt(0)란, str의 첫 문자를 리턴하는 메소드이다.

printChars(str.substring(1));

}

}

예제(문자열을 순서를 뒤집어 프린트)

public static void printCharsReverse(String str) {

if (str.length() == 0)

return;

else {

printCharsReverse(str.substring(1));

System.out.print(str.charAt(0));

}

}

(문자열의 출력 예제와 달라진 것은 else내에 출력과 호출의 순서만 바꼈을 뿐이다.)

예제(자연수를 2진수로 변환하여 출력)

public void printInBinary(int n) {

if (n<2)

System.out.print(n);

else {

printInBinary(n/2);

System.out.print(n%2);

}

}

예제(정수 배열(Array)의 합 구하기, data[0]에서 data[n-1]까지의 합)

public static int sum(int n, int [] data) {

if (n<=0)

return 0;

else

return sum(n-1, data) + data[n-1];

}

}

암시적(implicit)매개변수를 명시적(explicit)매개변수로 바꾸어라.

예제(순차 탐색, sequential search)

int search(int [] data, int n, int target) {

for (int i=0; i<n ; i++)

if (data[i]==target)

return i;

return -1;

}

(여기서 n은 명시적인데, search의 시작 인덱스인 0은 암시적 매개변수이다. 하지만 순환을 사용시 시작인덱스도 명시적으로 하자.)

예제(순차 탐색, 매개변수의 명시화)

int search(int [] data, int begin, int end, int target) {

if (begin > end)

return -1;

else if (target==data[begin])

return begin;

else

return search(data, begin+1, end, target);

}

(이렇게 시작 index를 begin으로 명시화하자. search(data, begin, end, target)으로하면 begin index부터 end index까지 target이 있는지 확인)

예제(최대값 찾기)

int findMax(int [] data, int begin, int end) {

if (begin==end)

return data[begin];

else

return Math.max(data[begin], findMaxt(data, begin+1, end));

}

예제(이진 검색, binary search)

public static int binarySearch(String[] items, String target, int begin, int end) {

if (begin>end)

return -1;

else {

int middle = (begin+end)/2;

int compResult = target.compareTo(items[middle]); // string 비교시 자바에서는 compareTo를 사용한다. target이 items[middle]보다 크면 양수, 작으면 음수, 같으면 0을 return한다. //

if (compResult == 0)

return middle;

else if (compResult < 0)

return binarySearch(items, target, begin, middle-1);

else

return binarySearch(items, target, middle+1, end);

}

}

예제(미로찾기)

Recursive한 생각

현재 위치에서 출구까지 가는 경로가 있으려면

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

예제(미로찾기의 슈도코드1)

boolean findpath(x,y)

if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell; //visited cell개념을 넣지 않으면 무한 루프에 빠질 수 있다.

for each neighbouring cell (x',y') of (x,y) do

if (x',y') is on the pathway and not visited

if findpath(x',y')

return true;

return false;

예제(미로찾기의 슈도코드2)

boolean findpath(x,y)

if (x,y) is either on the wall or a visited cell

return false;

else if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell;

for each neighbouring cell (x',y') of (x,y) do

if findpath(x',y')

return true;

return false;

예제(미로찾기의 실제 자바 코드)

public class Maze {

private static int N=8;

private static int [][] maze = {

{0, 0, 0, 0, 0, 0, 0, 1},

{0, 1, 1, 0, 1, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 0, 0, 1, 1, 0, 0},

{0, 1, 1, 1, 0, 0, 1, 1},

{0, 1, 0, 0, 0, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 1, 1, 0, 1, 0, 0},

};

private static final int PATHWAY_COLOUR = 0; // white

private static final int WALL_COLOUR = 1; // blue

private static final int BLOCKED_COLOUR = 2; // red

private static final int PATH_COLOUR = 3; // green

public static boolean findMazePath(int x, int y) {

if (x<0 || y<0 || x>=N || y>=N)

return false;

else if (maze[x][y] != PATHWAY_COLOUR)

return false;

else if (x==N-1 && y==N-1) {

maze[x][y] = PATH_COLOUR;

return true;

}

else {

maze[x][y] = PATH_COLOUR ;

if (findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePath(x,y-1)) {

return true;

}

maze[x][y] = BLOCKED_COLOUR; // dead end

return false;

}

}

public static void main(String [] args) {

printMaze();

findMazePath(0,0);

printMaze();

}

}

예제(Counting cells in a Blob)

상황:

입력으로 binary image를 받는다. 그리고 하나의 좌표(x,y)도 받는다.

각 픽셀은 background pixel이거나 혹은 image pixel

서로 연결된 image pixel들의 집합을 blob이라고 부름

상하좌우 및 대각방향으로도 연결된 것으로 간주

(x,y)가 image pixel로서 택해졌다면, 그 pixel이 속한 blob의 총 image pixel의 개수를 return하는 문제이다.

(x,y)가 background pixel이면 0을 return

슈도코드:

if (x,y)가 이미지 밖이면 

결과는 0

else if (x,y)가 image pixel이 아니거나 already counted면

결과는 0

else

(x,y)를 다른 색(예를 들면 빨강)으로 색칠하라; // 이미 카운트 됐음을 표시

1+(인접한 영역의 count값);

실제 코드

private static int BACKGROUND_COLOR = 0;

private static int IMAGE_COLOR = 1;

private static int ALREADY_COUNTED = 2;

public int countCells(int x, int y) {

if (x<0 || x>=N || y<0 || y>=N)

return 0;

else if (grid[x][y] != IMAGE_COLOR)

return 0;

else {

grid[x][y] = ALREADY_COUNTED;

return 1 + countCells(x-1, y+1) + countCells(x, y+1)

+ countCells(x+1, y+1) + countCells(x-1, y) 

+ countCells(x+1, y) + countCells(x-1, y-1)

+ countCells(x, y-1) + countCells(x+1, y-1)

}

}

예제(N-queens problems)

상황:

NxN 체스판에 N개의 말을 놓는다. 

이때 각 말은 같은 행, 같은 열, 같은 대각선 상에 놓이지 않게 N개의 말을 놓을 수 있는지?에 대한 대답

Backtracking이용

일련의 선택을 하다가 조건에 부합하지 않게 되면, 그 이전의 선택으로 거슬러 올라가 번복하는 방법

각 행에는 1개의 말만 올 수 있음을 인지하고

0행에서 (0,0)에 말을 놓은 뒤

1행에서 (1,2)에 말을 놓은 뒤..... 쭉 하다가 안된다는 것을 깨달으면 그 이전의 행에서 놓은 말을 이동시킨다.(열을 증가하는 방향으로)

상태공간트리(State Space Tree)이용

뿌리에 Start를 두고

뿌리와 거리가 1인 노드들에는 0행에 놓일 0번 말의 가능한 좌표를 vertex에 표시하여 둔다

뿌리와 거리가 2인 노드들에는 이전 vertex(좌표)에서 1행에 놓일 1번 말의 가능한 좌표를 vertex에 표시하여 둔다.

.... 반복

해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드sequence에 해당한다. 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

트리를 탐색하는 기법들

깊이 우선 탐색, (이후에 정확한 정의를 파악), 일단 위의 예제에서 backtracking을 상태공간트리에 적용하면 그게 깊이 우선 탐색

실제코드(recursion과 stack을 사용할 수도 있다. 아래는 recursion을 이용한 코드이다.)

int [] cols = new int [N+1]; // 매개변수 level은 현재 노드의 level(트리의 root에서 떨어진 길이)을 표현, cols[i]=j 는 i번째 말이 (i행,j열)에 놓였음을 의미

boolean queens(int level) { // 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정, level을 넣음으로써 정확한 위치는 아니지만 몇행인지는 앎

if (!promising(level))

return false;

else if (level==N) { // level이 N인데 promising(level)이 true가 나왔으니까 끝난것

for (int i=1 ; i<=N ; i++)

System.out.println("(" + i + ", " + cols[i] + ")");

return true;

}

for (int i=1 ; i<=N ; i++) {

cols[level+1] = i;

if (queens(level+1))

return true;

}

return false;

}

boolean promising(int level) {

for (int i=1 ; i<level ; i++) {

if (cols[i]==cols[level]) // level번째 말이 이전의 말들과 같은 열에 있는 경우를 검사

return false;

else if (level - i==Math.abs(cols[level] - cols[i]) // level번째 말이 이전의 말들의 영향받는 대각선에 있는 경우를 검사

return false;

}

return true;

}

(실제 사용시 queens(0)으로 호출하면 된다.)

(이해를 하기위해 queens(0)을 생각해보기)

예제(powerset 출력하기)

상황:

주어진 집합의 모든 부분집합을 출력하는 문제

전략:

만약 {a,b,c,d,e,f}라면 

a를 포함하지 않는 부분집합을 나열한 후,

각각의 부분집합마다 a를 포함시켜 나열하면 된다.

(b를 포함하지 않는){c,d,e,f}의 모든 부분집합들에 a를 추가한 집합들을 나열하고

(b를 포함하는){c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열

....

즉 recursion을 해나간다.

powerSet이란 함수를 설정하는데에 있어서 argument를 집합1개만 받게 설정하면 recursion과정에서 각각의 부분집합마다 포함시켜 나열하는 경우가 해결이 안된다. 

실제 코드:

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};

private static int n=data.length;

private static boolean [] include = new boolean [n];

public static void powerSet(int k) { // k와 include를 통해 상태공간트리에서 현재 위치를 알려주는 것이다.

if (k==n) { // 상태공간 트리에서 현재위치가 가장 밑인 경우

for (int i=0 ; i<n ; i++)

if (include[i]) System.out.print(data[i] + " "); // P를 출력

System.out.println();

return;

}

include[k]=false; // data[k]를 포함하지 않는 경우

powerSet(k+1);

include[k]=true; // data[k]를 포함하는 경우

powerSet(k+1);

}

(data[k], ..., data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,...,k-1인 원소를 추가하여 출력하라는 mission)

(처음 이 함수를 호출할 때는 powerSet(0)로 호출한다.)

상태공간트리 활용

해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리

트리의 모든 노드들을 방문하면 해를 찾을 수 있다.

루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.

k=0일땐 공집합

k=1일땐 공집합이거나 a만 있거나(k=0일때의 집합에 a를 안넣거나 넣거나)

k=2일땐 k=1에서의 각각의 집합에서 b를 넣거나 안 넣거나를 만듦

k=3일땐 k=2에서의 각각의 집합에서 c를 넣거나 안 넣거나를 만듦

정렬

종류:

Simple하고 slow:Bubble sort, Insertion sort, Selection sort, 

조금 복잡하지만 fast한:Quick sort, Merge sort, Heap sort, 

그 외:Radix sort

기본적인 정렬 algorithm

Selection Sort:

1. 가장 큰 값(M)을 찾는다.

2. 가장 오른쪽 값(R)과 exchange(정렬한다.)

3. 가장 오른쪽 값을 제외하고 1,2를 다시 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수:n-1, n-2, ..., 2, 1, 그리고 교환은 상수시간

Bubble Sort

1. 첫번째 값과 두번재값과 비교

2. 정렬(교환or유지)한다.

3. 두번째값과 세번째값과 비교

4. 정렬한다.

...반복

결과적으로 가장 큰 값이 가장 오른쪽에 오게 된다.

5. 이후 가장 오른쪽 값을 제외하고 다시 1~4를 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 안쪽 for문이 n-1,n-2,...,1번 반복, 교환은 상수시간 작업

Insertion Sort

1. 첫번째 값에 두번째 값을 끼워 넣는다.

2. 세번째 값을 이전 결과에 끼워 넣는다.

3. 네번째 값을 이전 결과에 끼워 넣는다.

...반복

즉 k-1개가 이미 정렬되어 있고 k번째 item을 끼워넣는 것을 반복하는 것

구체적으로

copy the k번째 item to tmp

k번째 item이랑 k-1번쨰 item이랑 비교, k번째가 k-1번째보다 크면 끝, 작으면 k-1번째 아이템을 오른쪽으로 덮어쓰기(shift), 

그리고 k번째 item이랑 k-2번째 item비교,... 이것을 반복

(만약 k번째 item을 k-1, k-2, k-3,...순으로비교할게 아니라, 1,2,3,...으로 비교한다면 대칭이므로 차이가 없어보이지만, 주어진게 배열이라면, 오른쪽에서부터 비교하는, 즉 k-1,k-2,k-3,...순으로 비교하는게 효율적이다. 왜냐하면 대상이 배열이기때문에 결국 k번째 item을 k-1개의 item들 사이에 끼워넣기 위해선, k번째 item보다 큰 녀석들을 결국 오른쪽으로 옮겨야하고, k번째 item보다 큰 값을 가진애들을 한번씩은 접근을 해야하기 때문이다. 즉 1,2,3,...순은 총 k-1개의 데이터를 결국 다 접근해야하는 것이고, k-1,k-2,k-3,... 순은 접근해야할 개수가 k-1개 전체가 되진 않을 수도 있다. 그래서 k-1,k-2,...순으로 비교하는 것이다.)

시간복잡도 : 최악이 O(n^2) = n(n-1)/2, 최선이 O(n) = n-1, 평균도 O(n^2)

for 루프는 n-1번 반복, i번째 item을삽입(Insertion)하는 최악의 경우 i-1번 비교

Merge Sort

Divide and conquer(본질적으론 recursion과 유사)

분할정복법):예전에 로마 제국이 주변 나라를 정복할 때, 전체를 통채로 정복하기 보다는 작은 것으로 분할하여 정복한 것과 유사함

분할:해결하고자 하는 문제를 작은 크기의 "동일한" 문제들로 분할(recursion할 때와 비슷)

정복:각각의 작은 문제를 순환적으로 해결

합병:작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

     Merge sort    

데이터가 저장된 배열을 절반으로 나눔

각각을 순환적으로 정렬

정렬된 두 개의 배열을 합쳐 전체를 정렬<<<이게 가장 중요, 관건

9개 데이터있는 1개의 배열이 있다면, 절반으로 나누는 과정을 몇번하면 정렬된 9개의 배열을 갖게 된다.

그리고 다시 2개씩 합쳐주며 merge하는 것이다.

Merge를 하는 방법(a1<a2<a3, b1<b2<b3인 경우)

추가 배열을 만든다.

a1과 b1 중 작은 것을 추가배열의 왼쪽에 둔다.(a1<b1이라하자)

a2과 b1 중 작은 것을 추가배열의 왼쪽에 둔다(a2<b1이라하자)

a3와 b1 중 작은 것을 추가배열의 왼쪽에 둔다(b1<a3이라하자)

...이하 반복

(a배열의 index i, b배열의 index j, 추가배열의 index k중 k는 항상 +1, i는 a가 작을때 +1, j는 b가 작을 때 +1)

(sub배열중 1개가 완료되면 나머지 sub배열을 그대로 가져오면된다.)

알고리즘:

mergeSort(A[], p, r) { // 배열 A[]을 index p에서 index r까지 배열

if (p<r) then {

q = (p+q)/2 ; // p, q의 중간 선택

mergeSort(A, p, q); // 전반부 정렬

mergeSort(A, q+1, r); // 후반부 정렬

merge(A, p, q, r); // 합병

}

}

merge(A[], p, q, r) {

정렬되어 있는 두 배열 A[p,...q]와 A[q+1,...,r]을 합하여 정렬된 하나의 배열 A[p,...,r]을 만든다.

}

(merge부분을 실제 자바 코드로 써보면)

void merge(int data[], int p, int q, int r) {

int i = p; // 앞 배열 index

int j = q+1; // 뒤 배열 index

int k =p; // 도움배열의 index

int tmp[data.length()]; // 도움을 줄 추가배열을 만듦

while(i<=q && j<=r) {

if (data[i] <= data[j]) {

tmp[k++] = data[i++];

}

else {

tmp[k++]=data[j++]; // k는 항상 증가, i,j는 비교해서 작을때만 증가

}

}

while ( i <= q)

tmp[k++]=data[i++]; // 남은 것들 추가로 가져오는 과정

while (j <= r)

tmp[k++]=data[j++]; // 이 2개의 while문 중 1개만 사실 실행됨

for (int i = p ; i<=r ; i++)

data[i] =tmp[i] // 원래 데이터에 도움배열 정보를 넣는 과정

}

Merge Sort의 유일한 단점:추가배열을 잡아둬야한다는 것

시간복잡도:

T(n)

=0 (n=1일때)

=T(ceil(n/2)) + T(floor(n/2)) + n (n>=2) // n은 merge하는데 비교연산의 최대횟수가 n, 사실 ceil, floor는 필요없음, n->inf일때 고려하므로

=O(n*logn))

Quick Sort

마찬가지로 Divide and Conquer

다만, divide가 다름

pivot 선택하기

어떤 값을 pivot을 선택할 지는 나중에 배우기

현재 강의 내용에선 배열의 가장 오른쪽 값을 pivot으로 선택

알고리즘 개요

1. "pivot보다 작은 것, pivot, pivot보다 큰 것"으로 분할(분할하면서 좌, 우가 정렬하지는 않음)

2. pivot 기준으로 나뉘어진 좌, 우의 부분들에 다시 recursion으로 분할

3. "합병"단계가 필요가 없다.

알고리즘

quicksort(A[], p, r) { // A[p,...,r]을 정렬한다.

if (p<r) then {

q=partition(A, p, r);

quicksort(A, p, q-1);

quicksort(A, q+1, r);

}

}

partition(A[], p. r) {

x = A[r]; // pivot넣기

i = p-1 // 작은 애들 index

j = p // 큰 애들 index

for j to r-1 {

if A[j]<=x {

i++;

exchange A[i] and A[j];

}

}

exchange A[i+1] and A[r]

return i+1;

(배열 A[p,...,r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 return한다.)

(작/큰/x로 만든 다음, 큰애들 중 가장 왼쪽인 애를 x와 exchange할 것이다.)

(작은 애들 중 마지막 값 index i, 검사하려는 값 index j, A[j]와 pivot과 비교하여 A[j]가 x보다 같거나 크면 그냥 j++(다음꺼 검사), A[j]가 x보다 작으면 A[j]와 A[i+1]과 exchange하고 i++ 그리고 j++(다음꺼 검사))

(제일 마지막에 i+1과 pivot의 exchange, 그리고 i+1을 return)

}

복잡도

partition 한번 하는데 걸리는 시간은 O(n) // 정확히는 n-1번의 비교연산

T(n)

최악의 경우는 아이러니하게, pivot이 가장 큰 값일 때, 즉 이미 정렬된 배열인 경우이다. (pivot을 항상 가장 오른쪽 값을 갖는 상황이라 한다면)

T(n) 

= T(0) + T(n-1) + Θ(n-1) = T(n-1) + Θ(n-1)

= T(n-2) + Θ(n-1) + Θ(n-2)

...

=Θ(1) + Θ(2) + ... + Θ(n-1) 

= Θ(n^2)

항상 절반으로 분할되는 경우(최선의 경우)

T(n)

=2*T(n/2) + Θ(n-1)

...

=Θ(n*logn)

항상 한쪽이 적어도 1/9이상이 되도록 분할된다면(편의상 항상 1:9일때를 고려)

T(n)

= T(n/10) + T(9n/10) + Θ(n-1) 

...

= k * Θ(n) = Θ(n*logn)

(이때 (9/10)^k * n = 1, k=log_(10/9) n )

(따라서 분할이 아주 극단적으로 일어나지 않는다면, Quick Sort는 빠르다.)

평균 시간 복잡도

A(n) = sum over all input I of size n P(I)*T(I), where P(I):I가 일어날 확률, T(I):I의 시간복잡도

P(I)를 구하기가 힘드므로 가정을 한다. P(I)=1/n!이라 가정(즉, 서로 다른 값을 갖는 배열만 고려)

A(n) 

= 2/n * sum from i=0 to i=n-1 {A(i) + Θ(n)} // pivot의 rank가 1,2,.i..,n 일 확률이 각각이 모두 1/n, 그때마다 A(i-1) + A(n-i) + Θ(n)

= Θ(n*logn)

pivot 선택하는 기준

첫번째 값이나 마지막 값을 pivot으로 선택

이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우

현실의 데이터는 랜덤하지 않으므로 정렬/거꾸로 정렬 된 데이터가 입력으로 들어올 가능성은 매우 높음

따라서 좋은 방법이라고 할 수 없음

"Median of Three"

첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택

최악의 경우 시간 복잡도가 달라지지는 않음, but 현실적인 방법이긴 함

Randomized Quick Sort

pivot을 랜덤하게 선택

no worst case instance(즉 최악의 입력은 없음), but worst case execution(즉 최악의 실행은 가능함)

(다른 방법들은 최악의 입력이 존재하지만, 이 경우는 최악의 입력이 아니라 최악의 주사위(랜덤)에 의해 최악의 실행이 가능)

평균 시간복잡도 Θ(n*logn)

그래프

개체(object)들 간의 이진관계(binary relation)를 표현하는데 사용한다.

vertex의 개수를 n, edge의 개수를 m

undirected graph, directed graph, weighted graph 등이 있다.

별말없으면 simple undirected graph를 다룬다,

그래프의 표현

undirected simple의 경우

인접행렬(Adjacency Matrix)

저장 공간:Ο(n^2)

어떤 v에 인접한 모든 노드 찾기:Ο(n)

어떤 에지 (u,v)가 존재하는지 검사:Ο(1)

Symmetric Matrix가 된다.

인접리스트(Adjacency List)

V집합을 표현하는 하나의 배열과 각 v마다 인접한 정점들의 연결 리스트

노드개수:2m(edge 하나당 2번세니까)

저장 공간:Ο(n+m)

어떤 노트 v에 인접한 모든 노드 찾기:O(d(v)) // d(v)란 degree of v 라 하자

어떤 에지 (u,v)가 존재하는 지 검사:Ο(d(u)) // u에 해당하는 배열에 있는 리스트를 다 읽어봐야 하므로

directed의 경우

인접행렬

비대칭행렬

인접리스트

m개의 노드를 가짐

weighted의 경우

인접행렬

에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장

에지가 없을 때 혹은 대각선

특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서

예:가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 inf, 대각선은 0

예:가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 inf

그래프의 순회(traversal)

모든 v를 방문하는 작업

대표적인 방법

BFS(Breadth-First search, 너비우선순회)

L_0 = {v_0} //출발노드 선택

L_1 = L_0의 모든 이웃 노드들

L_2 = L_1의 이웃들 중에서 L_0에 속하지 않는 노드들

...

L_i = L_(i-1)의 이웃들 중에서 L_(i-2)에 속하지 않는 노드들

(순회 그래프에서의 BFS, 6분40초부터 다시보기)

DFS(Depth-First search, 깊이우선순회)

컴퓨터 구조(Computer Architecture)

컴퓨터 시스템의 기본 구성:하드웨어, 소프트웨어(정보들이 이동하는 방향을 지정, 정보 처리의 종류를 지정, 이러한 동작들이 일어나는 시간을 지정해주는 명령(command)들의 집합으로, 시스템 소프트웨어(OS), 응용 소프트웨어(application software)가 있다.)

컴퓨터의 기본 구조:data read->processing->store

CPU(Central Processing Unit):data processing의 처리 길이에 따라 32bit, 64bit로 나뉨

Memory

-Cache Memory:CPU와 main memory간의 속도차 보정(즉 고속)

-Main Memory:반도체 기억장치 칩들로 구성, 가격 비싸고 면적 많이 차지, 휘발성, 최근에는 비휘발성 고속 액세스 메모리 SCM(Storage Class Memory)가 있음)

-Auxiliary Storage Device:저속 액세스, 저장밀도 높음, 비휘발성

I/O device:각 I/O device는 사용 data 다르고 명령어도 달라서 CPU와 직접 연결 안하고 각 I/O device별로 제어기(controller)가 있음

제어기

-상태 레지스터:I/O 장치의 현재 상태를 나타내는 비트들을 저장하는 레지스터로 준비 상태 비트, 데이터 전송확인 비트 등을 저장하는 레지스터

-데이터 레지스터:CPU와 I/O장치 사이 이동되는 데이터를 일시적으로 저장하는 레지스터, 데이터 버퍼라고도 불림

System Bus:CPU와 다른 요소들 정보 교환 통로

-Address Bus:CPU가 다른 요소들에게 주소 정보를 쏘는 통로, 일방통행

-Data Bus:CPU가 I/O장치와 데이터 전송 통로, 쌍방향

-Control Bus:제어신호선들의 집합, 일방통행, 제어신호(memory read/write, I/O read/write)

메모리 영역을 Command와 Data를 공유해서 사용 여부로 나눈 컴퓨터 구조

폰노이만 아키텍처(Von Neumann Architecture)

-하나의 메모리에 Command와 Data가 모두 저장, CPU는 한 번에 하나의 명령어만 실행가능(SISD:Single Instruction Single Data)

-명령어 처리 순서:fetch(CPU에 명령어 전달)->decode->execute->stored

-병목현상(Command읽을 때 Data못 읽음) 발생

-상대적으로 빠른 CPU의 속도를 효율적으로 사용안함

-Stored Programed 방식의 메모리 중심 구조(Stored Program:고수준 프로그래밍 언어(C 등)로 작성->컴파일->기계어 방식)

-고성능 CPU에 사용, 특히 인텔

-Cache Memory의 크기, CPU Prediction 알고리즘 등에 따라 성능 차이 큼

-저비용 소형 MCU(Micro Controller Unit, 집적 회로 안에 프로세서와 메모리, 입출력 버스 등 최소한의 컴퓨팅 요소를 내장한 초소형 컨트롤러)에 유리

하버드 아키텍처(Harvard Architecture)

-서로 다른 메모리에 Command와 Data를 각각 저장

-병목현상 없음(Command 읽기, 쓰기 병행 가능)

-하버드 마크 I의 릴레이를 사용한 극히 작은 메모리 영역으로 인한 버스 분리가 가능한 구조

-Harvard Architecture + RISC(Reduced Instruction Set Computer, ~~~)으로 성능향상

-임베디드 소형 프로세서에 사용, 특히 ARM(ARM Holdings에서 설계하는 Command set와 ISA(Instruction Set Architecture)의 총칭)계열에 사용

-2010년 이후 스마트폰이 대세->스마트폰의 CPU인 AP(Application Processor)가 확산->ARM 및 하버드 아키텍처 유명해짐

-고성능 DSP(Digital Signal Processor, 디지털 신호 처리를 위해 특별히 제작된 micro processor)개발에 유리

폰노이만 아키텍처의 문제점 해결방안

-병렬처리개념 도입(병렬처리기법(Pipeline, Super Pipeline, Super Scalar, VLIW(Very Long Instruction Word), EPIC(Explicitly Parallel Instruction Computing))

-Pipeline(한 데이터 처리 단계의 출력이 다음 단계의 입력으로 이어지는 형태로 연결된 구조, 각 단계 사이의 입출력을 중계하기 위해 버퍼가 사용될 수 있다.)

-Super Pipeline(파이프라인의 일종, 어떤 동작이 실행될 때, 그 클럭을 나누어서 다음 명령어에 대한 동작을 수행한다. 클럭이 높아짐에 따라서 나누기가 힘들어져서 잘사용안함)

(클럭(Clock):컴퓨터의 CPU 또는 디지털 회로가 일정한 속도로 작동하기 위해서는 일정한 간격으로 전기적 진동(pulse)을 공급받아야 하는데, 이 전기적 진동을 클럭이라 한다. 클럭 스피드는 Hz를 이용, 4.2GHz라 하면 초당 42억번의 사이클로 0과 1의 디지털 신호를 발생시킨다는 것을 의미, I7-7700k가 4.2GHz)

(순차회로/로직(Sequential Circuit/Logic):현재의 입력 뿐 아니라 과거의 입력 혹은 출력 값들도 함께 고려하여 현재의 출력값을 결정하는 논리회로이다, 조합회로와 기억 소자(memory element)들로 구성)

(논리회로(Logic Circuit):부울 대수(Boolean Algebra)를 이용하여 1개 이상의 논리 입력을 일정한 논리 연상에 의해 1개의 논리 출력을 얻는 회로)

(조합회로/로직(Combinational Circuit/Logic):현재 입력에만 의존하여 출력이 결정되는 논리 회로)

(기억 소자(Memory Element/Cell):기억 장치의 가장 최소 단위. 보통 한 비트를 기억할 수 있는 플립플롭이나 자기 코어, 축전기 하나를 가리킨다.)

(플립플롭(Flip-Flop) or 래치(latch):1비트의 정보를 보관, 유지할 수 있는 회로이며 순차 회로의 기본 요소이다.)

-Super Scalar(Pipeline을 여러 개 두어 명령어를 동시에 실행하는 기술, 동시에 처리(투입/완료)가 가능한 명령어 개수(N)에 따라 N-issue, N-wide, N-way super scalar로 불린다.)

-VLIW(Very Long Instruction Word, 여러 opcode 필드가 있는 긴 명령어 하나에 독립적인 연산 여러개를 정의하고 이들을 한꺼번에 내보내는 명령어 구조 집합의 종류이다.)

(opcode, operation code:연산(operation)종류를 나타내기 위한 코드, 즉 덧셈을 ADD, 제곱근을 SQR 등으로 기억에 편리하도록 기호화한 것을 가리킨다.)

-EPIC(Explicitly Parallel Instruction Computing, 사용자의 컴파일러가 소스 코드로부터 병렬성을 찾아내고 병렬처리용 기계어 코드를 생성하여 수행하는 방식, VLIW 방식에 기반을 둠)

-병렬처리개념 도입(멀티프로세서(SMP(Symmetric Multi Processor), MPP(Massively Parallel Processor))

-SMP(Symmetric Multi Processor, 두 개 이상의 프로세서가 한 개의 공유된 메모리를 사용하는 멀티 프로세서 컴퓨터 아키텍처)

-MPP(Massively Parallel Processor, 두 개 이상의 프로세서가 각각 전용의 메모리를 사용하는 멀티 프로세서 컴퓨터 아키텍처)

-Main Memory 병목 해결

-버스분리(명령어와 데이터용 버스 분리)

-CPU에 Memory Controller를 내장

-Cache Memory를 계층적으로 구성(Intel의 L1/L2/L3 캐시 구성)

-L1/L2/L3란, L은 Level을 가리키고, CPU가 L1확인하고 없으면 L2를 확인, L3는 멀티 코어 CPU에서 각 코어와 L2 캐시 사이의 버퍼역할

(L1은 Command Cache와 Data Cache로 나누어져있음, L2는 나누어져 있지 않음)

(코어:CPU에서 다이(die, 실리콘 위에 반도체 회로를 만들어서 사각형으로 잘라낸 것, CPU의 밑판)에서 Cache Memory를 제외한 회로부분)

-구조적 해결:최근에는 CPU<->Cache Memory는 하버드 아키텍처, CPU<->Main Memory는 폰노이만 아키텍처를 통해 병목현상을 개선하여 사용)

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

자료구조

배열(Array)

-데이터가 많아서 그룹핑(grouping)을 해야할 필요가 있을 때 사용한다.

-배열의 구성요소

배열생성

배열의 index

value

element(index+value 합쳐서 element라 함)

-주로 사용하는 기능

-반복문

-Java에서 사용법

-생성

int[] numbers1 = new int[4];

element의 자료형, []은 배열임을 표시, 배열의 이름, = new(객체생성키워드), int[4](배열의 크기 지정

String[] strings = new String[4];

-배열에 데이터 입력

numbers1[0]=10;

numbers1[1]=20;

numbers1[2]=30;

(아무것도 입력안한 numbers1[3]에는 처음 생성시 디폴트값으로 0이 들어가있다. 만약 배열의 자료형이 객체였다면 디폴트로 null이 들어감)

-배열의 생성과 입력을 한번에 해결하기(배열의 생성시점에 배열에 들어갈 values를 이미 알 때 주로 사용)

int[] number2 = {10, 20, 30, 40};

int[] number3 = new int[]{10, 20, 30, 40};

-배열의 값을 가져오기(get)

System.out.println(number1[0]);  //10이 나옴

System.out.println(numbers1[3]); //0이 나옴

-배열의 크기(size)가져오기

System.out.println(numbers1.length);  //4가 나옴(element의 개수가 나옴, 값을 지정한 개수가 나오는게 아니다.)

-배열과 반복문(Iteration)

int i = 0;

while(number1.length > i){

System.out.println(number1[i]);

i++;

}

(while문의 단점은 int i = 0;과 조건문 그리고 반복문 의 i들이 멀리 떨어져있을 수 있어서 가독성이 떨어지고 중간에 버그가 있을 수 있다.)

(그럴땐 for문을 사용)

for(i=0;numbers1.length > i;i++){

System.out.println(numbers1[i]);

}

-배열의 단점

-크기가 정해져있어서, 데이터를 추가해야할 때 오류가 발생한다.

-기능이 없다.

-배열의 장점

-크기가 정해있어서, 작고 가볍고 단순하다.

-기능이 없다. 그래서 이후에 부품으로 이용되기가 좋다.

리스트(List)

중요 키워드:순서, 중복허용

array와 list

array도 순서와 중복허용 둘 다 가능하다

list가 array보다 기능이 더 많다.

array는 주소(index)가 중요

list는 A다음에 B가, B다음에 C가, 등 순서가 더 중요하다

데이터를 추가할 때의 array와 list의 차이가 두드러진다.

array는 덮어쓰기

list는 정말 추가가 가능, 기존 데이터는 한칸씩 밀려난다.

데이터를 삭제할 때는

array는 그 index의 데이터가 사라지지만 그 공간은 남아 있고 비어있게 된다

list는 그 index의 데이터가 사라짐과 공간도 사라지고, 그 이후의 element가 앞당겨오게 된다.

즉 list는 비어있는 데이터가 없다. 따라서 데이터 삭제를 한 이후에도 반복문 사용시 데이터의 유무를 판단하지 않아도 되며, 빈 데이터가 없으므로 메모리를 덜 차지하게 된다.

list의 기능

처음, 끝, 중간에 element를 추가/삭제하는 기능

모든 데이터에 접근할 수 있는 기능

데이터의 존재유무를 판단할 수 있는 기능

언어별 특징(데이터 스트럭쳐는 언어마다 다르지만, 본질적 개념을 알아야 한다.)

C에서는 list가 없다, 자신이 만들거나 다른 사람이 만든 것을 가져와서 사용함

JavaScript에서는 list가 있다. 

ex)

numbers = [10, 20, 30, 40, 50];

numbers.splice(3,1); //numbers라는 array의 index 3에서부터 1개의 데이터를 삭제하라(splice)

(그러면 위에 설명한 list에서처럼 삭제하고 한칸씩 앞당겨온다. 따라서 JavaScript에서는 array가 list처럼 동작하는 부분이 있다는 것을 알 수 있다.)

Python에서는 array가 기본적으론 없고 list가 기본적으로 제공됨

ex)

numbers = [10, 20, 30, 40, 50]; //5개의 element를 갖고 있는 list

numbers.pop(3); // index 3에 해당하는 40이란 data를 삭제하고 뒤 데이터를 한칸씩 앞으로 당김

numbers[0]; //0번째 데이터에 접근 가능

(Python에서는 list가 array처럼 활용되기도 한다(number[0]보면은))

Java에서는 array와 list가 각기 다른 문법으로 제공된다.

int[] numbers = {10, 20, 30, 40, 50}; //array

ArrayList numbers = new ArrayList();

numbers.add(10);

numbers.add(20);

numbers.add(30);

numbers.add(40);

numbers.add(50);

numbers.remove(3); // 40을 제거하고 밀려서 10,20,30,50이 됨

(Java에서는 array와 list가 모두 지원)

LikedList, ArrayList, 2가지의 list를 지원한다. 

ArrayList는 데이터의 추가/삭제가 느리지만 인덱스 조회는 빠르다.

LikedList는 인덱스 조회는 느리지만 데이터의 추가/삭제가 빠르다.

(따라서 개발자가 장단점을 생각해서 사용하게끔 해줌)

ArrayList는 Array를 이용하여 List를 만든다.

데이터를 추가할 때, 그 위치의 데이터의 오른쪽에 있는 모든 데이터를 오른쪽으로 1칸씩 미리 옮긴다음에 추가한다.

데이터를 삭제할 때는, 바로 삭제후 그 이후 데이터를 왼쪽으로 한칸씩 모두 옮겨주어야 한다.

index를 이용해서 데이터를 가져오기(get)가 굉장히 효율적이다.

size라는 것을 이용해서 ArrayList의 데이터의 개수(size)를 쉽게 알 수 있다.

장점:

데이터의 가져오기가 빠르다.

단점:

데이터의 추가/삭제가 오래걸린다.(비효율적이다.)

예제)(ArrayList의 생성, 데이터 추가/삭제, size, 데이터 조회, 반복문)

import java.util.ArrayList;  //import를 먼저 하고 사용해야 한다. ArrayList는 java.util 패키지에 있다.

import java.util.Iterator;

public class Main { 

public static void main(String[] args) { 

ArrayList<Integer> numbers = new ArrayList<>(); //<>이란 generic을 사용하여 ArrayList 내에 있을 데이터의 자료형을 미리 지정해서 만들 수가 있다.//

numbers.add(10); //데이터의 추가(insert)

numbers.add(20);

numbers.add(30);

numbers.add(40); //[10, 20, 30, 40]이 된다.

numbers.add(1,50); //numbers내의 index 1의 위치 오른쪽것을 모두 오른쪽으로 이동후 1의 위치에 50을 끼워넣게 된다. [10, 50, 20, 30, 40]이 나옴

numbers.remove(2); // numbers내의 index 2의 데이터를 삭제후 오른쪽 데이터를 모두 왼쪽으로 옮긴다. [10, 50, 30, 40]이 나옴

numbers.get(2); // numbers내의 index 2의 데이터를 가져온다.

numbers.size(); // numbers의 size가 나온다.

Iterator it = numbers.iterator(); // Iterator란 interface를 사용

while(it.hasNext()){ 

int value = (int)it.next();

if(value == 30){

it.remove();

}

System.out.println(value);

}

}

//혹은 다음 방법도 가능//

for(int value : numbers){ //numbers의 값들을 하나씩 value에 넣어 처리 가능

System.out.println(value);

}

for(int i=0; i < numbers.size(), i++){

System.out.println(numbers.get(i));

}

}

}

예제)(ArrayList의 객체 생성하기)

new->package

new->class(객체 실행을 위해, public main void체크해서)Main만들기

new->class(ArrayList)

Main.java에 들어가서

ArrayList numbers = new ArrayList(); // instance를 만듦

numbers.addLast(10); // 가장 마지막에 10을 추가

numbers.addLast(20); 

numbers.addLast(30);

numbers.addLast(40);

ArrayList.java에 들어가서

public class ArrayList {

private int size = 0; // ArrayList의 size를 측정하기위해 변수 정의

private Object[] elementData = new Object[100]; //private으로 이 내부에서만 사용하게, 이해하기 쉬운 Object형을 사용, 100개의 데이터만을 수용할 수 있게 만듦, 실제 자바내 있는 collection primework?에 있는 것은 ArrayList가 크기가 유동적임//

public boolean addLast(Object element){ // 가장 마지막에 데이터를 추가할 메소드(함수)를 만들기

elementData[size] = element;

size++;

return true;

------------------------------------------------------------------------------------------------------------------------------------------------------------

다시 정리

1. 언어랑은 상관없이

2. 각 자료 구조 형태마다의 특징을 정리, 그 '구조'를 써야하는 적절한 예제를 함께 정리한다.

1. Array, 배열

배열의 구성 요소:index, value, element(index+value를 함께 element라 한다.)

사용하는 상황:반복문

장점:배열의 크기가 정해져 있어서 작고 가볍고 단순하다.

단점:배열의 크기가 정해져있어서 데이터를 추가할 때 오류가 발생한다.

2. List, 리스트

리스트는 Order가 중요하다. 

-데이터를 추가할 때 Array는 덮어쓰기, List는 끼워넣기(이후 데이터는 한칸씩 밀려난다.)

-데이터를 삭제할 때 Array는 그 index의 value가 사라지지만 그 공간은 남아 있고 비어있게 된다. List는 그 index의 value가 사라짐과 함께 공간도 사라지고, 그 이후의 element가 앞당겨 온다. 따라서 List는 비어있는 데이터가 없으며 삭제를 한 이후에도 반복문 사용시 데이터의 존재유무를 판단하지 않아도 되며, 빈 데이터가 없으므로 메모리를 덜 차지하게 된다.

ArrayList

-사용하는 상황:데이터 조회(index 조회)가 자주일어나되 처음/중간/끝 등에 데이터를 추가/삭제는 자주 하지 않는 상황(전자가 빠르고 후자는 느리기때문에)

-데이터를 추가/삭제를 생각하면 나머지 우측 데이터들의 한칸씩 이동이 걸리기 때문에 ArrayList는 데이터를 추가/삭제를 자주하는 경우에는 사용을 기피

-메모리상에 데이터들이 연속적으로 붙어 있음

Linked List

-Linked List의 구성요소:HEAD+data field+link field(link field는 다음 node가 무엇인지에 대한 정보를 갖고 있음, 따라서 HEAD(첫번째 node가 무엇인지에 대한 정보를 갖고 있음)

-사용하는 상황:처음/중간/끝 등에 데이터를 추가/삭제가 자주일어나는 상황, 데이터 조회(index 조회)는 자주 하지 않는 상황

-데이터 조회할 때 메모리를 일일이 찾아 HEAD를 찾아야하기때문에 데이터 조회에는 느린 속도를 갖는다.

-데이터를 추가/삭제시 메모리상에 임의의 위치에 추가/삭제 하고 기존의 link field만 수정하는 형태이므로 데이터를 추가/삭제는 빠른편이다.(ArrayList에 비해)

-메모리상에 데이터들이 흩어져있지만 연결되어 있음(link field 정보)

Doubly Linked List

-Linked List에서 link field가 양방향으로 확장된 형태(Previous link field와 Next link field가 있는 형태)

-사용하는 상황:데이터 조회시 크기의 절반보다 큰 index를 자주 조회하는 경우이면서 데이터를 추가/삭제가 자주 있는 상황

-메모리를 Linked List보다 더 많이 사용한다.

-Linked List보다 조금 더 복잡하다

정리 1.

Array:데이터의 크기가 정해져있고 수정이 없고 가벼운 형태

ArrayList:데이터의 추가/삭제가 빈번하지 않고 조회가 주로 이뤄질 때

Linked List:데이터의 추가/삭제가 빈번하고 조회는 비교적 적게 할 때

Doubly Linked List:데이터의 추가/삭제가 빈번하면서 조회가 앞 뒤로 양방향이 자주 일어날 때

3. Stack, 스택

한쪽 끝(top)에서만 삽입(push)과 제거(pop, 정확하게는 출력하면서 제거)가 일어남, LIFO(Last-In-First-Out), 스택은 엘리베이터!, peek은 pop과 유사하지만, 출력만 하고 제거는 하지 않음

구현은 Array를 이용하거나 Linked List를 이용한다.

Array를 이용하는 경우, 스택을 위한 배열을 하나 잡고, index 값을 0으로 잡는다. index가 0이면 스택이 비어있는 것, 스택에 뭔가를 집어넣을 때는 Index의 자리에 집어넣고 index를 하나 올린다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것, 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.

사용하는 상황:

연산 구현시 stack(아래 함수의 호출 참고)

함수의 호출에 관여, 기본적으로 함수 f를 호출하면 먼저 f가 받는 인수들이 push되고 그다음 f가 리턴값을 받을 공간이 push된다. 그다음 f에 해당하는 stack frame이 할당 되고 그 stack frame내부에 f의 내부 변수들이 push된다. 이후 f에 해당하는 연산이 종료되고 f의 stack frame 내부의 값들이 빠져나오면서 최종적으로 리턴값을 받기 위한 공간으로 들어오게 된다. 

f를 호출한 상황에서 다른 함수 g를 호출하는 상황을 생각하면, 스택내부에 스택이 또 쌓이는 것이다. 이 개념을 이해하면 recursion이 연산속도에서 불리한 점이 이해된다. recursion할 때마다 스택을 자꾸 쌓아서, 결국 최종값을 얻기 위해서는 쌓인 스택을 전부 다시 빼내야하기 때문이다. 따라서 recursion을 쓰기 전, recursion이 필요한지 설계를 먼저 정확히 이해하는 것이 필요하다.

4. Queue, 큐

한쪽 끝에서는 삽입/제거만 일어나고 다른쪽 끝에는 제거/삽입만 일어남

제거 되는 곳을 Front, 삽입되는 곳을 Rear라고 함, FIFO(First-In-First-Out)

배열의 양끝이 맞물린 것처럼 가정하여 구현

사용하는 상황:CPU 스케쥴링, 디스크 스케쥴링, 버퍼(buffer)로 producer, consumer 사이의 완충 역할, 트리 및 이진트리의 레벨순서(level-order) 방문(탐색) 및 그래프의 너비우선(breadth-first) 방문(탐색)

5. Tree, 트리

6. Graph, 그래프

Directed Graph, 유향그래프

Undirected Graph, 무향그래프

7. Set, 집합

알고리즘

시간 복잡도(time complexity)

실행 시간은 실행환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등)

따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트

연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현

데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐

최악의 경우의 시간 복잡도 (worse-case analysis)

평균 시간 복잡도 (average-case analysis)

점근적 분석(Asymptotic analysis)

데이터의 개수 n->inf일 때 수행시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법

유일한 분석법도 아니고 가장 좋은 분석법도 아니지만, 상대적으로 간단하고 알고리즘의 실행환경에 비의존적이어서 많이 사용됨

가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다.

Ο 표기법은 upper bound를 표현

Ω 표기법은 lower bound를 표현

Θ 표기법은 upper and lower bound를 표현

이진 검색(Binary Search)와 정렬(Sort)

이진 검색

오름차순으로 미리 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 

중앙값을 선택하여 target과 맞는지 비교후

맞으면 끝

중앙값>target이면 중앙값을 새로운 최댓값으로 택한다.

중앙값<target이면 중앙값을 새로운 최솟값으로 택한다.

정렬된 리스트에만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다 Ο(log_2 (n))

순차 검색과 비교하면 순차 검색은 Ο(n)으로 이진 검색이 훨씬 빠르다.

정렬

버블 정렬 혹은 거품 정렬(bubble sort)

가장 왼쪽(l)과 인접한 오른쪽(r)과 비교후 l>r이면 l<->r

이후 2번째 원소와 3번째 원소를 비교후 같은 방법

한차례 지나고나서 다시 또 한다. (다만 첫포문을 마치고나면 가장 오른쪽엔 가장 큰것이 이미 와있으므로 두번째 포문부터는 n-1까지만 하면된다.)

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)

삽입 정렬(Insertion sort)

index 1의 데이터를 0과 비교해 제자리에 둔다

index 2의 데이터를 0과 1과 비교해 제자리에 둔다.

...

index k의 데이터를 0~k-1까지의 데이터와 비교해 제자리(맞는 자리에) 둔다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)이다.

기타 정렬

퀵소트(quicksort)

합병(merger sort)

힙(heap sort)

등이 있다.

*code review부터 다시보고 정리

순환(Recursion)

순환(재귀함수)이란, 자기 자신을 호출하는 함수(메소드)를 가리킨다.

순환이 무한루프에 빠지지 않기 위한 조건이 있다.

적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. 이것을 base case라 한다. 

recursion을 반복하다보면 결국 base case로 수렴하게 recursive case를 둬야 한다.

가능하면 암시적(implict) 매개변수를 명시적(explicit)매개변수로 표현하라.

예제)(Hello를 n번 출력하는 형태)

public class Code02 { 

public static void main(String [] args) {

int n = 4;

func(n);

}

public static void func(int k) {

if (k<=0)  // base case

return;

else {

System.out.println("Hello");

func(k-1);  //recursive case

}

}

}

예제)(n까지의 합을 출력하는 형태)

public class Code03 {

public static void main(String [] args) {

int result = func(4);

}

public static int func(int n) {

if (n==0)

return 0;

else

return n + func(n-1);

}

}

예제)(실수 x의 n승 구하기)

public static double power(double x, int n) {

if (n==0)

return 1;

else

return x*power(x, n-1);

}

예제(피보나치 수열 구하기)

public int fibonacci(int) {

if (n<2)

return n; // f_0 =0, f_1 =1인 피보나치의 경우

else 

return fibonacci(n-1) + fibonacci(n-2);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 예제)

public static double gcd(int m, int n) {

if (m<n) {

int tmp = m;

m = n;

n = tmp; // swap m and n(즉 항상 first argument가 더 크거나 같게)

}

if (m%n == 0)

return n;

else 

return gcd(n, m%n);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 더 간단한 예제)

public static int gcd(int p, int q) {

if ( q==0 )

return p;

else

return gcd(q, p%q);

}

수학함수뿐 아니라 다른 많은 문제들을 순환을 이용하여 해결할 수 있다. 특히 for문, while문을 대신할 수 있다.

순환<->반복문(즉 모든 반복문도 순환으로 만들 수 있다.)

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

하지만 함수 호출에 따른 오버해드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등), 즉 순환은 프로그래밍 실행 속도에 단점이 있긴 있다.

예제(문자열의 길이 계산)

public static int length(String str) {

if (str.equals(""))

return 0;

else

return 1 + length(str.substring(1));  // str.substring(1)이란 str의 첫번째 문자를 제거한 substring을 가리킨다.

}

예제(문자열의 출력)

public static void printChars(String str) {

if (str.length() == 0)

return;

else {

System.out.print(str.charAt(0)); // str.charAt(0)란, str의 첫 문자를 리턴하는 메소드이다.

printChars(str.substring(1));

}

}

예제(문자열을 순서를 뒤집어 프린트)

public static void printCharsReverse(String str) {

if (str.length() == 0)

return;

else {

printCharsReverse(str.substring(1));

System.out.print(str.charAt(0));

}

}

(문자열의 출력 예제와 달라진 것은 else내에 출력과 호출의 순서만 바꼈을 뿐이다.)

예제(자연수를 2진수로 변환하여 출력)

public void printInBinary(int n) {

if (n<2)

System.out.print(n);

else {

printInBinary(n/2);

System.out.print(n%2);

}

}

예제(정수 배열(Array)의 합 구하기, data[0]에서 data[n-1]까지의 합)

public static int sum(int n, int [] data) {

if (n<=0)

return 0;

else

return sum(n-1, data) + data[n-1];

}

}

암시적(implicit)매개변수를 명시적(explicit)매개변수로 바꾸어라.

예제(순차 탐색, sequential search)

int search(int [] data, int n, int target) {

for (int i=0; i<n ; i++)

if (data[i]==target)

return i;

return -1;

}

(여기서 n은 명시적인데, search의 시작 인덱스인 0은 암시적 매개변수이다. 하지만 순환을 사용시 시작인덱스도 명시적으로 하자.)

예제(순차 탐색, 매개변수의 명시화)

int search(int [] data, int begin, int end, int target) {

if (begin > end)

return -1;

else if (target==data[begin])

return begin;

else

return search(data, begin+1, end, target);

}

(이렇게 시작 index를 begin으로 명시화하자. search(data, begin, end, target)으로하면 begin index부터 end index까지 target이 있는지 확인)

예제(최대값 찾기)

int findMax(int [] data, int begin, int end) {

if (begin==end)

return data[begin];

else

return Math.max(data[begin], findMaxt(data, begin+1, end));

}

예제(이진 검색, binary search)

public static int binarySearch(String[] items, String target, int begin, int end) {

if (begin>end)

return -1;

else {

int middle = (begin+end)/2;

int compResult = target.compareTo(items[middle]); // string 비교시 자바에서는 compareTo를 사용한다. target이 items[middle]보다 크면 양수, 작으면 음수, 같으면 0을 return한다. //

if (compResult == 0)

return middle;

else if (compResult < 0)

return binarySearch(items, target, begin, middle-1);

else

return binarySearch(items, target, middle+1, end);

}

}

예제(미로찾기)

Recursive한 생각

현재 위치에서 출구까지 가는 경로가 있으려면

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

예제(미로찾기의 슈도코드1)

boolean findpath(x,y)

if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell; //visited cell개념을 넣지 않으면 무한 루프에 빠질 수 있다.

for each neighbouring cell (x',y') of (x,y) do

if (x',y') is on the pathway and not visited

if findpath(x',y')

return true;

return false;

예제(미로찾기의 슈도코드2)

boolean findpath(x,y)

if (x,y) is either on the wall or a visited cell

return false;

else if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell;

for each neighbouring cell (x',y') of (x,y) do

if findpath(x',y')

return true;

return false;

예제(미로찾기의 실제 자바 코드)

public class Maze {

private static int N=8;

private static int [][] maze = {

{0, 0, 0, 0, 0, 0, 0, 1},

{0, 1, 1, 0, 1, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 0, 0, 1, 1, 0, 0},

{0, 1, 1, 1, 0, 0, 1, 1},

{0, 1, 0, 0, 0, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 1, 1, 0, 1, 0, 0},

};

private static final int PATHWAY_COLOUR = 0; // white

private static final int WALL_COLOUR = 1; // blue

private static final int BLOCKED_COLOUR = 2; // red

private static final int PATH_COLOUR = 3; // green

public static boolean findMazePath(int x, int y) {

if (x<0 || y<0 || x>=N || y>=N)

return false;

else if (maze[x][y] != PATHWAY_COLOUR)

return false;

else if (x==N-1 && y==N-1) {

maze[x][y] = PATH_COLOUR;

return true;

}

else {

maze[x][y] = PATH_COLOUR ;

if (findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePath(x,y-1)) {

return true;

}

maze[x][y] = BLOCKED_COLOUR; // dead end

return false;

}

}

public static void main(String [] args) {

printMaze();

findMazePath(0,0);

printMaze();

}

}

예제(Counting cells in a Blob)

상황:

입력으로 binary image를 받는다. 그리고 하나의 좌표(x,y)도 받는다.

각 픽셀은 background pixel이거나 혹은 image pixel

서로 연결된 image pixel들의 집합을 blob이라고 부름

상하좌우 및 대각방향으로도 연결된 것으로 간주

(x,y)가 image pixel로서 택해졌다면, 그 pixel이 속한 blob의 총 image pixel의 개수를 return하는 문제이다.

(x,y)가 background pixel이면 0을 return

슈도코드:

if (x,y)가 이미지 밖이면 

결과는 0

else if (x,y)가 image pixel이 아니거나 already counted면

결과는 0

else

(x,y)를 다른 색(예를 들면 빨강)으로 색칠하라; // 이미 카운트 됐음을 표시

1+(인접한 영역의 count값);

실제 코드

private static int BACKGROUND_COLOR = 0;

private static int IMAGE_COLOR = 1;

private static int ALREADY_COUNTED = 2;

public int countCells(int x, int y) {

if (x<0 || x>=N || y<0 || y>=N)

return 0;

else if (grid[x][y] != IMAGE_COLOR)

return 0;

else {

grid[x][y] = ALREADY_COUNTED;

return 1 + countCells(x-1, y+1) + countCells(x, y+1)

+ countCells(x+1, y+1) + countCells(x-1, y) 

+ countCells(x+1, y) + countCells(x-1, y-1)

+ countCells(x, y-1) + countCells(x+1, y-1)

}

}

예제(N-queens problems)

상황:

NxN 체스판에 N개의 말을 놓는다. 

이때 각 말은 같은 행, 같은 열, 같은 대각선 상에 놓이지 않게 N개의 말을 놓을 수 있는지?에 대한 대답

Backtracking이용

일련의 선택을 하다가 조건에 부합하지 않게 되면, 그 이전의 선택으로 거슬러 올라가 번복하는 방법

각 행에는 1개의 말만 올 수 있음을 인지하고

0행에서 (0,0)에 말을 놓은 뒤

1행에서 (1,2)에 말을 놓은 뒤..... 쭉 하다가 안된다는 것을 깨달으면 그 이전의 행에서 놓은 말을 이동시킨다.(열을 증가하는 방향으로)

상태공간트리(State Space Tree)이용

뿌리에 Start를 두고

뿌리와 거리가 1인 노드들에는 0행에 놓일 0번 말의 가능한 좌표를 vertex에 표시하여 둔다

뿌리와 거리가 2인 노드들에는 이전 vertex(좌표)에서 1행에 놓일 1번 말의 가능한 좌표를 vertex에 표시하여 둔다.

.... 반복

해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드sequence에 해당한다. 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

트리를 탐색하는 기법들

깊이 우선 탐색, (이후에 정확한 정의를 파악), 일단 위의 예제에서 backtracking을 상태공간트리에 적용하면 그게 깊이 우선 탐색

실제코드(recursion과 stack을 사용할 수도 있다. 아래는 recursion을 이용한 코드이다.)

int [] cols = new int [N+1]; // 매개변수 level은 현재 노드의 level(트리의 root에서 떨어진 길이)을 표현, cols[i]=j 는 i번째 말이 (i행,j열)에 놓였음을 의미

boolean queens(int level) { // 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정, level을 넣음으로써 정확한 위치는 아니지만 몇행인지는 앎

if (!promising(level))

return false;

else if (level==N) { // level이 N인데 promising(level)이 true가 나왔으니까 끝난것

for (int i=1 ; i<=N ; i++)

System.out.println("(" + i + ", " + cols[i] + ")");

return true;

}

for (int i=1 ; i<=N ; i++) {

cols[level+1] = i;

if (queens(level+1))

return true;

}

return false;

}

boolean promising(int level) {

for (int i=1 ; i<level ; i++) {

if (cols[i]==cols[level]) // level번째 말이 이전의 말들과 같은 열에 있는 경우를 검사

return false;

else if (level - i==Math.abs(cols[level] - cols[i]) // level번째 말이 이전의 말들의 영향받는 대각선에 있는 경우를 검사

return false;

}

return true;

}

(실제 사용시 queens(0)으로 호출하면 된다.)

(이해를 하기위해 queens(0)을 생각해보기)

예제(powerset 출력하기)

상황:

주어진 집합의 모든 부분집합을 출력하는 문제

전략:

만약 {a,b,c,d,e,f}라면 

a를 포함하지 않는 부분집합을 나열한 후,

각각의 부분집합마다 a를 포함시켜 나열하면 된다.

(b를 포함하지 않는){c,d,e,f}의 모든 부분집합들에 a를 추가한 집합들을 나열하고

(b를 포함하는){c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열

....

즉 recursion을 해나간다.

powerSet이란 함수를 설정하는데에 있어서 argument를 집합1개만 받게 설정하면 recursion과정에서 각각의 부분집합마다 포함시켜 나열하는 경우가 해결이 안된다. 

실제 코드:

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};

private static int n=data.length;

private static boolean [] include = new boolean [n];

public static void powerSet(int k) { // k와 include를 통해 상태공간트리에서 현재 위치를 알려주는 것이다.

if (k==n) { // 상태공간 트리에서 현재위치가 가장 밑인 경우

for (int i=0 ; i<n ; i++)

if (include[i]) System.out.print(data[i] + " "); // P를 출력

System.out.println();

return;

}

include[k]=false; // data[k]를 포함하지 않는 경우

powerSet(k+1);

include[k]=true; // data[k]를 포함하는 경우

powerSet(k+1);

}

(data[k], ..., data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,...,k-1인 원소를 추가하여 출력하라는 mission)

(처음 이 함수를 호출할 때는 powerSet(0)로 호출한다.)

상태공간트리 활용

해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리

트리의 모든 노드들을 방문하면 해를 찾을 수 있다.

루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.

k=0일땐 공집합

k=1일땐 공집합이거나 a만 있거나(k=0일때의 집합에 a를 안넣거나 넣거나)

k=2일땐 k=1에서의 각각의 집합에서 b를 넣거나 안 넣거나를 만듦

k=3일땐 k=2에서의 각각의 집합에서 c를 넣거나 안 넣거나를 만듦

정렬

종류:

Simple하고 slow:Bubble sort, Insertion sort, Selection sort, 

조금 복잡하지만 fast한:Quick sort, Merge sort, Heap sort, 

그 외:Radix sort

기본적인 정렬 algorithm

Selection Sort:

1. 가장 큰 값(M)을 찾는다.

2. 가장 오른쪽 값(R)과 exchange(정렬한다.)

3. 가장 오른쪽 값을 제외하고 1,2를 다시 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수:n-1, n-2, ..., 2, 1, 그리고 교환은 상수시간

Bubble Sort

1. 첫번째 값과 두번재값과 비교

2. 정렬(교환or유지)한다.

3. 두번째값과 세번째값과 비교

4. 정렬한다.

...반복

결과적으로 가장 큰 값이 가장 오른쪽에 오게 된다.

5. 이후 가장 오른쪽 값을 제외하고 다시 1~4를 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 안쪽 for문이 n-1,n-2,...,1번 반복, 교환은 상수시간 작업

Insertion Sort

1. 첫번째 값에 두번째 값을 끼워 넣는다.

2. 세번째 값을 이전 결과에 끼워 넣는다.

3. 네번째 값을 이전 결과에 끼워 넣는다.

...반복

즉 k-1개가 이미 정렬되어 있고 k번째 item을 끼워넣는 것을 반복하는 것

구체적으로

copy the k번째 item to tmp

k번째 item이랑 k-1번쨰 item이랑 비교, k번째가 k-1번째보다 크면 끝, 작으면 k-1번째 아이템을 오른쪽으로 덮어쓰기(shift), 

그리고 k번째 item이랑 k-2번째 item비교,... 이것을 반복

(만약 k번째 item을 k-1, k-2, k-3,...순으로비교할게 아니라, 1,2,3,...으로 비교한다면 대칭이므로 차이가 없어보이지만, 주어진게 배열이라면, 오른쪽에서부터 비교하는, 즉 k-1,k-2,k-3,...순으로 비교하는게 효율적이다. 왜냐하면 대상이 배열이기때문에 결국 k번째 item을 k-1개의 item들 사이에 끼워넣기 위해선, k번째 item보다 큰 녀석들을 결국 오른쪽으로 옮겨야하고, k번째 item보다 큰 값을 가진애들을 한번씩은 접근을 해야하기 때문이다. 즉 1,2,3,...순은 총 k-1개의 데이터를 결국 다 접근해야하는 것이고, k-1,k-2,k-3,... 순은 접근해야할 개수가 k-1개 전체가 되진 않을 수도 있다. 그래서 k-1,k-2,...순으로 비교하는 것이다.)

시간복잡도 : 최악이 O(n^2) = n(n-1)/2, 최선이 O(n) = n-1, 평균도 O(n^2)

for 루프는 n-1번 반복, i번째 item을삽입(Insertion)하는 최악의 경우 i-1번 비교

Merge Sort

Divide and conquer(본질적으론 recursion과 유사)

분할정복법):예전에 로마 제국이 주변 나라를 정복할 때, 전체를 통채로 정복하기 보다는 작은 것으로 분할하여 정복한 것과 유사함

분할:해결하고자 하는 문제를 작은 크기의 "동일한" 문제들로 분할(recursion할 때와 비슷)

정복:각각의 작은 문제를 순환적으로 해결

합병:작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

     Merge sort    

데이터가 저장된 배열을 절반으로 나눔

각각을 순환적으로 정렬

정렬된 두 개의 배열을 합쳐 전체를 정렬<<<이게 가장 중요, 관건

9개 데이터있는 1개의 배열이 있다면, 절반으로 나누는 과정을 몇번하면 정렬된 9개의 배열을 갖게 된다.

그리고 다시 2개씩 합쳐주며 merge하는 것이다.

Merge를 하는 방법(a1<a2<a3, b1<b2<b3인 경우)

추가 배열을 만든다.

a1과 b1 중 작은 것을 추가배열의 왼쪽에 둔다.(a1<b1이라하자)

a2과 b1 중 작은 것을 추가배열의 왼쪽에 둔다(a2<b1이라하자)

a3와 b1 중 작은 것을 추가배열의 왼쪽에 둔다(b1<a3이라하자)

...이하 반복

(a배열의 index i, b배열의 index j, 추가배열의 index k중 k는 항상 +1, i는 a가 작을때 +1, j는 b가 작을 때 +1)

(sub배열중 1개가 완료되면 나머지 sub배열을 그대로 가져오면된다.)

알고리즘:

mergeSort(A[], p, r) { // 배열 A[]을 index p에서 index r까지 배열

if (p<r) then {

q = (p+q)/2 ; // p, q의 중간 선택

mergeSort(A, p, q); // 전반부 정렬

mergeSort(A, q+1, r); // 후반부 정렬

merge(A, p, q, r); // 합병

}

}

merge(A[], p, q, r) {

정렬되어 있는 두 배열 A[p,...q]와 A[q+1,...,r]을 합하여 정렬된 하나의 배열 A[p,...,r]을 만든다.

}

(merge부분을 실제 자바 코드로 써보면)

void merge(int data[], int p, int q, int r) {

int i = p; // 앞 배열 index

int j = q+1; // 뒤 배열 index

int k =p; // 도움배열의 index

int tmp[data.length()]; // 도움을 줄 추가배열을 만듦

while(i<=q && j<=r) {

if (data[i] <= data[j]) {

tmp[k++] = data[i++];

}

else {

tmp[k++]=data[j++]; // k는 항상 증가, i,j는 비교해서 작을때만 증가

}

}

while ( i <= q)

tmp[k++]=data[i++]; // 남은 것들 추가로 가져오는 과정

while (j <= r)

tmp[k++]=data[j++]; // 이 2개의 while문 중 1개만 사실 실행됨

for (int i = p ; i<=r ; i++)

data[i] =tmp[i] // 원래 데이터에 도움배열 정보를 넣는 과정

}

Merge Sort의 유일한 단점:추가배열을 잡아둬야한다는 것

시간복잡도:

T(n)

=0 (n=1일때)

=T(ceil(n/2)) + T(floor(n/2)) + n (n>=2) // n은 merge하는데 비교연산의 최대횟수가 n, 사실 ceil, floor는 필요없음, n->inf일때 고려하므로

=O(n*logn))

Quick Sort

마찬가지로 Divide and Conquer

다만, divide가 다름

pivot 선택하기

어떤 값을 pivot을 선택할 지는 나중에 배우기

현재 강의 내용에선 배열의 가장 오른쪽 값을 pivot으로 선택

알고리즘 개요

1. "pivot보다 작은 것, pivot, pivot보다 큰 것"으로 분할(분할하면서 좌, 우가 정렬하지는 않음)

2. pivot 기준으로 나뉘어진 좌, 우의 부분들에 다시 recursion으로 분할

3. "합병"단계가 필요가 없다.

알고리즘

quicksort(A[], p, r) { // A[p,...,r]을 정렬한다.

if (p<r) then {

q=partition(A, p, r);

quicksort(A, p, q-1);

quicksort(A, q+1, r);

}

}

partition(A[], p. r) {

x = A[r]; // pivot넣기

i = p-1 // 작은 애들 index

j = p // 큰 애들 index

for j to r-1 {

if A[j]<=x {

i++;

exchange A[i] and A[j];

}

}

exchange A[i+1] and A[r]

return i+1;

(배열 A[p,...,r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 return한다.)

(작/큰/x로 만든 다음, 큰애들 중 가장 왼쪽인 애를 x와 exchange할 것이다.)

(작은 애들 중 마지막 값 index i, 검사하려는 값 index j, A[j]와 pivot과 비교하여 A[j]가 x보다 같거나 크면 그냥 j++(다음꺼 검사), A[j]가 x보다 작으면 A[j]와 A[i+1]과 exchange하고 i++ 그리고 j++(다음꺼 검사))

(제일 마지막에 i+1과 pivot의 exchange, 그리고 i+1을 return)

}

복잡도

partition 한번 하는데 걸리는 시간은 O(n) // 정확히는 n-1번의 비교연산

T(n)

최악의 경우는 아이러니하게, pivot이 가장 큰 값일 때, 즉 이미 정렬된 배열인 경우이다. (pivot을 항상 가장 오른쪽 값을 갖는 상황이라 한다면)

T(n) 

= T(0) + T(n-1) + Θ(n-1) = T(n-1) + Θ(n-1)

= T(n-2) + Θ(n-1) + Θ(n-2)

...

=Θ(1) + Θ(2) + ... + Θ(n-1) 

= Θ(n^2)

항상 절반으로 분할되는 경우(최선의 경우)

T(n)

=2*T(n/2) + Θ(n-1)

...

=Θ(n*logn)

항상 한쪽이 적어도 1/9이상이 되도록 분할된다면(편의상 항상 1:9일때를 고려)

T(n)

= T(n/10) + T(9n/10) + Θ(n-1) 

...

= k * Θ(n) = Θ(n*logn)

(이때 (9/10)^k * n = 1, k=log_(10/9) n )

(따라서 분할이 아주 극단적으로 일어나지 않는다면, Quick Sort는 빠르다.)

평균 시간 복잡도

A(n) = sum over all input I of size n P(I)*T(I), where P(I):I가 일어날 확률, T(I):I의 시간복잡도

P(I)를 구하기가 힘드므로 가정을 한다. P(I)=1/n!이라 가정(즉, 서로 다른 값을 갖는 배열만 고려)

A(n) 

= 2/n * sum from i=0 to i=n-1 {A(i) + Θ(n)} // pivot의 rank가 1,2,.i..,n 일 확률이 각각이 모두 1/n, 그때마다 A(i-1) + A(n-i) + Θ(n)

= Θ(n*logn)

pivot 선택하는 기준

첫번째 값이나 마지막 값을 pivot으로 선택

이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우

현실의 데이터는 랜덤하지 않으므로 정렬/거꾸로 정렬 된 데이터가 입력으로 들어올 가능성은 매우 높음

따라서 좋은 방법이라고 할 수 없음

"Median of Three"

첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택

최악의 경우 시간 복잡도가 달라지지는 않음, but 현실적인 방법이긴 함

Randomized Quick Sort

pivot을 랜덤하게 선택

no worst case instance(즉 최악의 입력은 없음), but worst case execution(즉 최악의 실행은 가능함)

(다른 방법들은 최악의 입력이 존재하지만, 이 경우는 최악의 입력이 아니라 최악의 주사위(랜덤)에 의해 최악의 실행이 가능)

평균 시간복잡도 Θ(n*logn)

그래프

개체(object)들 간의 이진관계(binary relation)를 표현하는데 사용한다.

vertex의 개수를 n, edge의 개수를 m

undirected graph, directed graph, weighted graph 등이 있다.

별말없으면 simple undirected graph를 다룬다,

그래프의 표현

undirected simple의 경우

인접행렬(Adjacency Matrix)

저장 공간:Ο(n^2)

어떤 v에 인접한 모든 노드 찾기:Ο(n)

어떤 에지 (u,v)가 존재하는지 검사:Ο(1)

Symmetric Matrix가 된다.

인접리스트(Adjacency List)

V집합을 표현하는 하나의 배열과 각 v마다 인접한 정점들의 연결 리스트

노드개수:2m(edge 하나당 2번세니까)

저장 공간:Ο(n+m)

어떤 노트 v에 인접한 모든 노드 찾기:O(d(v)) // d(v)란 degree of v 라 하자

어떤 에지 (u,v)가 존재하는 지 검사:Ο(d(u)) // u에 해당하는 배열에 있는 리스트를 다 읽어봐야 하므로

directed의 경우

인접행렬

비대칭행렬

인접리스트

m개의 노드를 가짐

weighted의 경우

인접행렬

에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장

에지가 없을 때 혹은 대각선

특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서

예:가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 inf, 대각선은 0

예:가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 inf

그래프의 순회(traversal)

모든 v를 방문하는 작업

대표적인 방법

BFS(Breadth-First search, 너비우선순회)

L_0 = {v_0} //출발노드 선택

L_1 = L_0의 모든 이웃 노드들

L_2 = L_1의 이웃들 중에서 L_0에 속하지 않는 노드들

...

L_i = L_(i-1)의 이웃들 중에서 L_(i-2)에 속하지 않는 노드들

(순회 그래프에서의 BFS, 6분40초부터 다시보기)

DFS(Depth-First search, 깊이우선순회)

프로그래밍 기법

-compile 기법(통 번역후 실행)

-interpret 기법(바로바로 번역해서 실행, 실행파일을 만들지 않는다.)

-Hybrid 기법(중간코드 사용)

객체지향언어(Object Oriented Language)란?

-클래스, 상속(상위개념의 정의를 따름), 캡슐화(incapsulation), 다형성 등 객체지향의 개념이 잘 적용된 언어

-예전에는 동사의 개념, 객체지향은 명사의 개념, 명사의 성향을 반영하여 실행

(객체지향은 프로그램 규모가 커질 시 유지보수가 쉽다. 하지만 같은 수준(level)의 프로그래머라면 객체지향이 아닌게 훨씬 프로그램의 속도가 빠르나, 하드웨어의 발전으로 그리 큰 차이가 아니므로 객체지향의 사용 추세가 늘고 있다.)

자바언어의 특징

-운영체제에 독립적이다. 윈도든 리눅스든 가능

-JVM을 사용하여 한번 작성된 프로그램은 어떠한 운영체제에서도 실행이 가능

-자바의 모든 개발환경은 open source

자바 프로그램은 사용 형태에 따라 구분

-자바 응용 프로그램:일반 응용 프로그램

-자바 애플릿:웹 검색기 상에서 작동하는 프로그램

-자바 서블릿:웹 환경에서 실행되는 자바 프로그램

-JSP(Java Server Page):서블릿과 비슷하나 HTML 속에 자바 코드를 삽입하여 사용

-Java Beans:자바로 작성된 프로그램(컴포넌트)을 부품처럼 사용하여 프로그래밍 하는 방법

자바 프로그램 실행방법

-운영체제(32bit, 64bit에 맞는 JDK(Java Development Kit)를 받아 설치한다.

-IDE(Integrated Development Environment)로서 이클립스 같은 것을 받아 설치한다.(운영체제에 맞는)

이클립스의 기본 구조

-window->show view에서 뷰 선택가능, 위치이동 가능

-view의 종류

package explorer(프로젝트 중심으로 자바 패키지와 클래스 관리), 

Navigator(package explorer와 비슷하나 실제 디렉터리의 구조를 보여주는 것), 

Outline(편집기에서 편집 중인 프로그램의 트리구조를 보여주는 뷰), 

Console(자바 프로그램에서 출력되는 메시지를 보여주는 뷰), 

Problems(소스에 문제가 있는 부분을 목록으로 보여주는 뷰), 

Javadoc(자바 API문서를 보여주는 뷰이다. 자바 소스가 포함되어 있다면 사용하는 클래스 라이브러리의 설명 문서를 참조할 수 있음)

이클립스의 프로그램 작성 순서

-file->new->project-> 프로젝트명 입력

-file->new->class-> class명 입력, public static void main을 항상 선택하기

-프로그램 실행시 매개변수가 없는 경우 run->run

-프로그램 실행시 매개변수가 있는 경우 run->run configurations을 이용

프로그래밍 오류의 종류

-구분(syntax)오류, compiler가 번역할 때 오류를 잡아줌

(타이핑 오류, 예약어의 잘못 사용, 닫는 괄호 생략, 구분 종료 기호(;) 생략, 구문 구조 오류 등)

-실행시간(runtime)오류, 말은 맞는데 0으로 나누라거나 등의 불가능한 것을 지시할 때, compiler가 잡아줌

(0으로 나누는 것, 배열의 첨자 범위를 벗어난 접근, 실행시 입력받은 데이터의 오류 등)

-논리(logic)오류, 애초에 프로그램 작성한 사람이 논리적인 오류를 범함, 즉 algorithm이 틀린 것

몇가지 용어들

식별자, 예약어, 클래스, 멤버변수, 변수, 상수, 자료형, 생성자, 메소드, 

식별자(identifier, 변수, 상수, 메소드, 배열, 문자열, 사용자가 정의하는 클래스나 메소드 등을 구분할 수 있는 "이름"을 의미)

식별자의 사용 원칙

문자, 숫자, 특수문자(_,$)가능

첫문자는 숫자가 불가능

예약어를 식별자로 불가능

true,false,null은 식별자로 불가능

길이제한없음

대소문자 구분함

식별자 사용의 관례

클래스 이름은 첫문자를 대문자로하고 space를 사용하지 않고 명사구는 붙여서 짓되 각 명사의 첫문자 대문자(ex:JavaTest1)

메소드, 변수, 배열, 문자열의 이름, 모두 붙여서, 명사의 첫문자는 대문자, 단 가장 첫문자는 소문자(ex:nameAddress)

상수, 모두 대문자로 사용, 만약 space처럼 띄운 느낌이 필요하면 _를 사용한다.(ex:MAX_NUMBER)

예약어(Reserved word)

미리 정해진 함수같은 것들이다.

코드내에 주석문 넣는 방법

// 주석문 : // 표시부터 그 줄의 끝까지 위치한 모든 문자를 주석으로 간주한다.

/* 주석문 */ : 줄 수와 상관없이 “/*” 시작과 “*/” 끝 사이에 있는 모든 문자를 주석으로 간주한다. 여러 줄의 주석이 가능하므로 긴 설명을 하거나 많은 양의 소스를 주석으로 처리하고 싶을 때 이용한다.

/** 주석문 */ : 줄 수와 상관없이 “/**” 시작과 “*/” 끝 사이에 있는 모든 문자를 주석으로 간주한다. 클래스의 선언부, 멤버, 생성자 등 클래스 인터페이스 시작 부분에 사용해야 한다. 이 주석은 소스를 라이브러리로 만들 때 공식 문서용으로 뽑아 사용할 수 있다. javadoc 시스템을 사용하여 API 문서나 도움말 등에 이용된다.

자료형(Data type)(주의:Java에서는 String은 자료형이 아니라 클래스이다.)

기본자료형(primitive type)

-정수형:byte(8비트), short(16비트), int(32비트), long(64비트)

-최상위비트(most significant bit, 줄여서 MSB)를 부호결정비트로 사용한다(0은+, 1은 -)

-묵시적인 정수형은 모두 int형

-연산 후 주어진 할당된 비트수보다 큰 값이 되면 오바된 앞자리들을 버린다.

-2의 보수법을 따른다.

장점:

-MSB가 0/1 = 양/음 성질 유지

-음수를 더하는 방식으로 뺄셈을 할 수 있다.

-음수의 비교연산에서 발생하는 모순이 해결된다.

-0이 두개나 존재하는 모순이 해결된다(1의 보수법 사용시 문제점)

-덧셈과 뺄셈을 구현할 때 캐리(가용비트수보다 한자리 커지는 현상)를 처리하지 않아도 된다.(1의 보수법 사용시 문제점)

 (1의 보수에서는 캐리발생시 LSB에 +1해줘서 해결한다. 이러면 매 계산마다 캐리가 발생하는지도 체크해야되서 효율성 떨어짐)

ex:

01000100=68

68의 덧셈 역원을 얻기 위해 0<->1을 바꿔서 10111011을 얻은 다음에 00000001을 더한다. 

10111100이 나오고 이것이 (-68)이다. (10111100을 MSB가 1이니 -, 나머지 1들을 2^n의 계수로보고 십진수로 바꾸면 -60이 나오는데 2의 보수법이란 이것을 -60이 아닌 -68로 보자고 약속하는 개념이다.)

-실수형:float(32비트), double(64비트)

-float의 MSB는 부호, 이후 8비트는 지수부분(exponent part), 나머지는 가수부분(mantissa, 23비트)

-double의 MSB는 부호, 이후 11비트는 지수부분(exponent part), 나머지는 가수부분(mantissa, 52비트)

-논리형:boolean(1비트로 가능해보이지만, 8비트에 할당함, 그 이유는 컴퓨터에서 꺼낼 수 있는 주소 단위가 8비트=1바이트 이므로)

-문자형:char(16비트의 유니코드로 문자를 나타냄, 원래는 1바이트로 나타냈으나, 각 나라의 언어가 많아짐에 따라 2바이트됨)

ex: 가:AC00, 각:AC01, A:0041, C:0042

ex: '1' + 10하면 59가 나온다.('1'은 char이고 char+int하면 char가 ascii코드로 바껴서 계산됨)

ex: "1"+ 10하면 110이 나온다.("1"은 string type이고 string+int하면 int를 string type로 바껴서 string의 나열이 출력된다.)

-특수문자 표현 방법

backspace는 \b

tab은 \t

linefeed(줄바꿈)는 \n

formfeed(커서 앞으로 이동)는 \f

carriage return은 \r

backslash는 \\

single quote는 \'

double quote는 \"

-형변환(casting)

int a = 259;          //a = 259

byte b = (byte) a;  //b = 3

위와 같이 길이가 더 긴 것을 짧은 자료형으로 바꾸거나, 짧은 자료형을 긴 자료형으로 바꾸기 위해 (byte) 등을 추가하여 할 수 있다. 이를 casting이라 한다.

더 긴 것을 짧은 것으로 casting할 때는 하위 비트만을 할당한다. 반대로도 짧은 것을 긴 것에 할당 시 긴 것의 하위 비트에 할당시킨다.

참조자료형(reference type)

-기본 자료형(primitive type)의 경우는 지정된 위치에 값이 저장되어 있는 반면, 참조 자료형(reference type)은 지정된 위치에 실제 값이 있는 곳의 주소가 저장된다. 따라서 실제의 어떤 값을 가져올 때는 두번의 접근이 필요하므로 기본 자료형에 비해 효율성이 떨어질 수 있다.

Ex)Integer b = new Integer(10); //Integer라는 class의 새로운 b라는 색체를 만든 것

변수(variable)과 상수(constant)

값이 저장된 main memory의 "위치"에 주어진 이름이다. CPU의 register로 보내는 역할을 하며, 자료형도 지정해줘야 한다. 자료형만 사용자가 지정하면 memory위치나 length등은 자동으로 설정된다.

값이 저장된 main memory의 위치이지만 그 값이 일정하게 지정한 것이 상수

연산자(operator)

단항

++a:a값을 계산하고 a를 1증가

a++:a값을 1증가하고 계산

이항

a/b:몫

a%b:나머지

삼항

ratio = count > 0 && count <= 100 ? count/100 : 0;// count란 변수값이 0초과에 100이하면 ratio에 count/100을 넣고 아니면 0을 넣어라.

관계연산자(>,>=,<,<=,==,!=, instanceof)

객체 instanceof 클래스, 객체가 클래스인지 확인하는 연산자

ex:

class A{}

class B extends A{}

class instanceofEx01 {

public static void main(String[] args) { 

  A a = new A();

  B b = new B();

  System.out.println("a instanceof A : " + (a instanceof A));

  System.out.println("b instanceof A : " + (b instanceof A));

  System.out.println("a instanceof B : " + (a instanceof B));

  System.out.println("b instanceof B : " + (b instanceof B)); 

  }

}

<결과>

a instanceof A : true

b instanceof A : true

a instanceof B : false

b instanceof B : true

논리연산자(&&, ||, !)

x&&y:x와 y가 모두 true일 때 true를 반환

x||y:x가 true이면 true를 반환, x가 false이면 y를 평가하고 y가 ture이면 true를 반환, x와 y모두 false이면 false를 반환(x가 true이면 y를 평가안한다는 점 주의)

!x:x의 negation

비트연산자(비트 단위로 연산할 수 있는 연산자, 정수형의 데이터에만 적용이 가능하다)

op1 >> op2 : op1을 오른쪽으로 시프트(shift)

op1 << op2 : op1을 왼쪽으로 shift

op1 >>> op2 : op1을 op2만큼 오른쪽으로 shift하면서 왼쪽에는 항상 부호에 무관하게 0이 채워짐

op1 & op2 : 비트 단위의 논리곱(&) ex)1&1=1, 1&0=0

op1 | op2 : 비트 단위의 논리합(|) ex)1|1=1

op1 ^ op2 : 비트 단위의 XOR ex)1^1=0, 1^0=1, 0^0=0

~op : 비트 단위의 보수

쉬프트연산자

비트 단위로 이동하는 연산자

정수형에만 사용 가능

정수에 해당하는 비트 값을 좌, 우로 이동시키면 곱셈 또는 나눗셈의 결과를 얻을 수 있다.

산술적 쉬프트

숫자 << 자릿수 : 숫자*(2*자릿수), 

ex) 4 << 1 = 8 //4의 뒷부분은 0으로 채워짐

ex) 010 << 1 = 16 // 010은 8진법으로 봐서 8로본다. 따라서  16이 나온다(octal)

ex) 16 >> 1 = 8 // 가장 앞 부호비트는 그대로두고 0이 추가됨

ex) -16 >> 1 = -8 //

ex) -16 >>> 28 = 15 // int 16의 비트표현인 000...10000, 2의 보수법에 따라 111...01111이고 이것을 오른쪽으로 28칸 옮겼으므로 000...0001111, 이렇게 3개쓰면 반드시 왼쪽에 0으로만 채워짐(원래 음수였더라도)

배정 연산자

i=8+2; // CPU의 register에서 8+2 계산한 값이 저장되어있는데, 그걸 i라는 변수의 메모리 위치에 배정

j=i+20; // i의 값을 cpu에서 가져와서 연산하고 register에 저장한 다음에 j라는 변수의 메모리 위치에 배정

30=10+20; // 배정문의 LHS에 상수가 올 수 없다.

단축 배정 연산자

i = i+8; 이거 대신에 i += 8 가능

op1 <<= op2; //op1에다가 <<op2연산한 것을 다시 op1에 넣는 작업

연산자의 우선순위

1. (), []

2. ++, --, ~(혹은 -), !

3. *, /, %

4. +, -

5. >>, >>>, <<<

6. >, >=, <, <=

7. ==, !=,

8. &

9. ^(XOR)

10. |(논리합)

11. &&

12. ||

13. ? :

14. =

a-b-c은 왼쪽부터 계산한다.(같은 우선순위내에서는 왼쪽부터)

(하지만 배정 연산은 오른쪽부터 계산한다. a = b = c = 1(c=1부터 함, b=c, a=b 이렇게 됨)

ex)

(4+5*2/2)=9

(-5 - -2 * 8 / (4 - 2) * 3)

우선순위

(4-2) 

-5

-2

-2*8

이후 */*은 왼쪽순으로

답은 19

문자열(String)(char은 문자형으로 기본 자료형에 속하고, 문자열(String)은 클래스의 객체로서 구현됨)

String str1 = "아! 대한민국!"; //자바의 String은 객체로 표현되지만 일반 변수처럼 사용이 가능하다.

String str2 = "Korea";

String str3;

String str4 = new String("Korea");

String str5 = str2 + str1; //str5는 결국 Korea 아! 대한민국 이란 String이 된다.

매개변수(Argument)

매개변수로 입력된 값은 문자열(String)의 배열로서 저장된다.

선택문(if문, if-else문, if-else if-else문, nested if문, switch문)

ex)(nested if문 사용시 주의)

int score = 89;

if ( score > 60)

if ( score > 70)

if ( score > 80)

if ( score > 90)

System.out.println("A학점");

else

System.out.println("학점취득 실패"); 

(아무것도 안뜬다. 왜냐하면 이 else는 첫번째 if문의 else에 걸린다. 마지막 if문에 걸리는게 아니다. 따라서 if문을 쓸 때 중괄호를 생략하지 말자.)

ex)(Swtich문)

int num = 2;

switch (num) //정수 혹은 string만을 argument로 받을 수 있음

{

case 1 :

System.out.println("num의 값은 1입니다");

break;

case 2 :

System.out.println("num의 값은 2입니다");

break; // 만약 break;를 지운다면, 그 이하 default도 실행이 되니까 조심

default : // default를 지정안하면 case가 없는 경우 그냥 끝남, default를 지정하면 없는 case일 때 실행함

System.out.println("num의 값은 1도 2도 아닙니다");

break;

}

ex)(switch문, string예제)

String str = "A";

        switch(str){

        case "A": 

            System.out.println("1");

        case "B":

            System.out.println("2");

        case "C" :

            System.out.println("3");

        default :

            System.out.println("그 외의 숫자");

    }

반복문(while문, do-while문, for문)

do-while문은 조건을 나중에 검사함으로써 반복될 문장이 최소 한번은 실행, 메뉴를 먼저 print한 다음에 input받고 while 돌리는 형태에 적합

for문의 기초 문법

for(초기식; 조건식; 증감식)
 {

반복될 문장들;

}

for문의 처리 순서:초기식->조건식->(참이면)반복문장->증감식->조건식->...

ex)(for문 내의 지역변수 or 글로벌 변수 차이)

int i, sum = 0; // i가 글로벌?변수라서 for문밖에서도 사용 가능

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

{

sum += i;

}

System.out.println("1부터 " + i + "까지의 합 = " + sum); // 이 경우 i=11나와서 문제임

ex)

int sum = 0;

for ( int i = 1 ; i <= 10 ; i += 1)

sum += i;

System.out.println("1부터 " + i + "까지의 합 = " + sum);

(이 경우 i는 지역(local)변수로서 사용하고 사라지기 때문에 System... 이 줄에서 문제가 발생함)

ex)

int a, b ;

for ( a = 1, b = 10 ; a < b ; a++, b--)

{

System.out.println("a = " + a);

System.out.println("b = " + b);

}

(초기식과 증감식에 콤마로 분리하여 두개 이상 넣을 수 있음)

(초기식, 조건식, 증감식 모두 생략할 수도 있다(null statement), 조건식을 생략하면 항상 True여서 loop됨)

관련 문법

break문

가장 가까운 반복문을 빠져나간다.(여러개의 반복문 사용시 가장 안쪽 반복문을 빠져나감)

continue문

가장 가까운 반복문의 시작으로 간다.(여러개의 반복문 사용시 가장 안쪽 반복문을 빠져나감)

while, do-while은 조건(평가)식으로 이동

for문은 증감부분으로 이동

return문

메소드를 호출한 지점에 값을 반환하며(void였다면 값 반환 안하고) 메소드를 종료한다.

반환 and 종료 (둘의 의미를 가짐)

배열(Array)

기본 문법:자료형 [][] name = new 자료형[size]; 

ex)(array의 선언과 생성 동시에 하는법)

int [][] id_and_score = new int[5][2];

String add_and_name [][] = new String [10][10];

int [][] score = new int [3][];

score[0] = new int[2];

score[1] = new int[3];

score[2] = new int[4];

(마지막 예제는, 정사각형모양이 아닌, 각 행의 요소의 개수가 다르게 생성가능)

(이후 score[0][1] 이렇게 접근이 가능)

ex)

int[] id = new int [5];

int[0] = 22311123;

int[1] = 12313222;

(배열의 생성과 동시에 초기화도 가능하다.)

혹은

int id [] = { 22311123, 12313222, ... }; // {}의 콤마 개수로 id의 size결정됨

ex)2차원 Array의 생성과 동시에 초기화

int [][] id_score = { {70,80,90}, {98, 69, 49, 97},, ...}

그럼 {70,80,90}은 첫 행(row)의 정보이다.

{98, ~~}은 2행의 정보이고, 따라서 톱니형 array일 것이다.

배열.length

배열의 size가 나온다.

ex)(다차원 배열의 length)

int id_score [][] = { {70, 80, 90}, {98, 23, 43, 54}};

System.out.println("id_score의 배열크기는" + id_score.length); // 행의 개수 2가 나옴

System.out.println("id_score의 배열크기는" + id_score[0].length); // 0행의 열개수 3이 나옴

System.out.println("id_score의 배열크기는" + id_score[1].length); // 1행의 열개수 4가 나옴

(1차월 배열은 그냥 열의 개수가 나옴)

객체지향 이론과 역사

컴퓨터를 통하여 실세계와 같은 환경을 흉내(simulation)내기 위해 발전한 이론

실세계의 모든 사물들은 "속성(attribute)+기능(method)"로 구성

실세계의 사물들은 각기 다른 속성과 기능을 가지고 상호작용하여 살아간다.

객체지향 이론은 1960년대 클래스(class), 상속(inheritance), 캡슐화(encapsulation), 다형성(polymorphism)등의 개념을 중심으로 발전

객체지향과 대비되는 개념으로 절차지향(Procedural-oriented)가 있다.

절차지향이란 프로그램의 기본 단위가 절차 또는 함수로 정의되며, 절차 또는 함수에 의해 속성(데이터)들이 공유되는 형태

(절차지향은 동사위주, 객체지향은 주어(명사)+동사 함께)

객체지향의 장점

문제를 쉽고 자연스럽게 프로그램화(모델링)할 수 있다.

쉬운 프로그램의 개발로 인한 생산성 향상 시킬 수 있다.

프로그램 모듈을 재사용할 수 있다.

클래스(Class)

객체를 생성하는 template이다.

(롤의 챔피언들을 class 사용없이 한다고 하면, String Teemoname = "Teemo"; int Teemopower = 80; ,... 이짓을 챔피언 마다 해야한다. 각 챔피언들 마다 갖는 속성이 있다. 그런것들을 모아서 class로 만들어서 각 챔피언마다 class안에서 정의했던 속성, 메소드 등을 사용하겠다는 생각)

클래스로부터 객체를 생성하는 과정을 실체화(instantiation)라고 한다.

객체를 instance 혹은 object라 한다.(둘의 차이를 구글링해봤더니 다른데에 신경쓰라는 답변이 추천수가 제일 많은...)

클래스를 구성하는 것은 "클래스헤더+속성(attribute)+생성자(Constructor)+기능(method)"이다.

클래스 선언하는 부분을 클래스 헤더라 한다.

기본문법:"[public/디폴트/final/abstract] class 클래스이름 extends 상위클래스이름 {~}"

(혹은 extends 상위클래스, implements 인터페이스 등이 뒤에 추가될 수도 있다.)

public:모든 클래스로부터 접근이 가능한 class(즉 객체 생성가능)

디폴트:같은 패키지내의 클래스에서만 접근 가능(즉 객체 생성가능)

final:subclass를 가질 수 없는 클래스, 정보보호측면에서 유리

abstract:객체를 생성할 수 없는 클래스

속성(attribute)

속성의 구성:

멤버변수:메소드 밖에서 정의된 변수(접근을 "객체이름(객체참조변수).멤버변수", 단, 클래스 변수의 경우는 "클래스이름.클래스변수" 로 사용)

기본문법:"[private/디폴트/protected/public][static/final/디폴트] type name"

객체변수:객체가 가질 수 있는 속성을 표현

static/final 의 한정자를 붙이지 않으면(디폴트) 객체변수이다.

local variable의 개념

객체속성변수:객체가 가질 수 있는 속성을 나타내는 값으로 기본 자료형의 값들로 구성값을 가진다.

ex) int vol; int width;

객체참조변수:선언된 객체를 지칭(참조)하는 변수, 사용자는 객체를 선언한 후 생성한 다음 객체참조변수를 통해 객체의 멤버들에 접근가능, 객체에 대한 참조 즉 주소를 가진다.

ex)Box mybox1; String boxname; //mybox1의 선언으로 memory상에 mybox1의 null 상태로 위치만 갖는다. 

ex)Box mybox1 = new Box(10,20,30); // 객체의 선언과 객체참조변수, 객체의 생성까지 한번에, 생성까지하면 각 객체변수(width, height, depth등의 시작점을 메모리 번지값으로 갖는다.)

클래스변수

static을 사용하여 선언

객체를 생성하지 않아도 사용이 가능하다.(클래스가 메모리에 올라갈 때 자동적으로 생성되므로)

global variable의 개념

같은 클래스로부터 생성된 모든 객체들이 하나의 클래스 변수를 공유

즉 클래스변수는 하나의 같은 클래스로부터 생성된 객체들 사이의 통신이나 객체들 사이의 공통된 속성을 표현하는데 사용

따라서 일반변수와 달리 객체이름을 통해 접근 불가, 클래스이름을 통해서 접근한다.

(예를 들면 Park씨집안의 class를 만든다하자. 그럼 last name은 모두 Park일 것이다. 이런 경우 static String lastname = "Park" 을 사용하여 lastname은 Park을 한번만 할당하여 메모리 할당을 한번만 하는 이점을 얻을 수 있다. 만약 그냥 String lastname = "Park"을 하면 class를 통해 객체를 만들 때 마다 객체변수 lastname이 메모리에 객체 마다 할당되어서 메모리를 많이 쓰게 된다.)

(혹은 클래스내에 정의된 메소드를 호출할 때 마다 클래스 내에 있는 static 클래스 변수를 ++하게 해주면 실행횟수를 count하게 된다.)

Ex)(count할 때 쓰는 클래스 변수)

public class Counter  {

    static int count = 0;

    Counter() {

        this.count++;

        System.out.println(this.count);

    }

public static void main(String[] args) {

Counter c1 = new Counter();

      Counter c2 = new Counter();

 }

}

(main에서 Counter 클래스의 객체를 생성할 때마다 count는 1씩 증가한다. 만약에 static int count가 아닌 int count였다면 각 객체 c1마다 count가 생성되므로 각 객체마다 count가 있기 때문에 정말 원하는 count를 할 수가 없다.)

종단변수

final을 사용하여 선언

변할 수 없는 상수 값을 가짐

final이 붙은 변수는 단 한번 초기화 할 수 있으며 그 이후에는 그 값을 변경할 수 없음

상수 변수를 관례상 대문자로 표현하듯이, 종단변수는 대문자로 나타낼 떄가 많다.

접근한정사의 사용

private:클래스 정의하는 내에서만 사용가능

디폴트:같은 패키지내에서만 사용가능

protected:같은 패키지 or subclass에서만 사용가능(다른 패키지지만 subclass인 것은 가능하다는 것)

public:외부 객체에서 마음대로 접근가능

(모든 멤버변수는 그 클래스 전체에서는 유효하다.)

(class A와 다른 패키지에서 만든 class B, B는 A의 subclass도 아닌 경우에 B내부에서 A o = new A();하면 A내부에서 public으로 선언한 멤버변수만 접근가능)

(class A와 다른 패키지에서 만든 class C, C는 A의 subclass인 경우 B내부에서 A o = new A();하면 A내부에서 public이랑 protected로 선언한 멤버변수에 접근가능)

(class A와 같은 패키지에서 만든 class C, C는 A의 subclass이거나 아닌 경우에도 C내부에서 A o = new A();하면 A내부에서 public, protected, 디폴트로 선언한 멤머변수에 접근가능)

생성자(Constructor, 메소드의 사용법을 따르기도하고 생성자메소드라 부르기도 한다.)

모든 클래스는 객체를 생성할 때(instantiation) 생성자를 사용한다.

매개변수가 없는 생성자를 기본 생성자라 한다.

생성자를 작성하지 않는다면 컴파일 할 때 매개변수가 없는 기본생성자가 자동으로 만들어진다.

(public class이름() {} 이 자동으로 들어가서 컴파일이 됨)

생성자는 클래스 이름과 동일하게 사용한다. ex)

생성자를 하나라도 프로그래머가 작성하였다면 기본생성자는 만들어지지 않는다.

생성자는 returntype이 없다.

매개변수가 다른 생성자를 여러개 만드는 오버로딩이 가능하다.

this와 super로 생성자를 호출할 수 있다.

생성자의 역할:

생성자가 하는 일은 객체가 될 때 필드를 초기화 하는 역할을 수행한다.(클래스로부터 객체를 만들때마다 매개변수를 받아와야하는 경우일 때 사용)

기능(method):클래스 안에서 정의된 함수

기본문법:"[private/디폴트/protected/public][static/final/abstract/synchronized] returntype name([매개변수들])"

(혹은 throws 예외클래스 가 추가될 수도 있다.)

접근한정자(private/디폴트/protected/public)은 멤버변수에서의 사용과 똑같다.

클래스메소드

static을 사용한다.

객체변수를 사용하지 않는 메소드인 경우 static을 붙인다. 그럼 메소드 호출시간이 짧아지기때문에 효율적이다.

클래스메소드 안에서는 클래스 변수만을 사용할 수 있다. 그러다보니 수학함수들에 많이 사용 된다.

호출방법:클래스이름.메소드명(매개변수), 즉 객체를 통한 접근은 불가능하다.

종단메소드

final을 사용한다.

subclass에서 overriding이 될 수 없다.

추상메소드

abstract을 사용한다.

애초에 클래스가 추상클래스여야 추상클래스 내에서 선언이 가능하다.

선언부분만 가지고 몸체부분은 가질 수 없다.

몸체부분은 subclass에서 overriding

synchronized메소드

thread를 동기화 할 수 있는 기법을 제공하기 위해 사용

접근한정자에 대해

public:소속된 클래스가 접근 가능하면 항상 접근 가능

private:소속된 클래스 내에서만 사용가능, 클래스 외부에서 접근하려면 오류가 발생

protected:메소드가 소속된 클래스의 하위클래스와 같은 패키지에 있는 다른 클래스에서만 사용가능

메소드의 name은 소문자로 시작하는 것이 관례

메소드 매개변수:메소드내에서만 사용가능한 변수, 메소드 호출시 값이나 주소가 전달되는 형식매개변수로서 메소드 내에서만 유효하다.

객체이름.메소드(매개변수) 형태로 객체에 일을 시킬 수 있고, 일을 시키는 행위를 메시지(message)라 한다.(클래스메소드는 호출방법이 다름)

해당 클래스에서 메소드를 찾아 수행하되, 해당 클래스에 없다면 상위클래스에서 메소드를 찾는다. 이후 최상위 클래스에서도 없으면 오류 발생

클래스로부터 생성된 객체는 속성만 가지고 메모리에 생성된다.

메소드는 클래스(클래스 메모리 영역)에 저장되어 객체들이 공유한다. 

returntype은 void가 아니면 반드시 메소드 내에 return문 사용하여서 지정된 type을 반환해야만 한다. 이대 기본 자료형, 참조 자료형 모두 returntype가능

지역변수(혹은 형식 매개변수)란 클래스 내에서 메소드를 정의할 때 메소드의 몸체에서 정의된 변수이다. 메소드가 실행이 완료되면 사라진다.

변수의 유효범위(scope로) 변수를 분류하면 멤버변수>메소드 매개변수와 메소드 내의 지역변수>예외 처리기 매개변수

예외 처리기 매개변수(exception handler parameter):예외 처리를 위한 매개변수

메소드 argument passing

call-by-value로, 실 매개변수의 값만을 형식 매개변수에 복사해주는 방식이다.

매개변수가 기본 자료형은 실제값을 복사, 참조 자료형은 참조 자료형에 있던 주소만을 복사해서 형식 매개변수에 전달

상속(Inheritance)

기존 클래스의 모든 속성과 기능을 상속받고, 더 필요한 속성과 메소드를 추가하여 새로운 클래스를 생성하는 개념

객체지향의 장점인 모듈의 재사용과 코드의 간결성을 제공하는 중요한 특성

모든 자바 프로그램은 상위 클래스를 가진다.(상위 클래스를 지정하지 않으면 Object 클래스가 묵시적인 상위 클래스)

상속의 형식

캡슐화(encapsulation)

객체가 동작하는 기능만 알고 그 객체를 사용하게 하는 개념

객체의 자세한 동작 방법은 비밀

비밀을 알려고 하면 오류 발생

이를 통해 정보 은폐(information hiding)가능

캡슐화의 장점:

객체에 포함된 정보의 손상과 오용을 막는다

객체 내부의 조작 방법이 바뀌어도 사용방법은 바뀌지 않는다.

데이터가 바뀌어도 다른 객체에 영향을 주지 않아 독립성이 유지

처리된 결과만 사용하므로 객체의 이식성이 좋다.

객체를 부품화 할 수 있어 새로운 시스템의 구성에 부품처럼 사용할 수 있다.

다형성(Polymorphism)

다형성은 서로 다른 객체가 동일한 메시지에 대하여 서로 다른 방법으로 응답하는 기능을 의미한다.

오버로딩:동일한 이름의 메소드(생성자 등)을 만드는 것이다. 메소드(생성자)를 사용시 다양한 매개변수를 받기 위함이다. 동일한 기능에 따가 다양한 매소드를 만들면 복잡하고 관리하기가 어렵기 때문이다.

생성자 오버로딩

조건:같은 클래스내에서, 같은 이름의 생성자, 매개변수 개수가 다르거나, 개수가 같아도 매개변수의 자료형의 순서가 다르면 된다. 개수가 같아도 자료형이 달라도 된다.

ex) public Box5() {...}, public Box5(int w) {...}, public Box5(int w, int h) {...}, public Box5(String name, int w){...}, public Box5(int w, String name){...} 

ex)(생성자 오버로딩시 유의할 점)

public Box(String name, String color, int w){...}

와

public Box(String color, String name, int w){...}

은 생성자 오버로딩이 아니다. 이후 생성자 Box를 사용하여 객체만들 때 오류가 발생, 즉 매개변수의 개수 and 자료형(형식매개변수의 이름이 아닌)이 같은 순서로 들어오면 안된다. (str, str, int)

다만, (str, str, int)랑 (str, int, str)은 오버로딩 가능

메소드 오버로딩

조건:같은 클래스내에서, 같은 이름의 메소드명, 매개변수 개수가 다르거나, 개수가 같아도 매개변수의 자료형이 다르거나, 개수가 같아도 매개변수의 자료형의 순서가 다르면 된다. 

메소드 오버로딩시 유의할 점: 메소드명과 매개변수의 자료형과 순서가 같고, returntype만 다르면 오버로딩이 되지 않는다. 생성자 오버로딩에서와 마찬가지로 형식 매개변수의 이름은 오버로딩 성립에 영향을 주지 않는다.

this사용법

용도1:생성자 내에서 다른 생성자를 호출시 사용한다

ex)

class Box5{ 

int width;

int height'

int depth;

public Box5()

{

this(1,1,1);

}

public Box5(int w)

{

this(w,1,1);

}

public Box5(int w, int h, int d)

{

width = w;

height = h;

depth = d;

}

}

public class Box5Test { 

Box5 mybox1 = new Box5();

Box5 mybox2 = new Box5(10);

Box5 mybox3 = new Box5(10,20,30);

}

(굳이 Box5(int,int,int)가 제일 하단에 있을 필요는 없음)

용도2:메소드의 형식매개변수명과 객체자신이 갖고있는 멤버변수명이 같아서 구분시에 사용한다.

ex)

class This_2 {

int i;

public void method1(int i) {

this.i=i;

}

}

(여기서 this.i는 클래스 This_2의 멤버변수(객체변수) i를 가리킨다.

1. 단어

a very compassionate person 

His life got much better when he stopped drinking and got his act together. 

a malevolent lie/smile 

votaries of freedom

pinkeye

The whole story was just an artifice to win our sympathy. 

The prison's warden was a cruel martinet. 

I want cilantro

gold nuggets 

chicken nuggets 

nuggets of wisdom/advice/information 

By (all) rights, you should have been the one to receive the promotion.

orthopedic hose up to her knees,

His opponent called him a bigoted demagogue.

you're a lot leaner.

lounging in bed 

The fruitcake contains dried currants and raisins

My (parking) meter is up

The project hit a big pothole a few weeks ago. 

He enjoys spending time with his old army comrades.

He bought the car for a pittance. 

What touched off the fire? 

We accepted the news with resignation. 

The manager received resignations from three members of the staff. 

The bird ruffled (up) its feathers. 

That boy is a lot of trouble. It's a good thing his parents aren't easily ruffled.

I agreed to do what they wanted because I didn't want to ruffle any feathers.

The dress has a ruffle around the collar. 

2. 문장

So it would appear

I'm down (with it)

table-top game

You see these fucking mole people?

unswervingly adhere to the leaders

Real leaders don't spread derision and division.

social institutions

topical pesticides

after the fact

You stubbed it during the basketball game, right?

snake in the grass

primary, secondary, tertiary

Thriving, it has been found, is less likely for the overly zealous and carefree.

quote unquote

Jobs was a poser. He didn't even write code

you had me worried sick

The patient suffers from some kind of psychosis

She deserves a baby monsoon. 

Integral transform의 일반적 얘기 정리

Laplace Transform정리

Fourier Transform정리

1. 단어

a venal court official

The agreement lays down the law (to everyone) on what the group allows.

I felt someone tugging on/at my sleeve.

The problem was a real sod to fix.

you're a chucker

the school dumpster

The game also reduced their daily tensions because its ups and downs seemed more momentous than their lives

gustation

theistic

the man is head over heels

The company canvassed several sites for a new factory.

a flouncing walk

He never leveled with his parents about the accident.

pay dirt

I'm taking a leak

blue-collar, pink-collar, white-collar

She acted in a completely open and aboveboard way.

It's this kind of selfishness that leads down the road/path to perdition.

I saw him grab his lighter and his bong

Your constant tapping is driving me up the wall!

She bolted awake when the alarm sounded.

a mining concession

grocer's apostrophe

That dinner really hit the spot.

You voted for him? Surely you jest.

Film cameramen and crew members with booms blended in with them, while the director shouted out what to do.

2. 문장

You don't have any leads for me?

hate-filled garbage

Dvorak's native Bohemia

on the promenade

One of the most important skills is to be amenable to new information

Have you looked in the cellar?

Rhetoric focuses on the way historical and cultural settings frame discourse.

smart money is on the skinny bitch

I'm just about set

1. 단어

Her recent expressions of concern are self-serving and disingenuous. 

He grilled me about inappropriate relationships for five hours today.

His objections were made in a captious spirit.

a beatific smile

She was the bane of my existence.

My father was an illegal falconer

Even politicians sound more veracious on the radio. 

a dessert trolley, a shopping trolley 

He started drinking again after a long period of total/complete abstinence from alcohol. 

not in farmland itself, but in soil

tax breaks for the elderly.

Do you want to have great looking perennials?

She's got BO

It ended way past midnight

go all the way to the end!

She's fresh widowed

Where's your can?

I prefer the company of nitwits

coordinating conjunction

I'm guessing lovers' quarrel

toward the beginning of Cliff's career

not only was she impaled by a loose metal handrail

people just get more stoked on me!

1. 식이요법, 운동
-어떠한 불행한 일이 일어나도, 이 건장한 내 몸은, 다른 일을 시도할 자신감을 준다.
-피로, 육체의 아픔은 불필요한 불행을 맞이하는 것이다.
-건강한 몸과 맑은 정신은 행복의 필요조건이다.
-어떠한 해야할일이 있더라도 식이요법과 운동을 반드시 지킨다. 무조건 우선순위 1등이다.
-이것을 어겨가며까지 해야할 중요한 일은 없다. 운동시간을 빼고 나머지 투자한다해서 그 일이 더 잘되리라 생각은 완전히 근시안적인 생각이다.

2. 무엇인가 늘어놓은 계획은 ㄴㄴ
-이때동안 A1,A2,A3,...식의 계획은 통하지 않았다.
-이루지못한 죄책감만이 남았다.
-성공하더라도 보상은 크지 않다.
-매일 하는 습관 1,2개만두고 나머진 우선순위만 둘 것이며 구체적으로 무언갈 하겠다고 계획하지 않는다.
-"만일 네가 꿈을 갖더라도, 그 꿈의 노예가 되지 않을 수 있다면, 또한 네가 어떤 생각을 갖더라도, 그 생각이 유일한 목표가 되지 않게 할 수 있다면"

3. 사랑
-사랑을 꾸미지 마라. 네 자신이 네 자신답게 살아라.
-사랑이란 이 사랑이 영원하지 않을 수 있다는 것을 인지하되 사랑에 냉소적이지 않는 것이다.
-이 사랑이 영원하진 않을 지언정, 사랑한 내 감정은 그 순간만큼은 솔직했고 순수했으며 그 기억은 영원한 것으로 남을 것이다.
-현재 사랑하는 사람을 두어라. 상상의 고통들로 나를 괴롭히지 않아야 한다. 누군가를 좋아하는 감정은 세월이 흐를수록 자주 오지 않는다. 그런 감정을 느끼면 감사해하고, 걱정하지 않고 받아들이고, 더욱 열심히 사랑하라.

4. 직업과 돈
-오직 내 능력을 확실히 키울 수 있는 직업이어야 한다. 회사의 소속감, 연봉, 회사 내 사람들과의 관계 등 보다도 가장 중요한 것은 내가 추구하는 방향의 실력을 키울 수 있어야 한다. 즉 능력향상 외의 것들로 안주해 회사에 버티려고 하는 나를 경계해야한다. 사랑하는 일이 아니란 생각이 들면, 그만 두어라. 사랑하는 척을 하지 말자.
-그만큼 내 능력을 키우고, 성공을 누군가에 기대지 않아야 한다.
-돈을 착실히 모으자. 돈이 있으면 불필요하게 비굴한 직업을 가질 일을 줄일 수 있다.
-많은 준비를 하고 직업을 찾으려 하지 않아야 한다. 어느 정도의 준비 후 일단 직장을 잡는다. 이것은 미래의 불필요한 걱정을 줄여 행복한 자아 발전의 근간이 된다.

1. 용어

f_n:seq from {0,1,2,...}->F

f(t):fps from {f_n}, :=G[f_n]

f(t,w):fps from {f_(n,k)}, bivariate formal power series from {f_(n,k)}

[t^n]f(t)

ord(f(t))

bar(f(t))

F[[t]], F_k[[t]]

L, laurent power series, 원소는 l(t)

(x)_k, falling factorial

[x]_k, rising factorial

(d(t),h(t))가 pRa

M(d(t),h(t)), riordan array

renewal array

R, riordan group

A, Appell subgroup

Lag, Lagrange subgroup

derivative subgroup, {M(h'(t),h(t)) s.t. h(t) in F_1[[t]]}

2. 정리

About F[[t]]

ord(f(t)+g(t)) >= min{ord(f(t)), ord(g(t)))

ord(f(t)g(t)) = ord(f(t)) + ord(g(t))

(F[[t]],+,*):ID, quotient field는 L

About F_0[[t]]

(F_0[[t]], *):abelian group((F_0[[t]], +, *)에서는 +에 대해 닫혀있지 않음)

About F_1[[t]]

(F_1[[t]], o):group

About L

[t^n]의 성질 중 f(t)g(t)와 f(g(t))와 bar(f(t))에 관해서 복습, 특히 마지막을 Lagrange Inversion formula([t^n]bar(f(t)), [t^n]{bar(f(t))}^k)

About riordan array, riordan group

R:group

M(d(t),h(t))*M(a(t),b(t))=M(d(t)a(h(t)),b(h(t))), riordan arrays are closed under the matrix product

multiplicative identity는 M(1,t)

M(d(t),h(t))의 multiplicative inverse는 M(1/d(bar(h(t)), bar(h(t)))

Every pRa can be seen as the product of an Appell by a Lagrange matrix

{f_(n,k)}:pRa iff te d(t) in F_0[[t]] and h(t) in F_1[[t]] s.t. f(t,w) = d(t)/{1-wh(t)}

pRa is characterized by d_(0,0), Z-seq, and A-seq

About functional equation w(t)=tΦ(w(t))

Φ in F_0[[t]] and F in F_0[[t]]일 때

[t^n]w(t) = 1/n * [t^(n-1)](Φ(t))^n, n>0

[t^n](w(t))^k = k/n * [t^(n-k)](Φ(t))^n, n>0

[t^n]F(w(t)) = 1/n * [t^(n-1)]F'(t)(Φ(t))^n = [t^n](F(t) * (Φ(t))^(n-1) * (Φ(t)-tΦ'(t)))

f(t), g(t) in L

[t^(-1)]f(t)g'(t) = - [t^(-1)]f'(t)g(t)

Φ in F_0[[t]] and F in F[[t]]일 때

(Diagonalization rule) {c_n}={[t^n]F(t)(Φ(t)^n)}의 generating function은 F(w)/(1-tΦ'(w)), w=tΦ(w)

F and Φ and φ in F_0[[t]]일 때

[t^(n-k)]F(t)(φ(t))^n(Φ(t))^k M(d(t),h(t)), where d(t) = F(w)φ(w)/(φ(w)-wφ'(w)), h(t)=wΦ(w), w=tφ(w)

About A-seq and B-seq and Z-seq of pRa, given pRa(=M(d(t),h(t))

About A-seq

An infinite lower triangular array D is pRa iff te A-seq of D(a_0 != 0)

(->방향은 M(d(t),h(t))에서 M(d(t),h(t))*M(A(t),M(t)) = M(d(t)h(t)/t, h(t))이용해서 M(t)=t보이고 좌우변 generic element비교)

(<-방향은 h(t)=tA(t) 이용해서 h(t) 구하고 d(t)는 D의 0-column읽어서 구함)

Given pRa, A-seq의 generating function바로 구하는 법, A(t)=t/bar(h(t)), A(y)=h(t)/t, y=h(t)

About B-seq

Given pRa, te B-seq(M(d(t),h(t))=M(d(t)h(t)/t, h(t))*M(A(t),t)^(-1)을 이용해서 구함, B(t)=(A(t))^(-1)임)

About Z-seq

Given pRa, te Z-seq

(z_0 = d_(1,0)/d_(0,0), d_(2,0)=z_0 * d_(1,0) + z_1 * d_(1,1)해서 z_1구하고 이런 방식으로 쭉 구함)

Given pRa, Z-seq의 generating function(implicit), d(t)=d_(0,0)/(1-tZ(h(t))), 따라서 Z(y)=(d(t)-d_(0,0))/(td(t)), y=h(t)

About renewal array

a pRa M(d(t),h(t)) is renewal array

iff d(t)=h(t)/t

iff A(y)=d_(0,0) + yZ(y) and d(0)=h(0) != 0

A:Appell subgroup

A:normal in R

Lag:Lagrange subgroup

L:subgroup in R

L giso (F_1[[t]], o)

3. 요약

P=M(1/(1-t), t/(1-t))의 경우 generic element가 계산 쉬움, binomial formula쓰면 됨

C=M(1/sqrt(1-4t), (1-sqrt(1-4t))/2)의 경우 generic element를 guess한 다음, [t^n]~~꼴로 써넣고 보니 n이 포함된 형태, 따라서 diagonalization rule사용하여 증명

4. 문제들

1. 용어

K_n, K_(n,n), K_n^o,

K_n^*

SS

incidence matrix for the configuration {X1,X2,...,Xm} of n-set X(mxn (0,1)-matrix), a seq of m distinct elements of X is a SDR

partly decomposable, fully indecomposable

reducible matrix, irreducible matrix, nearly reducible

totally unimodular matrix

nnn irreducible matrix중

primitive matrix

exponent

imprimitive matrix

index of imprimitivity

Adjacency(multigraph에서 생각, multiple edge개수가 entry로 들어감)

(0,1)-incidence

(0,1,-1)-incidence(orient는 내맘대로)

Adjacency(digraph에서 생각, multiple arc개수가 entry로 들어감, from row to column)

minimally strong digraph

index of imprimitivity of a strongly connected digraph

tourment

permanent(rectangular에서는?)

σ_k(A)

affine set, dimension of nonempty affine set, hyperplane, affine hull

convex hull, convex polytope, dimension of convex set

DQSMT

DSMT, elementary DSMT

SSMT

OSMT

Ω_n, Ω_n(D) where D:fully indecomposable (0,1)-matrix

DSSMT

DSPSMT

RSMT

CSMT

α=an, β=bn

α < β,majorization

α <_w β, weakly submajorized

α <^w β, weakly supermajorized

Ω_n(α<β)

preordering and partial ordering

A is a subset of R^n, f:A->R일 때

A:symmetric이란?

f가

Schur-convex on A

strictly Schur-convex on A

Schur-concave on A

strictly Schur-concave on A

kth-symmetric function, S_k

S=[n], Latin rectangle of S, Latin square of S, reduced Latin square of S

L_n:the number of Latin square of [n]

quasigroup, loop

partial transversal of size t of a Latin square A on [n], transversal of A

2. 정리

About affine, convex

affine set <-> Linear system's solution Ax=b

About Nearly reducible matrix

A:nearly reducible (1,0)-MT일 때

te P and 1<=m<=n-1 s.t. PAP^t = ...

P-chain of [n]으로 permutation구하기

about PAP^T

불변량:n-digraph에 labeling만 영향(adjacency matrix A), egv

about PAQ

(n,n)-bipartite에 labeling만 영향, rank

A:invertible 이고 PAQ:LMT iff te! 1-factor of nonzero weight in the weighted bipartite graph associated with A

About det

det(MT(nxn))를 weighted bipartite graph로 표현하기

det(MT(nxn))를 weighted digraph로 표현하기(loop도 포함, 조심)

det(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

If MT:PSD, then det(MT) <= prod over all diagonals of MT

About per

per(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

per(PAQ)=per(A)

per((A)^t)=per(A)

Laplace Expansion Theorem for permanent(for mxn matrix, choose r, α)

per(A+B)=...

(Frobenius-Konig Theorem), A:nnn nxn MT일 때 per(A)=0 iff te P,Q s.t. PAQ=... sxt, s+t=n+1

(Alexandrov-Egorycev Inequality)If A:nnn, then (per(A))^2 >= ... (if t column빼고 다 positive columns, then = holds iff t는 q column의 multiple)

If per(A(i|s))=per(A(i|t)) for any 1<=i<=n and some s,t, then per(B)=per(A), where B=A except for s,t column은 A의 s,t column의 평균

If A:CSMT s.t. 0<per(A)<=per(A(i|j)) for any i,j, then per(A(i|j))=per(A) for any i,j

About subpermanents, some conjectures

If A:nnn, all row sum<=1, then σ_k(A) <= nCk

(Tverberg)If A:DSMT, then σ_k(A) >= σ_k(J_n) for k=1,2,...,n, with = iff A=J_n

(Dokovic)A:DSMT일 때 σ_k decreases at A on the segment joining A to J_n.(거짓, 1999, Ian)

(Dittert)A:nnn, all entries sum=n, f(A):=prod rowsum + prod colsum - per(A)일 때 f(A) <= 2 - n!/n^n with = iff A=J_n

(Cheon and Hwang)A:nnn, all entries sum=n, f_k(A):=...

About egv

Gershigorin theorem

About Irreducible MT

irreducible 판정:n-digraph가 strongly connected

Frobenius normal form of any matrix A, PAP^t

Frobenius form of irreducible A with index of imprimitivity k, then PAP^t ...

invariant operation of irr:

-transpose

-product? NO

-addition? NO

Perron-Frobenius Thm의 내용(positive일때랑 nnn irreducible일때의 차이는 spectral circle상 egv개수뿐)

About imprimitivity

M:nnn irreducible일 때

M:primitive iff M^m:positive(M:irreducible없어도 됨)

M:primitive iff lim m->inf (M/r)^m exists, limit값은?

imprimitive of M = gcd of the lengths of directed cycles in n-digraph.(index of M = index of D(M))

index of M=k일 때

k개의 egv는 x^k=r^k인 복소수 근들이다.

k_i = k, where k_i:the gcd of lengths of all cycles of D(M) through vertex i

About exponents of primitive MT((0,1)-MT만 다뤄도 됨, 이하 모두 (0,1)-MT)

If M:primitive with p개 nonzero diagonals, then exp(M) <= 2n - p -1

If M:primitive with n개 nonzero diagonals, then exp(M) <= n - 1

If M:primitive and symmetric, then exp(M) <= 2n - 2 with = iff te P s.t. PMP^t = ...

If M:primitive, then exp(M) <= (n-1)^2 + 1 with = iff te P s.t. PMP^t = ...

About Incidence, Adjancecy

About graph, A:(0,1)-incidence, B:Adjacency, C:(0,-1,1)-incidence

(A)^t * A = B + D

(C)^t * C = B - D

If G:connected, then rank(C)=n-1

About DSMT and Majorization

About DQSMT

A:DQSMT iff 1:egv for A with (1,1,1...,1) eigenvector

About DSMT

A:each row sum = each column sum = 1이면 A:square

A:DSMT iff AJ=JA=J, J=[1/n] iff for any x in R^n, Ax < x (majorization)

DSMT1*DSMT2 is also DSMT

per(DSMT) > 0

(Schur)H:hermitian, then te SSMT s.t. h=SSMTλ, h:diagonal entries로 구성된 vector, λ는 egv로 구성된 vector(증명도)

if A:DSMT and reducible, then te P s.t. PAP^t=the direct sum of DSMTs

if A:DSMT and irreducible with index k, then k|n and te P s.t. PAP^t = ... all blocks are (n/k)-square and DSMT

(Birkhoff)Ω_n={all DSMT}=closed bounded convex polytope, dim=(n-1)^2, whose vertices n! permutation MT of order n

D:nxn fully indecomposable (0,1)-MT일 때

Ω_n(D):={all DSMT s.t. DSMT<=D}, called the face of Ω_n, which is a subpolytope of Ω_n

dim(Ω_n(D))=the number of 1 in D - 2n + 1

the number of vertices = per(D)

the barycenter of Ω_n(D) is 1/per(D) sum over P<=D P(P:permutation MT)

About Minimizing

A:minimizing이면

fully indecomposable

if a_(h,k)>0, then per(A(h|k)) = per(A)

(London-Minc)for any i,j, per(A(i|j)) >= per(A)

if 1st row of A and 2nd row of A have the same zero pattern, then per(A)=per(A'), A'의 1,2row는 A의 1,2row의 average로 replaced

if A:positive, then per(A)=per(J_n)=n!/n^n

if A != J_n, then all its zeros cannot occur in a single row(column)

(Egorycev)per(A(i|j))=per(A)

(Alexandrov-Egorycev Inequality)에서 = 성립 for any q,t(q != t)

per(A)=per(A'), A'의 i,j row는 A의 i,jrow의 average로 replaced

(van der Waerden)If A:DSMT, != J_n, then per(A) > per(J_n)

if A:positive DSMT sufficiently close to J_n and A != J_n, then per(A) > per(J_n)

About DSSMT

A:DSSMT

iff te DSMT s.t. A<=DSMT

iff A:nnn and Ae <= e and eA <= e

iff A:nnn and αA <_w α for all nnn α.

{all DSSMT}=convex hull of {M s.t. M has at most one 1 in each row and each column}

About DSPSMT

A:DSPSMT 이면 all row sums and column sums are at least 1(역은 성립 안함)

{all DSPSMT}=convex, not convex hull of its extreme points(extreme points가 permutation matrices뿐)

About Majorization

α < β with nnn

iff (Muirhead) using c and per

iff (HLP) using DSMT

α <_w β with nnn

iff te DSSMT s.t. α = DSSMTβ

α <^w β with nnn

iff te DSPSMT s.t. α = DSPSMTβ

About Schur-convex function on A, A:symmectric and convex subset of R^n, f:A->R, g:R->R

직접 Schur-convex보이기, 단, n=2일때만 보여도 충분

f:C1 on int(A) 일 때 f:Schur-convex on A iff f:symmetric and Schur-condition

f:symmetric and convex이면 f:Schur-convex

f:inc and Schur-convex and g:convex이면 f(g)는 Schur-convex

f:dec and Schur-convex and g:concave이면 f(g) 는 Schur-convex

f:Schur-convex이고 g:inc이면 g(f)는 Schur-convex,

f:Schur-convex이고 g:dec이면 g(f)는 Schur-concave.

대표적인 Schur-convex

sum 1/x_i

sum x_i

sum (-log(x_i))

대표적인 Schur-concave

S_k(k=1,2,...,n)

symmetric, inc, Schur-concave

(S_k)^(1/k):symmetric, inc, concave, Schur-concave

(S_k)/(S_(k-1)):symmetric, concave, Schur-concave

Note)

<_w인 경우 order-preserving의 경우는

f:order-preserving

iff 0>=f_x1>=f_x2>=...>=f_xn for all z in A(f가 C1일 때)

iff f:inc and Schur-convex

<^w인 경우 order-preserving의 경우는

f:order-preserving

iff f:dec and Schur-convex

About Latin squares

L_n = n!(n-1)!R_n, where R_n:the number of reduced Latin squares of [n]

quasigroup on [n] <-> Latin square, bijection

K_(n,n)의 edge coloring(adjacent edges는 다른 coloring, color set=[n]) <-> Latin square, bijection

M_i:=same color perfect matching

transversal of Latin square <-> differenct color perfect matching

|G|=odd이면 {(g)^2|g in G} = G(i.e. all element of G has a unique square root)

따라서 cayley table for a group with odd order의 diagonal은 transversal가 된다.

3. 다시봐야할 것들

αP <^w α for all nnn α이면 P는 DSPSMT인가?

2015 1학기

미분적분학1(박기섭)

대수학특강(권순학, About Field, Galois)

2015 겨울학기

선형대수학(허석문)

2016 1학기

미분적분학1(조나단 악스텔)

수리통계학(배종식)

2016 2학기

현대대수학2(김미경, About field, series of groups, sylow theorems, UFD, PID, ED)

1강

Scientist explore what is; engineers create what had not been -Theodore von Karman

훌륭한 연구자가 되기 위한 대학원 생활 조언

지도교수님을 사랑하라.

지도교수님이 어떤 사람인지, 지도교수님의 관심 연구분야가 무엇인지

대부분의 교수님은 자기주도적인 학생을 좋아한다. "~했는데, 다음엔 뭘할까요?" 라는 말은 하지 않도록

연구, 논문쓰기는 가능한 빨리 시작하라.

좋은 연구 문제를 택하라.

여러가지 문제를 탐색,

자기 분야에 핫한거

review papers를 참고하라. 자기분야의

가이드라인 for 효율적인 연구

솔루션보다 Problem이 더 중요

방해받지않는 시간을 설정하라.

가정에 대해 의문을 가져라.

가능한 문제를 다룰 수 있는 부분으로 나눠서 보아라

솔루션을 다른 연구자에게 설명해보라.

단기목표, 장기목표 설정

연구자들과 대화하는 것을 아끼지 마라.

출판하는데 있어서 적극적으로 생각하라.

어느 출판하고 뭘 출판할 지 생각

공동저자에 실는 것을 관대하게 생각, 단 순서는 조심히 고려

읽기 쉽고 흥미롭고 잘 적혀야함

standard notation사용

관련된 연구 또한 작성

결과가 나오면 발표 등 알리는데 적극적인 자세를 취해야 한다.

일관된 연구 계획

끊임없이 주제를 확장해보고

핫한 분야 연구

다른 사람과 연구

스스로가 먼저 좋은 동료가 되고자 해야한다.

buddy system을 만들기

동료에게 칭찬, 나에게도 칭찬

좋은 환경 만들기(방해받지않는 시간 확보, 연구실 환경 등)

효과적인 학술논문 쓰기

쓰기전에 생각 다듬기, 순서를 어케쓸지 등

outline짜기

지루한 부분 빼기

간결 명료

작성법을 독자들의 스타일대로 맞추기

slang(속어), fad words(유행어), redundancies(불필요한 중복), euphemisms(완곡한 표현), spelling errors, poor grammar

다양한 사람에게 feedback받기, 전문가에게 교정받기

좋은 논문 쓰기 팁

가능한 많은 논문 읽기, 넓은 분야로

자기 업적에 대해 객관적이게 되기

좋은 영어로 쓰기

거절과 함께 살기, 리젝=조언받을 수 있는 기회

연구와 논문쓰기는 함께 진행되어야 한다. 연구중에도 논문을 어떻게 구성할지를 함께 고민해야한다.

Become a reviewer, 비판적으로 내 논문을 봐보기

어디 출판할지를 일찍 정하라, 저널의 목적과 범위를 먼저 정해야한다.

퀄리티가 전부다

2강 좋은 학술 논문의 효과적인 과정

Planning

일정 및 시간 잡기

가능한 일찍 planning 시작

방해받지 않는 시간 잡기

밝은 조명과 편안한 상태

컴퓨터와 소프트웨어에 익숙해지기

독자 정의

독자들이 원하는 게 무엇이며 이미 알고 있는 것은 뭘까?

목적 정의

논문을 통해서 이루고자 하는게 무엇인지?

Inventing

아이디어 생각, 구체화

outline 작성

Mind mapping

Taxonomizing

연구 Organization

연대순

공간적

비교/대비

중요도순

문제, 해결순

일반에서 구체적으로 순

Drafting

초안 작성

PID를 섞어서 진행, ID섞어진행, DR섞어진행, IDR다따로진행, 좌to우, 더 효율적이다.(긴문서의 경우 IDR 다따로 진행이 효율적)

PID섞어 진행:쓰기 어려운 글을 시작하게 하기 좋은 방법

ID섞어 진행:5~15페이지 문서에 효율적, Draft마치기 전까지 계속 쓰기(글쓰기 관성 유지하기, 방해안받을 환경이 필수적)

DR섞어 진행:15~50페이지 문서에 효율적, 문자, 숫자가 굉장히 중요한 문서에 적용, Organization이 가장 중요

방해요인 handle(초고 쓸때는 방해요인들을 좀 유연하게 생각하고 적기!)

계획짜는데 방해(가능하면 빨리 진행)

환경요인 방해(노전화, 등)

주제 방해(잘아는 주제로)

단어 방해

양식 방해

독자 방해

기대 방해

긴급한 상황 방해

Revising and Editing

충분한 시간 쏟아야 한다.

초고를 작성 후 인쇄하여 계속 들고 다니다 보면, 구성이나 아이디어들이 떠오른다.(Take creative time out)

여러 차례 교정 필요(관점을 바꿔보며)

크게 읽어보며 교정할 곳 찾기

반복되는 문제는 그곳마다 찾아서 수정하기 보단, 맨 앞페이지에 수정할 내용 적고, 마지막에 수정하는게 덜 스트레스 받는다.

Introduction부분을 다시 작성해보자.

지루함과 완벽함 고려

철자 문법 체크

지나친 완벽주의를 경계하라. 시간에 대한 limit을 설정하라.

피드백을 받을 때 명료한 의견을 달라고 부탁하라.

Revising 즐겁게?(high-level task위주로(글의 구성 등, 오타는 low-level), checklist만들어서 사용)

학술논문쓰기는 사무적이고 반복적인 일이다.

숙련자는 25/35/40

비숙련자는 50/45/5 로 시간 사용, inventing/drafting/revising

3강 저널고르는 방법 및 academic data base in research and writing 을 어떻게 사용할지

SCI(Science Citation Index), 150개 분야, 3800저널들이 등재되어 있음

SCIE(Science Citation Index Expanded), SCI보다 기준이 등재되기 쉬움, 대부분 저널들이 SCIE를 거쳐서 SCI되는데 SCI가 더 좋음, 8500개 저널들

IF(Impact Factor), 평균적으로 높을수록 좋은 저널, 저널 평가에 절대적인 기준은 아님, IF가 높을수록 인용이 많이 되구나

(2011년 Nature)IF = 62691/1728 = 36.280, 62691=2009,2010년 인용횟수, 1728=출판된 논문 수

Target 저널 정하기

저널정하기의 중요성

-저널의 goals 과 내 논문이 일치하는지

-IF가 높은지

-출판하는데 시간이 얼마나 걸리는지(요즘은 다 온라인이라 빨리 안내면 다른 사람이 냄)

-저널의 주요 독자들이 누군지(specific한 target 저널)

-broad audience, high IF보다 더 중요한건 내 분야 사람들이 주로 내는 저널인지가 중요함

저널 잘 정하면 장점

-빨리 출판되어야 좋음(노벨상의 경우)

-출판하는데 시간과 노력이 덜 필요할수록 좋음

-rejection rate이 줄어듬

-다른 연구자들이 내 논문을 잘 찾을 수 있음(내 분야사람들이)

저널 정하는 방법

-3~5개 정도 저널 후보 정하기

-저널의 범위가 내 논문 주제가 맞는지

-그 저널이 내 논문 주제의 논문을 출판한 적이 있는지

-투고하기전에 editor랑 컨택해서 CV랑 dataset, research report를 제출해서 클리닉을 받을 수 있음

-클리닉보고 내든가 다른데 내든가

빠른 출판의 방법

-CV, abstract, data sets을 먼저 보내보기 to editor

-peer review 평균시간 알아보기(각 저널 홈페이지에 있음)

-Table screening(저널 자체 회의) or trasnsfer service(다른 저널로 보내주기), 등 저널 별 특징 알아보기

-저널 별 time consumption에 대한 정보를 지도교수에게 얻을 수 있다.ㅣ

-Online pre-publication도 가능한 경우가 있다, 아주 빠르게 출판가능(요즘은 온라인 출판도 정식으로 인정됨, DY번호만 있으면)

IF찾기

-저널 홈페이지에 들어가서 찾기

-ISI Web of Knowledge에서 저널명 입력하면 찾기 가능

Research Survey가 충실히 이루어져야, 선행 연구 조사가 충분히 이루어져야 내 연구를 이해할 수 있다.

SCI 등 indexed journal에 출판해야 다른 연구자들이 내 논문 잘 읽을 수 있다.

open access journal

저자가 저널에게 돈을 일정액 지불하면, 일반인들이 온라인으로 무료로 논문 다운로드 가능

최근에 증가하고 있긴 하지만, 퀄리티는 아직 높진 않음

논문을 출판한 뒤, 내 분야의 사람이 아닌 분들에게도 내 논문을 홍보해야할 때가 있다.(평판도 높이고 교류도 하고)

-social media, SNS사용

-언론사 이용

-리서치 그룹의 웹사이트, 블로그, 유투브

-수상

요약

-high IF라해서 무작정 좋은건 아님, 저널과 내 분야 일치가 더 중요,

Academic Databases활용하기

Web of science

-web of knowledge에서 제공하는 정보

-12,000개 저널 포함

-148,000 컨퍼런스

-과학, 소셜사이언스, 인문학, arts 등 다양한 분야

Science Direct

-25,000 E-book

-2,200 jornals

Scopus

-Elsevier가 주인

-1995년 이후 정보만 access가능

당장 Web of Science가입필요

-document검색에 용이, author identifier number같은걸 가진다면 CV에 모든 내용 안적어도 됨

-search operators, AND, OR, NOT, NEAR/n, SAME

ex) ABC SAME DEF란 ABC DEF가 같은 줄에 쓰인 document만 나옴

-Refine results area

-Use the functions here to sort results, show abstract, get to full-text of articles, and more

-저자 정보, funding information, keywords, 등도 볼 수 있음

-이 논문을 인용한 논문이 무엇인지도 알 수 있음

-Citation network, cited reference, times cited counts, citation mapping, related record serach, citation alert(이 논문 또 인용하면 알려주는 서비스)

Citation reports

Scopus User guide

-Web of science와 비슷하게 다양한 기능 많음

H-index

총 documents 중에서 평균 n번 이상 인용된 논문의 개수가 n개일 때 h-index = n

높을수록 많이 출판하고 인용도 많이 된다는 것을 의미함

4강 스토리텔링방법으로 쓰기, 논문쓰기 준비과정

논문 구성

-타이틀을 구체적으로 쓰기

-not technical, technical하면 아주 전문가만 이해 가능

-잠재적인 독자에게 적절하게

-구체적으로 쓰는게 필요할 때도 있다.

-모든(compendious) 내용을 담은 것의 요약

-저자쓰기

-주저자:가장 기여한 사람(다수 가능)

-저자 listing은 기여도에 따라

-co author 정하는 것은 지도교수님과 상담

-co author에게 미리 알려줘야 함

-Corresponding author(=contact author), 주로 지도교수님이 되고, 모든 출판관련을 책임짐,

(주저자, Corresponding author가 기여도에 중요한 저자들임)

-Abstract쓰기

-Preview of what's to come

-Less technical

-100~250단어 사이로 단문 1개로 요약하기, novelty를 잘 설명해야 함

-축약어이나 citation언급, 하지 않도록

-Introduction쓰기

-현재까지 연구결과 언급, 이 논문의 성과

-1~4개의 문단,

-현재까지 연구의 역사와 문제점 언급

-이 논문의 차별성

-Materials and methods

-(실험관련 논문이라면)실험을 재현할 수 있게끔

-시간순으로 적어야

-차트, 도표, 표 등 도움됨

-사람 실험, 동물 실험했을때면 윤리적 문제(동의 등) 언급 필요

-실험결과를 적지 않도록

-실험도구의 브랜드도 적기(specialized 도구를 사용했다면)

-Results

-Detailed data 언급 필요, figures, graphs, tables 등 이용 필요

-정성것 적어야함. 눈에 잘띄게

-clear, logical

-비이성적, 과대포장 하면 안됨

-한 문장으로 결과 요약

-모든 Data를 넣을 필요는 없다.

-Discussion쓰기

-얻은 결과 중 가장 중요한 것 강조하기

-question과 결과를 잘 연결 짓기

-아이디어를 organize, 가장 중요한 단어, 가장 중요한 점, 메인 idea를 supporting하는게 뭐냐

-한 문장으로 conclusion 요약, 강조

-Tables and Graphs

-x축, y축 labeling필요

-Acknowledgement

-Moral, financial, editorial, presentational, instrumental, technical, conceptual, peer interactive 등 감사인사

-References

-저자명, 논문제목, 저널명, volume, page number, 등, 각 저널별 template이용하면 쉬움

스토리텔링방법(강조!)

-동일한 연구결과라해도 요렇게 잘 써야 질을 높일 수 있다.

-일반적인 진행 Background, approaches, results, outlook of the work

-Dramatic 진행 Background, State of the art of previous technology, Limitation of previous technology, Results를 통해서 limit를 넘어섰다.

-일반적으로 할거냐 dramatic할거냐는 지도교수님과 먼저 상담해야, 결과가 dramatic하지 않은데 dramatic 진행이면 학계에서 싫어할 수도

-Magazine 스타일(Nature같은)

-Thesis 스타일(PRL같은)

-detail이 중요

-Figure arragement

-Topic figure in the head(두괄식)

-trendy issue

-big breakthrough

-New phenomenon

-경쟁이 많은 분야에서 효과적

-Topic figure in the end(미괄식, 대부분의 논문)

-설명적

-이해하기 쉽고 organize the content하기 좋음

-dramatic description에 좋음

-Importance of visulization

-Highest visualization하면 좋음

-improve understanding

-fast and exact information delivery

-추가적인 설명없이도

-figure개수

-letter는 4~6

-full은 8~10

-Main figures < supporting figures, 필요한 개수

(왜냐면 Main figures는 잡지에 실려야 하니까, supporting은 온라인상에서 확인가능한 figures)

논문 준비하기

-Abstract

-Background와 연관성

-주장하고 싶은 1개의 문장(결과가 3개이상 정도 되줘야 high IF 저널에서 먹힘)

-Main conclusions, results

-출판과정

-저자가 submission

-editor가 Cover letter(1~2장, clear하게, 저자가 reviewer suggesting가능) check

-editor가 Abstract, affiliation, author체크(국가, 대학, 연구소가 영향이 있긴 함)

-editor가 figure set check(eye catching이 clear한지), 이후 peer-review할지, pre screening(선거절)

-editor가 reviewer select(cover letter에서 + 저널별 reviewer들 골고루 선택)

-reviewer가 comments

-editor가 decision(요즘은 reviewers들 중 한명이라도 reject이면 reject하는 경우가 많다. 따라서 first sumission에서 잘하길)

-author랑 revise(author는 답신해줘야함)

-editor가 Final decision

(A저널에서 reject당하고 B저널에 그대로 제출해서 같은 reviewer만날 확률이 있으므로 reject comment대로 수정 필요)

-Cover article로 선정되는 방법

-optional인데 author들의 선택

-대부분의 경우는 editor가 먼저 선정하고 author에게 확인받는 격

5강 Title, Abstract, Introduction

저널에 실리는 논문의 형태

Article(=full papers)

-이미 많은 사람들이 한 연구 주제

Notes

-굉장히 중요한 주제에 대해 preliminary reports, 예비단계지만 알리고 싶다.

-연구수행방법 개선, 다른 참식한 관찰, 새로운 techniques

Communications(Letters, Correspondence)

-길이 제한있음

-Urgent한 내용일 때

-실험 detail설명 ㄴㄴ

-독자들은 full paper를 쓸껄로 기대하게 됨

Reviews

-이미 발표된 논문들을 통합하고 미래 전망 등

-해결된 점과 해결해야할 것들을 언급

-연구 시작할 때 이런 review논문을 보면 좋음

-Reference를 잘 달아줘야함

잘써야하는 이유

-rejection될 확률 높고 독자들의 흥미를 유지

각 부분마다 독자들

-Title은 1000명(가정)

-Abstract는 대략 4문장, 100명

-Introduction은 1page, 100명

-the problem은 1page, 10명

-idea, 2pages, 10명

-the details, 5pages, 3명

-related work, 1~2pages, 10명

따라서 Title, Abstract, Introduction이 중요

논문은 미래시제를 쓰지 않는다.

현재시제는 사실 및 진리

거의다 과거시제이다.

Title쓰기

-독자 이끌기, 잘 검색될 수 있게, 정확하고 매력적이게, 최소한의 단어로

-원고 다쓰고 제목 수정

-가장 중요한 키워드를 나열한 후에 conclusion을 잘 대변할 수 있게 결정

-다른 사람 입장에서 읽어보기

-간결하고 의미있고 구체적

-너무 짧아도 너무 길어도 안좋음, 길수밖에 없으면 ~:~, subtitle사용

-studies on, investigations on, using, novel, first, a study of, research on, report on 등은 사용 하지 않도록

-기호, 공식, 약어 사용 ㄴㄴ

-시작시 the~로 쓰지 않도록

-약자, 약어 사용 ㄴㄴ, 굉장히 잘알려진거 아니면

-superscripts, subscripts 등은 사용하지 않도록

-굉장히 중요한 문제일 때 의문형으로 가능

Abstract쓰기

-잘 써야 논문 분류에도 정확히 분류됨

-목적과 scope, 사용된 방법, 결과요약, 가장 중요한 conclusions

-원도 다쓰고 수정 필요

-과거시제

-간결하고 self-contained, complete

-한문단이 가장 optimal, 80~200 words가 적당, 4문장 정도

-이 논문의 figures와 일치한 내용이어야 함

-reference, table, figure, sections을 cite하면 안됨

-논문에서 언급되지 않은 결과를 사용 ㄴㄴ

-약어사용이 가능한데, 첫등장은 full로쓰고 이후엔 약어사용 가능, Abstract에서 썻다고해서 Introduction에서 약어 바로 등장 안됨

Introduction쓰기(논문의 시작)

-현재시제는 진리를 가리킴

-내 결과와 관련된 분야들 언급

-논문의 목적

-구체적이고 간결하게 문제 언급

-첫 문장, 정보가 잘 포함된, 독자의 흥미를 끄는

-정확한 인용 언급

-현재까지 결과와의 차별성

-사용한 방법, 결론 언급

like this

문제

문제의 흥미로움

문제는 unsolved

내 아이디어

My idea workds

My idea가 다른 결과와의 비교

2 pages

-가능하면 능동태

-Define any specialized terms or abbreviations

-이미 출판된 내용을 인용(안출판된 것은 ㄴㄴ)

-피해야할 것

-장황한 나열, 우쭐한 표현, 반복 ㄴㄴ, 관련없는 내용 ㄴㄴ, recently사용 ㄴㄴ

-문단을 산만하게 ㄴㄴ, 1문단엔 1개의 아이디어만

-너무 많은 인용 ㄴㄴ

6강 Experimental Method, Theoretical Background, Synthesis, Experimentals

Chapter 1 What is CMT?

*Def

walk

path(walk와의 차이는 distinct vertices)

connected graph

matching, k-matching, matching number

vertex-cover, cover number

K_n, complete graph

K_no, complete graph with all loops

K_n*, complete digraph with all loops

G(MT), called the Konig digraph

IcMT(configuration of X)

MT(nxn):reducible or irreducible

nnn irreducible중에서

primitive MT

the exponent of primitive MT?

imprimitive MT, 이경우 index of imprimitivity 정의
G1,G2:cospectral if spec(A(G))=spec(A(G'))

IcMT(G), (1,0) matrix

*Thm

Principal tools of Combinatorics

-Mathematical Induction

-Pigeonhole Principle

-Inclusion-Exclusion Principle

-The methods of recurrence relations and generating functions

-Graph Theory

-Burnside's Theorem

-Polya Enumeration Theorem

각각 내용 알기, 특히 Exponential Generating Functions관련해서 내용정리 추가 필요

Tree의 equivalent def

-connected acyclic

-for distinct u,v in V(G), te! path from u to v

-connected with n-1 edges

-connected and removing any edge makes G disconnected

G:bipartite이면 cover number = matching number

From Matrix to graph

no need square(invariant for PAQ, like rank)

MT(mxn) -> K_(m,n)의 subgraph, ker(MT), bar(ker(MT)), bar(ker(MT))의 경우 weigted로도 볼 수 있는데 그 경우 bar(ker(MT))에서 0는 no edge로 보면 됨

MT(mxn) -> G(MT), K_(m,n)의 digraph 형태, weight있는 경우

MT(nxn)의 경우 그냥 G(MT)보고 det(MT)를 wt(all 1-factors)로 묘사가능

square(invariant for PArt(P), like egv)

SMT(nxn) -> K_no의 subgraph, ket(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

MT(nxn) -> K_n*의 subgraph, ker(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

From (di)graph to matrix

(1,0)-A(G)

arc가 있냐 없냐로 1,0

det(A(G))=(-1)^n * wt(D_n),

where D_n:={all 1-factor of σ, σ in S_n},

wt(D_n)=sum over all σ wt(F_σ),

wt(F_σ)=sign(σ) * prod over all i=1 to i=n a_(i,σ(i))

따라서 (di)graph의 형태를 보고 det구할 수 있다. cycles

A(G)^k의 (i,j)원소의 의미는 the number of walks of length k from i to j

IcMT(G)

rt(IcMT(G))*IcMT(G) = sLap(G)

det, perm using IcMT

det(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

perm(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

Perron Theorem for positive MT

About irreducible

MT:irreducible

iff G(MT):strongly connected, (G(MT):K_n*의 subgraph, unweighted directed)

About primitive MT

the index of imprimitive = gcd(the lengths of all directed cycles in G(MT))

MT:primitive

iff lim m->inf (MT/specR(MT))^m exists, the limit = (p*rt(q))/(rt(q)*p) > 0, where p:perron for MT, q:perron for rt(MT)

iff the index of imprimitive = 1

iff gcd(the lengths of all directed cycles in G(MT)) = 1, (G(MT):K_n*의 subgraph, unweighted directed)

iff MT^m > 0 for some m, called the exponent

Perron-Frobenius Theorem for irreducible NNN MT

1. 흥선대원군의 개혁 정치(사실 말이 개혁이지 전통질서의 강화...정도? 근대화된게 없음)

1863~1873 집권, 흥선대원군 이전은 세도정치기(1801~1863)였다.

왕권 강화책

1) 인사 혁신

세도 정치 타파(안동김씨 일가 축출)

능력에 따른 인재 등용(남인, 소론 등)

비변사 혁파(세도정치기에서 가장 권력 쎘던)

의정부(행정)와 삼군부(군사)의 기능 부활

2) 통치 체제 정비(정치 기강, 사회 기강 확립을 위한

'대전회통' 편찬

'육전 조례' 편찬

3) 경복궁 증건(임진왜란때 탔었던 경복궁, 왕실 위엄을 위해 증건)

재원 마련을 위해 원납전(기부금)징수, 당백전(새 고액화폐(시중 화폐보다 100배)) 발행, 성문세(4개의 문 통행료) 시행

경제 혼란 초래(물가상승)

양반의 묘지림(묘지주위나무) 벌목(좋은 나무 필요해서), 백성들을 강제 노역 동원

양반, 백성들의 불만초래

민생 안정책

1) 서원 철폐(600개 없애고 47개만 남음)

붕당의 근거지였던 서원, 제거해서 왕권 강화의 계기 마련

옥산서원(이이, 서인), 도산서원(이황, 남인), 등 각 서원 출신들은 서원 당을 따를 것이다. 그래서 없애자.

만동묘 없앰

허묘, 명나라가 임진왜란 때 우리 도와준 명나라 왕 신종과 명나라가 후금에 공격당해 멸망할 때 왕 희종, 두 왕에게 제사지내는 곳)

2명이 죽은 날도 다르고 명절도 2번이니 1년에 4번, 만동묘 주위 서민들 힘듬

서원의 토지와 노비 몰수하여 국가 재정의 확충

양반 유생들의 횡포로부터 백성들을 보호하여 민생 안정

2) 삼정의 문란(농민 봉기의 원인이었던) 시정

전정(전세(토지에 부과되는 세금)제도)의 문란

은결(토지대장(장부)에서 고의적 누락)때문에, 탈세 증가

백지징세, 즉 수확이 없는 땅인데 세금 부과

해결책:양전사업(토지조사)하여서 은결색출, 양반과 토호(땅부자)들의 토지 겸병(농민땅 뺏어서 땅합치는) 금지

군정의 문란

군포를 정부에서 미리 총액을 지정한 다음에 각 군현에 할당(각 군현의 장정수보다 많게)하고 각 군현의 아전(하급관리)들이 농민에게 수탈, 그러한 수탈의 종류(백골징포(죽은사람에게도), 함구첨정(어린애에게도), 인징(이웃에게), 족징(친척에게) 등)가 있었다. 양반은 면제, 도망자 발생 등등, 남아 있는 사람에게 부담이 가중

해결책:호포제(인두세에서 가구세로 바뀜) 실시하여 양반과 상민 모두로부터 군포 징수, 즉 군역의 균등화

환곡의 문란

환곡(봄에 곡식 꿔주고 가을에 이자처서 받는 제도)는 정부에서 실시, 아전들의 비리(환곡으로 고리대금함)가 많았다.

해결책:사창제(주민들이 자발적으로 직접 운영) 실시하여 관리의 부정 방지, 양반 중심으로 시행됨

---------------------------------------------------------------------------------------------------------------------------------------

2. 통상 수교 거부 정책(근대화에 늦어지게 되었다. 병제병오신)

병인박해(1866.03)->제너럴셔먼호사건(1866.08)->병인양요->오페르트도굴사건->신미양요

병인박해

흥선대원군은 러시아의 남하정책을 견제하고 싶어했다. 그러기 위해 프랑스 군을 이용하려했는데 실패. 그래서 국내 선교사 살해

제너럴셔먼호사건

미군이 평양 대동강 유역에 와서 통상 요구, 평양 감사였던 박규수가 제너럴셔먼호 파괴