책 를 정리했습니다. 배열의 대안 : 연관배열 = 사전 = 해시표 둘의 공통점 하나의 집합에 데이터를 보관한다 둘의 차이점 해시표는 즉각적 검색 (=상수시간 검색) 상수시간 검색의 공식이 해시함수 해시함수는 특정 더미에 어떤 항목을 포함 시켜놓고, 그 항목을 빨리 찾을 수 있게 한다. 이런 식으로 이미 알고있는 사실(기억력)을 이용한 해결방법은 반복 작업에 유용하다. 로그시간 선형시간에서 로그시간으로 바꾸는 이점은 아주 많다. 로그시간은 물건이 정렬되어있을 때 유용하다. 로그시간의 예시 : 사전, 전화번호부, index ⇒ 정보폐기 방법 → 이진검색! 로그는 천천히 증가한다 = 방법이 항목의 수에 크게 영향을 받지 않는다는 뜻 역추적 미노스 아리아드네의 실 이야기 = 미로 탐색할 때, 실패 시 갈림길로 ..
알고리즘이란? 알고리즘이란 뭔가를 수행하는 방식의 집합이다. 알고리즘은 문제나 과제를 해결하기 위한 절차다. 문제 해결은 예를 들자면 사용설명서, 요리 레시피, 악보 같은 것이다. 대부분의 경우 문제 해결은 그저 우리가 가지고 있는 직관이나 생각들을 기계나 다른 사람들이 이해할 수 있는 방식으로 번역하는 것에 불과하다. 알고리즘을 기계가 이해할 수 있도록 프로그래밍 언어로 작성한 것이 프로그램이다. 예를 들어 로봇청소기는 사람이 미리 만들어 둔 알고리즘에 따라 움직이는 것이다. 방 청소라는 일을 하나씩 분해하여 순서대로 실행하도록 절차를 지시한 것이다. 절차가 알고리즘이기 위한 조건 정확한 결과를 얻을 수 있어야 한다. 문제 해결 = 올바른 답 출력 or 원하는 결과를 얻을 수 있다. 얻어진 결과가 틀리..
정보처리기사 필기 준비하며 정리한 내용입니다. 알고리즘 문제를 해결하기 위한 절차나 방법 자연어, 순서도, 의사 코드, 프로그래밍 언어 등을 이용하여 표현 조건 입력 출력 명확성 유한성 효과성 설계 기법 분할과 정복 더는 쪼갤 수 없을 정도로 작은 문제로 나누기 동적 계획법 더 작은 문제로 나누기 탐욕법 가장 좋은 해결책을 그때그때 찾기 백트래킹 더이상 해가 없으면 왔던 길 되돌아가기 성능 분석 알고리즘 효율성 높이기 위해 자원(시간과 공간)을 어떻게 소모하는가에 따른 분석 시간 복잡도 알고리즘의 수행시간 분석한 결과 빅오 표기법의 유형 O(1) : 오직 한단계만. 가장 빠르다 스택, Hash 함수 O(log n) 이진탐색 O(n) 배열 순차 탐색 O(n log n) 퀵, 힙, 병합 정렬 O(n^2) 버..
