[일본 기본정보기술자 자격증] 알고리즘과 순서도 ①

여기서 순서도란 流れ図를 번역한 것이다.

 

● 순서도 문제 푸는 법

    ① 초기값을 확인 (0부터 시작하는 지, 1부터 시작하는 지)

    ② 루프의 조건판단 

    ③ 제어 변수의 갱신

 

 

 

● 탐색 알고리즘

    ① 선형탐색 (線形探索)

    ② 이분탐색 (2分探索)

        - 중앙에서부터 단락을 잘라서(区切って) 값을 좁혀나가는 방법.

        - 중간의 요소와 값을 비교하는 과정을 반복함으로써 좁혀나가, 목적 값에 도달하는 방법

        - 전제조건 : 배열의 요소가 오름차순(昇順=しょうじゅん)/내림차순(降順=こうじゅん)으로 정렬되어 있어야 한다.

    ③ 해쉬탐색 (ハッシュ法探索)

        - 키 값을 해시함수(関数＝関数)를 사용해 변환하고 데이터를 저장하는 위치를 결정한다.

        - 한번에 위치를 찾을 수 있지만, 효율성이 안좋다.

        - 서로 다른 키 값으로부터 같은 해쉬값이 나올 가능성이 있기 때문에, 충돌(衝突＝しょうとつ、コリジョン)이 일어날 가능성이 있다.

        - 충돌이 일어났을 때, 저장된 데이터를 홈(ホーム), 충돌을 일으킨 데이터를 동의어(シノニム)라고 한다.

          シノニム가 뭐야?.. 하고 찾아봤는데 sysnonym이었음....

        - 충돌이 일어났을 때 오픈어드레스법(オープンアドレス法)과 같은 방법을 사용하여 증분(増分＝ぞうぶん)하여 충돌한 주소를 찾아낸다. 

        - 해쉬탐색에서 충돌이 일어날수록, 탐색 시간이 늘어난다.

 

2분탐색&해쉬탐색은 알고리즘에 더해서 전제안건에 대해 물어보는 경우가 있기 때문에 이해해두자.