본격적으로 알고리즘을 공부하려고 한다.

사용 책 : 코딩 테스트 합격자 되기 C++편

강의 주소 : https://www.inflearn.com/course/cpp-EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9/dashboard

강의 유튜브 주소 : https://www.youtube.com/watch?v=6oDZgi_7ao0&t=534s

알고리즘이란 무엇인가?

• 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한
  일반화된 작업이다.
• 함수라고도 볼 수 있을 것 같다.($\because$ 입력에 따른 예측가능한 출력)

그렇다면 좋은 알고리즘이란 무엇인가?

• 작동하는 데 걸리는 시간을 측정하여 그 시간이 짧으면 된다.
• 작동하는 실행된 연산횟수를 측정하여 그 시간이 짧으면 된다.

코딩테스트에서는 알고리즘의 성능을 연산횟수로 측정한다.

• 그렇다면 연산횟수를 매번 정확하게 측정할까?
  • 그렇지 않다. '대충 어느정도이다'라고 까지만 알면 된다.
  • 구체적으로 어떻게 대충 말하는 것일까?(대충의 기준은?)
    • 마치, 수학에서 무한대로 극한을 취할 때와 같이 나보다 차수가 낮은 애들은 무시한다.
    • $$
      x! > 2^x(지수함수) > x^n > \cdots > x^3 > x^2 > x > x \log x > \log x(로그함수) > \text{상수}
      $$
    • 따라서, 다항식의 경우 최고차항의 차수가 시간복잡도이다.

자주 보이는 복잡도는 다음과 같다.

이를 어떻게 활용하는가?

• 허용된 시간복잡도를 보고 어떤 알고리즘을 선택할지 결정하는 데 이용된다.
  • 즉, 문제에서 요구하는 성능을 만족하는 알고리즘을 택해야 한다.

메서드의 시간 복잡도를 파악하는 것이 중요하다.

• 동일한 동작처럼 보이지만, 시간복잡도가 다를 수도 있다.
  • 기본 컨테이너 vs Unordered 컨테이너
  • vector와 dictionary/set에서 특정 key 존재 유무 확인하기
  • vect와 list에서 특정 위치 원소 가져오기

실전예시

• 추후 계속 추가

한 학기 남짓 너무나도 많은 수업을 듣고있다...

솔직히 뭐가 뭔지 잘 모른다. 이게 저거 같고 저게 이거 같고..

이럴 때는 지식을 분류하는 게 좋다.

그래서, 챗 gpt와의 꽤나 긴 시간의 대화 끝에 배운 어떤 알고리즘들이 있는지 나열할 수 있었다.

1. 문제 유형에 따른 분류

분류 알고리즘:

1. Linear Discriminant Analysis (LDA) - 선형 판별 분석
2. Support Vector Machine (SVM) - 서포트 벡터 머신
3. Neural Networks - 신경망
4. K-Nearest Neighbors (KNN) - k-최근접 이웃
5. Decision Trees - 의사결정나무
6. Random Forest - 랜덤 포레스트
7. Naive Bayes - 나이브 베이즈
8. Logistic Regression - 로지스틱 회귀
9. Softmax Regression - 소프트맥스 회귀
10. Minimum Distance Classifier - 최소 거리 분류기
11. Optimal Statistical Classifier - 최적 통계 분류기

회귀 알고리즘:

1. Linear Regression - 선형 회귀
2. Polynomial Regression - 다항 회귀
3. Ridge Regression - 릿지 회귀
4. Lasso Regression - 라쏘 회귀

2. 모델 유형에 따른 분류

파라메트릭 모델 (Parametric Models):

1. Linear Regression - 선형 회귀
2. Logistic Regression - 로지스틱 회귀
3. LDA - 선형 판별 분석
4. Ridge Regression - 릿지 회귀
5. Lasso Regression - 라쏘 회귀
6. Softmax Regression - 소프트맥스 회귀

비파라메트릭 모델 (Non-Parametric Models):

