컴퓨터 지식/알고리즘14
[알고리즘] 인덱스 트리란? (IndexedTree ) / 코딩테스트 인덱스 트리 /Java 구현/
⭐ 인덱스트리란? ⭐ 리프 노드에 내가 쓸 값들을 저장해놓고, 부모들에는 해당 노드의 합들로 된 노드들을 만들어 구현해둔 트리입니다. 쉽게 말하자면 제일 밑 노드들은 값들, 그 위에 부모 노드들에는 값들의 정보(보통 노드의 부분합)를 모아둔 트리! 예시를 보시는게 좋을 것입니다. 언제 쓰이는가? 👀 인덱스 트리는 언제 쓰일까요? 1. 부분합을 계속해서 구해야할 때, 2. 특정 인덱스의 변경 또한 계속 일어날 수 있을 때 이 두 조건이 만족할 때 주로 쓰입니다! * left - right = N 이라 가정 보통 구간 left ~ right 부분합을 구한다는 것은 left 부터 right 까지를 전부 더해야 하기에 O(N) 의 시간복잡도를 가집니다. 그래서 우리는 누적합 배열을 쓰죠! 누적합 배열에서 누적합..
[알고리즘🔑] Iterative deepening Search와 Iterative lengthening Search
들어가기 앞서 BFS/DFS 에 대해 숙지하셔야 합니다. Blind Search 의 기본 원리를 알고 계셔야 합니다. Iterative Deepening Search란 iterative : 반복적인 즉, 한국 말로 '번역하자면 반복적인 깊이 탐색' 정도가 되겠네요. DFS 와, BFS 의 단점들을 보완하기 위해 고안된 search 방법입니다! 그러면 어떤 점들을 보완시켰는지 알기 전에, 먼저 DFS와 BFS의 특징들을 간단하게 알아볼까요? DFS의 특징 장점 : BFS 에 비해 메모리 소요가 적다. (BFS는 frontier 큐에 하위 노드들 전부 넣어야함) 목표해가 깊은 단계에 있을 경우, BFS 보다 훨씬 빠르다. 단점 : DFS 는 탐색트리에서 깊이가 아주 큰, 하지만 해가 해당 깊이에 없는 경우를..
[정보이론] 허프만 코드의 optimal 판단 / Huffman code optimal
들어가기 앞서 https://programming119.tistory.com/75 [알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm 문자열의 코드화 우리가 인터넷 상에서 쓰는 한글, abcd 알파벳. 컴퓨터는 우리처럼 글자 자체로 보지 않고, 결국 2진수 0과 1의 모음으로 이해를 한다! a는 01 로 약속, b는 10 으로 약속하면 ab라는 � programming119.tistory.com 허프만 코드에 대해 모르신다면, 참고해주세요! 허프만 코드의 Optimal 세 조건 코드화된 distribution이 있을 때, 다음과 같은 세 조건을 모두 만족시키면 Optimal 입니다. 1. 코드길이는 확률값과 반비례 한다. (코드 길이가 길수록, 확률..
[정보이론] 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 란 특정 비트표현이 다른 비트표현과 겹쳐지지 않는 코드 입니다. 예를..
[알고리즘] Approximation Algorithm 이란 / NP 문제 알고리즘
Approximation Algorithm 이란 세상에는 무수한 문제들이 있고, 그 만큼 어려운 문제도 무수히 많다. (ex. NP문제) 알고리즘적으로 보통 어려운 문제는 polynomial 시간 안에 풀 수 없는 문제들을 말한다. 이들을 프로그래밍 적으로 사용하기에는 과부하가 너무 크다. 따라서, 완벽한 답을 구하는 것에는 살짝 내려놓고, 조금은 틀릴 수 있는 가능성이 있더라 하더라도 근접한 답을 구해낼 수 있는 빠른 알고리즘(polynomial 시간안에 해결이 가능한)을 택하는 것이다. 예를들자면, 우리가 인터넷으로 성능대비 가격이 좋은 컴퓨터를 사려고한다. 가장 좋은 방법은 온라인 상에 있는 모든 웹 사이트에 판매중인 컴퓨터 제품들을 하나하나 다 비교하고, 최고 가성비의 제품을 사는 것이다. 하지만..
[알고리즘] MST / Disjoint set / 크루스칼 알고리즘
MST 알고리즘크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다. MST 와 그리디 알고리즘의 정보는 : https://programming119.tistory.com/78 크루스칼 알고리즘 나무와 숲 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다. 숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다. 예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다. 나무 : 노드 숲 : 노..