extractive summary : 기존 내용에서 몇 개 문장을 뽑아 만든 요약문. 예컨대, 기존 내용이 10개의 문장으로 이뤄져있다고 가정할 때 1번째 문장이 요약문에 포함되면 1 아니면 0 abstractive summary : 전체 내용을 그대로 사용하지 않은 새롭게 작성한 요약문 oracle summary : 전체 내용에서 문장 k개로 이루어진 집합을 만듭니다. 이때 ROUGE score를 구해 가장 높은 점수를 가진 집합을 만듭니다. 해당 집합을 ground-truth로 활용합니다. Greedy하게 진행합니다.

Introduction

목표 아티클에 대해 올바른 요약을 제공하는 것은 중요합니다. LLM이 나오고 나서 표현의 풍부함과 문맥의 일관성에 대해 눈에 띄는 성과를 얻을 수 있었습니다. 그러나, LLM은 목표 아티클에 대해 반대되는 내용이나 존재하지 않는 내용을 요약에 포함시키는 경향이 있습니다.

Extractive Summarization via ChatGPT for Faithful Summary Generation

the FactCC scores are extremely low for generate only baselines (less than 10 percent), highlighting the hallucination problems of ChatGPT-based summarization, where ChatGPT tends to make up new content in the summary

FactCC는 abstractive summary에 대해 Factual Consistency(요약문의 모든 사실적 정보가 원문에 나타나있는 사실과 일관되는가)를 평가할 수 있는 지표입니다. 해당 지표에서 10%보다 낮은 수치를 기록하였고, 이는 ChatGPT 기반의 요약 시 새로운 정보를 만들어내는 환각 문제를 강조합니다. 

LLM의 성능은 입력 토큰의 길이가 증가할수록 감소하며, 긴 문서 요약에서 LLM의 환각 현상이 특히 더 심해진다는 결론 또한 존재했습니다. 또한, LLM은 문맥이 제시되는 순서에 민감하며, 심지어 짧은 문장에서도 첫 번째 혹은 마지막에 제시되는 문장을 더 깊이 있게 사용한다는 사실이 밝혀졌습니다 이것은 LLM이 생성한 요약문이 시작/끝 쪽에 위치하는 문장에 의존함으로써 전체 아티클을 요약해야하는 요약문의 질을 낮출 수 있다는 것을 의미합니다.

최근 연구에서는 CoT 프롬프트를 사용하여 사실 의존도를 높이거나(Sum-CoT, LLM이 요약문을 step-by-step으로 생성하도록 함), LLM을 평론가 모델과 편집자 모델로 나누어 평론가 모델이 요약문을 작성하면 편집자 모델이 사실 관계를 정정하는 방법 등이 제시되었습니다. 그러나 이러한 방법들은 위치 편향(시작/끝 선호) 문제와 문단의 길이에 따라 성능이 저조해지는 문제를 해결하지 못했습니다.