1. K-Nearest Neighbors (KNN) - k-최근접 이웃
2. Decision Trees - 의사결정나무
3. Random Forest - 랜덤 포레스트
4. Naive Bayes - 나이브 베이즈
5. Neural Networks - 신경망
6. Parzen Window - 파르젠 윈도우

3. 최적화 알고리즘

확률적 최적화 (Stochastic Optimization):

1. Genetic Algorithm - 유전 알고리즘
2. Simulated Annealing - 시뮬레이티드 어닐링
3. Particle Swarm Optimization - 입자 군집 최적화
4. Differential Evolution - 차등 진화
5. Monte Carlo Methods - 몬테카를로 방법

결정적 최적화 (Deterministic Optimization):

1. Gradient Descent - 경사 하강법
   • Batch Gradient Descent - 배치 경사 하강법
   • Stochastic Gradient Descent (SGD) - 확률적 경사 하강법
   • Mini-Batch Gradient Descent - 미니 배치 경사 하강법
2. Newton's Method - 뉴턴 방법
3. Conjugate Gradient Method - 공액 기울기 방법
4. Quasi-Newton Methods - 의사 뉴턴 방법
5. Greedy Algorithm - 탐욕 알고리즘
6. Steepest Descent - 최급강하법
7. Gauss-Newton Method - 가우스-뉴턴 방법
8. Levenberg-Marquardt Method - 레벤버그-마쿼트 방법

4. 계산 복잡도에 따른 분류

단순 계산 최적화 (Simple Calculation Optimization):

1. Gradient Descent - 경사 하강법
   • Stochastic Gradient Descent (SGD) - 확률적 경사 하강법
   • Mini-Batch Gradient Descent - 미니 배치 경사 하강법

복잡한 계산 최적화 (Complex Calculation Optimization):

1. Newton's Method - 뉴턴 방법
2. Conjugate Gradient Method - 공액 기울기 방법
3. Quasi-Newton Methods - 의사 뉴턴 방법
4. Genetic Algorithm - 유전 알고리즘
5. Particle Swarm Optimization - 입자 군집 최적화
6. Differential Evolution - 차등 진화
7. Tabu Search - 타부 탐색
8. Ant Colony Optimization - 개미 군집 최적화
9. Complexity-Based Search - 복잡도 기반 탐색
10. Orthogonal Array Search - 직교 배열 탐색
11. Iterated Local Search - 반복적 지역 탐색

5. 정규화 기법

1. Total Variation Regularization - 총 변동 정규화
2. Ridge Regularization - 릿지 정규화
3. Lasso Regularization - 라쏘 정규화

6. 강화 학습 알고리즘

1. Q-Learning - Q-러닝
2. Double Q-Learning - 더블 Q-러닝
3. SARSA (State-Action-Reward-State-Action) - SARSA
4. Deep Q-Network (DQN) - 딥 Q-네트워크
5. Policy Gradient Methods - 정책 경사법
   • REINFORCE - REINFORCE
   • Actor-Critic - 액터-크리틱
   • Proximal Policy Optimization (PPO) - 근접 정책 최적화
   • Trust Region Policy Optimization (TRPO) - 신뢰 영역 정책 최적화
   • Advantage Actor-Critic (A2C, A3C) - 어드밴티지 액터-크리틱
   • Deep Deterministic Policy Gradient (DDPG) - 딥 결정적 정책 경사법
   • Soft Actor-Critic (SAC) - 소프트 액터-크리틱

7. 손실 함수

회귀 문제:

1. Mean Squared Error (MSE) - 평균 제곱 오차
2. Mean Absolute Error (MAE) - 평균 절대 오차
3. Huber Loss - 후버 손실
4. Log-Cosh Loss - 로그-코시 손실

분류 문제:

1. Cross-Entropy Loss - 교차 엔트로피 손실
2. Binary Cross-Entropy Loss - 이진 교차 엔트로피 손실
3. Categorical Cross-Entropy Loss - 범주형 교차 엔트로피 손실
4. Kullback-Leibler Divergence (KL Divergence) - 쿨백-라이블러 발산

일반화된 손실 함수:

1. Hinge Loss - 힌지 손실
2. Squared Hinge Loss - 제곱 힌지 손실

