독학두비니

Coding_Algorithm/DS_Algorithm

Heap Sort

Heap Sort 0. 개요 앞서 다뤘던 내용들은 자료구조를 사용하지 않는 알고리즘이었다. (Insertion Sort, Merge Sort 등) 그러나 자료구조를 사용할 경우 더 효율적으로 문제를 풀 수 있는 경우가 생기며, 대표적으로 Max heap를 사용하는 Heap Sort가 있다. 1. 자료구조 heap 자료구조 heap, 특히 max heap에 대해서 알아봅시다. Max Heap이 되기 위해서는 다음 조건을 만족해야한다. 1) a complete binary tree여야함 - tree 구조에서 마지막 level을 빼고는 모두 차 있어야 함 - 마지막 level은 왼쪽부터 오른쪽으로 차있음 2) Max-heap Property를 가지고 있어야 함 - key(x) >= keys(at x's chi..

Coding_Algorithm/DS_Algorithm

Probabilistic Analysis

Probabilistic Analysis 0. 개요 기존에는 알고리즘의 시간분석도를 계산할 때 알고리즘에서 실행되는 명령어의 수를 계산하는 방식으로 진행했다. 특히 worst case로 진행해 그러나 많은 알고리즘은 주어지는 입력에 따라 성능이 달라지는 경우가 많다. 이렇게 입력이 확률적으로 주어지는 상황에서, 입력에 대한 worst case로 성능을 보는 것이 아닌, 평균적인 성능으로 알고리즘의 성능을 분석하는 방법을 알고리즘의 확률적 분석이라고 한다. 다만 확률적 분석은 입력의 분포를 알고 있다는 가정 하에 진행된다. 입력의 분포를 모른다면 확률적 분포를 진행할 수 없다. 1. Hiring Problem Hiring Problem은 사람을 채용할 때의 문제를 칭한다. 각각 사람을 면접볼 때 비용이 들..

Coding_Algorithm/DS_Algorithm

Growth of Function

0. Asymptotic Notations 알고리즘을 만들다 보면 알고리즘을 평가해야 할 때가 많습니다. 너무나 당연한 이야기지만 슈퍼컴에서 돌릴 때와 내 작고 귀여운 5년된 노트북에서 돌릴 때 성능 차이는 당연히 날 것입니다.(아주많이..ㅠ) 따라서 알고리즘의 성능을 평가할 때는 컴퓨터의 성능과는 관계가 없는 방법으로 평가를 하게 됩니다. 이를 Asymptotic Notation(점근표기법)이라고 합니다. 한국어 이름 '점근'에서 볼 수 있듯이, Asymptotic Notation에서는 'n을 무한대로 보냈을 때 소요되는 시간이 얼마나 걸리는가'를 기준으로 봅니다. 예를 들어 어떠한 알고리즘의 시간소요량이 f(n)=5n^2+8n+10이라고 합시다. 이 경우 n을 무한대로 보내면, 5n^2의 값이 8n에..

Coding_Algorithm/DS_Algorithm

Divide and Conquer 관점에서 본 Merge Sort

Divide and Conquer 관점에서 본 Merge Sort 0. 개요 지난 글에 이어서 오늘은 Divide and Conquer approach에 대해서 알아보고, 나아가 Merge Sort에 대해서 알아보도록 하겠습니다. 1. Divide and Conquer 먼저 Divide and Conquer에 대해서 알아봅시다. 말 그대로 Divide(분할)한 뒤 Conquer(정복)하는 개념입니다. 가장 중요한 것은 Divide - Conquer - Combine의 순서로 진행된다는 점입니다. 이전 글이었던 Incremental approach와의 차이점에 대해서 이야기하자면, Incremental approach는 작게 문제를 나누어서 해결한 작은 문제를 기반으로 더 큰 문제를 풀어나간다면, 문제를 ..

Coding_Algorithm/DS_Algorithm

Incremental approach로 본 Insert sort algorithm

Incremental approach로 본 Insert Sort Algorithm 0. 개요 알고리즘을 구상할 때 여러 가지 접근 방법이 있겠지만, 크게 두 가지 approach에 대해서 다룰 예정이다. 첫 번째는 Incremental Approch이고, 대표적인 예시인 Insert Sort Algorithm에 대해서 알아볼 것이다. 1. Incremental Approach(증가적 도달) Incremental Approach란 위에서도 이야기했듯, 문제를 푸는 하나의 시각이다. 자세히 알아보자. GPT는 쪼개서 풀어내는 방법을 'Subproblems'라고 했는데, 추후 한 번 더 이야기하겠지만 작은 부분 문제를 순차적으로 해결하면서 전체적인 문제 해결을 추구하는 방법이다. 이는 작은 부분 문제를 독립적..

Coding_Algorithm/DS_Algorithm

알고리즘 & Halting Problem

알고리즘 & Halting Problem 0. 알고리즘이란? 다음은 위키백과에 수록되어있는 알고리즘의 정의이다. 알고리즘, 셈법은 수학과 컴퓨터과학, 전산언어학 등에서 사용되는, 문제 해결 방법을 정의한 일련의 단계적 절차이다. 알고리즘에 대해서 보기 전에, 한 가지 짚고 넘어가야 하는 점이 있다. 여기서 '문제'란 무엇일까? 특히 알고리즘에서 문제(Problem)을 논할 때는, Computational Problem을 논한다. 알고리즘에서의 Computational Problem이란 input과 output으로 구성됩니다. 그리고 이 input과 output 사이의 관계를 나타내는 것을 문제의 정의(definition)이라고 한다. 알고리즘의 문제에 대한 대표적인 예시는 정렬 문제(Sorting Pro..

취준일기

[대기업 계열사] ㅇㅇㅇㅇㅇ 지원 후기 (2023.06~2023.08)

보호되어 있는 글입니다.

War Games

[Prompt Injection]

보호되어 있는 글입니다.

CTF

Hacktheon 2023 (Quals) Write-Up

보호되어 있는 글입니다.

WEB/NETWORK

Types of Communication Networks

0. Background Knowledge What is a Communication Network? 컴퓨터 네트워크는 컴퓨터, 서버 및 다른 하드웨어 장치들이 서로 연결되어 통신과 자원 공유를 가능하게 하는 특정 모임을 뜻한다. 네트워크를 통해 데이터와 리소스를 공유할 수 있게 된다. 컴퓨터 네트워크의 종류로는 크게 LAN(Local Area Networks), WAN(Wide Area Networks), 그리고 MAN(Metropolitan Area Networks) 등등이 있다. 1. Types of Communication Network 1-1. LAN (Local Area Networks) 랜선. 가장 좁은 범위의 네트워크 ex) 집, 피씨방, 사무실 등 비교적 좁은 범위 Traditional ..

etc/Tips

C언어 Inline Assembler 가지고 놀기

나는 특별한 technique를 공부하는게 아닌 이상 그냥 큰 흐름만 이해하고 가는 편이다 그런데 역공학 수업을 들으면서 정말 한줄한줄 레지스터의 변화를 좀 파악해야 할 필요가 있어 Inline Assembler에 대한 내용을 정리한다. // gcc -masm=intel test.c -o test #include int main(){ __asm ( "mov eax, 0x12345678;" "mov ebx, 0x34000000;" ); return 0; } inline assembly를 쓰는 정말정말정말 간단한 코드다. 구글링을 하면 다 __asm {} 의 식으로 쓰던데, 컴파일러를 gcc로 해서 그런가 제대로 안된다. +) 더 찾아보니깐 Visual Studio 컴파일러만 알아보는듯. 암튼 위와 같은 형..

WEB/NETWORK

Fading in the Mobile Environment & Channel Correction Mechanisms

1. Types of Fading slow fading vs. fast fading slow fading: 천천히 줄어듦 fast fading: 전반적으로 줄어들지만, delta값이 매우 큼 fast fading을 어떻게 수신하고 복구할 것인지 Doppler Effect(Spread): 이동에 따라 주파수가 달라질 수 있음 Multipath fading: 여러 주파수가 만나면서 발생하는 fading Flat Fading Frequency Selective Channel 2. Channel Correction Mechanisms 앞서 알아본 간섭에 대해서 보상할 것인가?에 대한 방법들 1) Forward Error Correction 에러 검출 방식 -> 에러 검출까지, 직접 수정까지 가능 단점: redu..