해당 논문에서는 슬라이딩 생성과 자기 일관성(self-consistency, https://www.promptingguide.ai/kr/techniques/consistency)을 사용하여 문단의 길이와 상관없이 LLM의 신뢰성을 유지할 수 있는 요약 방법론, SliSum을 제시합니다.

Approach

1. Sliding Generation

![[Pasted image 20250512150145.png]] 첫 번째로 문단 A를 문장의 집합(C1, C2, ..., Cn)으로 나눕니다. 또한 미리 정의된 윈도우 사이즈로 문단 A를 문장의 집합(C1, C2, ..., Ct)로 나눕니다. 윈도우 내에 단어의 갯수는 윈도우 사이즈와 비슷하게 맞춥니다. LLM이 첫 번째 윈도우 안의 내용에 대한 로컬 요약문을 만들어냅니다. 이때 LLM이 오직 윈도우 내의 내용에만 집중하도록 해야합니다. 그 이후 스텝 사이즈(윈도우 크기보다 작거나 같아야 함)만큼 이동하여, 해당 윈도우에 있는 내용에 대한 로컬 요약문을 만들어냅니다. 전체 문단을 모두 순회할때까지 해당 과정을 반복합니다. 이때 중요한 것은 윈도우 간 중첩(overlap)이 존재해야 한다는 것입니다. 이는 LLM이 중요한 부분에 대해 더 많이 강조해서 볼 수 있다는 것을 의미합니다.

2. Filtering

로컬 요약문을 모두 생성한 후, DBSCAN 알고리즘(+ ROUGE-1 F1 Score)을 사용해 어휘 유사성을 계산하여 생성된 요약문들을 클러스터링합니다. 해당 작업을 통해 단어나 구조가 다르지만 같은 의미를 담고 있는 문장들끼리 묶습니다.

# R은 두 문장 간의 ROUGH-1 F1 score
R(C1, C2) = (2 * 겹치는 단어의 수) / (C1의 길이 + C2의 길이)

문장이 매우 적게 포진되어 있는 작은 클러스터들과 잡음(outliers)들을 필터링하여 오직 정보가 담겨있으며 반복되는 문장들만이 포함되도록 합니다.(이때 잡음의 판단 기준은 낮은 어휘적 유사성입니다.)

3. Aggregation

필터링된 클러스터들을 합치기전, 모순을 처리해야 합니다. 클러스터 내에서 의미적으로 유사한 문장을 비교하여 모순되는 정보(contradictions)를 찾아내고, 다음의 원칙에 따라 문장을 필터링합니다.

1. 지역 요약에서 빈도가 낮은 문장
2. 의미적으로 일관성이 부족한 문장
3. 원본 문서와의 유사성이 낮은 문장
4. 다수결에서 지지도가 낮은 문장 이제 각 클러스터에서 가장 대표적이고 일관성 있는 문장을 연결(concat)하여 최종 요약을 생성합니다.

내용이 다소 복잡하니, 예시를 들어보겠습니다. 다음과 같은 문단이 있다고 가정하겠습니다.

서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다. 한강이 서울을 가로질러 흐르며, 과거부터 현재까지 중요한 역할을 해왔습니다. 서울은 세계적으로도 유명한 도시로, 관광지와 현대적인 건축물들이 많이 있습니다. 서울의 기후는 온대성 기후로, 여름에는 덥고 겨울에는 추운 편입니다. 서울은 2022년 기준 약 천만 명 이상의 인구를 보유하고 있으며, 한국의 경제 활동 중심지로 평가받고 있습니다.

1. 슬라이딩 윈도우를 생성합니다.

   C1: 서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다.  
   C2: 한강이 서울을 가로질러 흐르며, 과거부터 현재까지 중요한 역할을 해왔습니다.  
   C3: 서울은 세계적으로도 유명한 도시로, 관광지와 현대적인 건축물들이 많이 있습니다.  
   C4: 서울의 기후는 온대성 기후로, 여름에는 덥고 겨울에는 추운 편입니다.  
   C5: 서울은 2022년 기준 약 천만 명 이상의 인구를 보유하고 있으며, 한국의 경제 활동 중심지로 평가받고 있습니다.
   

윈도우 크기(Window Size): 2문장 스텝 크기(Step Size): 1문장

``` 윈도우가 이동하며 LLM은 각 윈도우에 대해 로컬 요약을 생성합니다:
윈도우 1: [C1, C2] → "서울은 대한민국의 수도로, 한강이 중요한 역할을 하는 도시이다."
윈도우 2: [C2, C3] → "한강이 흐르는 서울은 관광과 현대적 건축물로 유명하다."
윈도우 3: [C3, C4] → "서울은 유명한 관광지로, 온대성 기후를 가진다."
윈도우 4: [C4, C5] → "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있다."

2. Filtering (필터링) DBSCAN 알고리즘과 ROUGE-1 F1 Score를 사용해 문장들의 어휘적 유사성을 계산하고 클러스터링합니다.
예를 들어, 다음과 같은 클러스터들이 생성됩니다:

• 클러스터 1:
  • "서울은 대한민국의 수도로, 한강이 중요한 역할을 하는 도시입니다."
  • "한강이 흐르는 서울은 관광과 현대적 건축물로 유명합니다."
• 클러스터 2:
  • "서울은 유명한 관광지로, 온대성 기후를 가집니다."
  • "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있습니다."

작은 클러스터나 잡음(outliers)은 제거됩니다.
예: "서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다."는 다른 문장들과 어휘적 유사성이 낮아 제거될 수 있습니다.

3. Aggregation (모순 처리 및 최종 요약 생성)  클러스터 내에서 모순을 탐지하고 다음 기준으로 필터링합니다:

1. 지역 요약에서 빈도가 낮은 문장
2. 의미적으로 일관성이 부족한 문장
3. 원본 문서와의 유사성이 낮은 문장
4. 다수결에서 지지도가 낮은 문장 최종적으로 각 클러스터에서 가장 대표적인 문장만 선택됩니다:

• 클러스터 1: "한강이 흐르는 서울은 관광과 현대적 건축물로 유명하다."
• 클러스터 2: "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있다."

최종적으로 선택된 문장을 연결하여 요약문을 만들어냅니다: 한강이 흐르는 서울은 관광과 현대적 건축물로 유명하며, 온대성 기후를 가지며 천만 명 이상의 인구를 보유하고 있다

Experiments and Results

LLaMA-2, Claude-2, GPT-3.5를 사용하여 네 가지 서로 다른 요약 데이터셋(CNN/DM, XSum - 짧은 텍스트용, PubMed, arXiv - 긴 텍스트용)에서 테스트한 결과, 요약의 사실적 일관성(factual consistency)을 크게 개선하면서도 유창성(fluency)이나 정보성(informativeness)이 떨어지지 않음을 보여주고 있습니다. ![[Pasted image 20250513094344.png]] 하이퍼파라미터의 영향

• 저자들은 SliSum의 성능에 영향을 미치는 다양한 하이퍼파라미터(윈도우 크기, 스텝 크기, 클러스터링의 최소 점 개수(MinPts))에 대한 Ablation study를 수행했습니다.
• 주요 결과:
  1. 윈도우 크기와 스텝 크기의 최적 비율은 사실적 일관성 점수 향상에 크게 기여함.
  2. MinPts의 적절한 선택은 잡음을 제거하면서 중요한 내용을 유지하는 균형을 맞추는 데 도움을 줌.

Conclusion

• SliSum은 LLM이 생성한 텍스트에서 본질적으로 나타나는 환각(hallucination) 문제를 줄이며 요약 출력의 신뢰성을 향상시킵니다.
• 중첩된 슬라이딩 윈도우와 자기 일관성(self-consistency) 전략의 결합은 다양한 텍스트 길이와 문맥에서 보다 신뢰할 수 있는 요약을 생성할 수 있습니다.
• 추가적인 파인튜닝(fine-tuning)이나 외부 리소스가 필요하지 않습니다.

extractive summary : 기존 내용에서 몇 개 문장을 뽑아 만든 요약문. 예컨대, 기존 내용이 10개의 문장으로 이뤄져있다고 가정할 때 1번째 문장이 요약문에 포함되면 1 아니면 0 abstractive summary : 전체 내용을 그대로 사용하지 않은 새롭게 작성한 요약문 oracle summary : 전체 내용에서 문장 k개로 이루어진 집합을 만듭니다. 이때 ROUGE score를 구해 가장 높은 점수를 가진 집합을 만듭니다. 해당 집합을 ground-truth로 활용합니다. Greedy하게 진행합니다.

Introduction

목표 아티클에 대해 올바른 요약을 제공하는 것은 중요합니다. LLM이 나오고 나서 표현의 풍부함과 문맥의 일관성에 대해 눈에 띄는 성과를 얻을 수 있었습니다. 그러나, LLM은 목표 아티클에 대해 반대되는 내용이나 존재하지 않는 내용을 요약에 포함시키는 경향이 있습니다.

Extractive Summarization via ChatGPT for Faithful Summary Generation the FactCC scores are extremely low for generate only baselines (less than 10 percent), highlighting the hallucination problems of ChatGPT-based summarization, where ChatGPT tends to make up new content in the summary

LLM의 성능은 입력 토큰의 길이가 증가할수록 감소하며, 긴 문서 요약에서 LLM의 환각 현상이 특히 더 심해진다는 결론 또한 존재했습니다. 또한, LLM은 문맥이 제시되는 순서에 민감하며, 첫 번째 혹은 마지막에 제시되는 문장을 더 깊이 있게 사용한다는 사실이 밝혀졌습니다(심지어 짧은 문장에서도요!) 이것은 LLM이 만든 요약문이 시작/끝 쪽에 위치하는 문장에 더 많이 의존함으로써 전체 아티클을 요약해야하는 요약문의 퀄리티를 낮출 수 있다는 것을 의미합니다.

최근 연구에서는 CoT 프롬프트를 사용하여 사실 의존도를 높이거나(Sum-CoT, LLM이 요약문을 step-by-step으로 생성하도록 함), LLM을 평론가 모델과 편집자 모델로 나누어 평론가 모델이 요약문을 작성하면 편집자 모델이 사실 관계를 정정하는 방법 등이 제시되었습니다. 그러나 이러한 방법들은 위치 편향(시작/끝 선호) 문제와 문단의 길이에 따라 성능이 저조해지는 문제를 해결하지 못했습니다.

해당 논문에서는 슬라이딩 생성과 자기 일관성(self-consistency, https://www.promptingguide.ai/kr/techniques/consistency) 문단의 길이와 상관없이 LLM의 신뢰성을 유지할 수 있는 요약 방법론, SliSum을 제시합니다.

Approach

1. Sliding Generation

![[Pasted image 20250512150145.png]] 첫 번째로 문단 A를 문장의 집합(C1, C2, ..., Cn)으로 나눕니다. 또한 미리 정의된 윈도우 사이즈로 문단 A를 문장의 집합(C1, C2, ..., Ct)로 나눕니다. 윈도우 내에 단어의 갯수는 윈도우 사이즈와 비슷하게 맞춥니다. LLM이 첫 번째 윈도우 안의 내용에 대한 로컬 요약문을 만들어냅니다. 이때 LLM이 오직 윈도우 내의 내용에만 집중하도록 해야합니다. 그 이후 스텝 사이즈(윈도우 크기보다 작거나 같아야 함)만큼 이동하여, 해당 윈도우에 있는 내용에 대한 로컬 요약문을 만들어냅니다. 전체 문단을 모두 순회할때까지 해당 과정을 반복합니다. 이때 중요한 것은 윈도우 간 중첩(overlap)이 존재한다는 것입니다.

2. Filtering

로컬 요약문을 모두 생성한 후, DBSCAN 알고리즘(+ ROUGE-1 F1 Score)을 사용해 어휘 유사성을 계산하여 생성된 요약문들을 클러스터링합니다. 해당 작업을 통해 단어나 구조가 다르지만 같은 의미를 담고 있는 문장들끼리 묶습니다.

# R은 두 문장 간의 ROUGH-1 F1 score
R(C1, C2) = (2 * 겹치는 단어의 수) / (C1의 길이 + C2의 길이)

문장이 매우 적게 포진되어 있는 작은 클러스터들과 잡음(outliers)들을 필터링하여 오직 정보가 담겨있으며 반복되는 문장들만이 포함되도록 합니다.(이때 잡음의 판단 기준은 낮은 어휘적 유사성입니다.)

3. Aggregation

필터링된 클러스터들을 합치기전, 모순을 처리해야 합니다. 클러스터 내에서 의미적으로 유사한 문장을 비교하여 모순되는 정보(contradictions)를 찾아내고, 다음의 원칙에 따라 문장을 필터링합니다.

1. 지역 요약에서 빈도가 낮은 문장
2. 의미적으로 일관성이 부족한 문장
3. 원본 문서와의 유사성이 낮은 문장
4. 다수결에서 지지도가 낮은 문장 이제 각 클러스터에서 가장 대표적이고 일관성 있는 문장을 연결(concat)하여 최종 요약을 생성합니다.

내용이 다소 복잡하니, 예시를 들어보겠습니다. 다음과 같은 문단이 있다고 가정하겠습니다.

서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다. 한강이 서울을 가로질러 흐르며, 과거부터 현재까지 중요한 역할을 해왔습니다. 서울은 세계적으로도 유명한 도시로, 관광지와 현대적인 건축물들이 많이 있습니다. 서울의 기후는 온대성 기후로, 여름에는 덥고 겨울에는 추운 편입니다. 서울은 2022년 기준 약 천만 명 이상의 인구를 보유하고 있으며, 한국의 경제 활동 중심지로 평가받고 있습니다.

1. 슬라이딩 윈도우 생성 ```

C1: 서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다.
C2: 한강이 서울을 가로질러 흐르며, 과거부터 현재까지 중요한 역할을 해왔습니다.
C3: 서울은 세계적으로도 유명한 도시로, 관광지와 현대적인 건축물들이 많이 있습니다.
C4: 서울의 기후는 온대성 기후로, 여름에는 덥고 겨울에는 추운 편입니다.
C5: 서울은 2022년 기준 약 천만 명 이상의 인구를 보유하고 있으며, 한국의 경제 활동 중심지로 평가받고 있습니다.

• 윈도우 크기(Window Size): 2문장
• 스텝 크기(Step Size): 1문장 ``` 윈도우가 이동하며 LLM은 각 윈도우에 대해 로컬 요약을 생성합니다:
• 윈도우 1:* [C1, C2] → "서울은 대한민국의 수도로, 한강이 중요한 역할을 하는 도시이다."
• 윈도우 2:* [C2, C3] → "한강이 흐르는 서울은 관광과 현대적 건축물로 유명하다."
• 윈도우 3:* [C3, C4] → "서울은 유명한 관광지로, 온대성 기후를 가진다."
• 윈도우 4:* [C4, C5] → "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있다."

2. Filtering (필터링) DBSCAN 알고리즘과 ROUGE-1 F1 Score를 사용해 문장들의 어휘적 유사성을 계산하고 클러스터링합니다.
예를 들어, 다음과 같은 클러스터들이 생성됩니다:

• 클러스터 1:
  • "서울은 대한민국의 수도로, 한강이 중요한 역할을 하는 도시이다."
  • "한강이 흐르는 서울은 관광과 현대적 건축물로 유명하다."
• 클러스터 2:
  • "서울은 유명한 관광지로, 온대성 기후를 가진다."
  • "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있다."

작은 클러스터나 잡음(outliers)은 제거됩니다.
예: "서울은 대한민국의 수도로, 정치, 경제, 문화의 중심지입니다."는 다른 문장들과 어휘적 유사성이 낮아 제거될 수 있음.

3. Aggregation (모순 처리 및 최종 요약 생성)  클러스터 내에서 모순을 탐지하고 다음 기준으로 필터링합니다:

1. 지역 요약에서 빈도가 낮은 문장
2. 의미적으로 일관성이 부족한 문장
3. 원본 문서와의 유사성이 낮은 문장
4. 다수결에서 지지도가 낮은 문장 최종적으로 각 클러스터에서 가장 대표적인 문장만 선택됩니다:

• 클러스터 1: "한강이 흐르는 서울은 관광과 현대적 건축물로 유명하다."
• 클러스터 2: "서울은 온대성 기후를 가지며, 천만 명 이상의 인구를 보유하고 있다."

최종적으로 선택된 문장을 연결하여 요약문을 만들어냅니다. 한강이 흐르는 서울은 관광과 현대적 건축물로 유명하며, 온대성 기후를 가지며 천만 명 이상의 인구를 보유하고 있다

실험 설정 및 결과

SliSum의 성능은 다양한 LLM(대규모 언어 모델)에서 평가되었으며, LLaMA-2, Claude-2, GPT-3.5를 사용하여 네 가지 서로 다른 요약 데이터셋(CNN/DM, XSum - 짧은 텍스트용, PubMed, arXiv - 긴 텍스트용)에서 테스트되었습니다. 결과는 요약의 사실적 일관성(factual consistency)을 크게 개선하면서도 유창성(fluency)이나 정보성(informativeness)을 희생하지 않았음을 보여줍니다.

핵심 지표

• 사실적 일관성 평가: FactCC와 SummaC를 사용하여 평가.
• 정보성 평가: ROUGE 지표(ROUGE-1, ROUGE-2, ROUGE-L)를 사용하여 평가.
  결과는 SliSum이 다양한 모델과 데이터셋에서 사실적 일관성과 요약 품질 지표에서 일관되게 기존 기준선을 능가했음을 나타냅니다.
• 하이퍼파라미터의 영향*
• 저자들은 SliSum의 성능에 영향을 미치는 다양한 하이퍼파라미터(윈도우 크기, 스텝 크기, 클러스터링의 최소 점 개수(MinPts))에 대한 소거 연구(ablation study)를 수행했습니다.
• 주요 결과:
  1. 윈도우 크기와 스텝 크기의 최적 비율은 사실적 일관성 점수 향상에 크게 기여함.
  2. MinPts의 적절한 선택은 잡음을 제거하면서 중요한 내용을 유지하는 균형을 맞추는 데 도움을 줌.
     결론
• SliSum은 LLM이 생성한 텍스트에서 본질적으로 나타나는 환각(hallucination) 문제를 줄이는 혁신적인 프레임워크를 제시하며, 요약 출력의 신뢰성을 향상시킵니다.
• 중첩된 슬라이딩 윈도우와 자기 일관성(self-consistency) 전략의 결합은 다양한 텍스트 길이와 문맥에서 보다 신뢰할 수 있는 요약을 생성할 수 있음을 입증했습니다.
• 추가적인 파인튜닝(fine-tuning)이나 외부 리소스가 필요하지 않아 접근성이 높고 효율적인 방법임을 강조했습니다.

<그림1: RAG 구조. 출처: Prompt Engineering Guide https://www.promptingguide.ai/kr/research/rag >

이렇듯 LLM에 외부 지식(External knowledge)를 단서로 제시함으로써 응답의 정확도의 질을 높이는 방법은 수많은 연구, 기업에서 사용되고 있습니다.

이때 궁금한 점이 생깁니다. LLM이 학습할 때 사용된 내부 지식과, 추가로 제공된 외부 지식이 상충한다면 LLM은 어떠한 지식을 사용할까요? 결론부터 말하자면, 외부지식이 일관성 있고 설득력이 있다면 내부지식과 상충되는 관점이어도 외부지식을 받아들입니다. 외부 지식과 내부 지식이 일관성을 가진다면, 해당 지식을 지지하는 근거가 충돌하더라도 해당 지식에 대해 강한 확신, 확증편향을 가지게 됩니다.

오늘 리뷰할 논문, [Adaptive Chameleon or Stubborn Sloth: Revealing the Behavior of Large Language Models in Knowledge Conflicts]는 LLM의 지식 충돌(Knowledge Conflict)에 대해 통합적으로 연구한 첫 번째 논문입니다.

논문 링크

Introduction

거대한 코퍼스를 통해 사전학습을 마친 LLM은 내부적으로 상식을 포함하여 다양한 종류의 지식을 가지게 됩니다. 이를 지금부터 파라메트릭 메모리(parametric memory) 라고 표현하겠습니다. 그러나 이러한 지식들은 부정확하거나 시간이 지나 업데이트가 필요할 수 있습니다. 그러한 지식들은 환각 현상의 주 원인이 되기도 합니다. 이를 해결하기 위해 RAG 등의 외부 지식을 사용하는 기법이 등장하였지만, 외부 지식과 파라메트릭 메모리가 일치하지 않는 경우가 발생하였습니다. 이때 충돌의 원인이 되는 외부 지식을 카운터 메모리(counter-memory) 라고 표현하겠습니다.
해당 논문에서는 지식 충돌이 일어났을 때 벌어지는 일을 명확히 밝히고자 파라메트릭 메모리에 대응하는 카운터 메모리를 구축하는 프레임워크를 만들었습니다.

Framework

closed-book QA: 질문 혹은 지문이 주어지는 것이 아닌, 모델이 자체적으로 가지고 있는 능력에 기반하여 정답을 찾는 것을 의미합니다. 기반 데이터셋은 엔티티 기반의 데이터셋인 POPQA(https://huggingface.co/datasets/akariasai/PopQA)와 Multi-step reasoning 데이터셋인 STRATEGYQA(https://huggingface.co/datasets/voidful/StrategyQA)를 사용하였습니다.

새로운 데이터셋을 만드는 과정을 구체적으로 살펴보겠습니다.

1. 질문에 대해 모델은 가지고 있는 지식에 기반한 대답(Memory Answer)을 생성합니다. 이때 이 대답을 생성할 때 증거로 사용된 내용, 즉 파라메트릭 메모리를 만듭니다.
2. Memory Answer의 내용을 지식 충돌이 일어날 수 있는 내용(Counter Answer)으로 만듭니다. 예를 들어 해당 논문에서는 Google DeepMind의 리더를 Demis Hassabis에서 Jeff Dean으로 변경했습니다. 이후 Counter Answer을 설명하는 증거, 카운터 메모리를 만듭니다.
3. 만들어진 파라메트릭 메모리와 카운터 메모리가 각각 대응하는 응답을 잘 설명하는지 결정하기 위해 당시 NLI Task에서 SOTA를 달성한 DeBERTa-V2를 사용하였습니다. 추후 실험의 신뢰성을 위해 오직 잘 설명하는 메모리만을 사용하였습니다. (참고로 해당 모델이 잘 수행하는지 확실히 하기 위해 랜덤으로 200개의 예시를 뽑아 테스트해 본 결과, 99%의 정확도를 달성했다고 합니다.)
4. 추출한 파라메트릭 메모리가 정말로 LLM의 내부적 믿음에서 나온건지 확인하기 위해, 동일한 질문을 LLM에게 한 번 다시 던졌다고 합니다. 예를 들어 Google DeepMind의 리더를 물어봤을 때, Demis Hassabis라고 동일하게 답했는지 확인해보았습니다. 만약 일치하지 않았다면 해당 데이터를 제외하였습니다.

최종적으로 만들어진 데이터셋의 형태는 다음과 같습니다.

Experiments

카운터 메모리만 증거로 제시되었을 때

카운터 메모리를 만드는 2번 과정에 대해 논문에서는 두 가지 방법을 제시했습니다. 첫 번째 방법은 '엔티티 대체 기반'방법입니다. (우리가 Figure 1에서 본 카운터 메모리 생성방법은 두 번째 방법을 따릅니다)

엔티티 대체 방법(entity substitution-based counter memory method)

해당 방법에서는 문장 구조에서 특정 엔티티(문장 구성요소라고 생각해주세요)를 정한다음, 동일한 요소를 가지는 랜덤한 엔티티로 대체시키는 방법입니다. 예를 들어 아래와 같은 파라메트릭 메모리가 있다고 가정해보겠습니다.

증거: 미국의 수도인 워싱턴 D.C.는 워싱턴 기념탑을 가지고 있습니다.
질문: 미국의 수도는 어디인가요? ChatGPT 답변: 워싱턴 D.C. 입니다.

카운터 메모리를 만들기 위해 증거 문장에서 '워싱턴 D.C.'라는 엔티티를 다른 수도로 변경하는 것입니다.

증거: 미국의 수도인 런던은 워싱턴 기념탑을 가지고 있습니다.
질문: 미국의 수도는 어디인가요? ChatGPT 답변: 워싱턴 D.C. 입니다.

그런데 문제가 생겼습니다. 증거를 명확하게 변경하여 제시했음에도 불구하고, LLM이 답변을 생성할 때 파라메트릭 메모리에 의존하여 답변을 생성합니다. 이러한 문제는 더 큰 파라미터를 가지고 있는 모델에서 두드러지게 나타나는 것을 확인할 수 있었습니다.

응답-기반 방법(generation-based method)

Figure 1에서 설명한 방식입니다. 단계는 다음과 같습니다.

1. 질문에 대해 모델은 가지고 있는 지식에 기반한 대답(Memory Answer)을 생성합니다. 이때 이 대답을 생성할 때 증거로 사용된 내용, 즉 파라메트릭 메모리를 만듭니다.
2. Memory Answer의 내용을 지식 충돌이 일어날 수 있는 내용(Counter Answer)으로 만듭니다. 예를 들어 해당 논문에서는 Google DeepMind의 리더를 Demis Hassabis에서 Jeff Dean으로 변경했습니다. 이후 Counter Answer을 설명하는 증거, 카운터 메모리를 만듭니다.

LLM은 이렇게 만들어진 일관성 있는 카운터 메모리를 매우 잘 받아들인다고 합니다.

실험 결과

아래 실험은 여러 모델들의 응답의 결과가 Memory Answer인지 Counter Answer인지 측정해본 결과입니다. Subs는 entity substitution-based 방식(일관성이 부족한 증거)으로 만들어진 카운터 메모리를 사용한 것이고, Gen은 generation-based 방식(일관성이 충분한 증거)으로 만들어진 카운터 메모리를 사용한 방식입니다.

위 실험 결과를 통해 다음의 결론을 얻을 수 있습니다.

1. LLM은 일관성 있는 외부 증거를 매우 잘 받아들인다.

2. 카운터 메모리로 인해 만들어진 답변은 LLM을 잘못된 답변으로 이끈다. 즉, LLM은 역정보(disinformation)에 취약하며 쉽게 받아들인다.

다양한 증거가 동시에 제시되었을때

여러 개의 증거가 동시에 제공되었을 때는 어떨까요? 검색 엔진과 같은 툴로 증강된 LLM을 생각해보면 다양한 출처에서 정보를 가져오므로 이런 종류의 지식 충돌이 자주 발생할 가능성이 있습니다. 분석 결과는 다음과 같습니다.

1. LLM은 인기 있는 정보에 대해서 내부 지식을 사용한다.

2. 증거가 제공되는 순서가 LLM의 응답에 영향을 미친다.

3. LLM은 더 많은 증거를 가진 메모리를 선택한다.

4. LLM은 무관한 증거에 의해 방해받을 수 있다

Conclusion

해당 논문에서는 올바르지 않은 외부 증거를 사용할 때 모델의 응답 경향을 측정했습니다. 그 결과 다음의 결론을 얻을 수 있습니다.

1. 확인 편향: LLM은 내부 메모리와 일치하거나 인기 있는 정보를 선호하는 경향이 있습니다.
2. 순서 민감성: 증거의 순서가 LLM의 응답에 영향을 미칠 수 있습니다.
3. 다수 증거 효과: LLM은 더 많은 증거를 가진 쪽을 선택하는 경향이 있습니다.
4. 무관한 증거 영향: LLM은 무관한 증거에 의해 혼란을 겪을 수 있으며, 이를 필터링하는 능력이 제한적입니다.

또한 올바르지 않은 외부 증거가 일관성 있을 때 해당 증거를 매우 잘 받아들인다는 점과, LLM이 역정보에 취약하다는 점 또한 파악할 수 있었습니다.

이 글이 여러분에게 도움이 되었으면 좋겠습니다 :)

Welcome to Expo! start by creating a file in the app directory

라는 메세지가 떠버렸다. 아무리 재실행하고 코드를 수정해도 index.tsx를 인식을 못하는 것 같아서 어지러웠는데

npx expo start --clear

캐시 삭제해주니까 다시 정상으로 돌아왔다.

2024-05-23 오류 재발생

갑자기 똑같은 오류가 한 번 더 발생했다. 찾아보니 Expo SDK 51(가장 최신 SDK)과 expo-router에서 발생하는 오류인듯 하다. https://stackoverflow.com/questions/78494804/expo-stuck-on-welcome-to-expo-screen

https://github.com/expo/expo/issues/28680

정확히는 typed-router 옵션 때문에 발생하는 듯 하다.

해결책

app.json에서 typed-router를 제거하는 것. 이후 cache clear를 해준다.

npx expo start --clear

2024-10-12 오류 재발생

xcode의 ios simulator를 사용 중이었는데, 어느날 켜보니까 오류가 발생했다.

npx expo start --clear

위와 같은 cache clean으로도 해결되지 않아, simulator 내부의 expo go가 아닌 실제 앱을 지우고 다시 명령어를 실행시키니 해결되었다.

여러분은 비동기 웹소켓 클라이언트를 개발해야합니다. 여러분의 클라이언트 프로그램이 암호화폐의 정보를 상시적으로 보내는 Binance 서버(https://www.binance.com/en/markets)의 스트리밍 채널을 구독하게 하세요.

암호화폐 거래소인 바이넌스의 웹소켓 서버에 연결하여 비트코인의 매수가(Bid)와 매도가(Ask)를 받아온 후, txt 파일에 기록하는 과제이다.

Websocket Library

웹이나 자바, 파이썬과 달리 외부 라이브러리를 추가하는 것이 생각보다 매우매우 아주 어려웠다.

설치과정은 Windows를 기반으로 작성했습니다. 맥이나 리눅스는 apt를 사용하는 것을 추천합니다.

Visual Studio와 vcpkg(패키지 매니저)를 사용하는 것이 정신건강에 이롭다.

vcpkg 설치과정

git clone으로 vcpkg 파일을 가져온 다음

git clone https://github.com/Microsoft/vcpkg.git

bat 파일을 실행시켜 vcpkg를 빌드하자.

cd vcpkg
.\vcpkg\bootstrap-vcpkg.bat

Visual Studio를 사용한다는 가정 하에, 아래의 명령어를 사용하면 추가 설정없이 cpkg로 설치된 모든 라이브러리를 #include로 바로 사용 할 수 있다.

.\vcpkg integrate install

Boost.Beast 웹소켓 라이브러리 설치

이제 라이브러리를 설치해보자. 자신이 64bit 컴퓨터라면(대부분 그럴 것이고) :x64-windows 옵션을 사용하여 명시해줘야 한다.

.\vcpkg install boost:x64-windows

설치하는 데에 꽤 시간이 걸린다.

Visual Studio 연동

솔루션 탐색기에서 프로젝트 오른쪽 -> 속성 -> 구성 속성 -> vcpkg로 들어가 다음과 같이 설정해야 한다.이제 다음과 같은 코드를 작성할 때 자동완성(Ctrl+Space)이 뜨길 기도하자.

#include <boost/beast/core.hpp>

만약 자동완성이 되지 않고 such file does not exist라면, IDE를 재실행해보자. 그래도 되지 않는다면 화이팅!

Binance WebSocket

만약 오류가 뜨지 않고 여기까지 왔다면 70%는 성공이다. 코드를 작성하기 전 Binance Websocket Market Stream Docs에 따르면 기본 엔드포인트는 아래와 같다.

wss://stream.binance.com:443(or 9443)

우리는 스트림에 아래와 같은 Json 형태의 쿼리를 보내 결과를 받아올 수 있다.

{
    "method": "SUBSCRIBE",
    "params":
    [
        "btcusdt@depth<levels>" //가장 높은 bid와 ask를 levels만큼 가져온다.
    ],
    "id": 1 //an identifier to uniquely identify the messages going back and forth.
}

또한 기본 프로토콜이 wss이므로 ssl 처리도 해줘야한다. 아니면 Binance 서버에서 아래와 같은 오류가 발생하니 참고!

Error: The WebSocket handshake was declined by the remote peer

소켓은 다음과 같은 흐름을 가진다.우리는 서버가 아닌 클라이언트이므로, 소켓을 만들고 -> 연결하고 -> 데이터를 보내고 받는 과정을 거치면 된다.

Headers and namespaces

구현하기 전 필요한 헤더파일과 손목 건강을 위한 namespace를 설정해줘야 한다.

#include <boost/beast/core.hpp>
#include <boost/beast/ssl.hpp>
#include <boost/beast/websocket.hpp>
#include <boost/beast/websocket/ssl.hpp>
#include <boost/asio/connect.hpp>
#include <boost/asio/ip/tcp.hpp>
#include <boost/asio/ssl/stream.hpp>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>

namespace beast = boost::beast;
namespace http = beast::http;
namespace websocket = beast::websocket;
namespace net = boost::asio;
namespace ssl = boost::asio::ssl;
using tcp = boost::asio::ip::tcp;

WebSocketClient

class WebSocketClient {
public:
    WebSocketClient(net::io_context& ioc, ssl::context& ctx)
        : resolver_(ioc), ws_(ioc, ctx) {}
    void connect(const std::string& host, const std::string& port, const std::string& target) {
        auto const results = resolver_.resolve(host, port);
        net::connect(ws_.next_layer().next_layer(), results.begin(), results.end());
        ws_.next_layer().handshake(ssl::stream_base::client);

        ws_.set_option(websocket::stream_base::decorator(
            [](websocket::request_type& req)
            {
                req.set(http::field::user_agent,
                std::string(BOOST_BEAST_VERSION_STRING) +
                " binance-websocket-client");
            }));
        ws_.handshake(host, target);
    }

    void send(const std::string& message, const std::string& param) {
        auto pos = message.find("\"params\": [");
        std::string subscribeMessage = message;
        subscribeMessage.insert(pos + 11, "\"" + param + "\"");
        std::cout << subscribeMessage << std::endl;
        ws_.write(net::buffer(subscribeMessage));
    }

    void receive() {
        beast::flat_buffer buffer;
        ws_.read(buffer);
        std::cout << beast::make_printable(buffer.data()) << std::endl;
    }

    void close() {
        ws_.close(websocket::close_code::normal);
    }

private:
    net::ip::tcp::resolver resolver_;
    websocket::stream<beast::ssl_stream<tcp::socket>> ws_;
};

BinanceWebSocketClient

class BinanceWebSocketClient {
public:
    BinanceWebSocketClient(net::io_context& ioc, ssl::context& ctx, const std::string& host, const std::string& port, const std::string& param)
        : wsClient(ioc, ctx), host_(host), port_(port), param_(param), target_("/ws/" + param) {}

    void run() {
        try {
            wsClient.connect(host_, port_, target_);

            const std::string subscribeMessage = R"({"method": "SUBSCRIBE", "params": [], "id": 1})";
            wsClient.send(subscribeMessage, param_);
            while (true) {
                wsClient.receive();
            }

            wsClient.close();
        }
        catch (std::exception const& e) {
            std::cerr << "Error: " << e.what() << std::endl;
        }
    }

private:
    WebSocketClient wsClient;
    std::string host_;
    std::string port_;
    std::string param_;
    std::string target_;
};

STEP A

Write a streaming client program receiving ‘btcusdt@depth5’ and a trade stream of ‘btcusdt’ information in the same stream connection. The data will be updated every 100-500 milliseconds. Your program will save the data into a text file (do not use shell redirect), called stream-databinance.txt. You will add a new line of data as they arrive. The trade stream shows “p” and “q” values only.

btcusdt@depth5와 btcusdt@trade의 reponse를 같은 스트림 내에서 받는 클라이언트 프로그램을 작성해야 한다. 그리고 그 데이터를 텍스트 파일에 저장하면 된다.

int main()
{
    const std::string host = "stream.binance.com";
    const std::string port = "443";
    const std::string param = "btcusdt@trade";

    net::io_context ioc;
    ssl::context ctx{ ssl::context::tlsv12_client };

    BinanceWebSocketClient client(ioc, ctx, host, port, param);
    client.run();
}

패킷을 전송하는 send side는 message를 segment로 나누어 네트워크 계층으로 보내며 패킷을 받는 rcv side는 segment를 message로 조립하여 응용계층으로 보낸다.

다중화란 여러 곳에서 전송되는 데이터를 하나로 모으는 것이다. 전송(transport) 계층에서 어플리케이션 계층에 있는 소켓에서 전송되는 데이터를 모은 다중화 데이터를 세그먼트(segment)라고 한다. 세그먼트는 헤더와 데이터로 나누어진다.

역다중화

호스트가 ip 데이터그램(IP계층의 가변길이 패킷)을 받는다. 호스트는 ip 주소와 포트 넘버를 사용해 세그먼트를 적절한 소켓에 전달한다. TCP와 UDP는 역다중화하는 방법이 다르다.

Connectionless demux(demultiplexing)

들어온 패킷이 UDP 프로토콜인 경우이다. UDP는 신뢰성 낮은 프로토콜인만큼 TCP에 비해 단순하다. 서버는 하나의 소켓만으로 통신한다.

헤더에 있는 dst IP, dst port로 데이터를 전송할 소켓을 구분한다. 즉, 어떤 source IP주소, source port를 갖고 있던 간에 목적지 IP와 포트만 같다면 같은 소켓으로 보낸다.

Connection-oriented demux

TCP 프로토콜인 경우이다. 신뢰성이 필요한 프로토콜이기에, 다음 4-tuple 데이터가 필요하다.

• source IP address
• source port number
• dest IP address
• dest port number 하나의 클라이언트 소켓에 하나의 서버 소켓이 매핑된다. 즉, 클라이언트 수만큼 소켓이 필요하다.

프로토콜

데이터 교환 방식을 정의하는 규칙 체계이다. 각기 다른 컴퓨터는 매우 상이한 소프트웨어와 하드웨어를 사용할 수 있기에, 공통된 통신 규약을 만들어 소통한다. 대표적으로 IP(Internet Protocol)가 있다.

그러나 과거에는 장비 제조사별로 다른 프로토콜을 사용하고 있었고, 이를 해결하기 위해 프로토콜을 국제적으로 표준화한 것이 OSI 7 Layers이다.

OSI 7 Layer

교수님 자료에서 ISO/OSI reference model이라고 표현되었다. 총 7계층으로 나누어져 있다.

physical

전선, 광섬유 등 물리적인 연결방식을 다루는 계층이다.

link(=data link)

바로 이웃한(=직접 연결된, neighboring) 네트워킹 장치들간의 데이터 전송을 담당한다. 대표적으로 ethernet, WI-FI가 있다.

network

데이터그램(=패킷)을 source부터 destination까지 라우팅을 담당한다. 대표적으로 IP가 있다.

transport

응용 프로세스 간의 통신을 돕는다. 대표적으로 TCP/UDP가 있다.

session

호스트들간의 연결을 최초로 연결하고, 통신 중 연결이 끊어지지 않도록 유지시켜준다. 에러 복구도 함. 대표적으로 SSH가 있다.

presentation

데이터 값이 다양한 시스템에 저장될 때 다양한 형태로 저장되는데, 이때 다양한 표현양식(syntax)를 공통의 형식으로 변환하여 번역기 역할을 수행한다. 암호화, 압축 등의 역할도 수행한다.

application

네트워크 서비스들이 기능을 제공하도록 도와준다. 대표적으로 HTTP가 있다.

network vs transport layer

network layer는 호스트들간의 소통을 담당한다면, transport layer는 프로세스들간의 소통을 담당한다.

TCP & UDP

어플리케이션은 각자 다른 특성( 데이터 손실, 딜레이, 데이터 전송률(Throughput), 보안)을 요구하고, 이에 따라 사용하는 전송 서비스(transport service)가 다르다. 데이터 신뢰성을 중요시여긴다면 TCP를 사용해야 한다.

TCP

TCP는 다음과 같은 특성을 가진다.

• 연결지향(connection-oriented) : 클라이언트와 서버 프로세스가 연결되기 전 준비(setup)이 필요하다.
• 믿을 만한(reliable) 전송률
• 흐름 제어 :
• 혼잡 제어 : timing, security, minimum throughput guarantees는 제공하지 않는다.

UDP

최선을 다하는(best effort) 프로토콜이다. 커넥션 준비(establishment)가 필요없고, 세그먼트(전송 계층에 존재하는 데이터의 집합, 패킷과 비슷함)의 헤더가 작고, 혼잡 제어 기능이 없다.

데이터 손실이 발생하는대신 전송 속도가 빨라 일반적으로 멀티미디어 스트리밍에 사용된다. DNS와 SNMP 또한 UDP를 사용한다.

UDP Checksum

전송된 세그먼트의 에러를 검출하기 위함이다. 다음과 같은 과정을 거친다.

1. 도착 IP주소, 송신 포트번호, 수신 포트번호, 데이터 길이, payload 등의 세그먼트의 데이터들을 16비트 단위로 쪼개서 전부 더한다.
2. 계산한 sum 값을 1의 보수를 취해 체크섬 값을 구한다.
3. 송신자는 체크섬 필드에 값을 넣어서 보낸다.
4. 수신자는 받은 세그먼트의 데이터들을 계산하여 체크섬을 구한다.
5. 체크섬 필드의 값과 동일한지 체크하여 오류를 검출한다.

그러나 전송 도중 checksum값이 바뀔 수도 있고, 데이터가 변형되었음에도 불구하고 checksum 값이 동일한 경우도 발생할 수 있기에 완벽한 방식은 아니다.

계산 문제

Circuit Switching

How long does it take to send a file of 640,000 bits from host A to host B over a circuit-switched network?

• all link speeds : 1.536 Mbps
• each link uses TDM with 24 slots/sec
• 500 msec to establish end-to-end circuit

먼저 파일의 크기와 링크의 스피드 단위를 통일시켜야 한다.

link speed : 1.536 Mbps = 1,536,000 bps 1 Mbps = 1,000,000 bps

TDM은 하나의 time slot에 하나의 사용자 채널을 할당하므로, 하나의 사용자 채널(링크)의 속도는 다음과 같이 구할 수 있다.

one link speed = all link speeds / number of time slots

계산하면 1,536,000 / 24 = 64,000 bps 를 구할 수 있다. 그렇다면 총 파일 사이즈를 링크의 속도로 나누면 파일이 보내지는 시간을 구할 수 있다.

Time = File Size / Link Speed

640,000 / 64,000 = 10s가 걸린다. 이후 circuit을 초기 연결하는 데에 0.5초가 걸리므로 총 걸리는 시간은 10.5초가 된다.

Application Layer

어플리케이션들은 크게 세 가지 아키텍쳐를 가진다.

Client-Server

컴퓨터 네트워크 1에서 설명했던 아키텍쳐로, 클라이언트는 서버에게 요청을 보내고 서버에 응답하여 값을 받는다.

Pure P2P

임의의 End system들이 직접 통신한다. End system들은 서로 클라이언트와 서버 역할을 동시에 수행하면서 동등한 지위를 가진다. 이때의 End system들을 peer라고 부르며, peer들은 간헐적으로 연결되고 ip 주소를 바꾼다. 확장성이 좋으나 관리하기 어렵다.

Hybrid of client-server and P2P

대표적으로 Skype와 같은 영상 통화 프로그램이 사용한다. 중앙 서버가 참여자의 주소를 찾고, 그 주소를 이용해 클라이언트들끼리 직접 연결된다. 또한 Instant Messaging에 사용하기도 한다.

데이터 통신

Process

호스트 안에서 실행되고 있는 프로그램을 일컫는다. 같은 호스트 안에서 실행되고 있는 두 프로세스들은 운영체제에 의해 정의되는 inter-process communication을 사용하여 통신한다. 다른 호스트 안에서 실행되는 프로세스들은 Socket을 이용해 통신한다.

Socket

프로세스가 데이터를 주고받기 위한 창구이다. 소켓은 프로토콜, IP 주소, 포트 넘버로 정의할 수 있다.

프로토콜

어플리케이션 레이어 프로토콜은 다음을 정의한다.

• request / response : 메세지의 타입
• message syntax(메세지 구문) : 메세지에 어떠한 필드들이 있는가
• message semantic(메세지 의미) : 필드 내의 정보들의 의미 대표적으로 HTTP / SMTP와 같은 프로토콜이 존재한다.

  IP 주소

  모든 호스트들은 유니크한 32-bit 주소를 가지고 있다.

  포트 넘버

  IP주소를 이용해 호스트가 어딨는지 찾을 수 있다. 그러나 다양한 프로세스들은 같은 호스트 내에서 실행되기에, IP 주소만으로는 프로세스를 특정하는 것에는 한계가 존재한다. 이를 해결하기 위해 0 ~ 65536사이의 숫자를 가지는 포트 넘버를 함께 조합하여 프로세스를 찾는다.

Web And HTTP

HTTP

어플리케이션 레이어 프로토콜 종류이다.

• client-server 아키텍쳐 사용 : server는 요청에 응답으로 object(HTML 파일, 이미지, etc)들을 보낸다. client는 받은 object들을 화면에 보여준다.
• TCP 통신 사용
• 포트 번호 : 80

HTTP request message

ASCII 코드로 작성되어 있다.

//Request Start line
GET /index.html HTTP/1.1\r\n
//Request Headers lines
Host:
User-Agent:
Accept:
...
Connection:
//Request Message Body
Entity Body

HTTP Methods

데이터를 이용해 어떠한 일을 할 것인지 알려준다.

• GET : 데이터를 요청할 때 사용
• POST : 리소스를 만들거나 업데이트 시 사용, 요청 횟수마다 리소스 생성
• PUT : POST와 비슷하나 일반적으로 리소스 수정 시 사용, 요청 횟수마다 같은 리소스 반환
• DELETE : 데이터를 삭제할 때 사용

HTTP response message

//Response Start line
HTTP/1.1 200 OK\r\n
//Response Headers lines
Date:
Server:
Last-Modified:
...
Content-Type:
//Response Message Body
Entity Body(Data)

HTTP response status code

Response start line에 존재하며, request의 상태를 나타낸다.

• 200(OK) : request 성공
• 301(Moved Permanently) : request한 object가 이동함
• 400(Bad Request) : request 메세지 이해 불가
• 404(Not Found) : request한 문서 서버에서 찾을 수 없음
• 505(HTTP Version Not Supported) : 그 말 그대로 버전 지원안됨

HTTP Cookie

서버가 사용자의 웹 브라우저에 전송하는 작은 데이터 조각이다. 브라우저는 그 데이터 조각들을 저장해 놓았다가, 동일한 서버에 재 요청 시 저장된 데이터를 함께 전송한다. 쿠키는 두 요청이 동일한 브라우저에서 들어왔는지 아닌지를 판단할 때 주로 사용한다. 이를 이용하면 사용자의 로그인 상태를 유지할 수 있다. 쿠키는 Response Headers lines에서 설정할 수 있다.

//HTTP Response Message
Set-Cookie: yummy_cookie=choco

이후 동일한 서버로 요청을 할 때마다 Cookie 헤더에 이전에 서버로 부터 받았던 쿠키를 그대로 돌려 보낸다.

//HTTP Request Message
Cookie: yummy_cookie=choco

Web caches

클라이언트가 멀리 있는 origin server까지 가지 않고 가까운 프록시 서버의 web caches 파일에 접근하여 원하는 파일을 받아오는 기술이다. 다음과 같은 과정을 거친다.

1. 클라이언트가 프록시 서버에 접근하여 캐시가 있는지 확인한다.
2. 있다면 프록시 서버에서 데이터를 받아온다.
3. 없다면 오리진 서버에 요청에 데이터를 받아오고, 받은 데이터는 프록시 서버에 저장된다. 그리고 클라이언트에 데이터를 전달해준다.

일반적으로 캐시는 ISP(하나의 네트워크를 운영하는 대학, 회사 등)에서 설치하고 관리된다.

DNS

Domain Name System. 웹사이트에 접속할 때 우리는 외우기 어려운 ip 주소 대신 도메인 이름을 사용한다. 도메인 이름을 URL에 입력했을 때 입력한 도메인을 실제 네트워크에서 사용하는 ip주소로 바꾸고 해당 ip주소로 접속하는 시스템을 DNS 서비스라고 한다.

• ‘계층 구조’를 가지는 분산 데이터베이스 구조
  • Root Name Server
  • TLD Server : com, org, net, edu, uk, fr, ca, jp
  • Authoritative DNS Server
  • Local Name Server
• hostname을 ip 주소로 번역(translation)한다.
• 별칭 호스트네임을 정식 호스트네임(Canonical hostname)을 찾을 수 있게 한다.

네트워크 구성 요소

네트워크는 총 3가지로 구성되어 있다.

1. Network Edge
2. Access Network
3. Network Core

1. Network Edge

그 말대로 네트워크의 가장자리, 즉 말단을 의미한다. 이 말단에는 수많은 End System(=Host)가 존재한다. 이 호스트들은 네트워크에 연결된 수많은 기기들을 의미한다. 우리가 사용하는 스마트폰이나 PC, 서버 등이 그 예시이다. 이 호스트들은 각각 Client/Server로 나누어진다.

Client

• 서버와 통신한다.
• 간헐적(intermittently)으로 연결되어 있다.
• 일반적으로 동적 IP 주소를 가진다.
• 클라이언트들끼리는 직접적으로 통신하지 않는다.

Server

• 정적 IP 주소를 가진다.

2. Access Network

End System(Host)들이 인터넷을 사용할 수 있도록 그 End System에서부터 다른 End System까지의 경로 상에 있는 첫 번째 라우터(Edge Router)에 연결하는 네트워크를 의미한다.

다른 말로 네트워크에 연결되기 위한 네트워크이다. 랜선이나 와이파이가 대표적인 예시이다.

Access Network의 종류

구분 기준 : 설치되는 위치 Residential, Institutional, Mobile 주거용, 기관용, 모바일용

구분 기준 : 공유 / 전용

• Shared Network : 많은 사용자가 동일한 인터넷을 공유하므로, 네트워크의 리소스는 사용자별로 분할되어 공유된다. 일반 가정에서는 공유 네트워크를 사용한다.

• Dedicated Network : 특정 사용자나 기기에 전용 리소스를 할당한다. 따라서 높은 대역폭과 빠른 응답 시간, 그리고 향상된 보안이 장점이다.

Ethernet Internet Access

이더넷을 사용하여 인터넷에 연결되는 것을 말한다. 이더넷은 네트워크 연결을 위한 표준 유선 연결 기술을 의미한다. 이때의 Access Network를 Ethernet Switch라고 부른다.

Wireless Access Networks

Access Point를 기점으로 작동한다. 대표적으로 WLAN(Wireless Local Access Network), Cellular Access Network 등이 있다.

3. Network Core

Host(Network Edge)들이 정보를 보내려고 한다. Access Network를 통해 네트워크에 연결되었다. 그렇다면 네트워크 안에서 정보는 어떻게 전달되는 걸까?

서로 연결되어 있는 라우터들의 집합인 Network Core를 통해 전달된다.

데이터 전달방식(노드들을 연결하는 방식)에는 Circuit Switching, Packet Switching 두 가지가 있다.

Circuit Switching

교수님 수업자료의 표현을 빌리자면, 네트워크 리소스를 여러 개의 조각(Pieces)로 나누어 사용한다. 각 조각들은 일반적으로 통화에 연결되어 사용된다. 이 조각들은 유저가 사용하지 않을 때까지 다른 유저가 사용할 수 없는, 각각이 독립된 채널이다. 채널을 할당하는 과정(setup)이 필요한 대신, 리소스를 공유하지 않아 속도와 성능이 일정하다.

회선을 분할하는 방식(링크를 공유하는 방식, 회선=링크)에는 대표적으로 세 가지가 존재한다. 주의 : 아래의 방식들은 Circuit Switching 뿐만 아니라 Packet Switching에서도 사용될 수 있다.

FDM(Frequency Division Multiplexing)

회선의 주파수 대역을 여러 개로 분할하여 각 채널에 배당함으로써 많은 채널의 하나의 회선을 공유하는 방식.

TDM(Time Division Multiplexing)

하나의 회선 대역폭을 시간 슬롯(Time Slot)으로 나누어 각 채널에 배당함으로써 각 채널은 정해진 시간동안 대역폭을 사용할 수 있다.

STDM(=Statistical Multiplexing, 통계적 시분할 다중화)

TDM은 각 채널의 데이터 존재 여부와 상관없이 시간을 할당하기 때문에 효율적이지 않다는 문제점이 있었다. 이를 해결하기 위해 만들어진 방식으로, 전송 데이터가 있는 경우에만 타임슬롯을 배정하여 효율성을 높인다. 대신 채널 식별자와 같은 정보가 필요하고, 채널주소 제어를 위한 마이크로프로세서가 필요하다.

Packet Switching

송신할 데이터를 Packet으로 쪼개어 전송한다. 라우터는 패킷 하나를 받으면 잠깐 저장(Store)한 후, 어디로 보낼지(Forward) 판단하고 보내게 된다. 이를 Store and Forward 방식이라고 한다.

Circuit Switching 방식에 비해 더 많은 유저가 네트워크를 사용할 수 있도록 한다.

각각의 패킷들은 전송 링크의 전체 대역폭을 사용하여 최대한 빠르게 전송되며, Circuit Switching과는 다르게 각각의 패킷들은 Network resource를 공유하게 된다.

패킷들은 전송 링크를 사용하기 위해 경쟁(contention)하게 된다. 패킷은 라우터에서 전송되면 줄(Queue)을 서게 되고, 링크로 보내지길 기다리게 된다. 데이터가 전송되기 전에 모든 패킷이 반드시 라우터에 도달해야 한다.

일반적으로 링크를 사용할 때는 Statistical Multiplexing 방식을 사용한다.

패킷을 전송할 때 막힘없이 전송되면 좋겠지만, 실제로는 여러가지 요인들로 인해 전송이 지연되게 된다.

Nodal Processing Delay

라우터에서 패킷의 헤더를 조사하고, 어디로 보내야할지 결정하는 데에 걸리는 지연시간. 이때 bit error 또한 체크한다.

Queueing Delay

패킷이 큐에서 기다리면서 생기는 지연시간. 라우터의 혼잡도에 따라 결정된다.

Transmission Delay

패킷이 큐를 빠져나간 후 링크까지 도달하는 데 걸리는 지연시간. 즉, 전송하려는 패킷을 링크로 밀어내는데 걸리는 시간을 의미한다. 링크의 대역폭에 따라 결정되며, (Packet Length / Link Bandwidth)로 계산할 수 있다.

Propagation Delay

패킷이 링크를 타고 전송될 때 생기는 지연시간으로, 거리와 링크의 매체(ex: 광통신)가 결정한다. 만약 assume zero propagation delay라는 가정이 있다면, 링크로 이동하는 시간을 계산하지 않고 위의 세가지 딜레이만을 고려하면 된다. (Length of link / Propagation speed in medium)으로 계산할 수 있다.

위와 4가지 지연시간의 합을 Nodal Delay(총 지연시간)이라고 한다.

패킷 손실

또한 라우터의 큐(=Buffer)는 제한된 수용 크기를 가지고 있는데, 큐가 꽉 차있을때 도달한 패킷은 버려지게(lost)되게 된다. 버려진 패킷은 이전의 노드나 End systems들에서 재전송될 수도 있고, 되지 않을 수도 있다. 이때 패킷 손실이 발생하게 된다.

ThroughPut(처리율)

네트워크에서 초당 실제로 처리되는 패킷의 양을 나타낸다. 일반적으로 bit를 사용한다.

고속도로에 차들이 움직이는 것을 상상해보자. 이론상 차들은 고속도로 위에서 모든 차선을 이용하여 최대 속도로 주행할 수 있다.이때 차들이 잠재적으로 얼마나 빠르게 이동할 수 있는지를 나타내는 것이 Bandwidth이다.

그러나 실제 고속도로에 CCTV를 달아 관찰해본다면, 실제로 차들이 얼마나 빠르게 이동하는지를 측정할 수 있을 것이다. 이것이 ThroughPut이다.

Ethernet Switch

모든 이더넷 호환 기기에는 고유한 하드웨어 주소(MAC ADDRESS)가 존재한다.

1. 이더넷 스위치는 PC1에게 패킷을 받으면, 패킷 안에 담겨있는 이더넷 스위치에게 데이터를 송신한 하드웨어의 주소(Source Mac Address, SA)와 수신된 포트를 자신의 Mac Address Table에 기록한다.
2. 이후 수신된 패킷의 목적 주소(DA)를 확인하고, 이 주소가 Mac Address Table에 있는지 확인한다. 없다면, 해당 패킷을 어떤 포트로 보내야할지 알 수 없으므로 패킷을 수신한 포트를 제외한 모든 포트에 패킷을 송신한다.
3. 패킷을 받은 PC2는 받은 패킷에 대한 응답으로 DA(PC1의 맥 주소)와 SA(PC2의 맥 주소)를 기록하여 다시 이더넷 스위치에 패킷을 보낸다.
4. 패킷을 받은 이더넷 스위치는 마찬가지로 Mac Address Table에 SA와 포트번호를 기록한다.
5. 이후 패킷의 DA를 확인하는데, 이 경우 Mac Address Table에는 PC1의 맥 주소와 해당 포트번호가 이미 기록되어 있다. 따라서 이더넷 스위치는 모든 포트에 해당 패킷을 보내지 않고, 해당 포트번호(PC1)로만 패킷을 보낸다.

라우터

부산을 목적지로 운전한다고 생각해보자. 물론 지구는 둥그니까 일직선으로 가다보면 나올 수도 있지만, 우리는 빠르게 도착하기 위해 내비게이션을 사용해 최적의 경로를 찾을 것이다. 이처럼 패킷을 목적지 IP(Host의 고유 번호)로 최적의 경로로 안내해주는 네비게이션이 라우터이다.

패킷(Packet)

우체국에서 우편을 보낸다고 생각해보자.

1. 어디서 보내는지, 어디로 가야하는지 상자와 편지 봉투에 작성한다.
2. 우편의 내용을 작성한다.
3. 우편물을 잘 받았다는 것을 확신하기 위해 서명을 받는다. 서명이 올바르지 않거나 서명을 받지 않는다면, 우편물이 제대로 가지 않았다는 의미이다.

패킷은 우편과 동일하다. 패킷의 구성요소는 다음과 같다.

• 헤더 : 소스 주소(SA), 목적 주소(DA), 프로토콜 및 포트 번호, TTL(Time to live), 등등
• 페이로드 : 패킷에 의해 전송되는 실제 데이터가 담긴다.
• 트레일러 : 트레일러의 내용은 각 네트워크의 유형별로 달라지지만, 일반적으로 모든 패킷이 완전히 수신되었는지 확인할 수 있도록 하는 CRC가 트레일러에 들어간다.

PDF 파일
원본 PDF 해석본 PDF

Eclipse / Becker

다운로드
Eclipse Downloads Becker

Eclipse 설치 과정

여기서 Select Another Mirror KaKao Corp을 선택하면 비교적 빠른 속도로 다운로드가 된다.

워크스페이스(앞으로 프로젝트 폴더 보관할 곳) 지정해주고 실행

프로젝트 만들기

프로젝트 이름은 PlayRobot, JRE 버전은 1.8로 설정 Libraries -> Add External JARs -> becker.jar 선택. becker.jar은 becker.zip 압축풀면 나온다. 왼쪽의 Package Explorer에서 PlayRobot 오른쪽 클릭 -> New -> Class 이름은 RobotAction으로 하자.

기본 코드 실행해보기

RobotAction.java 파일이 만들어지면 이렇게 기본 코드가 자동으로 작성된다.

• 코드에 빨간 줄 그어진 경우 : 프로젝트를 만들때 설정한 자바와 버전이 다르기 때문

에러 해결

PlayRobot 오른쪽 클릭 -> Build Path -> Configure Build Path Library -> Add Library -> JRE System Library Workspace default JRE -> finish

그 이후 (unbound)라고 써져있는 기존의 JRE를 Remove를 통해 지워주자. 이제 Order and Export 섹션으로 들어가, 오른쪽의 Up, Down를 비롯한 버튼을 적절히 활용해 다음과 같은 순서로 바꿔준다음, Select All를 누르고 Apply and Close 해준다.

이후 첫 번째 줄에 다음과 같은 코드를 넣어주자.

import becker.robots.*;

import는 C언어에서의 #include와 같은 역할을 한다. 외부 라이브러리(미리 정의된 기능들의 집합)인 becker를 불러오는데, 그 중 하위 폴더인 robots 안의 모든 기능(*로 표현한다.)을 불러온다는 의미이다.

이제 main메소드 안에 다음과 같은 코드를 입력해보자.

City mountain = new City();

new Wall(mountain, 3, 2, Direction.WEST);
new Wall(mountain, 2, 3, Direction.WEST);
new Wall(mountain, 1, 3, Direction.WEST);

new Wall(mountain, 1, 3, Direction.EAST);
new Wall(mountain, 2, 4, Direction.EAST);
new Wall(mountain, 3, 4, Direction.EAST);

new Wall(mountain, 3, 2, Direction.NORTH);
new Wall(mountain, 1, 3, Direction.NORTH);
new Wall(mountain, 2, 4, Direction.NORTH);

new Thing(mountain, 3, 1);

Robot karel = new Robot(mountain, 3, 0, Direction.EAST);

그리고 실행해보자. 처음 실행할 때는 PlayRobot 오른쪽 클릭 -> Run As -> Java Application을 선택하자.

• 만약, 이런 화면이 뜬다면, 밑으로 내려 RobotAction을 찾아주고 OK를 누르자.

코드 이해하기

과제를 수행하기 위해서는 이 코드를 이해해야 한다.

import becker.robots.*;
public class RobotAction {
    public static void main(String[] args) {
        City mountain = new City();

        new Wall(mountain, 3, 2, Direction.WEST);
        new Wall(mountain, 2, 3, Direction.WEST);
        new Wall(mountain, 1, 3, Direction.WEST);

        new Wall(mountain, 1, 3, Direction.EAST);
        new Wall(mountain, 2, 4, Direction.EAST);
        new Wall(mountain, 3, 4, Direction.EAST);

        new Wall(mountain, 3, 2, Direction.NORTH);
        new Wall(mountain, 1, 3, Direction.NORTH);
        new Wall(mountain, 2, 4, Direction.NORTH);

        new Thing(mountain, 3, 1);

        Robot karel = new Robot(mountain, 3, 0, Direction.EAST);        
    }
}

여기서는 public과 static, class와 객체에 대한 설명은 하지 않겠습니다. 자바에 대해 배우고 싶다면 FORIF로!

City Class

City mountain = new City();

미리 정의된 City 클래스의 새로운 객체를 만드는 과정. 쉽게 말해 City라는 개념을 가진 mountain이라는 변수를 만들어낸다.

Wall Class

새로운 Wall 객체를 생성한다. 이 Wall은 다음과 같은 규칙을 가진다.

Wall(City city, int street, int avenue, Direction orientation)

두 번째 줄:

new Wall(mountain, 3, 2, Direction.WEST);

street(동-서를 잇는 거리)은 3, avenue(남-북을 잇는 거리)은 2, 벽이 바라보는 방향은 동쪽이다. 좌표는 길이 아닌 산(초록색 네모)로 계산되며, 맨 왼쪽 위 산을 기준으로 (1,1)로 시작한다. 좌표를 (street, avenue)로 표현할 시 (3,2)는 위 사진과 같은 위치에 존재하게 된다. 위와 같은 규칙으로 벽들을 모두 만들어보자.

new Wall(mountain, 3, 2, Direction.WEST);
new Wall(mountain, 2, 3, Direction.WEST);
new Wall(mountain, 1, 3, Direction.WEST);
...
new Wall(mountain, 2, 4, Direction.NORTH);

Thing class

Thing은 로봇에 의해 들릴 수 있고 이동될 수 있는 무언가를 의미한다. Thing 클래스는 다음과 같은 규칙을 가진다.

Thing(City aCity, int aStreet, int anAvenue)

new Thing(mountain, 3, 1);

mountain시티에 street은 3, avenue는 1인 위치로 새로운 Thing을 만든다. 이때 thing은 wall과 달리 걸어다닐 수 있는 길을 기준으로 좌표를 설정해야 한다. 쉽게 말해 왼쪽과 위쪽 숫자보고 좌표 잡으면 된다. 로봇은 이 Thing(깃발)을 주워 산의 정상에 꽂아야 한다.

Robot class

Robot karel = new Robot(mountain, 3, 0, Direction.EAST);

karel이라는 로봇 객체를 생성한다. karel은 mountain(City)에 있으며, street은 3, avenue는 0이다. 바라보는 방향은 동쪽이다.

깃발 얻기 및 산 정상에 깃발 꽂기

이제 우리는 karel을 움직여 깃발(Thing)을 얻은 후, 산의 정상에 꽂고 다시 내려와야 한다.

Move, Pick things and turn left!

공식 홈페이지에서 모든 함수들의 정의를 확인할 수 있다.

move()

현재 바라보고 있는 방향으로 다음 교차로(1칸 앞)로 이동한다. 이때 방향은 바뀌지 않는다.

pickThing()

현재 있는 위치에서 Thing을 주우려고(pick up) 시도한다.

turnLeft()

왼쪽으로 90도 꺾는다.

위와 같은 함수들을 사용해 필요한 동작들을 수행할 수 있다.

karel.move();
karel.pickThing();
karel.turnLeft();
+karel.move();

(2,1)까지 오는 데에 성공했지만, 여기서 산을 오르기 위해서는 오른쪽으로 돌아야 하는데 Robot 클래스에는 turnRight()함수가 존재하지 않는다.

4-2. turnRight()

우리는 킹왕짱 쎈 SuperRobot 클래스를 새로 만들 것이다. (클래스, 로봇의 이름은 상관없다. 하지만 파일명과 클래스명은 항상 같아야한다.) RobotAction 클래스를 만들 때처럼 SuperRobot 클래스를 만들어주자. SuperRobot.java에 다음과 같은 코드를 입력한다.

import becker.robots.*;

public class SuperRobot extends Robot {
    public SuperRobot(City aCity, int aStreet, int anAvenue, Direction aDirection) {
        super(aCity,aStreet,anAvenue,aDirection);
    }

    public void turnRight() {
        this.turnLeft();
        this.turnLeft();
        this.turnLeft();
    }
}

public class SuperRobot extends Robot

Robot 클래스를 상속(extends)했기에 move, turnleft와 같은 기능들을 모두 사용할 수 있다. .

public SuperRobot(City aCity, int aStreet, int anAvenue, Direction aDirection) {
        super(aCity,aStreet,anAvenue,aDirection);
}

생성자(Constructor)를 만들어준다. 객체를 초기화시켜주는 역할을 한다.

super는 부모 클래스(Robot)로부터 상속받은 변수나 메소드를 자식 메소드(SuperRobot)에서 참조(사용)하는 데 쓰인다.

public void turnRight() {
        this.turnLeft();
        this.turnLeft();
        this.turnLeft();
}

새로운 메소드인 turnRight()를 만들었다. 이 메소드는 3번 왼쪽으로 돌아 오른쪽으로 1번 돌게 한다.

이제 RobotAction으로 가보자.

// RobotActoin.java
Robot karel = new Robot(mountain, 3, 0,Direction.EAST);

기존의 평범한 로봇을 슈퍼로봇으로 바꾸어주자.

// RobotActoin.java
SuperRobot karel = new SuperRobot(mountain, 3, 0,Direction.EAST);

karel은 이제 오른쪽으로 돌 수 있다.

// RobotActoin.java
karel.move();
karel.pickThing();
karel.turnLeft();
karel.move();
karel.turnRight();
karel.move();

산의 정상까지 쭉쭉 올라가보자.

karel.move();
karel.pickThing();
karel.turnLeft();
karel.move();
karel.turnRight();
...
karel.move();

4-3. 산 정상에 깃발 꽂기

산 정상에 깃발을 꽂기 위해서, putThing()을 사용하면 된다.

karel.putThing();

다시 내려간다.

karel.move();
//이 정도는 할 수 있잖아 여러분을 믿어요!
...
karel.turnLeft();

4-4. 색깔 바꾸기(필수 아님!)

karel을 시크한 블랙으로 색깔을 바꾸어주고 싶다면

import java.awt.Color;

색깔을 가져올 수 있는 라이브러리를 불러온다.

karel.setColor(Color.black);

깃발 색깔도 바꾸고 싶다면

Thing flag = new Thing(mountain, 3, 1);
flag.setColor(Color.black);

자바를 더 배우고 싶다면 FORIF로!

최종 제출

import java.awt.Color;
import becker.robots.*;
public class RobotAction {
    public static void main(String[] args) {
        City mountain = new City();

        new Wall(mountain, 3, 2, Direction.WEST);
        new Wall(mountain, 2, 3, Direction.WEST);
        new Wall(mountain, 1, 3, Direction.WEST);

        new Wall(mountain, 1, 3, Direction.EAST);
        new Wall(mountain, 2, 4, Direction.EAST);
        new Wall(mountain, 3, 4, Direction.EAST);

        new Wall(mountain, 3, 2, Direction.NORTH);
        new Wall(mountain, 1, 3, Direction.NORTH);
        new Wall(mountain, 2, 4, Direction.NORTH);

        Thing flag = new Thing(mountain, 3, 1);
        flag.setColor(Color.black);
        SuperRobot karel = new SuperRobot(mountain, 3, 0,Direction.EAST);
        karel.setColor(Color.black);

        karel.move();
        karel.pickThing();
        karel.turnLeft();
        karel.move();
        karel.turnRight();
        karel.move();
        karel.turnLeft();
        karel.move();
        karel.move();
        karel.turnRight();
        karel.move();
        karel.putThing();

        karel.move();
        karel.turnRight();
        karel.move();
        karel.turnLeft();
        karel.move();
        karel.turnRight();
        karel.move();
        karel.move();
        karel.turnLeft();
    }
}

5-2. 로봇 초기상태와 마지막 상태 스크린샷

초기상태

마지막 상태

이 포스팅 보는 정시템 화이팅! 수고하셨습니다.

백준 2750
문제 링크

문제

문제 이해

1. 오름차순으로 정렬한다.
2. 수는 중복되지 않는다.

(1 ≤ N ≤ 1000)

💡문제 해결 과정

수를 정렬하는 알고리즘에는 여러 종류가 있다. 대표적인 것에는 다음과 같은 것들이 있다.

버블 정렬

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 크기가 순서대로 되어 있지 않으면 교환하면서 자료를 정렬한다.

출처 : Gyoogle

선택 정렬

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

출처 : Toptal

퀵 정렬

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.(출처 : Wikipedia)

출처 : Gyoogle

오늘은 선택 정렬 알고리즘을 사용해 수를 정렬해보았다.

선택 정렬 알고리즘

1. arr배열 안에 n만큼 숫자를 담는다.

   int n, i, j, temp;
   int arr[1000];
   scanf("%d", &n);
   
   for (i = 0; i < n; i++) {
   scanf("%d", &arr[i]);
   }

2. 두 수를 바꾸는 swap 함수를 미리 만들어 준다.

   void swap(int* a, int* b)
   {
    int temp = *a;
    *a = *b;
    *b = temp;
   }

3. 가장 작은 값을 맨 처음에 놓는 작업을 반복한다.

   for (int i = 0; i < n-1; i++) { //마지막 순서는 바꿀 필요 X
    for (int j = i + 1; j < n-1; j++) { //현재 순서 바로 다음 순서부터 비교 시작
      if (arr[i] > arr[j]) { //큰 값이 있으면       
        swap(&arr[i], &arr[j]); //swap
      }
    }
   }

4. 출력한다.

   for (i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
   }

   코드

   #include <stdio.h>
   void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
   }
   

int main(void) { int n, i, j, temp; int arr[1000]; scanf("%d", &n);

for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } //아래의 2중 for문이 선택 정렬 핵심. for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n - 1; j++) { if (arr[i] > arr[j]) { swap(&arr[i], &arr[j]); } } }

for (i = 0; i < n; i++) { printf("%d\n", arr[i]); } return 0; }

## ✅성능 및 결과
### 버블 정렬
![](https://velog.velcdn.com/images/standard_wish/post/4d2819e4-5013-40ac-83c6-d2eb12f08eca/image.png)
### 선택 정렬
![](https://velog.velcdn.com/images/standard_wish/post/23a3a1bf-48a7-4547-9b5a-785597836ed3/image.png)

PDF 파일
원본 PDF 해석본 PDF

가이드

순서는 다음과 같다.

1. Processing
2. Task 2 : 튀는 공(ball-bouncing) 만들기
3. Task 3 : 충돌하는 공(ball-colliding) 만들기
4. Task 4 : 웹페이지에 bouncing balls 올리기

1. Processing

Processing이란?

Processing is a flexible software sketchbook and a language for learning how to code.

프로세싱은 미디어아트 및 교육용으로 만들어진 프로그래밍 언어로, JAVA로 작성되어 있다.

우리의 웹사이트는 Javascript를 사용하기 때문에, 변환과정을 거쳐야 한다.

다운로드

Processing

바로가기 만들기

Processing은 별도의 설치 과정이 존재하지 않는다. processing-[version] 폴더 내의 processing.exe을 실행하면 된다.

Task 2 : 튀는 공(ball-bouncing) 만들기

LMS 강의자료실에 올라온 ball-bouncing.txt 파일 내의 코드를 Processing에 붙여넣은 다음 왼쪽 위의 실행 버튼 혹은 Ctrl+R로 코드를 실행시켜보면 결과를 볼 수 있다.

새로운 공 추가하기

이제 우리는 새로운 공 하나를 추가할 것이다. 원래 코드에서 공 하나를 만들기 위한 여러 속성들을 똑같이 추가하면 된다.

원래 코드
PVector location;  // Location of shape
PVector velocity;  // Velocity of shape
PVector gravity;   // Gravity acts at the shape's acceleration

이제부터 기존의 공을 공1, 새로운 공을 공2라고 해보자. 공1의 변수 이름을 다음과 같이 수정하자. (//으로 시작하는 주석은 같을 필요 없다.)

PVector location1;  // Location of ball_1
PVector velocity1;  // Velocity of ball_1
PVector gravity1;   // Gravity of ball_1

그리고 그 밑에 공2 속성을 새롭게 추가하자.

PVector location1;  // Location of ball_1
PVector velocity1;  // Velocity of ball_1
PVector gravity1;   // Gravity of ball_1

PVector location2;  // Location of ball_2
PVector velocity2;  // Velocity of ball_2
PVector gravity2;   // Gravity of ball_2

원래는 다음과 같이 속성 이름을 하나하나 모두 바꿔주어야 하지만, 하나하나 수정하기는 쉽지 않기에 Processing의 찾기 및 바꾸기 기능을 이용하자.

Ctrl+F를 눌러 찾기 기능을 킨다. 모두 바꾸기를 클릭하여 모든 'location'을 'location1'으로 바꾸어준다.

PVector location1;  // Location of ball_1
.
.
.
PVector location2;  // location1 of ball_2

location을 제외한 velocity와 location도 동일하게 작업해주자. 프로그램 실행시 공 하나가 튀고 있다면 오류가 없는 것이다.

이제 모든 코드 중 location1/velocity1/gravity1과 관련된 코드가 있다면, 모두 복사하여 location2/velocity2/gravity2와 관련된 코드도 추가하자. 예를 들어 다음과 같은 원본 코드가 있다면(16-21줄)

void setup() {
  size(640,360);
  location1 = new PVector(100,100);
  velocity1 = new PVector(1.5,2.1);
  gravity1 = new PVector(0,0.2);
}

다음과 같은 코드로 수정하자.

void setup() {
  size(640,360);
  location1 = new PVector(100,100);
  velocity1 = new PVector(1.5,2.1);
  gravity1 = new PVector(0,0.2);

  location2 = new PVector(100,100);
  velocity2 = new PVector(1.5,2.1);
  gravity2 = new PVector(0,0.2);
}

원본 코드(27-33줄)

void draw() {
  background(0);

  // Add velocity1 to the location1.
  location1.add(velocity1);
  // Add gravity1 to velocity1
  velocity1.add(gravity1);

수정 코드

void draw() {
  background(0);

  // Add velocity1 to the location1.
  location1.add(velocity1);
  // Add gravity1 to velocity1
  velocity1.add(gravity1);

  // Add velocity1 to the location1.
  location2.add(velocity2);
  // Add gravity1 to velocity1
  velocity2.add(gravity2);

원본 코드(40-50줄)

// Bounce off edges
if ((location1.x > width) || (location1.x < 0)) {
  velocity1.x = velocity1.x * -1;
}

if (location1.y > height) {
  // We're reducing velocity1 ever so slightly 
  // when it hits the bottom of the window
  velocity1.y = velocity1.y * -0.95; 
  location1.y = height;
}

수정코드

// Bounce off edges
if ((location1.x > width) || (location1.x < 0)) {
  velocity1.x = velocity1.x * -1;
}

if (location1.y > height) {
  // We're reducing velocity1 ever so slightly 
  // when it hits the bottom of the window
  velocity1.y = velocity1.y * -0.95; 
  location1.y = height;
}

// Bounce off edges
if ((location2.x > width) || (location2.x < 0)) {
  velocity2.x = velocity2.x * -1;
}

if (location2.y > height) {
  // We're reducing velocity1 ever so slightly 
  // when it hits the bottom of the window
  velocity2.y = velocity2.y * -0.95; 
  location2.y = height;
}

다음과 같이 세 가지 부분을 모두 수정했다면, 이제 공2를 그려보자.

다음과 같은 원본 코드에서(ellipse는 원을 그리는 함수이다.)

// Display circle at location1 vector
stroke(255);
strokeWeight(2);
fill(127);
ellipse(location1.x,location1.y,48,48);

다음과 같이 바꿔주자.

// Display circle at location1 vector
stroke(255);
strokeWeight(2);
fill(127);
ellipse(location1.x,location1.y,48,48);
ellipse(location2.x,location2.y,48,48);

프로그램 실행 시 두 공의 위치/속도/중력이 모두 동일하여 겹쳐서 보이므로, 이제 공2의 속성을 조금씩 바꿔야 한다.

void setup() {
  size(640,360);
  location1 = new PVector(100,100);
  velocity1 = new PVector(1.5,2.1);
  gravity1 = new PVector(0,0.2);

  location2 = new PVector(100,100);
  velocity2 = new PVector(1.5,2.1);
  gravity2 = new PVector(0,0.2);
}

location2,velocity2,gravity2의 숫자를 바꾸어주자.

location : 시작 위치의 (x좌표,y좌표)

location1 = new PVector(100,100); //공1의 시작 위치 : (x : 100, y : 100)
location2 = new PVector(200,100); //공2의 시작 위치 : (x : 200, y : 100)

velocity : (x방향 속도, y방향 속도) gravity : (x방향의 중력 세기, y방향의 중력 세기)

이제 마지막으로 달라야 하는 속성인 크기를 바꾸자.

크기 관련 코드(68-69줄)

ellipse(location1.x,location1.y,48,48);
ellipse(location2.x,location2.y,48,48);

ellipse 함수의 속성

ellipse(공의 시작 x좌표, 공의 시작 y좌표, 공의 가로 크기, 공의 세로 크기)

공 두개가 튀기고 있는 모습을 스크린샷 찍어 저장해놓자.

* 공 색깔 바꾸기(in Processing)

만약 공의 색깔을 바꾸고 싶다면? fill() | color()

// Display circle at location vector
stroke(255);
strokeWeight(2);
fill(127); //127 = gray
ellipse(location1.x,location1.y,60,60);
ellipse(location2.x,location2.y,48,48);

fill() 함수는 다음 그리기 함수 시 색깔을 지정한다. 따라서 코드의 순서는 fill -> ellipse이어야 한다.

// Display circle at location vector
stroke(255);
strokeWeight(2);
fill(color(16,71,173)); //한양블루
ellipse(location1.x,location1.y,60,60);
fill(color(115,115,115)); //한양실버
ellipse(location2.x,location2.y,48,48);

"diff" 사용하기

이제 ball-bouncing-new.txt파일을 새롭게 만들고, 위에서 작성한 Processing 코드를 붙여넣자.

Task 2의 마지막 단계이다. "diff" 명령어를 사용해 어느 부분을 수정했는지 보여주자. 맥에서는 그냥 터미널에 예시로 나온 명령어를 그대로 입력하면 되지만 윈도우에서는 불가능하다.

첫 번째 방법 : "diff"와 비슷한 "FC" 사용 두 번째 방법 : cygwin(윈도우에서 리눅스 명령어을 쓸 수 있도록 해주는 프로그램)을 설치

"FC" 명령어 사용하기

편하긴 하지만, 실제 diff 명령어와 모양새가 조금 다른 결과물을 만들어낼 수 있다. 교수님은 상관쓰지 않음.

CMD를 열고 ball-bouncing.txt 파일과 ball-bouncing-new.txt 파일이 있는 위치로 이동하자. 예를 들어 파일이 D:\Downloads에 있다면 다음과 같이 이동할 수 있다.

D: //D 드라이브로 이동
cd Downloads //Downloads 폴더로 이동

*참고 만약 현재 경로에서 부모 폴더(상위 폴더)로 이동하고 싶다면

cd ..

파일이 있는 폴더로 이동 후 FC 명령어를 실행한다.

FC ball-bouncing.txt ball-bouncing-new.txt

cygwin 사용하기

cygwin 다운로드

프로그램 실행 후 다음과 같은 명령어를 입력한다.

cd `cygpath -m -a "윈도우 경로"`

예를 들면 다음과 같다.

cd `cygpath -m -a "D:\downloads"`

이제 diff 명령어를 사용하면 된다.

3. Task 3 : 충돌하는 공(ball-colliding) 만들기

LMS 강의자료실에 올라온 ball-colliding.txt 파일 내의 코드를 Processing에 붙여넣는다. 왼쪽 위의 실행 버튼 혹은 Ctrl+R로 코드를 실행시켜보자.다음과 같이 충돌하는 두 공을 볼 수 있다.

새로운 공 추가하기

충돌하는 새로운 공을 추가해보자. 우리가 수정해야 할 부분은 두 가지이다.

1. 새로운 공 객체를 추가한다.

   Ball[] balls =  { 
   new Ball(공이 나타나는 x좌표, 공이 나타나는 y좌표, 공의 반지름)
   };

원본코드(142줄부터)

Ball[] balls =  { 
  new Ball(100, 400, 20), 
  new Ball(700, 400, 80) 
};

수정코드

Ball[] balls =  { 
  new Ball(100, 400, 20), 
  new Ball(700, 400, 80),
  new Ball(300, 200, 50)
};

2. 새로운 공이 기존의 공과 닿았을 때, 충돌 효과가 나도록 한다.

원본코드

balls[0].checkCollision(balls[1]);

수정코드

balls[0].checkCollision(balls[1]); //ball의 0번째 객체와 1번째 객체 충돌효과
balls[0].checkCollision(balls[2]); //ball의 0번째 객체와 2번째 객체 충돌효과
balls[1].checkCollision(balls[2]); //ball의 1번째 객체와 2번째 객체 충돌효과

2-4와 동일하게 diff(혹은 FC)명령어를 사용하여 차이를 기록하면 Task 3 완료!

4. 웹페이지에 bouncing balls 올리기

4-1 Processing -> p5.js

웹페이지에 올리기 전, 프로세싱으로 만든 자바 파일을 자바스크립트로 변환하는 과정을 거쳐야 한다. p5.js 웹 에디터로 이동한 후, 로그인 과정을 거치자. 로그인해야만 작성한 sketch.js 파일을 다운로드 받을 수 있다.

p5.js Web Editor

이제 웹 에디터에 우리가 만든 ball-bouncing-new.txt 파일 내의 코드를 붙여넣어보자.다음과 같이 에러가 날 것이다.(당연히 java문법을 사용해 작성한 파일이니까!)

지금부터 javascript 문법으로 바꾸어보자.

4-1-1. 변수 선언하기

PVector location1;  // Location of shape
PVector velocity1;  // Velocity of shape
PVector gravity1;   // Gravity acts at the shape's acceleration

PVector location2;  // Location of shape
PVector velocity2;  // Velocity of shape
PVector gravity2;   // Gravity acts at the shape's acceleration

위의 코드를

let location1;  // Location of shape
let velocity1;  // Velocity of shape
let gravity1;   // Gravity acts at the shape's acceleration

let location2;  // Location of shape
let velocity2;  // Velocity of shape
let gravity2;   // Gravity acts at the shape's acceleration

다음과 같이 바꾸어주자.

let 변수명; // javascript에서는 변수 타입(정수/실수/문자열)에 관계없이 변수를 만든다.

4-1-2. 함수 선언/캔버스 생성/벡터 생성

void setup() {
  size(640,360);
  location1 = new PVector(100,100);
  velocity1 = new PVector(1.5,2.1);
  gravity1= new PVector(0,0.2);

  location2 = new PVector(350,350);
  velocity2 = new PVector(2,2);
  gravity2 = new PVector(0,1);

}

위 코드를 아래와 같이 바꾸어주자.

function setup() { //javascript에서 함수를 선언하는 방법
  createCanvas(640,360); //p5.js에서의 size()함수
  location1 = createVector(100,100); //p5.js에서의 PVector 생성 방법
  velocity1 = createVector(1.5,2.1);
  gravity1= createVector(0,0.2);

  location2 = createVector(350,350);
  velocity2 = createVector(2,2);
  gravity2 = createVector(0,1);

}

void draw() {

위 코드를 아래와 같이 바꾸어주자.

function draw() {

4-1-3 sketch.js 다운로드

28번째 줄까지 수정을 모두 완료했다면, 실행 버튼을 클릭하여 두 개의 공이 제대로 튀기고 있는지 확인해보자. 이제 Save -> Download 순서대로 눌러주자. 그러면 [괴상한 파일명.zip]이 다운로드 될텐데, 압축을 풀어준다. 안쪽의 파일들을 살펴보자면 다음과 같다.

index.html //HTML파일로, 페이지 파일이다.
p5.js //sketch.js가 제대로 작동하도록 돕는다.
p5.sound.min.js //sketch.js에 소리를 넣었을 시 제대로 작동하도록 돕는다.
sketch.js //우리가 만든 js코드가 들어가있다.
style.css //HTML파일의 스타일(모양새)를 지정한다.

우리의 ball-bouncing-new에는 소리가 들어가지 않으므로, p5.sound.min.js파일은 삭제해주자.

4-2. Nextjs에 HTML파일 렌더링하기

Render HTML file in pages of next js 위와 같은 설명 페이지를 참고했다.

4-2-1. public 폴더에 index.html,p5.js,sketch.js 넣기

아까 다운로드한 파일 p5.js sketch.js style.css 세 개의 파일을 모두 public폴더에 넣어준다.

4-2-2. api 만들기

다음과 같은 폴더 구조로 api.js 파일을 만들어주자.

pages/api/api.js

api.js에 다음과 같은 코드를 입력한다.

import fs from "fs";
const filename = "/index.html";
export default async function api(req, res) {
  res.setHeader("Content-Type", "text/html; charset=utf-8");
  res.write(await fs.readFileSync(filename, "utf-8"));
  res.end();
}

4-2-3. next.config.js 만들기

다음과 같이 BEGIN-NEXTJS(혹은 nextjs-blog)폴더 바로 밑에, 즉 루트 폴더 밑에 next.config.js파일을 만든다.

nextjs-blog/next.config.js

next.config.js에 다음과 같은 코드를 입력한다.

rewrites: async() => [
    {
        source: "/public/index.html",
        destination: "/pages/api/api.js",
    },
]

4-2-4. 개발용 서버 키고 접속해보기

최종 폴더 구조는 다음과 같다.

npm run dev

http://localhost:3000/index.html로 접속하여 테스트해보자. 혹은 직접 url을 바꾸어주어도 된다. 아름답게 작동하는 것을 볼 수 있다!

Task 4를 모두 완수한 당신, 축하드립니다. 만약 Link 태그를 사용하여 웹페이지 연결까지 하고 싶다면, 4-2-5 단계까지 따라해보세요!

4-2-5. Link 연결하기

index.js파일에서 연결하고 싶은 부분을 선택하고, Link태그로 위의 주소로 연결만 시켜주면 된다.

<Link href="/index.html">
  <span>You can see bouncing balls by clicking this card!</span>
</Link>

* 공 색깔 바꾸기(in p5.js)

Processing과 동일하다.

// Display circle at location vector
stroke(255);
strokeWeight(2);
fill(color(16,71,173));
ellipse(location1.x,location1.y,60,60);
fill(color(115,115,115));
ellipse(location2.x,location2.y,48,48);

글의 목적

C프로그래밍 공부를 하다, 컴퓨터가 실수를 나타내는 방식으로 부동 소수점을 배웠는데 구조가 어려워 정리하는 목적으로 작성하려 한다.

컴퓨터가 실수를 나타내는 방식에는 고정 소수점과 부동 소수점이 있다.

고정 소수점(Fixed point)

고정 소수점은 실수를 정수부(정수 부분)와 소수부(소수점 뒷 부분)으로 나눈다. 이때 소수부의 자릿수를 미리 정하고, 고정된 자릿수의 소수를 표현한다. 하지만 이는 자릿수를 고정하기에 표현할 수 있는 범위가 적어 잘 사용되지 않는다.

부동 소수점(Floating point)

부동 소수점은 실수를 부호부와 지수부(Exponent), 가수부(Mantissa)로 나누어 표현하는 방식으로 정규식을 사용한다.

전 강의에서 배웠듯 Float는 4byte, Double은 8byte의 크기를 가진다. 1byte는 8bits이기에 Float는 총 32bits를 가지고 Double은 64bits를 가진다. 이로 인해 Double이 표현할 수 있는 수의 범위가 더 커지는 것이다.

정규형

정규형에선 정수를 한 자리수(1)만 남김으로써 표현법을 통일하려 한다. 정규형을 사용하지 않으면 하나의 숫자에 대해 너무나 많은 표현이 가능하기 때문이다. 먼저 밑의 IEEE 754 표준을 보자.

IEEE 754 표준방식에 따르면, 정규형은 다음과 같다.

하나씩 나누어 설명하자면 다음과 같다.

부호부

Double과 Float 모두 1bit는 sign bit(=MSB(Most Significant Bit))에 할당한다. 이를 통해 우리는 이 실수의 부호를 확인할 수 있다.

지수 부분의 S는 sign bit를 의미한다. sign bit가 1이면 (-1)이 되어 음수가 되고, 0이면 (1)이 되어 양수가 된다.

가수부

M은 Mantissa, 즉 가수부를 나타낸다. 가수부에는 소수점 뒷자리를 표기하기 위한 비트들이 들어간다. 여기서의 M은 십진법으로 표현하지만, 나중에는 2진수로 변환하여 표기하여야 한다. 이해가 가지않는다면 가장 밑의 예시를 보자.

정규형에서 앞의 정수 부분이 왜 1인지 의문이 생긴다. 이는 가수부의 첫 번째 비트를 항상 1로 가정한다는 뜻인데, 다음과 같은 질문에 우리 교수님은 다음과 같은 답을 해주셨다.

"every value except the 0 starts with 1. by defining like this, 1 bit can be saved."

쉽게 말해, 가수부는 23 bit로 구성되어 있다는 것을 위의 도식을 통해 알 수 있는데, 정규화를 하게 되면 가수부의 정수부는 항상 1이 된다.

이때, "당연히 1인 것을 알고 있기 때문에" 가장 앞의 1(1 bit)을 실제 메모리에 저장하지 않고 존재한다고 가정한다. 따라서 실제로는 24bit를 사용해 가수부를 표현할 수 있으므로, 비트 하나를 아껴 소수점 자리를 더욱 정확히 표현할 수 있게 되는 것이다.

이를 "hidden-bit"를 사용한다고 말한다.

지수부

E는 Exponent, 즉 지수부를 나타낸다. 지수부는 소수점의 위치를 나타낸다.

* 만약 지수부가 3이라면, 소수점 3번째 자릿수부터 값이 있다는 것을 의미한다.

이 표현식에서, E는 아직 10진수이다. 그러나 결국 E는 Binary number로 변환되어야 하고, 그 Binary number는 위의 8 bit(Float) 혹은 11 bit(Double)안에 들어간다.

* 이해가 가지 않는다면 가장 밑의 예시를 보자!

excess-127 표기법

IEEE 754 표준에서 사용하는 32비트 부동 소수점 수(Float Type)에서 지수 부분은 8비트로 구성되어 있으며, excess-127 표기법을 사용한다.

지수를 나타내는 비트 패턴에 127을 더한 값을 실제 지수 값으로 사용한다.

그렇다면 왜 127이라는 숫자를 쓰는 것일까?

위의 식에서 Exponent에 8 bits를 할당하므로 256(2^8)까지를 나타낼 수 있다.

이때 일반적으로 사용되는 범위인 0255를 사용하지 않는다. 0은 0을 표현하기 위해, 255는 무한을 표한하기 위해 예약되어 있기 때문이다. (원문 : 0 and 255 are reserved for special use.) 따라서 1254가 사용된다.

이때 우리는 1~254에서 절반을 음수에, 나머지 절반을 양수에 할당한다. 이때 정규화하기 위해 127을 E에서 빼주게 된다.

EXCESS-127 표기법은 교수님이 설명한 바 없습니다. E-127을 이해하기 위해 더 찾아본 것을 기입한 것임을 밝힙니다.

두 부동소수점 수를 비교할 때 각각의 지수를 비교하는 것이 아니라, 비트 패턴을 비교하여 부동소수점 수의 크기를 판단한다. 이때 지수값에 127을 더한 비트 패턴을 사용하면, 지수값이 같은 두 부동소수점 수를 비교할 때 각각의 비트 패턴을 비교 연산자로 비교하여 크기를 판단할 수 있다.

부동소수점 비교 예시

예를 들어, 두 개의 부동소수점 수 A와 B가 있고, 이들의 부호, 지수 및 가수를 excess-127 표기법으로 나타내면 다음과 같다고 가정해보자.

A = 0 10000010 10100000000000000000000 B = 0 10000011 01000000000000000000000

이제 이 두 수를 비교해보자.

1. A와 B의 부호가 같은지 먼저 확인한다. 맨 왼쪽의 sign bit에 따라 이 경우 두 수 모두 양수이므로 부호 비교는 무시한다.
2. A의 지수 130과 B의 지수 131을 비교한다. 이들은 모두 양수이므로, 131이 130보다 크므로 B가 A보다 크다. 따라서 A < B라고 결론 내릴 수 있다.

이해가 잘 가지 않는다면, 다음과 같은 질답을 확인해보자.

Question: Why do we add 127 to the exponent in IEEE-754 floating number format to get the actual exponent value?

Answer: The exponent in IEEE 754 single precision is in Excess-127 format, which means you subtract 127 from the exponent field to get the number’s actual exponent. You add 127 to the exponent value to get the value to put into the exponent field. This ends up giving IEEE 754 some interesting properties: All bits zero naturally means zero. That’s both convenient and conceptually nice. The encodings for subnormal numbers flow smoothly into the normal numbers. If you have two floating point numbers, you can determine which one has the larger magnitude by interpreting the lower 31 bits as an integer and performing an integer comparison. That last property is perhaps the most mind blowing when you first notice it. Basically, there is a natural ordering among all floating point values, and if you ignore the sign bit, it exactly corresponds to the ordering of integers expressed in the same number of bits. This property makes it really easy to generate a total ordering primitive that’s no more expensive than an integer comparison. It also makes it easy to perform error calculations in terms of ULPs (units of the last place) by simply performing an integer subtraction on the bit patterns for the numbers. The all-bits-zero-means-0.0 aspect is handy. Many languages specify a default initializer of 0.0 for floating point variables. (In C and C++, it only applies to globals; others may apply it to locals as well.) Zeroing memory is often cheaper than initializing it to other values. If the exponent field were instead expressed as a signed exponent, the value 0.0 would have a more awkward representation, probably 4000000016 and all-bits-zero would likely correspond to 1.0 or 2.0. That just feels a bit weird, and in the face of default initializers, far less convenient.

예시

예시를 보자. 다음과 같은 숫자가 컴퓨터에 Float type(single precision)으로 어떻게 저장될까?

-0.15625(decimal)

1. 첫 번째로 10진수 숫자를 2진수로 바꿔줘야한다.(Transform to binary number) 소수부를 2진수로 바꾸는 방법은 소수부가 아닌 숫자(Non-fraction)를 바꾸는 방법과 반대이다. 원래는 2로 나눠주었다면, 소수부는 2를 곱해준다. 마지막으로 2를 곱해 나온 숫자가 0일때 멈추고, 위에서부터 아래로 숫자를 써내려가면 된다. 원래 숫자는 음수였으므로 앞에 -를 붙여주면 2진수 변환이 완성된다.

-0.00101

2. 변환한 2진수를 Normalized Format으로 정규화시킨다. 2-1. 음수이기에 Sign bit에 1이 들어가야한다. -> (-1)^1 2-2. 앞자리 수를 1로 맞추기 위해 왼쪽으로 3번 움직이기에 (1.01)X2^(-3)으로 표현할 수 있다. 2-3. 이때 01이 Fraction이 되고,Float Type에선 Fraction part에 총 23bit를 부여하므로 01000000000000000000000로 쓸 수 있다. 2-3. 이때 정규화 식에 따라 (E-127) = -3이므로, E는 124가 되고, E는 바이너리 형태로 변환되어야 하기에 124를 2진수로 변환하면 1111100이 된다. 2-4. Exponent에 8bit(in Float Type)를 부여하므로, 01111100으로 쓸 수 있다.

    1              01111100            01000000000000000000000

   (Sign Bit)       (Exponent)                 (Fraction)

백준 2750
문제 링크

문제

문제 이해

1. 오름차순으로 정렬한다.
2. 수는 중복되지 않는다.

(1 ≤ N ≤ 1000)

💡문제 해결 과정

수를 정렬하는 알고리즘에는 여러 종류가 있다. 대표적인 것에는 다음과 같은 것들이 있다.

버블 정렬

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 크기가 순서대로 되어 있지 않으면 교환하면서 자료를 정렬한다.

출처 : Gyoogle

선택 정렬

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

출처 : Toptal

퀵 정렬

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.(출처 : Wikipedia)

출처 : Gyoogle

오늘은 버블 정렬 알고리즘을 사용해 수를 정렬해보았다.

버블 정렬 알고리즘

1. arr배열 안에 n만큼 숫자를 담는다.

   int n, i, j, temp;
   int arr[1000];
   

scanf("%d", &n);

for (i = 0; i < n; i++) { scanf("%d", &arr[i]); }

2. 인접한 두 수를 바꾸는 swap 함수를 미리 만들어 준다.
```cpp
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

3. 인접한 두 수를 비교한다.

   for (i = n - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j],&arr[j+1]);
            }
        }
    }

