오식랜드

logn < n < nlogn < n^2 < n^3 < 2^n < n! 분석 입력 크기에 따라, 단위 연산이 몇 번 수행되는지 결정하는 절차 사용하는 자료구조에 좌우되는 경우도 있다. 표현 척도 단위 연산 : 비교 / 지정 입력 크기 : 배열의 크기 / 리스트의 길이 / 행과 열의 크기 / 트리의 노트와 연결선의 수 분석 방법 최선의 경우 (Best-case) : 단위 연산 수행 횟수가 최소인 경우 잘 안 쓴다. ex) 순차검색의 x가 제일 처음에 위치하면 T=1 최악의 경우 (Worst-case) 단위 연산 수행 횟수가 최대인 경우 대부분 최악의 경우로 구한다. ex) 순차검색의 x가 제일 마지막에 위치하면 T=n 평균의 경우(Average-case) (최선+최악)/2 로 계산 최악의 경우보다 계산이 ..

피보나찌 수 구하기 피보니찌 재귀 함수의 한계를 설명하기 좋음 n(n ≥ 2)의 피보나찌 = (n-2) + (n-1) 1. 재귀적 방법으로 피보나찌 수 구하기 n-1과 n-2의 값이 1 또는 0이 될 때 까지 fib 함수가 재귀적으로 호출된다. int fib(int n) { if (n 2 x T(n - 2) → 왜냐하면 T(n - 1) > T(n - 2) > 2^2 x T(n - 4) > 2^3 x T(n - 6) … 2n/2 x T(n-n) = 2n/2xT(0) = 2^n/2 결론 재귀적 알고리즘으로 구성한 재귀 트리의 노드 수를 T(n)이라 하면, n2인 모든 n에 대하여 T(n)> 2n/2 이다. ⇒ 매우 느림 이유: 같은 피보나찌 수를 중복 계산 2. 반복적 방법으로 피보나찌 수 구하기 int ..

예제 : 임의의 수 x 찾기 문제: 크기가 n인 배열 S에 x가 있는가? 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x의 위치, 만약 없으면 0. 알고리즘(자연어): x와 같은 원소를 찾을 때까지 S에 있는 모든 원소를 차례로 검사한다. 만일 x 와 같은 원소를 찾으면 S 에서의 그 위치를, S 를 모두 검사하고도 찾지 못하면 0을 내준다 1. 순차 탐색 void seqsearch(int n, // 입력(1) const keytype S[], // (2) keytype x, // (3) index& location) { // 출력 location = 1; while (location n) location = 0; } while-루프: 아직 검사할 항목이 있고, ..

알고리즘 문제에 대한 해답을 찾기 위한 체계적인 “문제 해결 절차” 항상 “효율적인 알고리즘”을 고안하는게 중요 최초의 알고리즘 : 유클리드의 최대공약수 알고리즘의 특성 정확성 : 주어진 입력에 대한 올바른 해 도출 수행성 : 각 단계는 컴퓨터에서 수행 가능해야 한다. 유한성 : 무한루프X, 단계를 마친 후 종료되어야 한다. 효율성 : 효율적일수록 가치가 높아진다 효율성의 척도 : 시간 복잡도 / 공간 복잡도 정확한 알고리즘 : 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘 정확하지 않은 알고리즘 : 어떤 입력에 대하여 멈추지 않거나 틀린 답을 출력하면서 멈추는 알고리즘 문제의 표기 방법 문제 파라미터 : 문제에서 특정 값이 주어지지 않은 변수 문제의 사례 (입력) : 파라미터에 특정 값 지정 ..

통신의 발전 모스부호 - 전화 - 무전기 통신 방향 단방향 : 모스부호, 라디오, TV 등 양방향 : 전화 반양방향 : 무전기 프로토콜 : 다른 기기와의 통신을 위한 약속, 통신규약 네트워크 연결 LAN : 수미터 ~ 약 1km 연결되는 근거리 네트워크 IP : 서로다른 LAN을 넘어다니며 목적지까지 데이터를 전송하는 프로토콜 TCP : LAN으로 보낸 데이터가 잘 도착하는지 감시 ⇒ 전송 제어 프로토콜 WAN : 국가 전체, 국가간의 연결되는 네트워크 웹 시스템 문자 기반 사용자 인터페이스 (CUI)에서 발전 웹 브라우저가 보급되며 현재는 GUI가 발전 무선 통신 시스템 1G - 2G - 3G - 4G = 5G → 단파일수록 장애물에 예민 분산 시스템 강결합 시스템 네트워크로 연결된 컴퓨터들이 하나의 ..

파일 시스템 ( = 윈도우 탐색기) 파일 관리자가 저장장치 전체 관리 파일 테이블을 사용하여 관리 (만든 시간, 수정 시간, 용량, 위치 등… 내용은 없음!!) 파일 접근 권한 등을 관리 (파일 디스크럽터 관리) 파일 테이블 블록 : 저장장치에서 사용하는 가장 작은 단위 어떤 파일이 어떤 블록에 있는지 기록 파일 이름과 확장자 과거에는 이름과 확장자의 글자수 제한이 있었음 → 현재는 완화 (최대 길이는 255자) 파일 이름에 마침표 여러번 사용 가능 → 마지막 마침표 뒤를 확장자로 인식 윈도우보다 유닉스 규칙이 더 빡셈 (특수문자는 아예 안됨) 파일 작업 파일 내용 변경 편집기를 통해 변경 작업명에 괄호가 있음 (함수인듯) 파일 자체 변경 윈도우 탐색기에서 하는 일 (생성, 삭제, 이동, 복사, 검색 등..