8. 정보 엔트로피

1. Shannon Entropy - 섀넌 엔트로피
2. Conditional Entropy - 조건부 엔트로피
3. Joint Entropy - 결합 엔트로피
4. Relative Entropy (Kullback-Leibler Divergence) - 상대 엔트로피 (쿨백-라이블러 발산)
5. Mutual Information - 상호 정보
6. Cross-Entropy - 교차 엔트로피
7. Jensen-Shannon Divergence - 젠슨-섀넌 발산

9. 기타 개념

모델 평가 및 선택:

1. Bias-Variance Tradeoff - 편향-분산 트레이드오프
2. Cross-Validation - 교차 검증
3. ROC Curve - ROC 곡선
4. Precision-Recall Curve - 정밀도-재현율 곡선
5. F1 Score - F1 점수

집합 학습 (Ensemble Learning):

1. Ensemble Methods (e.g., Bagging, Boosting, Stacking) - 집합 학습 방법
2. Gradient Boosting Machines (GBM): XGBoost, LightGBM, CatBoost - 그래디언트 부스팅 기법

차원 축소 (Dimensionality Reduction):

1. Principal Component Analysis (PCA) - 주성분 분석
2. Independent Component Analysis (ICA) - 독립 성분 분석
3. t-Distributed Stochastic Neighbor Embedding (t-SNE) - t-분포 확률적 이웃 임베딩
4. Autoencoders - 오토인코더

하이퍼파라미터 튜닝 (Hyperparameter Tuning):

1. Hyperparameter Tuning (e.g., Grid Search, Random Search) - 하이퍼파라미터 튜닝
2. Bayesian Optimization - 베이지안 최적화

심층 학습 (Deep Learning):

1. Convolutional Neural Networks (CNNs) - 합성곱 신경망
2. Recurrent Neural Networks (RNNs) - 순환 신경망
3. Long Short-Term Memory Networks (LSTMs) - 장단기 메모리 네트워크
4. Generative Adversarial Networks (GANs) - 생성적 적대 신경망

최신 연구 동향 및 기술:

1. Transfer Learning (전이 학습) - 전이 학습
2. Meta-Learning (메타 학습) - 메타 학습
3. AutoML (자동화 머신러닝) - 자동화 머신러닝
4. Semi-Supervised Learning (반지도 학습) - 반지도 학습
5. Self-Supervised Learning (자기지도 학습) - 자기지도 학습
6. Metric Learning (거리 학습) - 거리 학습

10. 고급 개념 및 최신 연구

고급 최적화 알고리즘:

1. Second-Order Methods (BFGS 등) - 2차 미분 기반 방법
2. Constrained Optimization (Lagrange Multipliers, SQP 등) - 제한 조건 최적화

분산 및 병렬 최적화:

1. Distributed Computing (Horovod, TensorFlow Distributed 등) - 분산 컴퓨팅
2. Federated Learning - 연합 학습

최신 알고리즘 및 모델:

1. Transformers (BERT, GPT, T5 등) - 트랜스포머
2. Graph Neural Networks (GNNs) - 그래프 신경망
3. Self-Supervised Learning (SimCLR, BYOL 등) - 자기지도 학습

최적화 기법의 응용:

1. Hyperparameter Optimization (Hyperband, Optuna 등) - 하이퍼파라미터 최적화
2. Meta-Learning (MAML 등) - 메타 학습

MLOps (Machine Learning Operations):

• MLflow - MLflow
• Kubeflow - Kubeflow

Explainable AI (XAI):

1. SHAP (SHapley Additive exPlanations) - SHAP
2. LIME (Local Interpretable Model-agnostic Explanations) - LIME

11. 수학적 최적화 알고리즘 (Mathematical Optimization Algorithms)

선형 계획법 (Linear Programming)

• 설명: 선형 관계식으로 구성된 제약 조건과 목표 함수를 가지는 최적화 문제를 해결하는 기법.
• 예시: Simplex Algorithm, Interior Point Methods.

비선형 계획법 (Nonlinear Programming)