4. 출력한다.

   for (i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
    }

   코드

   #include <stdio.h>
   void swap(int* a, int* b)
   {
    int temp = *a;
    *a = *b;
    *b = temp;
   }
   

int main() { int n, i, j, temp; int arr[1000];

scanf("%d", &n);

for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
}

for (i = n - 1; i >= 0; i--) {
    for (j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
            swap(&arr[j],&arr[j+1]);
        }
    }
}

for (i = 0; i < n; i++) {
    printf("%d\n", arr[i]);
}

return 0;

}

## ✅성능 및 결과
![](https://velog.velcdn.com/images/standard_wish/post/4d2819e4-5013-40ac-83c6-d2eb12f08eca/image.png)

원본파일
원본 PDF 해석본 PDF

가이드

순서는 다음과 같다.

1. Node.js와 Git설치
2. Next.js 기본 앱 만들기(create-nextjs-app)
3. 다른 페이지로 링크 시키기(/posts/first-page)
4. first-page와 index.js 꾸미기
5. Git CLI를 사용하여 Commit/Push하기
6. 최종 제출해야 할 3가지

1. Node.js와 Git설치

다운로드

Node.js Git

맥에서 깃 설치하기

맥에서 깃 설치하기

테스트

Node.js와 Git이 잘 설치되었는지 테스트를 해보자.
cmd에 각각 git과 node -v을 입력하고 잘 출력되는지 확인한다.

git 입력시

node -v 입력시

2. Next.js 기본 앱 만들기

Visual Studio Code를 기준으로 작성하였다.

2-1. Visual Studio Code로 새롭게 만든 폴더를 연다.

2-2. Visual Studio Code 내의 터미널에서 명령어를 입력한다.

터미널을 여는 단축키는 Ctrl+~이다.

npx create-next-app@latest nextjs-blog --use-npm --example "https://github.com/vercel/next-learn/tree/master/basics/learn-starter"

OK to proceed? (y)라는 문구가 나오면 y 입력하고 엔터, 혹은 그냥 엔터를 누르면 진행된다. (이렇게 뜨면 성공)

기본적인 파일들이 만들어졌을텐데, 우리가 개발용 서버(development server)를 열기 위해서는 경로를 이동해줘야 한다. 터미널에 다음과 같은 명령어를 치도록 하자.

cd nextjs-blog

npm run dev

(경로는 Tab키를 사용하여 자동완성 시킬 수 있다.)

url: http://localhost:3000

위와 같은 부분에 커서를 올리면 밑줄이 쳐지는데, 이때 Ctrl+Click으로 해당 주소를 열 수 있다. 다음과 같은 창이 뜨면 성공이다.

*만약 터미널 입력시 오류가 난다면, 맨 밑의 오류 모음을 참고하자.

3. 다른 페이지로 링크 시키기

3-1. first-page.js 만들기

폴더명 오른쪽의 New File과 New Folder버튼을 사용하여
다음과 같은 경로로 파일을 만든다.

nextjs-blog/pages/posts/first-page.js

first-page.js에 다음과 같은 코드를 작성한다.

export default function FirstPage() {
    return (
        <div>
            MY FIRST PAGE
        </div>
    )
}

Ctrl+S로 파일을 저장한다음, 개발 서버에 다시 접속해보자.

참고: 파일명 오른쪽의 흰색 동그라미가 있을 때는 아직 저장되지 않은 것이다. index.js는 저장되지 않았고, first-page.js는 저장되었다.

그리고 URL을 http://localhost:3000/posts/first-page 로 바꿔주면 아까 만든 페이지가 보인다!

3-2. index.js와 first-page.js 연결시키기

이제 특정 DIV(문장,버튼 등등)을 클릭 시 위와 같은 페이지로 연결되게 해보자. NextJS에서는 Link 태그를 사용하여 페이지를 이동시킨다.

index.js의 맨 윗부분에 Link를 불러와준다.

import Link from 'next/link';

Welcome to Next.js!에서 Next.js!를 눌렀을 때 first-page로 이동되게 하자.

기존 링크를

Welcome to <a href="https://nextjs.org">Next.js!</a>

다음과 같이 바꿔준다.

Welcome to <Link href="posts/first-page">Next.js!</Link>

저장 후 Next.js!를 클릭했을 때 잘 이동한다면, 성공이다!

3-3. first-page.js 기본 세팅

import Link from 'next/link'
export default function FirstPage() {
    return (
        <div>
            <h2>Write your message here!</h2> 
            <Link href="/">Back to home</Link> //GO TO "/"(MAIN PAGE)
        </div>
    )
}

4. 웹페이지 꾸미기

4.1 HTML 기본

웹페이지를 꾸미기 전, html의 tag에 대해 먼저 알아야 한다.

1. 태그는 /를 사용해 항상 닫아줘야 한다.
2. 태그와 태그 사이에 Content, 즉 쓰고자 하는 글이 들어간다.
3. 여러 태그를 사용해 Content에 다양한 속성을 부여할 수 있다.

   <h1 className={styles.title}>
   Welcome to <Link href="posts/first-page">Next.js!</Link>
   </h1>

   즉, Next.js!라는 문장은 다음과 같이 이해할 수 있다.

   <h1></h1>태그에 감싸져 있으므로 글씨 크기가 커지고 글씨 굵기가 굵어짐.
   <Link></Link>태그에 감싸져 해당 문장을 클릭했을 때 "posts/first-page" 주소로 이동

   4.2 대충 꾸미기

   중요 : 디자인 다 달라야합니다. 누가봐도 비슷한 부분이 있으면 점수 깎는다고 합니다.

   꾸미기를 위한 간단한 태그 소개
4. div/span tag

<div>Divison의 약자로, 레이아웃을 나누는 데 쓰인다. 특별한 기능은 없다.</div>
<div>자동 줄바꿈이 된다.</div>
<div style="color:#0E4A84">보통 CSS와 함께 사용된다.</div>

<span>특별한 기능이 없고 레이아웃을 나누는데 쓰인다.</span>
<span>줄바꿈이 되지 않는다.</span>
<span>줄을 바꾸고 싶다면 br 태그를 사용하자.

1. p tag

   <p>"줄바꿈 되는 일반 문장"</p><p>"줄바꿈 되지롱"</p>

   "줄바꿈 되는 일반 문장"

   "줄바꿈 되지롱"

2. h tag

   <h1>이렇게 바뀝니다.</h1>
   <h2>이렇게 바뀝니다.</h2>
   <h3>이렇게 바뀝니다.</h3>
   ...
   <h6>이렇게 바뀝니다.</h6>

   이렇게 바뀝니다.

   이렇게 바뀝니다.

   이렇게 바뀝니다.

   ...

   이렇게 바뀝니다.

3. ul/oi tag 순서 있는 리스트/순서 없는 리스트

<ol>
    <li>장유유서</li>
    <li>삼십이립</li>
</ol>

순서 없는 리스트
<ul>
  <li>가는 데 순서 없어</li>
  <li>가는 데 순서 없어</li>
</ul>

1. 장유유서
2. 삼십이립

• 가는 데 순서 없어
• 가는 데 순서 없어

이제 Content에 해당하는 문장을 맘대로 꾸미면 된다. 예를 들어

1. Next.js를 본인 이름으로 바꾼다.

   Welcome to <Link href="posts/first-page">Jun Seong Pyo!</Link>

2. Description을 소개 문구로 바꾼다.

   <p className={styles.description}>
   Let me introduce myself
   </p>

3. 웹에 대해 배우고 싶다면 FORIF로 오세요!

5. Git CLI -> Commit/Push!

5.1 Github Repository 만들기

https://github.com/ Github에 접속해 계정이 없다면 계정을 만들고 로그인한다. New repository를 클릭해 새로운 저장소를 만든다.

Public(교수님이 보실 수 있도록)에 체크해주자. Add a README file은 체크하지 말자.

완성!

5.2 Git CLI를 이용한 Commit/Push

vscode 내 터미널을 새로 열고, 다음과 같은 명령어 한 줄씩 입력하면 된다. 개발 서버는 꺼도/켜도 상관없다.

cd nextjs-blog //nextjs-blog 폴더를 repository에 올리기 위함이다.
git init // 이제부터 이 폴더는 git의 영향을 받는다.
git add . // 모든 파일을 원격 저장소에 올리겠다.
git config --global user.email "이메일" //github계정의 이메일을 쓰면 된다.
git config --global user.name "이름" //Github계정의 아이디를 쓴다.

git commit -m "First Commit"
git branch -M main
git remote add origin https://github.com/[github 계정명]/[원격저장소명].git
git push -u origin main

예시는 다음과 같다.

git remote add origin https://github.com/standardwish/cs_nextjs.git

다음과 같이 파일이 업로드 되면 최종 성공이다.

* 이후 파일을 수정한 후 다시 git에 올리고 싶다면

git add . //수정된 모든 파일을 올릴 것이다.
git commit -m "Message" //왜 수정했는지, 어떤 것이 수정되었는지 메세지에 작성하면 된다. 커밋에 대한 규칙도 있는데, commit convention 참고
git push

에러 모음

1. Git Push 시 오류날 때(맥북 사용시)

다음 링크를 참고하세요. GitHub 토큰 인증 에러 해결

2. 'npm' 용어가 cmdlet, 함수, ...

전역 환경변수 설정을 해주어야 합니다.

다음 링크를 참고하세요. VS Code 프로젝트 폴더에 npm 설치 에러

백준 10812
문제 링크

문제

문제 이해

• I J K 순서대로 입력되고, 바구니가 K부터 재배열된다.

• 예시1

  입력 : 1 6 4 원래 배열 : 1 2 3 4 5 6 바뀐 배열 : 4 5 6 1 2 3

• 예시2

  입력 : 3 9 8 원래 배열 : 3 4 5 6 7 8 9 바뀐 배열 : 8 9 3 4 5 6 7

• 모든 순서를 회전시킨 다음, 가장 왼쪽에 있는 바구니부터 공백으로 구분해 출력한다.

• 바구니의 번호는 100을 넘지 않는다. 따라서, I/K/J도 100을 넘지 않는다.

(1 ≤ N ≤ 100, 1 ≤ M ≤ 100)

💡문제 해결 과정

1. 첫째 줄에 N,M을 입력받는다. 바구니를 N 크기의 배열로 선언하고, 바구니 번호에 맞는 공을 담는다.

   int N,M;
   scanf("%d %d", &N, &M);
   int basket[M+1];
   for(int i=0; i<N; i++) basket[i] = i+1;

2. M번 동안 반복되며, I J K를 순서대로 입력받는다.
   편의상 beg : end : mid라고 부르겠다.

   int beg, end, mid;
   for(int i=0; i<M; i++) {
   scanf("%d %d %d", &beg, &end, &mid);
   }

3. 여기서 본격적인 고민이 시작된다. 배열이 나열되는 순서는 다음과 같다.

   mid,mid + 1, ... ,end - 1,end, beg, beg+1, ... , mid - 1

   따라서 첫번째로 mid - end값을 begin까지 앞으로 밀어줘야 한다.

   for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];

   그러나 위와 같은 알고리즘을 실행했을 때 mid-1부터 beg까지의 값이 사라지게 된다. 이를 해결하기 위해 임시 변수 temp에 그 값을 저장시킨다음, 다시 end부터 차례대로 temp값을 넣어준다.

   int temp;
   for(; beg - 1 < mid - 1; mid--, end--) {
      temp = basket[mid - 2];
      for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];
      basket[end-1] = temp;
    }

   (INDEX는 0부터 시작하므로 모든 beg,mid,end값에서 1를 빼야 한다.)

