ㅂㄱ
훌륭한 알고리듬이 갖춰야 할 자질 본문
1. 입력과 출력이 명확히 정의되어 있어야함 -> 입력은 시작시 비어있을 수도 있음
2. 알고리듬의 각 단계가 명확하며 모호하지 않아야 함
3. 유한 시간 안에 결과(출력)가 나와야 함
4. 컴퓨터 코드를 포함하면 안 됨 -> pope는 동의 안함 --> 포팅이 어려운 컴퓨터 코드를 포함하면 안 됨
5. 같은 문제를 푸는 다양한 방법 중에 가장 효율적임
컴퓨터 코드를 사용하면 생기는 문제
1. 이해가 어려울 수 있음 : 그 코드를 못 읽는 사람이 있을 수 있음
2. 포팅이 어려울 수 있음 : 특정 언어에만 있는 기능을 사용할때
- 최종 목표 : 어떤 프로그래밍 언어로도 알고리듬을 구현할수 있어야
- 목표는 올바름 그러나 방법이 틀림
코드 없이 알고리듬을 설명하려면?
- 인간의 언어로 표현해야 함
양자를 비교했을때 일반적으로 코드가 쉽게 읽힘
- 모든 사람이 충분히 이해하는 인간 언어가 있어야만 가능한 일
- - 기원이 같은 인간 언어들은 공통점이 꽤 있음
- - 하지만 매우 상이한 언어도 있어서 이건 말이 안되는 이야기
코드가 차라리 더 낫다.
public int add(int num1, int num2){
return num1 + num2;
}- 그 보다는 프로그래밍 언어들끼리는 공통정이 더 많음
- - C계열 언어끼리는 매우 비슷
- - 그 외 언어도 충분히 비슷
- 따라서 차라리 코드로 설명하는게 더 좋은 방법
- - 최종 목표는 이해입니다. 문법은 적당히 틀려도 됨(의사코드, pseudocode)
의사코드의 예 : FizzsBuzz
결과적으로 이해만 가면 된다.
포팅이 가능한 의사코드 작성하기
- 거의 모든 언어에 공통되는 연산만 사용하기 - 사칙연산, 비트연산, 조건문 , 반복문 등
- 결국 하드웨어와 기계어/ 어셈블리어 수준에서 지원하는 것들
- 고수준 언어 중에서는 C에서 지원하는 것 정도(단, 포인터 연산은 제외)
왜 알고리듬 과목을 이리 뒤에 배우는지 알겠죠?
네 컴퓨터가 도는 방법을 잘 알아야 하니까요?
알고리듬 공부를 해도 안 느는 프로그래머들
- 하드웨어가 어떤 연산을 지원하는지 모름
- 이미 존재하는 마법 같은 함수만 호출해봄
- 툭하면 언어 문법이 틀리는데 컴파일 오류를 봐도 그 문제를 못 참음
- 컴퓨터에 데이터가 어떻게 저장되는지 모름
- 힙과 스택 메모리의 차이에 대해 모름
- 등
알고리듬의 효율성
- 자원의 효율적 사용을 뜻함
- 자원(resource) - 시간(time) : cpu 속도 등, 공간/용량(space) : 메모리 사용량 등
- 시간과 공간은 종종 상반 관계 -> 메모리를 좀도 먹으면 시간이 줄어들거나 한다.
- 자원을 많이 사용할수록 그 알고리듬이 복잡하다고 말함 - 시간 복잡도(time complexity), 공간복잡도(space complextiy), 알고리듬 복잡도를 표현하는 방법 중 하나 : 빅오(Big- O) 표기법
덜 효율적인 더하기 알고리듬
1. 변수 num1, num2, sum을 선언한다.
2. num1과 num2 용 값을 읽는다.
3. sum에 num1을 대입한다.
4. 총 num2번 동안 sum을 1씩 증가한다.
5. sum을 화면에 출력한다.
코드1은 무조건 1번에 실행으로 끝난다. 하지만 위 코드는 숫자가 증가하면 할 수록 코드 실행 횟수가 증가한다.
알고리듬의 효율성과 실제 성능
한번에 한명 밖에 컴퓨터가 못 센다면?
알고리듬의 효율성 분석은 다소 추상적
즉 어떤 컴퓨터에서 이 코드를 돌리나에 따라서 달라질수도 있다는 것이다.