• 설명: 비선형 관계식으로 구성된 제약 조건과 목표 함수를 가지는 최적화 문제를 해결하는 기법.
• 예시: Gradient Descent, Newton's Method, Sequential Quadratic Programming (SQP).

혼합 정수 계획법 (Mixed Integer Programming, MIP)

• 설명: 일부 변수는 정수로 제한되는 최적화 문제를 해결하는 기법.
• 예시: Branch and Cut, Branch and Price.

동적 계획법 (Dynamic Programming)

• 설명: 문제를 더 작은 하위 문제로 나누어 순차적으로 해결하는 최적화 기법.
• 예시: Bellman Equation, Viterbi Algorithm.

제약 충족 문제 (Constraint Satisfaction Problems, CSP)

• 설명: 주어진 제약 조건을 만족하는 해를 찾는 문제.
• 예시: Backtracking, Forward Checking, Arc Consistency.

이진 결정 다이어그램 (Binary Decision Diagrams, BDD)

• 설명: 불 대수 함수의 효율적인 표현과 조작을 위한 데이터 구조.
• 예시: ROBDD (Reduced Ordered BDD), ZDD (Zero-suppressed BDD).

메타휴리스틱 (Metaheuristics)

• 설명: 다양한 최적화 문제에 적용 가능한 일반적인 탐색 기법.
• 예시: Genetic Algorithms, Simulated Annealing, Tabu Search, Ant Colony Optimization, Particle Swarm Optimization.

라그랑주안 최적화 (Lagrangian Optimization)

• 설명: 제약 조건을 가진 최적화 문제를 해결하기 위한 방법.
• 예시: Lagrangian Relaxation, Augmented Lagrangian Methods.

라그랑주 승수법 (Lagrange Multipliers)

• 설명: 제약 조건이 있는 최적화 문제를 해결하기 위한 방법.
• 예시: Method of Lagrange Multipliers.

이차 계획법 (Quadratic Programming)

• 설명: 목표 함수가 이차 함수이고 제약 조건이 선형인 최적화 문제를 해결하는 기법.
• 예시: Wolfe's Method, Interior Point Methods for QP.

유한차분법 (Finite Difference Methods)

• 설명: 미분 방정식의 수치 해법을 찾는 방법.
• 예시: Forward Euler Method, Backward Euler Method, Crank-Nicolson Method.

제약 최적화 (Constrained Optimization)

• 설명: 제약 조건이 있는 최적화 문제를 해결하는 방법.
• 예시: Penalty Methods, Barrier Methods.

실수 기반 최적화 (Real-Valued Optimization)

• 설명: 실수 공간에서 최적화 문제를 해결하는 방법.
• 예시: Hill Climbing, Simulated Annealing.

비선형 방정식 시스템 (Nonlinear Systems of Equations)

• 설명: 비선형 방정식의 집합을 해결하는 방법.
• 예시: Newton-Raphson Method, Broyden's Method.

이산 최적화 (Discrete Optimization)

• 설명: 이산 변수로 구성된 최적화 문제를 해결하는 방법.
• 예시: Integer Programming, Combinatorial Optimization.

다목적 최적화 (Multi-Objective Optimization)

• 설명: 여러 개의 목표 함수를 동시에 최적화하는 방법.
• 예시: Pareto Optimization, Weighted Sum Method, ε-Constraint Method.

로지스틱 회귀 (Logistic Regression)

로지스틱 회귀는 이진 분류 문제를 해결하는 데 주로 사용되는 통계 모델이다. 이 글에서는 로지스틱 회귀의 개념, 수학적 유도, 비용 함수 등을 다룬다.

용어정리

• 로지스틱 함수 (Logistic function): 시그모이드 함수로, 입력 값을 0과 1 사이의 확률로 변환한다.
• 로짓 함수 (Logit function): 로지스틱 함수의 역함수로, 확률 값을 로그 오즈로 변환한다.
• 로지스틱 회귀 (Logistic Regression): 선형 결합된 입력 값을 로지스틱 함수에 적용하여 클래스에 속할 확률을 예측하는 이진 분류 모델이다.
• Logistic cost function: 이진 크로스 엔트로피 함수 (binary cross entropy function)이다.
• 엔트로피 (Entropy): 정보 이론에서 불확실성의 척도이다.
• 크로스 엔트로피 함수 (Cross Entropy function): 두 확률 분포 간의 차이를 측정하는 함수이다.