5. basket배열을 차례대로 출력한다.

   for(int j=0; j<N; j++) printf("%d ", basket[j]);

   코드

   #include <stdio.h>
   int main() {
   int N,M, basket[100], temp;
   int beg, end, mid;
   scanf("%d %d", &N, &M);
   for(int i=0; i<N; i++) basket[i] = i+1;
   for(int i=0; i<M; i++) {
    scanf("%d %d %d", &beg, &end, &mid);
    for(; beg - 1 < mid - 1; mid--, end--) {
      temp = basket[mid - 2];
      for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];
      basket[end-1] = temp;
    }
   }
   for(int j=0; j<N; j++) printf("%d ", basket[j]);
   return 0;
   }

   ✅성능 및 결과

   

백준 1157
문제 링크

문제

문제 이해

• 알파벳 대소문자를 구분하지 않는다.

• 가장 많이 사용된 알파벳이 여러 개일 경우 "?"를 출력한다.

• 단어의 길이는 1,000,000을 넘지 않는다.

(1 ≤ WORD ≤ 1,000,000)

💡문제 해결 과정

1. 입력받은 단어를 저장할 배열 'arr'과 알파벳 별 카운트를 저장할 배열 'cnt'를 선언한다.
2. 'arr'에 단어를 입력받고, strlen함수로 단어의 길이를 계산한다.

   int len;
   char arr[1000000];
   int cnt[26] = {0};
   int select = 0;
   

