최대 숫자 찾기 - 순차 탐색 알고리즘(C언어)

 

 문제를 해결하기 위한 절차인 알고리즘을 공부할 때 처음으로 나오는 것은 최대 숫자 찾기이다. 정수 배열 중 최대 숫자 찾기에는 여러 방법이 있는데 이 중에서도 가장 기본적인 아이디어인 순차 탐색 알고리즘을 알아보자

 

1. 문제 이해

 

 

먼저 우리는 가장 큰 숫자를 어떻게 찾을까? 전체적으로 숫자들을 보며 눈에 띄는 큰 숫자를 찾은 뒤 더 큰 숫자가 없나 확인해 볼 것이다. 그리고 더 큰 숫자가 보이지 않는다면 탐색을 종료할 것이다.

하지만 컴퓨터 문제로 가져온다면 최대 숫자 찾기 문제는 달라진다. 컴퓨터는 저 종이를 어떻게 깔아놓을까?

 

 먼저 컴퓨터는 CPU 연산 전 작업을 위해 메모리에 숫자를 로드한다. 해당 메모리에서 연산할 것을 레지스터에 가져와 연산하게 된다. 편하게 메모리라는 책장에서 작업을 위해 레지스터라는 책상으로 책을 가져온다고 생각하면 된다. 메모리는 일렬로 쭉 긴 형태로 생각할 수 있으며, 번지수(주소값)를 통해 해당 주소의 값에 접근한다.

 이러한 방식 때문에 주소값으로 해당 주소로 가서 값을 가져오기 전에는 그 주소에 어떤 값이 들어있는지 알 방법이 없다. 카드가 일렬로 모두 뒤집혀져 있고 해당 자리로 가서 카드를 뒤집어 보기 전까지는 숫자를 알 수 없다는 말이다.

 

 자 이제 컴퓨터의 입장에서 문제를 재정의했다. 카드가 모두 뒤집혀져 있다면 우리는 어떻게 최댓값을 찾을까?

 

2. 해결책

 카드를 하나하나 뒤집어 숫자를 확인하고 가장 큰 숫자를 기억하고, 더 큰 숫자가 나오면 그것으로 최댓값을 바꿔주면 된다!

 

3. 코드로 바꿔보자(C언어)

 1) 문제를 세팅해주자(최댓값 찾을 카드 세팅)

컴퓨터는 여러 가지 자료구조로 나열되는 숫자를 저장할 수 있는데, 가장 기본적인 배열로 숫자를 세팅해 보도록 하겠다.

숫자는 모두 정수, 10개의 숫자이므로 크기가 10인 정수 배열을 선언하며 숫자들을 바로 넣어 초기화 해주도록 하겠다.

 2) 문제를 해결하자

 2.1) 카드를 뒤집어 숫자를 확인하고, 최댓값과 비교해 더 크면 그 숫자를 최댓값에 넣어준다

 숫자들이 0보다는 크므로 처음 숫자가 최댓값에 담길 수 있게 0으로 초기화 해 준다. 사실 초깃값을 지정하지 않아도 되지만 여러 가지 이유로 적당한 값으로 초기화 해 준다.

numArr 정수 배열의 첫 숫자가 max보다 크면 max에 그 숫자를 집어넣는 코드이다

 2.2) 해결 방법을 배열 전체에 적용한다

 정수 배열의 처음부터 끝까지 이를 반복하기 위해  for문 안에 if문을 넣고 배열을 선택하는 숫자를 i로 바꿔주면 0번지부터 9번지까지 10개의 숫자를 돌아가며 최댓값을 찾게 된다.

 2.3) 눈으로 확인해 보자

 마지막으로 최댓값을 잘 찾았는지 확인해 보기 위해 printf문까지 작성해 주고 결과를 확인해 보자

출력은 90으로 잘 나왔다!

 

다른 해결방법은 없었을까?

1. 우선 정수 배열 10개를 넣어주기 위해 일일이 다 쓰는 것은 비효율적이다. 랜덤하게 배열에 넣는 방법도 알아보자.

2. 현재 랜덤한 숫자에서 최댓값을 찾기 위해서는 하나하나 전부 확인해 보아야 한다. 하지만 정렬되어 있다면 더 빠르게 찾을 수 있지 않을까?

 

이는 각각 다른 글에서 해결해 보기로 하겠다.