유도

로지스틱 회귀 모델을 수학적으로 유도하는 과정은 다음과 같다.

1. 이진 데이터와 확률00

데이터가 이진 데이터라면 종속변수 ( y )는 0과 1의 값만 가질 수 있다. 이를 선형 함수로 추정할 때 종속변수의 범위는 $$0 \quad OR \quad1$$이며,
독립변수의 범위는 $$(-\infty, \infty)$$이다. 따라서 두 변수 간의 범위를 맞추기 위해 확률을 도입한다.

$$
0 \le P(Y) \le 1
$$

2. 오즈 (Odds)와 로그 오즈 (Log Odds)

확률 ( P(Y) )의 범위는 여전히 ([0, 1])이므로, 새로운 개념인 오즈 (Odds)를 도입한다.

$$
\text{odds} = \frac{P(Y)}{1 - P(Y)}
$$

오즈의 범위는 ((0, \infty))이다. 이를 로그 변환하여 로그 오즈 (Log Odds)를 구하면, 범위가 ((- \infty, \infty))가 된다.

$$
\log(\text{odds}) = \log \left( \frac{P(Y)}{1 - P(Y)} \right)
$$

3. 로짓 함수 (Logit function)

로그 오즈를 선형 함수로 표현하면 다음과 같다.

$$
\log \left( \frac{P(Y)}{1 - P(Y)} \right) = W^T X + b
$$

이를 다시 ( P(Y) )에 관해서 정리하면 다음과 같은 로지스틱 함수가 된다.

$$
P(Y) = \frac{1}{1 + e^{-W^T X + b}}
$$

따라서,

$$
H(x) = \frac{1}{1 + e^{-W^T X}}
$$

로지스틱 회귀 비용 함수 (Logistic Regression Cost Function)

로지스틱 함수의 경우 MSE(Maximum Square Error) 방법으로 오차를 평가하기에 적절하지 않다. (왜냐하면 연속형 데이터가 아니기 때문이다.) 따라서 크로스 엔트로피를 이용하여 비용 함수를 표현한다.

크로스 엔트로피 손실 함수 (Cross Entropy Loss Function)

크로스 엔트로피 손실 함수는 다음과 같이 정의된다.

$$
C(H(x), y) =
\begin{cases}
-\log H(x) &  \text{if } y = 1 \\
-\log (1 - H(x)) & \text{if } y = 0
\end{cases}
$$

이를 하나의 식으로 나타내면 다음과 같다.

$$
\text{Cost}(H(x), y) = - [y \log(H(x)) + (1 - y) \log(1 - H(x))]
$$

이 식은 정보 엔트로피 개념과 관련이 있다.

정보 엔트로피와 크로스 엔트로피

• 정보 엔트로피:
  $$
  \sum P(Y_i) \times \frac{1}{P(Y_i)}
  $$
  여기서 ( \log \frac{1}{P(Y)} )는 정보량을 의미하며, ( P(Y) )는 사건이 일어날 확률이다.
• 크로스 엔트로피:
  $$
  \sum P(Y_i) \log \frac{1}{P(x_i)}
  $$
  이는 예상 정보량과 실제 확률의 곱으로 두 분포 간의 차이를 나타낸다.

손실 함수 해석

$$
\text{Cost}(H(x), y) = - [y \log(H(x)) + (1 - y) \log(1 - H(x))]
$$

이는 두 가지 사건만이 존재하는 크로스 엔트로피임을 알 수 있다.

• y = 1일 때:
  • 손실 함수는 ( $-\log H(x)$ )가 된다.
  • 예측 확률 ( H(x) )가 1에 가까울수록 손실이 작아진다.
• y = 0일 때:
  • 손실 함수는  $(-\log(1 - H(x)))$ 가 된다.
  • 예측 확률 ( H(x) )가 0에 가까울수록 손실이 작아진다.

