1. 알고리즘의 효율성
프로그래머들은 알고리즘을 작성하기 위한 3가지 요소를 경험을 통해 알게 되었고
프로그램을 작성시 고려해야한다.
> 그 세 가지 효율성 : 시간의 효율성, 공간의 효율성, 코드의 효율성
ⓐ 시간의 효율성
- 모든 알고리즘에서 가장 중요하게 생각해야 하는 요소
- 컴퓨터에서 실행하는 프로그램이 주어진 조건에 맞춰서 적은 시간을 사용하는 것이 좋음
무한대의 시간을 사용할 수 없음. 가능하면 적은 시간을 사용하는 것이 좋음.
ex) 게임소프트웨어 : 동작에 대한 반응속도가 빨라야 한다.
- 주어진 조건에서 문제를 해결하기 위해 가능한 한 빠른 실행 속도를 가진 효율적인 해결책을 찾는 것
문제 : Data라는 이름의 배열안에 1부터 1000까지의 모든 정수들이 차례대로 저장되어있다.
배열 안의 정수에서 사용자가 입력한 값을 찾는 알고리즘을 작성하라.
① 순차적 검색 알고리즘 (Sequential Search)
- 배열의 첫번째 요소부터 1000번째 요소까지 순차적으로 검색하는 방법
- 관찰
> 사용자가 입력한 값이 첫번째에 있으면 한번만에 검색 가능
> 사용자가 입력한 값이 마지막에 있으면 1000만에 검색
> 평균적으로 500만에 확인 가능
- 시간의 효율을 고려하지 않은 알고리즘
② 이진검색(binary search)알고리즘
- 사용자가 입력한 값을 배열의 중간 값과 비교
- 입력 값이 중간 값보다 크면 배열의 뒷부분, 중간값보다 작으면 배열의 앞 부분을 다시 실행
- 입력 값과 중간 값이 같으면 종료
- 관찰
> 입력 값이 배열 내에 존재하지 않는 경우에도 9번 검색으로 검색 및 판단 가능
- 시간적으로 효율적인 프로그램
ⓑ 공간의 효율성
- 알고리즘에 따라 작성된 프로그램이 컴퓨터의 메모리를 얼마나 사용하느냐의 문제
- 대부분의 운영체제(OS)는 하나의 메모리를 여러개의 프로그램이 공유해서 사용(멀티케스팅)
> 메모리를 효율적으로 관리하고 사용하는 것이 더욱 중요(메모리의 최적화/최소화)
ⓒ 코드의 효율성
- 개발자 입장과 컴퓨터 입장에서 보는 관점이 다르다
- 개발자의 입장
> 개발자가 시간이 지나서 코드를 수정해야 하는 경우 쉽게 수정할 수 있어야 한다. > 가독성↑
> 다른 개발자가 자신의 코드를 수정할 수도 있기 때문에 쉽게 이해할수 있게 만들어야 한다.
> 예제 : b = ++(a--*++c)/++d; // 변수명, 이해도에 의해 가독성이 낮아짐
> 프로그램의 소스코드
· 다른 사람이 보고 이해하기 쉽도록 작성
· 이해가 쉽지 않은 코드는 주석을 이용하여 설명
· 변수나 함수를 작성할 때, 의미가 모호한 이름을 사용하지 말고, 다른 사람이 볼때 쉽게 이해할
수 있는 이름으로 작성
- (컴퓨터의 입장) 컴파일러와 하드웨어에 좀더 최적화된 코드
> 컴파일러의 발전으로 컴파일시 기계어로 만들어줌
> 따라서 개발자 입장에서 프로그램 작성하는 것이 맞음.
2. 알고리즘의 평가
- 하나의 문제는 다양한 알고리즘으로 해결 가능
> 가장 접합한 알고리즘을 찾는 것이 중요
- 좋은 알고리즘의 조건
① 신뢰성이 높은 것 : 정확도가 높고, 올바른 결과를 만들어 냄
② 처리 효율이 좋을 것 : 계산 횟수가 적고 처리속도가 빨라야함.
③ 일반 적인 것 : 특정 상황에서만 사용되는 알고리즘이 아니라 일반적인 상황에 적용이 가능해야한다.
④ 확장성이 있는 것 : 누가 보아도 알기 쉬워야 함. 이해하기 어려운 알고리즘은 유지 보수에 방해
⑤ 알아 보기 쉬울 것 : 누가 보아도 알기 쉬워야 함. 이해하기 어려운 알고리즘은 유지보수에 방해
⑥ 이식성이 높은 것 : 유용한 프로그램은 타 기종에서 사용할 가능성이 높음
3. 알고리즘과 데이터 구조
- 컴퓨터에서 대량의 데이터를 다룰 경우가 많음
> 데이터를 처리 할 때 어떤 데이터 구조를 사용하느냐에 따라 문제 해결을 위한 알고리즘이 달라짐
- "Algorithm + Data Structure = Program"
> 좋은 데이터 구조를 선택하는 것이 프로그램을 만드는 기초
- 자료 구조를 알고리즘 보다 먼저 공부하는 것이 좋음.
프로그래머들은 알고리즘을 작성하기 위한 3가지 요소를 경험을 통해 알게 되었고
프로그램을 작성시 고려해야한다.
> 그 세 가지 효율성 : 시간의 효율성, 공간의 효율성, 코드의 효율성
ⓐ 시간의 효율성
- 모든 알고리즘에서 가장 중요하게 생각해야 하는 요소
- 컴퓨터에서 실행하는 프로그램이 주어진 조건에 맞춰서 적은 시간을 사용하는 것이 좋음
무한대의 시간을 사용할 수 없음. 가능하면 적은 시간을 사용하는 것이 좋음.
ex) 게임소프트웨어 : 동작에 대한 반응속도가 빨라야 한다.
- 주어진 조건에서 문제를 해결하기 위해 가능한 한 빠른 실행 속도를 가진 효율적인 해결책을 찾는 것
문제 : Data라는 이름의 배열안에 1부터 1000까지의 모든 정수들이 차례대로 저장되어있다.
배열 안의 정수에서 사용자가 입력한 값을 찾는 알고리즘을 작성하라.
① 순차적 검색 알고리즘 (Sequential Search)
- 배열의 첫번째 요소부터 1000번째 요소까지 순차적으로 검색하는 방법
- 관찰
> 사용자가 입력한 값이 첫번째에 있으면 한번만에 검색 가능
> 사용자가 입력한 값이 마지막에 있으면 1000만에 검색
> 평균적으로 500만에 확인 가능
- 시간의 효율을 고려하지 않은 알고리즘
② 이진검색(binary search)알고리즘
- 사용자가 입력한 값을 배열의 중간 값과 비교
- 입력 값이 중간 값보다 크면 배열의 뒷부분, 중간값보다 작으면 배열의 앞 부분을 다시 실행
- 입력 값과 중간 값이 같으면 종료
- 관찰
> 입력 값이 배열 내에 존재하지 않는 경우에도 9번 검색으로 검색 및 판단 가능
- 시간적으로 효율적인 프로그램
ⓑ 공간의 효율성
- 알고리즘에 따라 작성된 프로그램이 컴퓨터의 메모리를 얼마나 사용하느냐의 문제
- 대부분의 운영체제(OS)는 하나의 메모리를 여러개의 프로그램이 공유해서 사용(멀티케스팅)
> 메모리를 효율적으로 관리하고 사용하는 것이 더욱 중요(메모리의 최적화/최소화)
ⓒ 코드의 효율성
- 개발자 입장과 컴퓨터 입장에서 보는 관점이 다르다
- 개발자의 입장
> 개발자가 시간이 지나서 코드를 수정해야 하는 경우 쉽게 수정할 수 있어야 한다. > 가독성↑
> 다른 개발자가 자신의 코드를 수정할 수도 있기 때문에 쉽게 이해할수 있게 만들어야 한다.
> 예제 : b = ++(a--*++c)/++d; // 변수명, 이해도에 의해 가독성이 낮아짐
> 프로그램의 소스코드
· 다른 사람이 보고 이해하기 쉽도록 작성
· 이해가 쉽지 않은 코드는 주석을 이용하여 설명
· 변수나 함수를 작성할 때, 의미가 모호한 이름을 사용하지 말고, 다른 사람이 볼때 쉽게 이해할
수 있는 이름으로 작성
- (컴퓨터의 입장) 컴파일러와 하드웨어에 좀더 최적화된 코드
> 컴파일러의 발전으로 컴파일시 기계어로 만들어줌
> 따라서 개발자 입장에서 프로그램 작성하는 것이 맞음.
2. 알고리즘의 평가
- 하나의 문제는 다양한 알고리즘으로 해결 가능
> 가장 접합한 알고리즘을 찾는 것이 중요
- 좋은 알고리즘의 조건
① 신뢰성이 높은 것 : 정확도가 높고, 올바른 결과를 만들어 냄
② 처리 효율이 좋을 것 : 계산 횟수가 적고 처리속도가 빨라야함.
③ 일반 적인 것 : 특정 상황에서만 사용되는 알고리즘이 아니라 일반적인 상황에 적용이 가능해야한다.
④ 확장성이 있는 것 : 누가 보아도 알기 쉬워야 함. 이해하기 어려운 알고리즘은 유지 보수에 방해
⑤ 알아 보기 쉬울 것 : 누가 보아도 알기 쉬워야 함. 이해하기 어려운 알고리즘은 유지보수에 방해
⑥ 이식성이 높은 것 : 유용한 프로그램은 타 기종에서 사용할 가능성이 높음
3. 알고리즘과 데이터 구조
- 컴퓨터에서 대량의 데이터를 다룰 경우가 많음
> 데이터를 처리 할 때 어떤 데이터 구조를 사용하느냐에 따라 문제 해결을 위한 알고리즘이 달라짐
- "Algorithm + Data Structure = Program"
> 좋은 데이터 구조를 선택하는 것이 프로그램을 만드는 기초
- 자료 구조를 알고리즘 보다 먼저 공부하는 것이 좋음.