오늘도 삽질

노트정리/알고리즘

[알고리즘] 기하 알고리즘

기하 알고리즘에 앞서기하학은 기본 요소로 점 , 선 , 다각형, 다면체가 있습니다. 기하문제를 풀기 위해선 기본 요소인 점 , 선, 다각형, 다면체 등을 어떻게표현할 것인가를 결정해야 하는데 간단판 표현법 으로 좌표를 사용합니다. 기하학의 기본요소- 점 : 1차원 물체- 선, 다각형 : 2차원 물체- 다면체 : 3차원 물체 기하학의 문제- 간단한 문제 : 선분교차, 직각 삼각형, 내접 다각형- 복잡한 문제 : 순환 외판원, CAD, 최소 신장 나무 두 선분의 교차 검사두 선분이 주어졌을 떄, 이 둘이 서로 교차하는지 아닌지를 검사하는 것은 가장 기본적인 기하 알고리즘 중에 하나입니다. 여기서 두 선분이 교차한다는 것은 그 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 기본적인 용어에는 - 선분..

Web

웹 표준 & 웹 접근성에 대해

웹 프론트엔드 면접을 보다보면 웹 표준 , 웹 접근성에 대해서 얘기가 많이 나온다. 앞으로도 지켜야 할 사항이고 정리할겸 다시적어본다. 웹 표준웹 표준 W3C 의 토론을 통해 나온 권고안을 사용하는 것.. 표준화 기구에서 정의 해준 명세에 맞게 마크업을 하는 것이라 보면 된다.웹 표준이 없던 1990년대 말 ~ 2000년대 초반에는 웹개발자 두 개의 사이트를 만들어야 했다고 한다. 인터넷 익스플로러용과 넷스케이프용의 두 개. 각종 핵과 브라우져 판별 코드를 삽입해야 해 3배의 노동이 들었다.https://validator.kldp.org/ HTML 마크업 문법 검사를 할수 있다. 필자의 포트폴리오에도 맨 처음에 작업했던 사이트들을 전부 검사해서 웹에 W3C 뱃지같은걸 달 수 있게 주었는데 통과하면 뱃지를..

노트정리/알고리즘

[알고리즘] 스트링 매칭

스트링 매칭주어진 텍스트에서 주어진 패턴이 어디에 나타나는지를 알아내는 문제를 스트링 매칭 문제라고 한다.어떤 문서에서 특정 단어를 찾을 때 이것이 스트링 매칭이 되고 여기서 문서를 텍스트라 하고 찾아낼 특정 단어를 패턴 이라고 합니다.즉 텍스트에서 패턴과 일치하는 모든 부분을 찾아내는 문제이죠. 직선적 알고리즘텍스트의 매 위치에서 패턴 일치가 발생하는지를 조사하는 방법입니다. T에서 P가 나타나는 부분을 찾는 직선적인 방법이 하나하나 차례대로 비교해 나가는 것 입니다. 즉T[0]과 P[0]으로부터 하나씩비교해 나가는데 이를 불일치가 발생할 때까지 반복합니다. 위예의 경우 처음부터 불일치가 발생하는데 다시 오른쪽으로한 번 이동시켜서 패턴의 처음부터 비교를 다시 반복합니다. 직선적 스트링 매칭 방법의 시간..

노트정리/알고리즘

균형나무와 외부 탐색법

2-3-4 트리는 모든 중간 노드들의 자식수가 2,3,4이면서 모든 단말 노드가 같은 레벨에 있는 나무입니다.2-3-4 나무 특징- 2-3 나무를 확장 하여 다양한 나무를 만들수 있다.- 데이터베이스에서 사용하는 색인구조의 형태- 한 노드에 있을 수 있는 값의 수가 많다면 나무의 높이 감소.- 나무의 높이가 감소하면 할수록 검색 향상됨.2-3-4 나무의 삽입- 단말 노드에서 이루어집니다. 삽입할 노드를 찾는동안 4-노드를 만나면 분할합니다.2-3-4 나무의 삭제- 먼저 삭제할 값을 포함한 노드를 찾아야 한다.- 그 노드가 단말 노드가 아니면 그값과 그것의 중위 순위상에서 바로 앞 값을 교환함. (이 값은 항상 단말 노드에 있음) n개의 노드로 구성된 2-3-4 나무가 있을때 나무의 높이 = 최대 logn..