이를 통해 모델이 참과 거짓을 잘 예측할수록 손실이 작아진다는 것을 알 수 있다.

한글에 excess-3 입력하면 오류 뜬다;;

SR 플립플롭에서 S=1, R=1일 때 실제로는 어떻게 될까?

디지털 공학 수업에서 SR 플립플롭을 배웠다. 기본 동작은 간단하다.
Set(S)=1이면 출력 Q가 1이 되고,
Reset(R)=1이면 Q가 0이 된다.
그런데 S=1, R=1이면 Q와 ~Q가 모두 1이 되어서 불능 상태라고 한다.
그래서 이 조합은 애초에 피해야 하는 입력으로 분류된다.

이 얘기를 들었을 때는 그냥 "아~ 그렇구나" 하고 넘어갔지만,
문득 이런 생각이 들었다.

"근데, 진짜 회로에다 S=1, R=1을 억지로 넣어버리면 어떻게 되지?"

실제로 해볼 수는 없었다. 장비가 없기도 하고
시뮬레이터도 대부분 이 상태를 허용하지 않는다.
그래서 결국 챗GPT한테 물어봤다.

몇 번의 대화를 통해 다음과 같은 내용을 알게 되었다.

1. 불확정 상태

S=1, R=1일 때 플립플롭의 출력은 예측할 수 없다.
이건 단순히 값이 정해지지 않은 수준이 아니라,
Q와 ~Q가 동시에 1이 되는 비논리적 상황이 발생할 수도 있는 것이다.
플립플롭 내부 회로가 어떻게 설계되었는지에 따라
그 결과는 다르게 나타날 수 있다.

2. 메타스테이블 상태

조금 더 흥미로운 건 메타스테이블 상태이다.
이건 ‘불안정한 중간 상태’라고 보면 된다.
Q가 0도 아니고 1도 아닌, 애매한 전압값에 놓인 상태.
디지털 회로는 0과 1만 다룬다고 하지만,
현실은 전압 레벨이라는 아날로그 물리량을 다루기 때문에
이런 경계선에서 회로가 잠시 흔들릴 수 있다.

메타스테이블 상태에선 출력이 안정화되기 전까지
다른 회로에서 그 출력을 읽어버리면 오류나 동기화 문제로 이어질 수 있다.
그래서 동기 회로에서는 이 문제를 아주 조심스럽게 다룬다.

3. 회로 손상은 없을 가능성

다행히 요즘 디지털 회로는 S=1, R=1 같은 상태가
일시적으로 들어오더라도 물리적으로 망가지지 않도록 설계된다.
예외 처리 회로나 기본값으로 리셋되는 구조가 들어가 있는 경우도 있다.
다만, ‘망가지지 않는 것’과 ‘의미 있는 출력을 내는 것’은 다르다.

4. 일부 설계에서는 이 상태를 활용하기도 한다

일부 특수한 플립플롭 설계에서는
S=1, R=1 같은 입력 조합을 특정 기능으로 활용하기도 한다.
예를 들어 모든 출력을 초기화하거나, 시스템을 강제 리셋하는 트리거로 삼는다.
하지만 이런 경우는 엄격하게 제어된 환경에서만 사용된다.

결론을 내보면

S=1, R=1은 이론적으로 "쓰면 안 되는 입력"이지만
현실에서는 이 입력이 들어왔을 때도
그 결과는 설계에 따라 달라질 수 있다.
그래서 단순한 ‘금기’가 아니라,
디지털 회로와 아날로그 물리의 경계선을 보여주는 흥미로운 사례라고 느꼈다.

디지털 회로는 이론적으로는 0과 1이라는 이산적 세계에 살고 있지만,
실제로는 전압이라는 연속적인 물리량을 다루고 있다.
불확정 상태, 메타스테이블 상태 같은 개념은
바로 이 경계에서 발생하는 자연스러운 현상이다.

역시 GPT다 덕분에 궁금증이 풀렸다! 고마워요!

데이터가 모여서 법칙을 만들고!!
법칙은 등식을 만들어!!
문제를 풀 수 있게 해준다!!!

