The note of Legendre

1.2-1 응용프로그램: 웹 브라우저, HTML을 읽어와서 태그에 맞게 해석하여 화면에 출력하는 알고리즘이 필요하다. HTML 태그를 읽어와서, 정규식 등을 이용해 파싱하고 이 엘리먼트에 대응하는 출력 형식을 판단한 후 화면에 나타내는 기능.

1.2-2 8n² 과 64nlgn 여기서 lgn=log₂n이다. n이 무한히 커질 때, 8n²이 64nlgn보다 커질 것이고, 두 값이 같은 점이 8n²이 64nlgn을 앞지르는 지점이다. n 자리에 2의 거듭제곱 꼴을 넣고 그 수는 x라고 할 때 8n은 2^3+2x 64nlgn은 x*2^6+x이다.  x에 8을 대입할 경우 2의 지수가 19로 같다. 따라서 n은 2⁸ 즉 256보다 클 때 8n²이 64lgn보다 커진다.

1.2-3 100n²이 2ⁿ보다 클 경우 n의 최소치를 구하려면 대입해서 범위를 좁힌다. 14를 대입할 경우 100n²는 19600 2ⁿ는 16384가 나와서 앞 쪽이 크지만, 15를 대입하면 100n²는 22500 2ⁿ는 32678이 나와서 큰 정도가 뒤집어진다. 계산 횟수는 정수이므로, 최소값 n은 14이다.

이 글은 스프링노트에서 작성되었습니다.

1.1-1 정렬 문제가 발생하는 현실 세계의 사례에는 사전 표제어 들이 멋대로 흩어진 데이터에서 국어같으면 ㄱ, ㄴ, ㄷ..  순으로 정렬해야 하고, ㄱ 내부에서는 ㅏ, ㅑ, ㅓ.. 순으로 정렬해야 하는 문제가 발생한다. 영어사전이라면 맨 처음 글자를 a, b, c .. 순으로 정렬하고 바로 다음 글자도 앞과 같은 순으로 정렬해야 하는 문제가 발생한다.

1.1-2 속도 외에 효율성을 평가할 만한 다른 척도에는 소모하는 메모리 공간, 알고리즘이 요구하는 통신 대역, 알고리즘이 요구하는 하드웨어 자원 등이다.

1.1-3 자료구조
연결리스트  장점은 자료의 추가와 삭제가 빠르다. 단점은 특정 데이터를 찾으려고 할 때 순차적으로 찾아야 하므로, 느리다.

1.1-4 최단 경로 문제와 순회 판매원 문제는 거리를 계산하고, 짧은 경로를 목적으로 한다는 점이 비슷하다. 다른 점은 최단 경로 문제는 출발지에서 목적지로 가는 경우이지만, 순회 판매원 문제는 물건을 여러 지점에서 판매하고 다시 원래 지점으로 돌아온다는 점이 있다. 최단 경로 문제는 효율적 해결 방법이 있으나, 순회 판매원 문제는 어느 정도 좋은(최적의 알고리즘은 아닌) 해결 방법이 있다.

1.1-5 최적의 해만이 의미 있는 문제: 전자 상거래에서 보호가 필요한 정보를 안전하게 관리하는 알고리즘
근접한 해를 구해도 충분한 문제: 인터넷에서 특정 정보가 있는 페이지를 검색하는 알고리즘

이 글은 스프링노트에서 작성되었습니다.