본문 바로가기

알고리즘/알고리즘 도감

 (44)
계산 시간 구하는 법 지난 글: [알고리즘] - 입력 크기와 계산 시간과의 관계 입력 변화에 따른 계산 시간 변화는 실제로 프로그램을 작성해서 컴퓨터에서 실행해보고 실제 걸리는 시간을 계측하는 것이 가장 현실적이다. 하지만 이 방법으로는 같은 알고리즘이라도 사용하는 컴퓨터에 따라 계산 시간이 달라져서 불편하다. 따라서 계산 시간에는 '스탭 수'라는 것을 활용한다고 한다. '1스텝'은 계산의 기본 단위로, '계산을 종료하기까지 기본 단위를 몇 회 실행했는가'로 계산 시간을 측정한다. 예로, 선택 정렬의 계산 시간을 이론적으로 구해보자. 선택 정렬은 아래어ㅏ 같은 알고리즘이었다. 1. 수열에서 최솟값을 찾는다. 2. 최솟값을 수열의 가장 왼쪽 숫자와 교환하고 정렬을 끝낸다. 1로 돌아간다. 수열의 숫자 개수를 n이라고 하면 1의..
입력 크기와 계산 시간과의 관계 지난 글: [알고리즘] - 정렬(sort) 이 전 글에서 사용한 정렬 방법인 선택 정렬과 입력 받은 n개의 숫자가 나열된 수열을 하나 만들고(단, 지금까지 사용하지 않은 나열 순서) 앞에서 만든 수열이 왼쪽부터 작은 순서대로 나열돼 있으면 출력, 아니면 수열을 만드는 작업으로 돌아가 반복하는 완전 탐색에 읜한 정렬이 있다. 이는 어느 알고리즘을 사용하느냐에 따라 계산 속도에 차이가 있음을 보여준다. 또, 알고리즘의 실행 시간은 같은 알고리즘이라도 입력 값에 따라 크게 달라진다. 참고 서적:
정렬(sort) 지난 글: [알고리즘] - 알고리즘이란? 정수를 순서대로 나열하는 알고리즘 : 정렬(sort) 작은 숫자를 찾아 교환하기 : 선택 정렬 알고리즘의 구체적인 예로 정렬(sort, 소트)을 알아보자. 이것은 아무렇게나 나열된 정수를 입력받아서 작은 것부터 차례로 재나열하는 것이다. 정수의 n이 적은 문제만 해결하는 것이라면 간단하겠지만, 알고리즘은 어떤 입력 값에 대해서도 대응할 수 있는 일반적인 방법을 기술해야 한다고 한다. 따라서 정수의 n이 아무리 커지더라고 같은 결과를 내어야 하는 것이다. 가장 먼저 떠오르는 방법은 입력 값 중 가장 작은 숫자를 찾고, 가장 왼쪽에 있는 숫자와 교환하는 것이다. 그러면 가장 왼쪽으로 옮겨진 숫자는 고정돼 이후로 움직이지 않는다. 그럼 다음은 남은 숫자 중 가장 작은 ..
알고리즘이란? 알고리즘과 프로그램의 차이 '알고리즘(Algorithm)'이란 계산이나 작업을 하기 위한 순서를 의미한다. 쉽게 특정 문제를 컴퓨터로 해결하기 위한 순서가 알고리즘이다. 이 때 알고리즘은 모든 순서가 수학적으로 기술된다. 알고리즘을 프로그램과 비슷하다고 생각할 수도 있다. 나도 알고리즘이 프로그램에서 사용하는 일종의 메서드인 줄 알았었다. 하지만 둘의 차이점은 프로그램은 컴퓨터상에서 실행할 수 있도록 컴퓨터가 이해할 수 있는 언어로 작성하는 것에 반해, 알고리즘은 프로그램을 작성하기 이전 단계에서 사람이 이해할 수 있도록 작성하는 것이라고 한다. 다만 알고리즘과 프로그램의 구분선을 분명하게 긋는 것은 어렵다고 한다. 같은 알고리즘이라도 프로그래밍 언어가 다르면 다른 프로그램이 되고, 같은 프로그래밍 언어..

티스토리툴바