ex) 역학적 에너지 보존 법칙이 등식을 만들어서!!

초기 높이를 알 때, 떨어지고 난 속력을 알 수 있게끔 해준다.

운동도 하고 입시도 겪고 여러 학문에 대한 공부도 하고 언어도 배우고 그 과정에서 여러 전문가들, 학자들의 동영상이나 글에 대해서도 읽다보니 무언가를 잘하게 된다는 것이 어떻게 이루어지는가 고민을 하게 됐다.

나 역시 어떤 것은 극복하고 어떤 것에는 좌절하며 무언가를 배우는 과정에 있기에,,,

그 동안 깨달은 것들을 잊지 않기 위해 여기에다 적어두려 한다.
전적으로 저만의 의견임을 알립니당.

1. 무언가를 배우는 과정은 Input/Output으로 나뉜다.
 Input은 정보의 입력이고 Output은 정보의 꺼냄이다. Output은 말로 언어로 내뱉는 것 뿐만 아니라 머릿속으로 생각하는   것까지 포함한다.
 이 말은 능동적으로 학습하라는 의미이다.

 이 말은 끊임없이 두 과정을 반복하면 할수록 무언가에 대해 숙달됨을 뜻한다.
 어떤 목적이 있다면 Input의 과정을 세분화시키고(ex elaborate, 친숙화 등) Output의 방법들을 여러가지로 정하는데
 어쨌든 이 같은 경우도 Input과 Output에 모조리 들어간다.

2. 세상은 너무나도 다변수함수이기에 효율을 추구하기 쉽지 않다.

 최고의 효율이라 자부했던 것도 내가 생각치 못한 변인에 의해서 좌절된다.
 따라서, 모든 사람이 같은 방식으로 학습하는 것은 쉽지 않다.
(ex 학습자의 여유, 심리, 능력, 환경등의 여러 요인의 차이가 존재)
 그럼에도 효율적인 방법론을 찾는 시도는 계속돼야 한다.
 그러다보면 점점 오차값이 작아지게 된다.

3. 2에 의해 무언가를 배우는 초기 시기에는 효율이 아닌 효과를 측정해야한다.
 시행착오를 겪어야 본인의 상태가 진단될 수 있다.(나 또는 교수자에 의해)
 효과를 측정할 수 있는 시스템을 구축하고 효과를 계속해서 측정해 나가야 한다.

 그러다보면 어떨 때 효과증가량이 증가하고 감소하는지 감(직관)이 온다.

4. 3의 과정으로 본인의 실력이 늘어나면 즉, 변인통제가 되면 이후 효율을 추구하면 좋다.

 진단된 상태, 또는 정량화된 수치가 쌓이고 감(직관)이 생기면 이후 내가 해당 영역을 어느정도 이해했다는 뜻이다.

 이는 어떤 상태를 '주요'변인들을 통제할 수 있다는 의미이다.

5. 학제간(Interdispline)의 공통점과 차이점을 찾는 것은 효과적이면서 효율적인 방법이다.
 수학문제를 잘 풀게 된 경험을 과학문제에
 국어문제를 잘 풀게 된 경험을 수학문제에
 수학문제에 대한 깨달음을 알고리즘에 
 공부를 하면서 깨달은 내용들을 운동에
 적용시킬 수 있다면 적용시키면 좋다.

오늘은 여기까지

코딩도장이란 사이트에서 가져온 문제입니다.

내 생애 처음으로 푼 알고리즘 문제입니다.~

문제.
n개의 정수를 가진 배열이 있다. 이 배열은 양의정수, 음의 정수를 모두 가지고 있다.
이제 당신은 이 배열을 좀 특별한 방법으로 정렬해야 한다.

정렬이 되고 난 후, 음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다.
또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.

예시 -1 1 5 -8  3  → -1 -8  1 5 3

파이썬 기준

챗 GPT한테 물어보니 이렇게 푸네요

챗GPT 풀이

def special_sort(arr):
    negative = [x for x in arr if x < 0]
    positive = [x for x in arr if x >= 0]
    return negative + positive

