1. 버블 정렬 정렬 알고리즘: 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까? 2 1 3 5 위와 같은 배열이 있을 때, 포인터 1은 2를, 포인터 2는 1을 가리킨다. 포인터 1 > 포인터 2 일 때, 두 항목을 교환한다. 포인터들은 한 칸씩 이동하며 두 항목을 비교하고 필요시 두 항목을 교환한다. 이렇게 한 번 배열 전체를 pass through하고 나면, 다시 맨 왼쪽으로 포인터를 옮겨 교환이 일어나지 않을 때까지 반복한다. 2. 버블 정렬의 구현 생략 파이썬 코드 예쁘다 3. 버블 정렬의 효율성 버블 정렬 알고리즘에서 중요한 단계는 비교와 교환이다. 비교: 배열 크기가 N이라고 했을 때, 비교는 N - 1 + N - 2 + N - 3 + … + 1번 실행된다. 교환: ..
알고리즘의 효율성을 결정하는 주 요인은 알고리즘 수행에 필요한 단계 수 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하면…? 빅 오 표기법 1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까? O(N) “빅 오 엔”이라고 발음한다. 보통 “빅”을 생략하고 “오 엔”이라고 부름. 알고리즘에 N단계가 필요하다는 뜻 O(1) 1장에서 배열 읽기에 필요한 단계 수는 “배열의 크기와 상관없이” 딱 한 단계. 이때의 표기를 O(1)이라고 한다. 즉 배열에 원소가 몇 개든 한 단계만 필요할 때. O(1)의 시간 복잡도를 갖는 알고리즘을 가장 빠른 알고리즘 유형으로 분류한다. 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다. 2. 빅 오의 본질 빅 오가 진정으로 의미하는 것:..
1. 정렬된 배열 orderred array: 값이 항상 순서대로 존재하는 배열 삽입할 때는 항상 삽입 전에 값의 올바른 위치를 찾고, 다른 값들을 옮겨 공간을 만들어야 한다. O(N) 삽입에 필요한 단계 수는 새 값이 정렬된 배열 어디에 놓이게 되든 비슷하다 앞 부분에 삽입할 경우, 비교가 줄어들고 이동이 늘어남 뒷 부분에 삽입할 경우, 비교가 늘어나고 이동이 줄어듬 2. 정렬된 배열의 검색 선형 검색: 앞에서부터 검색 이 경우 시간복잡도는 O(N)이다. 그러나 더 나은 방법이 있다… 3. 이진 검색(이진 탐색, Binary Search) 1에서 100 사이의 업다운 게임을 생각해 보자. 50, 25, 13… 찾는 값의 범위는 절반의 절반의 절반으로 줄어든다. 4. 이진 검색 대 선형 검색 작은 크기의..
1. 자료 구조 데이터: 모든 유형의 정보를 망라하는 용어 자료구조: 데이터를 조직하는 방법 2. 배열: 기초 자료 구조 배열: 데이터 원소들의 리스트 2.1 자료구조 연산 읽기: 특정 위치를 찾아보는 것 검색: 자료구조 내에서 특정 값을 찾는 것 삽입: 자료구조에 새로운 값을 추가하는 것 삭제: 자료구조에서 값을 제거하는 것 3. 속도 측정 연산이 얼마나 빠른가를 측정할 때는 시간 관점에서 측정하지 않고 얼마나 많은 단계가 필요한지를 논해야 한다. 연산의 속도 측정 → 시간 복잡도 측정 == 속도, 시간 복잡도, 효율성, 성능 4. 읽기 읽기: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것 컴퓨터의 특징 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다. 컴퓨터는 배열을 할당할 때 어떤 메..
바이트 코드, 바이너리 코드, 기계어, 네이티브 코드, 네이티브 언어에 대해 다룹니다. 바이트 코드 가상머신이 이해할 수 있는 중간 코드이다. 어셈블리어에 가까운 형태를 띠고 있다. 바이트코드는 인터프리터 방식으로 해석된다. 인터프리터 방식 코드를 한 줄씩 내려가며 실행하는 프로그램 방식 정적 컴파일 언어보다 실행속도가 느리다. 대표적인 가상머신, JVM을 사용하는 Java의 컴파일 방식을 잠시 들여다보자. Java는 플랫폼 독립적인 성질이 있다. 보통 프로그램들은 OS에 얹혀서 돌아가게 되는데, 그렇기 때문에 OS에서 규정하는 실행 방식을 따라야 한다. OS에서 규정하는 실행 방식? 예를 들어서, 윈도우 플랫폼에서 컴파일 과정과 어셈블링 과정을 거쳐 실행 파일을 만든다고 생각해 보자. windows에서..
