[이상선의 10분 강의 알고리즘] 1. 수열 알고리즘 -2

알고리즘

안녕하세요. 오늘도 하루 10 분 강의 알고리즘편입니다.

이 강의는 C언어 강의를 전부 수강한 분께서 들으면 매우 적합한 강의입니다.
처음부터 풀기 어려운 알고리즘을 하지 않고 초급부터 할 예정이지만,
C언어 문법을 모르고 공부하는것은 매우 어려울 것이라 생각하므로
필수로 C언어 기초를 배우고 와서 도전해보시길 바랍니다.

문제 난이도가 점차 어려워 질 것입니다. 그래도 끝까지 포기하지 않고 도전해보세요.^^

시작해볼까요?

문제

풀이

#include<stdio.h>

void main() {

int i, j = 1, k = 1;

for (i = 0; i < 10; i++) {
    j = j + i;
    k = k + j;
}

printf("총 합계는 %d 입니다", k);

}

1번 문제부터 천천히 풀어보겠습니다.

1번 문제는 1+2+4+7+11+16+22+29+37+46의 합계입니다.

뭔가 어려운 문제처럼 보이지만, 소스를 보면 전혀 그렇지 않습니다. 감이 오시나요?
알고리즘은 무조건 법칙을 찾아내야 합니다. 그래야 그 법칙을 소스에 고스란히 옮겨담을 수 있죠.

문제와 소스를 보면 변수 3개가 필요하다는 것을 알 수 있습니다.

첫번째 필요한 변수 : i 역할 : 1이 들어있는 1항부터 46이 들어있는 10항까지 1항씩 증가하기 위한 변수
두번째 필요한 변수 : j 역할 : 수열의 각 항을 나타내기 위한 변수
세번째 필요한 변수 : k 역할 : 총 합계를 저장하기 위한 변수

이해가 좀 되시나요?

1항부터 10항까지 증가하기 위한 변수 i와 1,2,4,7,11,16의 수를 담는 변수 j
그리고 이 모든것의 합계를 저장하는 k가 필요합니다.

이해가 안될 수도 있지만 천천히 단계를 리스트로 정리해 보겠습니다.

for 문을 자세히 살펴보면 i는 0부터 9까지 1씩 증가합니다. 즉, 항이 10번 반복되는 것입니다.

첫번째 항에 1이 들어있기 때문에 j와 k는 각각 1로 초기화 됩니다.
j는 1항의 수 1을 의미하는 것이고
k는 1항까지의 합계 1을 의미하는 것이죠.

for문이 처음 돌아갈 때, i는 0이고 j는 i와 더해져 1의 값을, j역시 k와 더해져 2의 값을 갖습니다.
두번째 for문이 돌아갈 때는 i는 1을, j는 2를, k는 4를 갖습니다.

이렇게 계속 10항까지 누적하여 최종 합계를 구하는 것입니다.

천천히 디버깅하여 값을 확인하면서 소스를 이해해보시길 바랍니다.

이해가 잘 안되면 언제나 댓글 부탁드립니다.

이번에도 마찬가지로 응용 알고리즘 2번을 풀어봅시다.

문제

풀이

#include<stdio.h>

void main() {

int i, j = 1, k = 0;
int cnt = 0;

for (i = 0; i < 10; i++) {

    j = j + i;
    cnt++;

    if (cnt % 2 == 0) {
        k = k - j;
    }

    else {
        k = k + j;
    }
}
printf("최종 합계 = %d\n", k);

}

이번에는 조금 더 응용된 코드입니다.

하지만 문제 이해만 잘 된다면 크게 어려운 것이 없습니다. 여러분은 C언어를 배웠기 때문에!
for문에 대한 자세한 내용은 위에 설명을 다시 참고해주시길 바라며,
cnt에 대하여 설명해 드리겠습니다.

여러분은 위에서 i, j, k가 각각 무슨 역할을 하는지 이해하였습니다.
하지만 이번에는 홀수 항에는 + 연산을, 짝수 항에는 - 연산을 하는군요.

그래서 cnt라는 변수 하나를 더 추가하였습니다.
cnt를 처음에 0으로 초기화 시킨 후 for문에서 1을 만들었죠.

아래 if에 cnt를 접목하여 짝수인지 홀수인지 검사하게 하였습니다.
만약 cnt % 2 == 0의 값이 참이라면 짝수 항이니 - 연산을 수행하여 k에 저장하였고
그렇지 않으면 홀수 항이니 + 연산을 수행하여 k에 저장하게 하였습니다.

이렇게 10번의 for문 연산 후 최종 값을 추출하기만 하면 끝입니다.

어떠셨나요?
수열 알고리즘 2도 생각보다 쉽지 않으신가요?

앞으로 나오는 기초 알고리즘과 중급, 고급 알고리즘은 생각보다 어려운 친구들이 많습니다!
차근히 하나 둘 풀다보면 어느새 알고리즘과 자료구조 응용 및 해결 방법이 보일 거에요.

코드는 무조건 적고 이해하고 또 적는 것입니다.
오늘 코드도 무조건 적어보고 디버깅하여 이해하시길 바랍니다.

이번주도 매우 고생 많았습니다.

공부하는 여러분 파이팅입니다.