저는 파이썬의 문법에 대해서는 1도 모르지만 대충 뭔 말인지는 알겠습니다.

수학에서 집합의 조건 제시법이란 굉장히 비슷하네요.

저는 수학문제 풀듯이 해결했습니다.

방법1

def move_positives_right(arr):
    length = len(arr)
    i = 0
    count = 0
    while count < length:
        if arr[i] >= 0:
            arr.append(arr.pop(i))
        else:
            i += 1
        count += 1
    return arr

간단하게 저런 문법 모르겠고라는 마음가짐으로 푼 건데 아이디어는 제가 제시했고

문법은 기특한 챗GPT님께서 제시해줬습니다.

저의 지시사항은

양수를 볼 때마다 맨 오른쪽으로 보내라였습니다.

그런데, 한가지 문제점이 생기죠. 처음 풀때는 사실 너무 쉽다 생각했는데 간과한 점이 있었습니다.

바로 양수를 맨 오른쪽으로 보내면 오른쪽에 양수에 쌓여있기에 계속해서 무한히 이 과정을 반복합니다.

아하~

그래서 조금 궁리하다 제 아이디어를 어떻게든 관철시키고자 한 가지 조건을 덧붙입니다.

흠,,

그냥 정수의 갯수만큼만 탐색하면 되지 않나?
조금 생각해보니 될 것 같아서

만든 소스코드가 저것입니다.

방법2

def rearrange_negatives_method1(arr):
    last_negative_index = -1
    for i in range(len(arr)):
        if arr[i] < 0:
            last_negative_index += 1
            arr.insert(last_negative_index, arr.pop(i))
    return arr

다음 방법은 방법1과 발상은 비슷합니다.

초기에 문제를 보고 여러가지 아이디어를 냈는데

심플하게 양수를 오른쪽으로 제끼는 게 방법 1이고

음수를 왼쪽으로 제끼는 게 방법 2입니다.

처음에는 음수를 보이면 왼쪽으로 보내면 된다고 생각했는데 역시 예기치 못한 문제가 발생합니다.

초기에 GPT가 준 해답에서 '음수가 발견되면 가장 왼쪽에 있는 양수와 위치를 교환한다'라는 논지의 코드를 짰는데

그러면 음수는 왼쪽으로 순서가 그대로 정렬되지만

양수는 위치가 바뀌죠

예를 들어,

-1 1 5 -3 같은 경우 -3을 탐지하고 1과 위치를 교환할 겁니다.

그러면 이는

-1 -3 5 1이 되버립니다.

그래서, GPT한테 왜 그따구로 코드를 짰는지 고민해봤는데 찾아보니 교환하는 것이
알고리즘에서는 가장 적은 노동, 가장 적은 에너지를 사용하는(이런 표현을 해도 되는지 모르겠지만) 행위이기 때문임을 깨닫습니다.

그래서 또 돌파구를 찾았는데

교환하려니 순서가 바뀌고

다른 조건을 넣자니 코드가 길어지고 탐색의 과정이 길어집니다.

그래서, 어떻게든 음수를 왼쪽으로 보내버린다라는 아이디어를 살린 게 음수를 추출하고 삽입하는 형식의 위 방법인데

제가 생각해도 별롭니다.

알고리즘 문제를 처음 풀어봤는데 수학이랑은 쫌 다르다고 느꼈습니다. 확실히

그렇지만 또 이것만의 매력이 있어서 푸는 재미를 쫌 느꼈는데

처음 아이디어를 관철시키려고 이것저것 궁리하는 재미랑

효율적인 풀이가 뭐가 있을까 아이디어를 내는 재미가 있어서 이 점은 수학 문제 풀이랑은 쫌 비슷하기 했습니다.

코딩이란 것이 결국 컴퓨터의 언어로 표현해야 하기 때문에 '내가 이러면 되는 거 아니야?'라고 생각한 것이

컴퓨터한테는 어려운 문제일수도 있고 나한테 어려운 행위가 컴퓨터한테는 쉬울 수도 있단 것을 깨달았습니다.

앞으로 알고리즘 문제를 푸는 것도 꽤 재밌을 것 같네요.