본문 바로가기

알고리즘

최대값 구하기 n개의 정수를 입력받아 배열 요소에 저장했을 때, 0 이상의 연속된 정수들의 합 중에서 최댓값을 구하려면 어떻게 해야 할까? -2 1 5 예를 들어서 이러한 배열이 존재한다고 가정할 때, 연속된 정수들의 합을 구하면 1) -2 + 1 + 5 = 5 2) 1 + 5 = 6 두 가지 경우의 수를 가지며, 최댓값은 6이라고 할 수 있다. 1번의 경우는 배열의 0번 인덱스부터 2번 인덱스까지 차례로 더한 것이고 2번의 경우는 배열의 1번 인덱스부터, 2번 인덱스까지 차례로 더한 것이다. 이를 간단히 의사 코드로 나타내면 max is zero for i = 0 to n-2 sum is zero for j = i+1 to n-1 sum += data[j] if sum > max then max = sum 정도로 나.. 더보기
소수 출력 사용자에게 입력받은 int형 정수 N까지의 모든 소수를 출력해보자. 소수(Prime Number)란 1보다 큰 수 자연 중에 1과 자기 자신만을 약수로 가지는 수이다. 대충 나열해보면 2, 3, 5, 7, 11, 13, 17, 19,............이다. N = 100이라면 어떻게든 찾아낼 수 있겠지만, N = 100000이라면 여간 힘든 일이 아닐 것이다. 어떻게 하면 소수를 가려낼 수 있을까? 처음에 생각한 방법은 이랬다. 1. 10 이하에서는 2, 3, 5, 7만 출력한다. 왜냐하면 10 이하에서는 2, 3, 5, 7만 소수이므로. 2. 10 이상부터는 2, 3, 5, 7로 나누어 떨어지는 수를 제외하고 출력한다. 왜냐하면 10 이상에서는 2, 3, 5, 7로 나누어 떨어지지 않는 수가 소수이.. 더보기
배열요소 한 칸씩 뒤로 밀기 크기가 6인 정수형 배열 data가 있다고 하자. 2 3 5 8 13 21 data배열이 위와 같다고 생각하고, 각 요소를 한 칸씩 오른쪽으로 이동시킨다면 21 2 3 5 8 13 이런 모습이 될 것이다. 굉장히 간단한 문제지만, 조금만 생각해보면 당황스러운 부분이 존재하는데 '어떻게 배열 요소를 옮길 것인가?'라는 부분이다. 예를 들어 data [0]을 무턱대고 data [1]로 덮어 씌운다면, 원래의 요소 data [1]은 그냥 없어진다. 즉, 이 문제를 해결하기 위해선 원래의 요소를 보관할 임시 보관장소(이하 임시 변수)가 필요하다는 사실을 알게 된다. 그런데 각 요소를 옮길 때마다 임시 변수를 사용하는 것은 매우 번거로운 문제일 것이다. 어떻게 해야 최대한 효율적으로 옮길 수 있을까? 아니 그전에.. 더보기

티스토리툴바