컴퓨터 지식64
[정보이론] Kraft inequality(크래프트 부등식) 과 데이터 비트 표현
들어가기 앞서 컴퓨터는 특정 데이터를 비트로 압축시켜 표현합니다. 이 예시로는 허프만 코드가 있는데 아래 포스팅을 참고해 주시면 좋을 것 같습니다. https://programming119.tistory.com/75 [알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm 문자열의 코드화 우리가 인터넷 상에서 쓰는 한글, abcd 알파벳. 컴퓨터는 우리처럼 글자 자체로 보지 않고, 결국 2진수 0과 1의 모음으로 이해를 한다! a는 01 로 약속, b는 10 으로 약속하면 ab라는 문자는 컴퓨.. programming119.tistory.com Prefix code Prefix code 란 특정 비트표현이 다른 비트표현과 겹쳐지지 않는 코드 입니다. 예를..
[프로토콜] ARP spoofing 이란? / ARP poisoning /
ARP Address Resolution Protocol 의 약자로서, 말그대로 주소를 결정해줍니다. 어떤 주소를 결정해주냐? 같은 IP 를 쓰는 여러 장치들이 있겠죠? 그 중에 통신의 대상이 될 장치의 MAC 주소가 필요합니다. IP 주소를 받아 MAC주소(장치의 직접적인주소)를 결정해줍니다. ARP 통신방법 ARP는 기본적으로 MAC 주소를 얻기 위해 IP를 BroadCast 방식으로 Target으로 보냅니다. (특정 상황에 따라 Unicast로 보내는 경우도 있습니다.) 쉽게 말하자면, 네트워크 내에 모든 이들에게 요청을 하는 것이죠. (하나에게만 보내는것은 unicast) 그 중에 필요한 MAC주소를 가지고 있는 특정 장치의 Response를 이용해 MAC 주소를 얻어냅니다. 그럼, 이때 받았던 ..
[알고리즘] Approximation Algorithm 이란 / NP 문제 알고리즘
Approximation Algorithm 이란 세상에는 무수한 문제들이 있고, 그 만큼 어려운 문제도 무수히 많다. (ex. NP문제) 알고리즘적으로 보통 어려운 문제는 polynomial 시간 안에 풀 수 없는 문제들을 말한다. 이들을 프로그래밍 적으로 사용하기에는 과부하가 너무 크다. 따라서, 완벽한 답을 구하는 것에는 살짝 내려놓고, 조금은 틀릴 수 있는 가능성이 있더라 하더라도 근접한 답을 구해낼 수 있는 빠른 알고리즘(polynomial 시간안에 해결이 가능한)을 택하는 것이다. 예를들자면, 우리가 인터넷으로 성능대비 가격이 좋은 컴퓨터를 사려고한다. 가장 좋은 방법은 온라인 상에 있는 모든 웹 사이트에 판매중인 컴퓨터 제품들을 하나하나 다 비교하고, 최고 가성비의 제품을 사는 것이다. 하지만..
[컴퓨터구조] Locality 란 / Locality 종류
Locality 란Locality를 한국어로 직역하면 '지역성' 이라는 뜻이다. 프로그램적으로 생각해보자. 우리의 프로그램은 항상 메모리의 특정 주소를 찾아가서 데이터를 읽어오고 특정 주소로 찾아가서 데이터를 쓰는 행위들이 기본이다. 여기서 '특정주소' 가 어떻게 될지, 실행해보기 전의 우리는 아직 잘 모른다. 하지만! 이 Loaclity 라는 특성을 이용하면 이를 예상하고 접근 시간을 줄일 수 있다는 것이다! (또한, 이 접근 시간은 프로세서의 성능에 직접적인 연관이 있다.) Temporal Locality 와 Spartial LocalityTemporal Loaclity : 최근에 접근했던 주소값을 다시 접근하는 경향 - 한번 사용한 주소의 메모리 영역은 자주 접하게 된다. - 예시) Loop문 안의..
[DB] 데이터베이스 Evaluation / PipeLining 과 Materialization
쿼리 실행의 단계 1. Parsing and Translation 2. Optimization 3. Evaluation Evaluation - 엔진이 1,2 단계를 거친 쿼리를 보고 어떻게 실행할건지 실행 계획을 세우고 행하는 것. 대표적으로 Pipelining 방식과 Materialization 방식이 있다. Pipelining 한 연산의 실행이 끝나서 결과 값을 내기 전에, 다른 연산도 실행하는 방법 ( 동시에 계산 이라 생각해도 됨) - Materialization 보다 저렴하다. (따로 릴레이션을 메모리에 저장할 필요가 없음) - 정렬이나 해쉬 조인에는 적용 불가. - demand driven 과 producer driven 으로 나뉜다. demand driven(lazy driven) : 현재 ..
[알고리즘] MST / Disjoint set / 크루스칼 알고리즘
MST 알고리즘크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다. MST 와 그리디 알고리즘의 정보는 : https://programming119.tistory.com/78 크루스칼 알고리즘 나무와 숲 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다. 숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다. 예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다. 나무 : 노드 숲 : 노..