2. 어텐션 메커니즘 등장

핵심 아이디어: “중요한 단어에 더 집중하자!” • 인코더의 모든 은닉 상태를 참고함 • 중요한 단어에는 높은 가중치 부여 • 다만, 모든 상태를 저장해야 해서 메모리 증가 • RNN 기반이라 여전히 느림

3. 트랜스포머: RNN을 완전히 버린 모델 • 병렬 처리 가능 → 엄청 빠름 • 입력 문장을 전체적으로 한꺼번에 분석 • 핵심 기술 = 셀프 어텐션(Self-Attention) → 각 토큰이 다른 모든 토큰과 관계를 학습

4. 추가 기술들

위치 인코딩(Positional Encoding) • 트랜스포머는 순서를 모르기 때문에 sin·cos로 위치 정보 추가

잔차 연결 + 층 정규화 • 학습 안정 • 깊은 모델에서도 정보 손실 감소

인코더·디코더 블록 • 여러 층을 쌓으면 강력한 표현 가능

5. BART / KoBART (텍스트 요약에 특화) • 트랜스포머 인코더-디코더 구조 • 요약, 생성에 아주 강함 • KoBART는 한국어 데이터로 파인튜닝됨 → 실사용 가능

6. HuggingFace transformers • pipeline() 하나로 요약 / 번역 / 생성 다 가능 • 모델과 토크나이저는 별도의 객체 • GPU 설정도 간단

순차 데이터란?

• 텍스트, 시계열 데이터, 일정시간 간격으로 기록된 데이터 처럼 순서에 의미가 있는 데이터

이미지 한장을 분류하는 것은 순서가 상관 없다. 모델을 만들 때 골고루 있는 더 좋을 때가 있다. 하지만 그렇지 않은 경우는 순서를 유지해야한다.)

• 피드 포워드 신경망 :: 입력 데이터 흐름이 앞쪽으로 전달되느 신경망
• 토큰 :: 분리된 단어
  • 샘플 하나에 토큰 여러개 존재
  • 1개의 토큰이 하나의 타임스텝에 해당한다.
  • 0 : 패딩, 1: 문장의 시작, 2: 어휘사전에 없는 토큰

순환 신경망

• 일반적인 완전 연결 신경망과 거의 비슷하지만, 이전 데이터를 순환하도록 하는 고리를 붙인다.
• 이전 샘플에 대한 기억을 가지고 있다.

순환 신경망으로 IMDB 리뷰 분류

IMDB 리뷰 데이터셋

from tensorflow.keras.datasets import imdb

(train_input, train_target), (test_input, test_target) = imdb.load_data(
    num_words=200)

순환 신경망 만들기

순환 신경

rmsprop = keras.optimizers.RMSprop(learning_rate=1e-4)
model.compile(optimizer=rmsprop, loss='binary_crossentropy',
              metrics=['accuracy'])

checkpoint_cb = keras.callbacks.ModelCheckpoint('best-simplernn-model.keras',
                                                save_best_only=True)
early_stopping_cb = keras.callbacks.EarlyStopping(patience=3,
                                                  restore_best_weights=True)

history = model.fit(train_oh, train_target, epochs=100, batch_size=64,
                    validation_data=(val_oh, val_target),
                    callbacks=[checkpoint_cb, early_stopping_cb])

plt.plot(history.history['loss'])
plt.plot(history.history['val_loss'])
plt.xlabel('epoch')
plt.ylabel('loss')
plt.legend(['train', 'val'])
plt.show()

단어 임베딩 사용하기

model2 = keras.Sequential()

model2.add(keras.layers.Embedding(200, 16, input_shape=(100,)))
model2.add(keras.layers.SimpleRNN(8))
model2.add(keras.layers.Dense(1, activation='sigmoid'))

model2.summary()

plt.plot(history.history['loss'])
plt.plot(history.history['val_loss'])
plt.xlabel('epoch')
plt.ylabel('loss')
plt.legend(['train', 'val'])
plt.show()

LSTM과 GRU 셀

• LSTM : 장단기 메모리
• GRU : 게이트 순환 유닛

인공 신경망으로 패션 아이템 분류하기

• 케라스 모델은 훈련하기 전 설정 단계가 존재
• complite() 메서드에서 수행한다.
• 필수로 지정할 것은 손실함수의 종류이다.

  model.compile(loss='sparse_categorical_crossentropy', metrics=['accuracy'])
  