scanf("%s", arr); len = strlen(arr);

3. 알파벳 별 카운트를 계산한다. 이때 대소문자를 구분하지 않으므로 a부터 z까지 / A부터 Z까지 반복문을 두 번 실행해야 한다.
4. 알파벳 별 count가 cnt에 들어가게 된다.
```cpp
for(int i = 'a'; i <= 'z'; i++)
    {
        for(int j = 0; j < len; j++)
        {
           if(i == arr[j])
               cnt[i-'a']++;
        }
    }
for(int i = 'A'; i <= 'Z'; i++)
    {
        for(int j = 0; j < len; j++)
        {
           if(i == arr[j])
               cnt[i-'A']++;
        }
    }

5. cnt배열에서 가장 큰 값을 찾아 출력해야 한다. C는 max함수가 없으므로 인덱스를 증가시키며 max값과 해당 인덱스(select)를 찾는 방식을 택했다.

   int max = cnt[0];
   for (int i = 1; i < 26; i++) {
   if (max < cnt[i]) {
    max = cnt[i];
    select = i;
   }
   }

6. cnt배열에서 가장 큰 값과 같은 값을 가진 원소의 개수를 'result'에 넣는다.
   result가 1보다 크면 "?"를 출력하고, 그렇지 않으면 'select'에 해당하는 알파벳을 출력한다.

   for (int i = 0; i < 26; i++) {
   if (max == cnt[i])
    result++;
   }
   if (result > 1)
   printf("?\n");
   else
   printf("%c", select + 'A');

   코드

   #include <stdio.h>
   #include <string.h>
   

int main(void) { int max, result = 0, len; char arr[1000000]; int cnt[26] = {0}; int select = 0;

scanf("%s", arr); len = strlen(arr);

for (int i = 'a'; i <= 'z'; i++) { for (int j = 0; j < len; j++) { if (i == arr[j]) cnt[i - 'a']++; } } for (int i = 'A'; i <= 'Z'; i++) { for (int j = 0; j < len; j++) { if (i == arr[j]) cnt[i - 'A']++; } }

max = cnt[0]; for (int i = 1; i < 26; i++) { if (max < cnt[i]) { max = cnt[i]; select = i; } }

for (int i = 0; i < 26; i++) { if (max == cnt[i]) result++; }

if (result > 1) printf("?\n"); else printf("%c", select + 'A'); return 0; }

## ✅성능 및 결과
![](https://velog.velcdn.com/images/standard_wish/post/6fd7a1a3-f116-4476-b6c1-3a81588b77c8/image.png)

백준 10813
문제 링크

문제

문제 이해

• 바구니의 개수 : N / 공을 바꾸는 횟수 : M

(1 ≤ N ≤ 100, 1 ≤ M ≤ 100)

• 1번 바구니부터 N번 바구니까지는 각각 번호에 해당하는 공이 들어있다.

(EX : 1번 바구니 : 1번 공, 2번 바구니 : 2번 공, ... N번 바구니 : N번 공)

• I번 바구니와 J번 바구니의 공을 바꾼다.

(EX : I = 1 / J = 3라면 1번 바구니에는 3번 공을, 3번 바구니에는 1번 공을 넣는다.)

(1 ≤ i ≤ j ≤ N)

💡문제 해결 과정

첫 번째로 각 바구니에 바구니의 번호와 대응하는 공을 넣어줘야 한다. 이때 바구니의 최대 범위는 N까지이다.

for (int i = 1; i <= n; i++) {
    arr[i] = i;
  }

이후 M번 동안 I와 J의 입력을 받은 후, J번째 공과 I번째 공을 스왑하면 된다.

int i, j;

  for (int a = 1; a <= m; a++) {
    scanf("%d %d", &i, &j);
    swap(&arr[i], &arr[j]);
  }

여기서 중요한 것은 C언어에선 SWAP 함수가 내장되어 있지 않다. 따라서 SWAP 함수를 직접 구현해야한다. 처음 내가 시도한 SWAP 함수는 다음과 같았다.

void swap(int x, int y) {
  int temp = x;
  x = y;
  y = temp;
}

그러나 다음과 같은 함수를 사용했을 때 값이 바뀌어 나오지 않고 그대로 출력되었다. 이유를 찾아보니 함수 내에서 바뀐 값은 함수 밖에서 적용이 되지 않는다는 사실을 깨달았다. 이를 해결하기 위해서는 변수의 메모리 주소를 찾는 포인터 변수가 필요했다.

void swap(int* x, int* y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

x와 y를 포인터 인자로 받은 후, 임시 그릇인 temp에 x를 담는다. 이후 x와 y의 포인터 값을 바꾸고, 다시 y에서 temp(x의 값)을 넣어주면 x와 y의 포인터 값이 바뀌게 된다.

마지막으로 출력해주면 코드가 완성된다.

for (int a = 1; a <= n; a++) {
    printf("%d ", arr[a]);
  }

코드

#include <stdio.h>

void swap(int* x, int* y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

int main(void) {
  int n, m, temp;
  scanf("%d %d", &n, &m);
  int arr[100];
  for (int i = 1; i <= n; i++) {
    arr[i] = i;
  }
  int i, j;

  for (int k = 1; k <= m; k++) {
    scanf("%d %d", &i, &j);
    swap(&arr[i], &arr[j]);
  }
  for (int k = 1; k <= n; k++) {
    printf("%d ", arr[k]);
  }
}

✅성능 및 결과