Front-end_dev

순열(재귀), 조합(재귀), 그리고 분할(재귀) 3가지 알고리즘을 합쳐서 구현했다. 처음으로 재귀디자인을 해보았다... 어렵다.편하다. 얻은것 : 특정 상황에서 재귀를 생각해낼수있는 능력이 조금 향상됬다. 결과화면 'abcd'를 2개의조로 나눴을떄의 분할. 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119..

압축알고리즘에는 대표적으로 두가지 방법론이 존재한다. 비손실 압축 : 원래의 정보를 그대로 보존해야 하기 때문에 손실압축보다 압축률의 성능에 있어서 불리하다. 원본데이터를 그대로 유지시킬수 있어야 하기때문에 텍스트데이터에 많이 사용된다. 손실 압축 : 일부 사람이 감지할수 없는 고음역대 주파수, 픽셀값에 의도적으로 제거하여 압축률을 크게 높이는 방식이기때문에 사진파일,동영상파일,오디오파일에 많이 사용된다. 이 문서에서는 비손실압축 알고리즘에 초점을 맞추며 Huffman tree with run-length encoding알고리즘기법을 사용하여 압축프로그램을 만든다. 앞으로 Huffman tree with run-length encoding알고리즘을 HTRE라고 하겠음. HTRE의 기반이되는 기술에는 엔트..

동적해싱의 구체적인 구현방법에 대해서 설명. 동적해싱은 인덱스를 2진수료표현한다. 따라서 들어오는 키값을 hash함수에 넣고 돌린값을 2진수로 convert해야하며 2진수를 토대로 들어갈 인덱스를 결정하며 실제 인덱스에 mapping할때는 다시10진수로 convert하는 작업이 필요하다.단, 그냥 변환하는것이 아니다. 현재 depth를 기준으로 변환해야한다.예를들어, 11이라는 값이 들어왔을때, 11은 2진수로 1011로 표현되며 현재 depth가 2라고 가정했을경우에 가장끝자리서부터 2개만 파싱해야한다.따라서 11로 변환되야하며, depth가 4라면 1011로 변환된다. Operation : transformToBinary(decimal) ::= 10진수를 2진수로 변환한다extract(binary) ..

밑의 그림은 무방향그래프이다. 하지만 멀티리스트에서는 무방향그래프로 구성을하지않고도 서로서로가 누구누구에게 연결되있는지 알고있는 그래프이다.예를들어,6->44->54->35->15->22->32->1 총 7개의 간선으로만 연결했을경우에 1에서는 5와 2가 달려있지않고, 3에는 4와 2가 달려있지않게된다...하지만 멀티리스트를 구현할경우 내가직접적으로 달고있지않고, 상대방이 나를달고있으면 내가 누구랑 연결되있는지 알아내는 알고리즘이다. 멀티리스트를 이용하면 15개의 간선으로도 밑의 그래프를 형성할수있다.

일단 룰이 빡쎄다!!... 레드블랙트리는 BST에서 균형이 깨지는 경우에 균형을 다시잡아주는 트리인데 룰이 빡쎄다... '문제점을 파악하고 어떠한 룰을 만들고 그 룰에대해 위반되는사항들에대해 조치방법을 만들어 놓은 것' 을 '레드블랙트리'라고 생각한다. 우선 먼저 개념을 익히고, 샘플코드를 살펴보고, 직접 코드작성에 들어갔을떄 NIL노드를 무시하고 그냥 NULL을 쓰다가 호되게 털렸다.처음에는 위의 그림이 크게 와닿지 않았다. 하지만 실제 코드작성에들어가서 NIL노드 대신 NULL을 쓰다가 한번 털리고 다시 이그림을 보니 아!!....... 우선 NIL노드가 존재하는 이유 중 가장 큰 이유는 '형제노드'를 찾기 위함이다. 먼저 노드삭제과정에서 삭제된 노드가 블랙노드일경우 fixup(균형을맞춰주는 함수)을..

어떤 임의의 정점에서 출발하여 특정정점까지(정확히 말하자면 1 : N) 의 최단경로를 구하는 다익스트라 알고리즘에 대해서 포스팅 해보겠습니다. 다익스트라 알고리즘을 구현해 본 후에 제가 느낀 이슈 3가지에 대해서 살펴보겠습니다. 1. 그리디 알고리즘2. 우선순위 큐를 써야하는 이유(꼭 써야하는건 아닙니다)3. 메모이제이션 1. 그리디 알고리즘다익스트라 알고리즘의 의사코드를 보면 '그리디하다' 라는것을 느낄 수 있습니다. 그리고 실제 구현할때 그리디하게(매순간 가장짧은경로를 취하는)하지 않으면 최단경로를 구하기가 매우 어렵습니다. 2. 우선순위 큐를 써야하는 이유많은 정보글에서 우선순위큐를 쓰면 좋다고 이야기들 합니다. 구현 중간에 '도대채 왜 써야하지?' 라는 의문이 들어서 우선순위 큐가 아닌 스택으로 ..