![](https://velog.velcdn.com/images/joo_zero/post/087b89e2-bf66-43cf-af47-233ee5296071/image.png)
![](https://velog.velcdn.com/images/joo_zero/post/e0a2c81f-a98d-4a6e-ad3d-a2e7a99ee836/image.png)


### kaggle Student Performance(Multiple Linear Regression)

#### 1. kaggle Student Performance

1. 데이터 불러오기 
- 기본 통계 확인(info(), describe())
``` python
import pandas as pd
df = pd.read_csv("farm/kaggle/input/students-performance-in-exams/StudentsPerformance.csv")
df.info(); df.describe()

2. EDA

• 이상치 확인
• 성별 인종 부모학력 점심 등 점수 분포 시각화

  import seaborn as sns, matplotlib.pyplot as plt
  sns.countplot(x='gender', data=df)
  sns.boxplot(x='test_preparation_course', y='math_score', data=df)
  sns.heatmap(df.corr(), annot=True)
  
  

3. 데이터 전처리
- 범주형변수인코딩
- 새로운 피처 생성
- 데이터셋 분할(train_test_split)
``` python
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
df['gender'] = le.fit_transform(df['gender'])
df = pd.get_dummies(df, drop_first=True)
df['average_score'] = df[['math_score','reading_score','writing_score']].mean(axis=1)

4. 모델 학습 및 평가

• LinearRegression, LogisticRegression, RandomForestClassfier 등 비교
• 예측 결과 시각화 및 정확도 평가

  from sklearn.model_selection import train_test_split
  from sklearn.linear_model import LinearRegression, LogisticRegression
  from sklearn.ensemble import RandomForestClassifier
  

X = df.drop('average_score', axis=1) y = df['average_score'] X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

lr = LinearRegression().fit(X_train, y_train) rf = RandomForestClassifier().fit(X_train, y_train.round()) # 분류형 예시

#### 2. Student Performance ((Multiple Linear Regression)
1. 데이터 불러오기/기초 확인
``` python
import pandas as pd  
df = pd.read_csv("…Student-Performance-Multiple-Linear-Regression.csv")  
df.info(); df.describe()

2. EDA
3. 데이터 전처리 및 특징 엔지니어링

• 학습용 데이터셋 / 테스트용 데이터 셋 나누어짐

4. 다변량 선형 회귀

   from sklearn.linear_model import LinearRegression  
   lr = LinearRegression()  
   lr.fit(X_train, y_train)  
   y_pred = lr.predict(X_test)

• 여러 독립변수를 사용해서 종속변수 예측
• 모델의 유의성 분석이 존재.

5. 모델 평가 및 해석

• 회귀모형이 얼마나 잘 들어맞는지 R² 값, 잔차 분석 등을 통해 평가. 각 독립변수가 얼마나 유의미한지(p-value) 분석: 공부시간, 이전시험점수는 유의

1. 가장 기본적인 인공 신경망은 확률적 경사 하강법을 사용하는 로지스틱 회귀와 같다.
2. 이미지, 음성, 텍스트 분야에서 효과적인 성능

패션 MNIST

(train_input, train_target), (test_input, test_target) = keras.datasets.fashion_mnist.load_data()

import matplotlib.pyplot as plt

fig, axs = plt.subplots(1, 10, figsize=(10,10)) 
for i in range(10):
    axs[i].imshow(train_input[i], cmap='gray_r')
    axs[i].axis('off')
plt.show()

unique 확인

    import numpy as np
    print(np.unique(train_target,return_counts=True))

딥러닝 라이브러리

• 다른 머신러닝 라이브러리와 다르게 GPU사용하여 인공신경망 훈련한다.
• (백터/행렬 연산에 최적화)

심층신경망 만들기

dense1 = keras.layers.Dense(100, activation='sigmid', input_shape=(784,))
dense2 = keras.layers.Dense(10, activation='softmax')

• 뉴련 개수는 직접 판단해야하는 것이다.
• 정보손실이 없도록 하기 위해 출력층의 유닛 개수보다 많은게 좋음

층을 여러개 추가하는 방법도 있음 = Dense() 클래스 > Sequential()에서 바로 하는 것

model = keras.Sequential([
    keras.layers.Dense(100, activation='sigmid', input_shape=(784,) , name='hidden'),
    keras.layers.Dense(10, activation='softmax', name='output)
    ], name='패션 MNIST model')

모델에 .add()로 원하는 만큼 추가 가능

model = keras.Sequential()
model.add(keras.layers.Dense(100, activation='sigmid', input_shape=(784,) , name='hidden'))
model.add(keras.layers.Dense(10, activation='softmax', name='output))
model.add(keras.layers.Dense(10, activation='softmax', name='output))

확인해볼 명령어

model.summary()

훈련하는 것은 동일

model.compile(loss='sparse_categorial_crossentropy', metrics='accuracy')
model.fit(tranin_scaled, train_target, epochs=5)

Flatten()을 사용하여 추가

model=keras.Sequential()
model.add(keras.layers.Flatten(input_shape=(238,28), name='flatten'))
model.add(keras.layers.Dense(100, activation='sigmid', input_shape=(784,) , name='hidden'))
model.add(keras.layers.Dense(10, activation='softmax', name='output))

• .reshape() 필요가 없어진다.

ps. 앙상블 알고리즘 vs 심층신경망

1. 앙상블 알고리즘

• 여러개의 모델로 예측을 앙상블
• 얘는 각각의 모델들이 독립적으로 훈련됨
• 정형 데이터에 적합(DB, 엑셀 등)

2. 심층 신경망

• 은닉층만 보면, 여러층의 뉴런을 쌓아 최종 출력값을 계산
• 뉴런들이 동시에 훈련됨
• 더 길게 층을 쌓아서 단계적 학습기능
• 비정형 데이터에 적합(이미지, 텍스트 등)

로지스틱 회귀

1. 표준화 할 때 훈련세트의 통계값으로 테스트 세트를 변환해야한다.
2. 로지스틱 회귀가 이진 분류에서 확률을 출력하기 위해 사용하는 것으로 선형 방정식의 출력을 0~1 사이의 값으로 하여 이진 분류를 위해 사용한다.
3. 로지스틱 회귀가 이진 분류에서 확률을 출력하기 위해 쓰는 함수는 시그모이드 함수다.
4. 다중분류에서는 여러개의 선형방정식 출력값을 0~1 사이로 압축하고 합이 1이 되도록 하는 소프트 맥스 함수 사용하기
5. 선형 분류 알고리즘

과대/과소 적합

import numpy as np
import matplotlib.pyplot as plt

sc = SGDClassifier(loss='log_loss', random_state=42)

train_score = []
test_score = []

classes = np.unique(train_target)

for _ in range(0, 300):
    sc.partial_fit(train_scaled, train_target, classes=classes)

    train_score.append(sc.score(train_scaled, train_target))
    test_score.append(sc.score(test_scaled, test_target))

plt.plot(train_score, label='train_score')
plt.plot(test_score, label='test_score')
plt.xlabel('epoch')
plt.ylabel('accuracy')
plt.legend(loc='lower right')
plt.title('과대/과소 적합확인')
plt.show()

• 에포크 수를 많은 경우 과대적합
• 에포크 수가 적으면 과소적합

트리 알고리즘

1. 결정트리

• 모델 :: 스무고개와 비슷

• 출처 : Baek Kyun Shin

지니 불순도

• 노드에서 데이터를 분할할 기준을 정할 때 사용
• O :: 순수한 노드, 0.5 :: 최악의 지니 불순도
• 지니 불순도 = 1 - (음성 클래스 비율 ^2 + 양성 클래스 비율^2)

엔트로피

• 지니 불순도와 동일하게 결정트리의 불순도를 구하는데 사용
• 수식에서 지니는 제곱을 사용하고 엔트로피는 로그를 사용(차이점)

Pruning

• == 가지치기
• 트리의 가지가 계속 많아지면 모델의 정확성이 떨어진다. 즉 일반화가 안된다.

교차 검증과 그리드 서치

• 훈련세트(약 60%), 검증세트 (약 20%), 테스트세트(약 20%)정도로 구분 (구글링)

Cross Validation

• 검증세트를 떼어내서 평가하는 과정을 여러번 반복
• K-Fold Cross Validation
  • k-1개의 훈련세트와 1개의 검증세트를 만들고 학습하고 검증. ( 이를 k 번 반복 )

그리드 서치

• 하이펄파라미터 탐색을 자동화 해주는 도구

랜덤 서치

• 그리드 서치하는 시간이 오래걸리면 사용해보기

트리의 앙상블

• 정형 데이터 : 표, 그래프와 같이 정리되어 있는 것

• 반정형 데이터 : csv, JSON, XML

• 비정형 데이터 : .avi, .wav, .JPG

• n_jobs를 -1로 설정

앙상블 학습

• 더 좋은 예측 결과를 만들기 위해 여러개의 모델을 훈련하는 알고리즘 (머신러닝)

랜덤 포레스트

• 대표적인 결정 트리 기반의 앙상블 학습 방법

엑스트라 트리

• 랜덤 포레스트와 비슷한데 부트스트랩 샘플 사용 X
• 램덤하게 노드를 분할하여 과대적합을 방지

양도 많고 어렵다 ...

현재 혼자 공부하는 ~ 시리즈의 책으로 공부를 진행하려고 한다. 13주차까지 계획을 세웠는데, 회의하여 10주차에 맞춰서 다시 계획을 작성할 예정이다.

목표

사용자가 특정 포맷의(pdf, docx, txt) 논문, 과제를 포함한 텍스트 데이터를 입력하면 이를 AI, Human으로 분류하여 분석

인공지능 공부 안해봐서 잘 모르는데, 지피티 킬러 같은 느낌인 것 같다. 일정 상 분석까지만 하는 걸로 하였는데, 기간이 끝나더라도 목표한 것까지 완료해보고 싶다.

교재는 해당 교재이다. '딥 러닝을 이용한 자연어 처리 입문'과 위 교재를 두고 고민했는데, 팀원들의 의견에 맞춰 실습 위주인 책으로 골랐다.

1주차 내용

1주차에는 1~3까지의 챕터를 진행하기로 했고, 일단 코랩 설정까지 해야한다. 그 전까지는 기본 이론 내용이여서 해당 글에는 작성하지 않겠다. 계정은 동국대 계정으로 코랩을 진행할 예정이다.

코랩은 전에 사용했던 설정 그대로 사용하면 될 것 같다.

아직은 크게 진행된 내용이 없는데, 2주차에는 조금 더 많은 내용과 깊이있는 내용을 작성하고 싶다.

가비지컬렉션이란 쓰레기 값 :: 참조되지 않는 값을 의미한다. JVM이 지워준다고 하는데, 왜 우리가 신경을 써야할까 ?

파일은 어떻게 저장될까

같은 파일에 속성을 보았을 때, 왜 크기와 디스크할당크기가 나뉘어있고 크기가 다를까?

1. 컴퓨터는 보조기억장치와 주기억장치로 나뉘어 있다. 디스크는 어디와 더 가까운 걸까?

   보조기억장치에 더 가깝다.

2. 저장할 때는 1byte로 저장을 했는데, 사용할 때 사용되는 크기는 이제 (TLS)8kb로 사용하게 될 것이다. + ssd는 하드디스크랑 다르게 덮어쓰기가 불가능하다. read/write이 8kb와같이 크다면, 어떻게 구성해야하나 ?

그럼 이 때 가비지컬렉션은 언제 하는걸까 ?

SSD는 새로운 데이터를 쓰기 위해서 크게 3가지의 과정을 거친다. *1. 유효한 페이지 복사 2. 블록 전체 삭제 3. 새로운 데이터 쓰기 *

[쉽게 말하면,]

1. 참조를 끊어놓는다. (실제 삭제하지 않음)
2. OS 자체에서 사용자가 보조기억장치만 쓰고 주기억장치가 사용되고있지 않다고 판단되면, 그때 실제로 삭제한다. ex ) 게임하는데 갑자기 PC가 우웅하면서 재부팅 되는 느낌이 드는 것 => 가비지컬렉션 하는 것

3. 그렇다면 예를 들어보자. 3-1.정말 꽉 찬 usb(블록) 두개가 있다고 가정하자. 3-2. ssd 100%로 사용한다고 하자 3-3. 그럼 블록을 복사해두고 사용해야할텐데,어떻게 하나? 3-4. usb 속성을 보면, 용량이 자연수가 아닌 소수로 끝난다. 이때, 남은 소수점자리는 뭐하나 ??

유효블록을 남겨둔 것이다. 1. 가비지컬렉션하기위해 2. 성능 좋게하기 위해서 3. 복원 잘 할 수 있기 위해서

내용을 어지럽게 써둔 것 같은데 다시 공부를 하고 잘 정리해야겠다. 이제 HW의 가격을 내리고 크기를 올리는 추세라고 하는데, 이거에 대응되는 SW를 만들기 위해 저장공간/가비지컬렉션 하는 방법을 주의하면서 공부해야겠다.

이진탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 나누어 데이터를 탐색하는 방법으로, 시작점, 끝점, 중간점을 이용

  순차탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

특징

• 단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 log2N에 비례한다.
• 이진탐색은 탐색범위를 절반씩 줄어든다.
• 시간복잡도 O(logN)

  예시

  찾고자 하는 값

  4

  1단계

• (인덱스) : 시작점 : 0, 끝점: 9, 중간점 4(소수점 이하 제거)
• List : [0,2,4,6,8,10,12,14,16,18]

1. List[중간점:4]의 값은 8이 된다.
2. 8의 값이 찾고자 하는 값보다 크기 때문에, 끝점이 9->3로 변경된다.

• 끝점 수식 : 중간점 - 1

  2단계

• (인덱스) : 시작점 : 0, 끝점 : 3, 중간점 : 1
• List : [0,2,3,6]

1. List[중간점:1]의 값은 2가 된다.
2. 2가 찾고자 하는 값(4) 보다 작기 때문에, 시작점이 0->2 로 변경된다.

• 시작점 수식 : 중간점 + 1

  3단계

• (인덱스) : 시작점 : 2, 끝점 : 3, 중간점 :2
• List : [4,6]

1. List[중간점:2]의 값은 4가 된다.
2. 4가 찾고자 하는 값 (4)와 같기 때문에 로직은 끝나게 된다.

• 찾고자 하는 값 수식 : 중간 == 찾고자 하는 값

코드

def binary_search(array, target, start, end):
   while start <= end:
       mid = (start+end) // 2
       if array[mid] == target:
           return mid
       elif array[mid] > target:
           end = mid-1
       else:
           start = mid+1

    retrun None


n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

자주 쓰이는 Python라이브러리

• bisect_left(array,x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(array, x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

a= [1,2,4,4,8]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))

[]실행결과 2 4

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

[]실행결과 2 6

활용 예시

• 파라메트릭 서치

1. 주차마다 배운 내용 정리

2. 개념은 해당 페이지에 이어서 정리

3. 코드 정리는 주차씩 블로그 만들어서 정리

4. ** 알고있는 개념이여도 다 적어둘 것**

1. 재귀함수

• 큰 문제를 부분 문제로 나눠 풀 때 사용
• 반드시 기저사례를 사용할 것
• 사이클이 있다면 사용 금지
• 반복문이 될 수 있다면, 반복문으로 구현
• 이해가 가지 않는다면, 그림으로 그려보기

ex1. 팩토리얼

5! = 5 x 4 x 3 x 2 x 1 ---> n x n-1 x n-2 x n-3 x n-4 f(n) = n(n-1) f(n-1) = (n-1)(n-2) f(n-2) = (n-2)(n-3)

//코드

int fac(int n){
    if(n==1) return 1;
    return n * f(n-1);
}

ex2. 피보나치

0 + 1 + 1 + 2 + 3 = 5

//코드

int fivo(int n){
    if(n==1 || n==0) return n;
    return f(n-1) + f(n-1);
}

ex3. 하노이탑 ⭐

1. 맨 마지막을 제외(n-1)을 제외하고 temp에 넣어주기
2. 맨 마지막을 to(옮길 위치)에 넣어주기
3. 맨 마지막을 to(옮길 위치)에 넣어주기

void hanoi(int n, char from, char temp, char to){ if(n==1) printf("원판 1을 %c -> %c로 이동\n", from, to); // 마지막 넣는 것 else{ hanoi(n-1, from, to, temp); printf("%d를 %c -> %c로 이동\n", n-1, from, to); hanoi(n-1, temp, from, to); }

}

int main(){ hanoi(4, 'A', 'B','C'); return 0; }

## 2. 순열
-  순서와 상관 있게 뽑는 것 :: 순열
-  순서와 상관없이 뽑는 것 :: 조합
- 정렬이 되어 있어야함.

 next_permutation(시작, 끝); :: 오름차순
 ~~prev_permutation(시작, 끝); :: 내림차순~~

 > [공식]
 nPr : n! / (n-r)!
 n : 몇개중에
 r : 몇개 뽑을 건지


``` c++
//코드

vector<int> v = {2,1,3};
int a[] = {1,2,3};

sort(v.begin(), v.end());
sort(&a[0], &a[0]+3);

next_permutation(v.begin(), v.end());
next_permutation(&a[0], &a[0]+3);
next_permutation(a, a+3);

2-1. 재귀함수로 만드는 순열

1. 기본순열

   //코드
   
   next_permutation(v.begin(), v.end());

2. 재귀함수로 만드는 순열

• 이해가 안된다면, 꼭 그림 그려서 파악해보기

  
  int make_permutation(int n, int r, int depth){
    if(r==depth) return;
  
   for(int i=depth; i<n;i++){
       swap(v[r], v[depth]);
       make_permutation(n, r, depth+1);
       swap(v[r], v[depth]);
   }
   return;
  }
  

  

2. 메모리

• 메모리는 16진수로 이뤄져 있으며, 1byte씩 사용됨
• 포인터 변수는 자료형에 상관 없이 항상 8byte(64bit기준)

• N개 만큼 입력 된 좌표에 대한 촤표압축 문제

💡알고리즘 설계

• 입력한 리스트에 대해 오름차순 정렬을 한 후 중복제거를 해준다.
• key : 작은 좌표부터 큰 좌표 순으로 저장
• value: 본인 좌표보다 작은 좌표의 개수 저자
• 본인 좌표보다 작은 좌표의 개수를 출력

💡코드

import sys

N = int(sys.stdin.readline().strip())

X = list(map(int, sys.stdin.readline().strip().split()))

X_sort = sorted(list(set(X)))

dic = {}
for i in range(len(X_sort)):
  dic[X_sort[i]] = i

for i in X:
  print(dic[i], end=" ")

💡시간복잡도

💡 틀린 이유

처음에 시간초과가 떴다.

💡 틀린 부분 수정 or 다른 풀이

Set을 이용하여 중복을 제거해줬더니 문제 해결 됐다.

💡 느낀점 or 기억할정보

파이썬에 내장되어 있는 라이브러리가 많다는 것을 계속 느끼게 되고 , 코테를 위해 좀 더 많이 알아둬야겠다는 생각을 했다.

• 랜선의 길이를 움직여 랜선 갯수를 확인하는 문제

💡알고리즘 설계

• start : 1 , end : 랜선 길이 중 가장 긴 길이
• mid 를 start 와 end의 중간으로 두고, 모든 랜선 값을 mid로 나눠 총 몇개의 랜선이 나오는지 확인
• 랜선이 목표 이상이면 start : mid + 1
• 랜선이 목표 이하이면 end : mid - 1 (이분탐색)
• start == end라면 조건을 만족하는 최대의 랜선 길이를 찾는다.

💡코드

import sys
K, N = map(int, input().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(lan) #이분탐색 처음과 끝위치

while start <= end: #적절한 랜선의 길이를 찾는 알고리즘
    mid = (start + end) // 2 #중간 위치
    lines = 0 #랜선 수
    for i in lan:
        lines += i // mid #분할 된 랜선 수

    if lines >= N: #랜선의 개수가 분기점
        start = mid + 1
    else:
        end = mid - 1
print(end)

💡시간복잡도

O(logN)

💡 틀린 이유

💡 틀린 부분 수정 or 다른 풀이

💡 느낀점 or 기억할정보

백트래킹이랑 dfs bfs 하다가 이진탐색 문제 나오니까 조금 쉬워진 느낌이다.. 난 이진탐색도 중요하지만 그래프 탐색이 좀 더 어려우니 같이 공부 좀 해야겠다..

• 두번째 줄에 입력된 값들의 합 중 S 와 같은 값이 있다면 더하여, 합의 결과가 S와 같은 값이 몇개가 있는지 알아내는 문제.

💡알고리즘 설계

DFS에서 조금 응용하여 만약 반복문에서 돌고 있는 리스트의 인덱스 번호가 N보다 큰 값이라면 종료.

💡변경한 코드

def dfs(i, SUM):
  global cnt
  if i >= N:
      return
  SUM += n_list[i]
  if SUM == S :
    cnt += 1
  dfs(i+1, SUM-n_list[i])
  dfs(i+1, SUM)


N,S = map(int, input().split())
n_list = list(map(int, input().split()))
cnt = 0
dfs(0,0) #index 번호도 처음은 0이고, 처음 더한 값도 0이기 때문
print(cnt)

💡시간복잡도

💡 틀린 이유

재귀함수로 처음 dfs 를 다시 호출할 때 어떻게 해야할지 막막했다.

💡 틀린 부분 수정 or 다른 풀이

합을 다시 구해야하기 때문에 SUM-n_list[i]를 추가함

💡 느낀점 or 기억할정보

백트래킹과 DFS의 차이점은 알았다. 하지만 백트래킹을 DFS와 다르게 어느시점에 구현해야하는지 잘 모르겠다. DFS로 구현했다가 시간 초과가 나면 바로 BFS 로 해보고 BFS로 해도 시간초과 오류가 뜨면 백트래킹으로 해야하는 걸까 ? ㅜㅜ 어렵다

• 각 나라의 승패 횟수가 주어졌을때 해당 예제가 가능한지 불가능하지 판별해야함

💡알고리즘 설계

[처음]

• 팀의 승,무,패 모든 경우를 고르는 방식으로 진행(DFS) [이후]
• 백트래킹
• 6개의 국가가 있고, 총 18번의 경기를 한다.
• 승, 무, 패의 결과가 있으며, 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0
• 입력은 네 줄로 들어오며, 각 줄에 대해 가능한 결과 1, 불가능한 결과 0 을출력하는 문제이다

💡변경한 코드

• 실패를 계속 해서,, 다른 사람의 소스를 옮겨봤다.

from sys import stdin
from itertools import combinations as cb


def solution(round):
    global ans
    if round == 15:
        ans = 1
        for sub in res:
            if sub.count(0) != 3:
                ans = 0
                break
        return

    t1, t2 = game[round]
    for x, y in ((0, 2), (1, 1), (2, 0)):
        if res[t1][x] > 0 and res[t2][y] > 0:
            res[t1][x] -= 1
            res[t2][y] -= 1
            solution(round + 1)
            res[t1][x] += 1
            res[t2][y] += 1


answer = []
game = list(cb(range(6), 2))
# 백트래킹
for _ in range(4):
    data = list(map(int, stdin.readline().split()))
    res = [data[i:i + 3] for i in range(0, 16, 3)]
    ans = 0
    solution(0)
    answer.append(ans)

print(*answer)

💡시간복잡도

💡 틀린 이유

DFS 로 하려고 하니까 시간초과 + 메모리 초과 오류가 발생했다. 백트래킹으로 다시 풀어봐야할 것 같다.

💡 틀린 부분 수정 or 다른 풀이

DFS 방식에서 백트래킹 방식으로 변경

💡 느낀점 or 기억할정보

DFS와 백트래킹의 차이를 잡기가 조금 어려운 것 같다. 조금 더 개념에 익숙해진 후에 소스 적용을 더 해봐야할 것 같다.

• 백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법이다.
• 원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back해서 돌아가는 방법으로 이름 그대로 backtracking 알고리즘

관련용어

• 유망함(promising): 진행중인 경로가 해답을 찾을 가능성이 있음
• 유망하지 않음(nopromising): 진행중인 경로가 해답을 찾을 가능성이 없음
• 가지치기(pruning): 유망하지 않은 하위 트리를 잘라냄

특징

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 탐색
• 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않음
• 해답의 가능성이 있으면 유망함
• 가지치기 사용가능 (유망하지 않은 노드가 포함되는 경로는 고려하지 않는 기법)
• 기본적으로 재귀의 성격을 띄는 형태

백트래킹과 DFS의 차이점

백트레킹

• 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소
• 불필요한 경로의 조기 차단
• N! 가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능
• 모든 후보를 검사하지 않음

DFS

• 모든 경로를 추적
• N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 이용하면 처리 불가능 모든 후보를 검사

활용 예시

해를 찾는 도중 막히면 되돌아가서 다시 해를 찾는 기법

최적화 문제, 결정 문제에서 많이 사용 미로 찾기 / n-Queen 문제 / Map coloring / 부분 집합의 합 등

• 입력 한 값을 그래프로 만들었을 때, 만들어지는 그래프의 수를 출력

💡알고리즘 설계

• DFS 함수와 BFS 함수를 작성
• visited => 7 까지 하는 이유 : 노드에 0이 없기 때문
• 1~7까지 방문하지 않은 노드는 방문시작하도록 dfs/bfs시작
• dfs/bfs가 끝나면 count ++

💡변경한 코드

[DFS]
import sys
input = sys.stdin.readline

# dfs 함수
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        count += 1 # dfs 한 번 끝날 때마다 count+1

print(count)



[BFS]
from collections import deque

# bfs 함수
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        bfs(graph, i, visited) # bfs 한 번 끝날 때마다 count+1
        count += 1

print(count)

💡시간복잡도

O(N+M)

💡 틀린 이유

for 문을 돌면서 false였던게 true로 변경될 수도 있는데, 무작정 for문에서 false의 값을 체크하여 cnt++ 하려했다.

💡 틀린 부분 수정 or 다른 풀이

다시 풀어야지 ..

💡 느낀점 or 기억할정보

다시 풀어야지 ..

• DFS, BFS 개념 요약
• 노드갯수, 간선 수, 시작 노드 를 입력 받은 후 DFS값 출력, BFS 값 출력 하는 문제
• 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V
• M개의 줄에는 간선이 연결하는 두 정점의 번호

  💡알고리즘 설계

• DFS 함수와 BFS 함수를 작성
• 그래프의 처음은 빈 값으로 설정 > 그래프는 0번이 아닌 1번부터 사용한다고 조건에 되어있기 때문
• 그래프 입력 및 구현
  1. 입력 받은 두 수는 서로 연관이 되어 있기 때문에 인접리스트로 구현해줘야 한다.
  2. 예를 들어 1 4를 입력 받은 경우, 1번 노드에 4번 노드가 연결되어 있음을 구현하고, 4번 노드에 1번 노드가 연결되어 있음을 구현한다. 2-1. 이중 리스트의 1번 인덱스에 4를 넣고, 4번 인덱스에 1을 넣는다. EX) graph[a].append(b) graph[b].append(a) graph[a].sort() graph[b].sort()
  3. DFS BFS 호출

     💡코드

     # 1. 그래프 생성
     # 2. dfs 생성
     # 3. bfs 생성
     #. dfs 출력 후 bfs 출력
     

def dfs(g,v,visited) : visited[v] = True print(v, end =' ')

for i in graph[v]: if not visited[i] : dfs(g, i, visited)

from collections import deque def bfs(g, start, visited):

queue = deque([start]) visited[start] = True

while queue: v = queue.popleft() print(v,end =' ')

for i in graph[v]:
  if not visited[i]:
    queue.append(i)
    visited[i] = True

n,m,v = map(int, input().split()) graph = [[] for _ in range(n+1)]

for i in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) graph[a].sort() graph[b].sort()

visited = [False] * (n+1) dfs(graph, v, visited)

print("")

visited = [False] * (n+1) bfs(graph, v, visited)

```

💡시간복잡도

O(N+M)

💡 틀린 이유

입력시 그래프 sort를 시켜주지 않았다.

💡 틀린 부분 수정 or 다른 풀이

sort부분 추가

💡 느낀점 or 기억할정보

DFS와 BFS와 같은 개념 코드를 구현하는 것은 어렵지 않은데, 응용문제는 힘든 것 같다. 잘 이해하고 하나하나 구현해봐야겠다.

🎀기본개념

그래프 : 정점(Node)와 간선(Edge)로 이루어져 있는 자료구조 이런 그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있습니다. 노드를 하나씩 방문하여 모든 노드를 탐색하는 것을 목표로 합니다.

🎀🎀 깊이우선탐색 DFS

• 시작 노드를 기준으로 하여 가장 깊은 노드까지 방문 한 후 다음 노드를 탐색하는 것

DFS 이해하기

방법

[조건] 시작 노드 1 번호가 낮은 인접 노드부터 방문 stack = []

[방법]

• 시작노드를 기준으로 하여 방문한 노드를 stack에 쌓는다.
• 방문하지 않은 노드 중에서 낮은 인접 노드부터 방문하여 stack에 쌓는다.

1. 노드 1의 인접노드 : 2, 3 stack => [1 2,3]

2. 노드 2의 인접노드 : 1, 7 stack => [1,2,3,7]

3. 노드 7의 인접노드 : 6, 8 stack => [1,2,3,7,6,8]

4. 노드 6의 인접노드 : 7, 8 stack => [1,2,3,7,6,8]

5. 노드 8의 인접노드 : 1, 7 stack => [1,2,3,7,6,8]

6. 노드 3의 인접노드 : 1, 4, 5 stack => [1,2,3,7,6,8,4,5]

7. 노드 4의 인접노드 : 3, 5 stack => [1,2,3,7,6,8,4,5]

8. 노드 5의 인접노드 : 3, 4 stack => [1,2,3,7,6,8,4,5]

활용도

1. 모든 노드를 방문하고자 할 때 방법 사용
2. DFS 가 BFS보다 코드 간결
3. BFS보다는 속도가 느림
4. Stack | 재귀함수로 구현

🎀🎀 너비우선탐색 BFS

• 시작 노드를 기준으로 하여 인접한 노드를 먼저 탐색하는 방법
• 시작 노드로부터 가장 가까운 노드를 먼저 방문하고, 가장 멀리 떨어져 있는 노드를 나중에 방문하게 된다.

BFS 이해하기

방법

[조건] ** Queue 사용(deque) ** 시작 노드 1 번호가 낮은 인접 노드부터 방문

result = [] [방법]

1. 시작 노드 1을 큐에 넣는다. queue => [1]

2. queue 에서 노드 1을 꺼낸 후 방문하지 않은 인접한 노드 2,3,8을 queue에 넣는다. queue => [2,3,8] result => [1]

3. queue 에서 노드 2를 꺼낸 후 방문하지 않은 7을 queue에 넣는다. 1은 이미 방문처리가 되어 있기 때문에 PASS queue => [3,8,7] result => [1,2]

4. queue 에서 노드 3을 꺼낸 뒤 방문하지 않은 4,5를 queue에 넣는다. queue => [8,7,4,5] result => [1,2,3]

5. queue에서 노드 8을 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다. 1,7 모두 방문되어 있기 때문에 PASS queue => [7,4,5] result => [1,2,3,8]

6. queue에서 노드 7을 꺼낸 뒤 방문하지 않은 6을 queue에 넣는다. 2,8은 모두 방문되어 있기 때문에 PASS queue => [4,5,6] result => [1,2,3,8,7]

7. queue에서 노드 4를 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다. 3,5는 모두 방문했기 때문에 PASS queue => [5,6] result => [1,2,3,8,7,4]

8. queue에서 노드 5를 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다. 3,4는 모두 방문했기 때문에 PASS queue => [6] result => [1,2,3,8,7,4,5]

9. queue에서 노드 6을 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다. 7,8은 모두 방문했기 때문에 PASS queue => [] result => [1,2,3,8,7,4,5,6]

활용도

1. 최단 경로를 찾고 싶을 때 사용
2. DFS보다 구현이 어려움
3. Queue를 사용하여 구현

🎀🎀 DFS와 BFS의 정리

시간복잡도

• 두 방식 모두 모든 노드를 탐색했기 때문에 시간복잡도는 동일합니다.
• N: 노드, E: 간선일 경우
  • 인접리스트 : O(N+E)

활용한 문제

1. 경로의 특징을 저장해야하는 문제 ex ) 각 정점에 숫자가 있고 a~b까지 가는 경로를 구하는데 경로에 같은 수가 있으면 안된다는 문제등, 각각의 경로마다 특징을 저장해둬야 하는 경우 DFS를 사용. (BFS는 경로의 특징을 가지지 X)
2. 최단거리를 구하는 문제 미로찾기 등 최단거리를 구해야하는 경우, BFS가 유리
3. 검색 대상의 그래프가 크면 DFS사용
4. 검색대상의 규모가 크지 않고, 검색 시작 점으로부터 원하는 대상이 멀지 않다면 BFS사용

DFS Python코드

dfs DFS(g, v, visited):
    visited[v] = True
    print(v, end =' ')

    for i in g[v]:
        if not visited[i]:
            dfs(g, i, visited)

--------------------------------

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]

visited = [False] * 9

dfs(g, 1, visited)

g의 1번 노드를 비워둔 이유? -> 시작 노드는 대부분 1부터 시작하기 때문에 비워둔 것

visited에서 왜 * 9를 한 것인지? * 8하면 되는거 아닌가? -> 첫번째 노드를 비워뒀기 때문에 해당 노드 제외하고 false를 처리해야하기 때문. 그래야 인덱스 1~9번까지 false로 들어가게 된다.

• dfs(g, 1, visited) : 1번 노드부터 시작하겠다 의미

• visited[v] : True : 방문한 노드는 True로 설정 방문한 노드는 출력
• for i in g[v] :그래프 도는 동안
• if not visited[i] dfs(g, i, visited) : 방문하지 않은 노드가 있다면, 해당 노드를 탐색

BFS Python코드

from collections import deque

def bfs(g, start, visited):
    queue = deque([start])
    visited[start] =True

    while queue:
        v = quque.popleft()
        print(v, end =' ')
        for i in g[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True


----------

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]
visited = [False] * 9

bfs(g,1,visited)

• queue = deque([start]) : 기준이 되는 노드 queue에 삽입

• visited[start] = True : 해당 노드 방문처리
• while queue : queue 가 빌 때까지
• v = queue.popleft() : 노드 출력
• for i in g[v] if not visited[i] queue.append(i) visited[i] = True : 인접한 노드들 중 방문하지 않은 노드들을 큐에 삽입 후 방문 처리 하기

• stack 사용
• 처음에 몇 문장을 받을지 입력
• 문장을 띄어쓰기 기준으로 입력 받기

💡알고리즘 설계

• 띄어쓰기를 기준으로 하여 스택 쌓인거 출력

💡코드

T = int(input())

for _ in range(T):
  str = input()
  str += " "
  stack = []
  for i in str:
    if i != " ":
      stack.append(i)
    else:
        while stack:
          print(stack.pop(), end ='')
        print(' ', end= '')

💡시간복잡도

O(n)

💡 틀린 이유

처음에 밑에 else를 이중 for문 바깥에 넣어버려서 띄어쓰기가 되지 않고 출력됨

💡 틀린 부분 수정 or 다른 풀이

else를 이중 for문 안에 넣기

💡 느낀점 or 기억할정보

뭔가 리스트로 구현할 수 있을 것 같은데 일부러 스택사용 해봤다.. 리스트로도 구현해봐야지..

• queue 사용 (deque)

1. 입력받은 M의 중요도를 따져서 몇번째로 나오는지 확인

💡알고리즘 설계

0. 인덱스(index)와 원소를 동시에 접근하면서 루프를 돌릴 수 있는 enumerate 사용
1. 조건에 맞게 입력을 받기
2. 중요도를 확인하기 위해 max 함수를 사용
3. 큐의 맨 앞 문서가 현재 가장 중요한 문서인지 확인 중요한 문서라면 count += 1 && 종료
4. 찾는 문서가 아니면 출력되었으니까 큐에서 제거

💡코드

from collections import deque

num = int(input())
for _ in range(num):
    N, M = map(int, input().split())
    queue = deque(map(int, input().split()))
    queue = deque([(i, idx) for idx, i in enumerate(queue)])

    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == M:
                print(count)
                break
            else:
                queue.popleft()
        else:
            queue.append(queue.popleft())

💡시간복잡도

O(n)

💡 틀린 이유

queue서 뽑지 않는 경우 뒤로 보내지 않았음

💡 틀린 부분 수정 or 다른 풀이

queue.append(queue.popleft()) 를 통하여 해결

💡 느낀점 or 기억할정보

스택 큐 문제 이제 익숙해질 만도 한데 아직 힘들다 ㅜㅜ

1. Stack 사용
2. ( 괄호와 ) 괄호의 짝이 맞는지 확인

💡알고리즘 설계

1. 리스트로 구현하는 것이 아닌, stack 으로 구현할 것
2. ( 인경우 stack 에 쌓고, stack에 ( 이 있는 상태에서 ) 가 들어오면 (를 제거.
3. ( 가 없는데 )를 stack 에 넣으려고 한다면, 해당 반복문을 다시 돌지 말고(break) 바로 NO 출력

💡코드

n = int(input())

for _ in range(n) :
  text = input()
  stack = []
  for i in text:
    if i == '(' :
      stack.append("(")
    elif i == ')':
      if len(stack) == 0:
        stack.append(")")
        break
      else :
        stack.pop()

  if len(stack) == 0:
    print("YES")
  else :
    print("NO")

💡시간복잡도

O(n * text길이)

💡 틀린 이유

처음을 while로 구현하려다가 컴파일 에러 발생 그래서 그냥 for문으로 변경하여 사용

💡 틀린 부분 수정 or 다른 풀이

리스트로 충분히 구현할 수 있는 문제. 짝을 맞추는건 스택을 활용하자.

💡 느낀점 or 기억할정보

항상 테스트 코드는 맞는데, 시간 복잡도라던지 다른 케이스에서 틀리는건지 오류가 발생할 때가 있다.. 더 분발해야겠지