프림 알고리즘의 핵심은 '어떻게 하면 비용이작은 간선들을 우선해서 찾아갈 것인가?' 가 입니다.물론 방법은 여러가지가 될 수 있습니다만, '우선순위 큐'를 쓰면 그 고민들을 한방에 날릴 수 있습니다.프림 알고리즘에 정말x5 아주 딱 어울리는 알고리즘 인 것 같습니다.하지만 우선순위 큐로 작은 가중치들의 간선을 먼저 탐색 할 수 있다고해서 알고리즘이 여기서 끝나지는 않습니다. 한가지 더 고려해야 할 점 이 있습니다.싸이클을 감지 할 수 있어야 합니다.(크루스칼 알고리즘은 union+find 알고리즘이 대표적입니다(이전 포스트 참고))싸이클 감지에 대한 이슈를 찾아보려고 검색을 좀 했는데 잘 안나와서 직접 구현 했습니다. 원리는 다음과 같습니다.0. 임의의 정점에서 시작하며, BFS와 비슷한 방식으로 정점을..

위의 3개의 X노드는 서로 다른 노드이다. (메모리가 각각 할당 되어있음) 또한, 2번쨰그림에서 왼편의 X는 노드가 아니라 인접리스트 or 인접행렬의 인덱스이다.예를들면, 인접리스트 or 인접행렬의 A인덱스에서 X를 탐색했을때의 경우는 A인덱스에서 X노드를 탐색하는 것이다. 즉, X인덱스로 가는게 아니다.따라서 A인덱스에서의 탐색은 여기서 종료되는것이다. 한가지더 살펴보면 (BFS기반으로설명) X인덱스에서 A탐색후 G탐색후 H탐색의 경우에, H노드까지만 탐색이 이루어지고, H인덱스로 가는것이 아니다. 이것이 'C'언어가 아닌 다른 언어로 구현 할 때 실수 할 수 있는 부분이다.정리하자면 인접리스트 or 인접행렬의 각 인덱스의 연결리스트의 스코프(범위)는 한 칸 씩으로 제한된다.왜 이런식으로 메모리를 쓸데..

크루스칼 알고리즘 기반의 MST 구현에 있어서 2가지 방법이 존재한다. 1. 선택 2. 삭제 우선 가장 먼저 해야할 것은 가중치를 정렬하는건데, '선택'을 하냐 '삭제'를 하냐에 따라서 정렬 방법이 틀리며, 구현방법 또한 틀리다. [선택을 했을 경우 방법]1. 가중치는 오름차순 정렬한다.2. find + union 알고리즘을 사용한다. (cycle을 감지하기 위해) find + union 알고리즘을 처음 접했을 때, 도대체 이게뭔가? 단순히 배열안에 정수값을 넣는건데, 도대채 어떻게 이걸 트리라고 볼수있는가? 처음에 이론을 접했을 떄는 50%정도만 이해됬다. 그리고 디버깅을 해보고 완전히 이해했다. 만약 이론으로 이해가 안되면 디버깅을 해보자. 그럼 100% 이해 할 수 있다. 가장 먼저 알고 들어가야할..

2차원에서의 경우는, 노멀벡터를 다음과같이 구할수있다.x = yy = -x이렇게 좌표를 바꿔준뒤, 꼭 정규화를 해주어야한다. 그래야 투영축은 무한해지고, 내적으로 얼마나 투영됬는가를 파악할수있기때문이다 2D에서 이 알고리즘의 중요한 이슈는 '원'과의 충돌에있다. 3차원에서 원을 드로잉할떄는 수많은 버텍스로 이루어져있기때문에 그에따라 노멀벡터가 수백개수천개가된다. 하지만 2D(HTML5 canvas)에서는 버텍스버퍼를 기반으로 드로잉하지않기때문에 원에서의 투영축은 하나로만 제한한다. 3차원에서의 적용하기위해선, 위의같은방식으로는 노멀벡터를 구할수없다 (이전포스트를 참고)원리는 똑같고, 축을 구하기위해 노멀벡터의 구하는방식이 틀릴뿐.