• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

36강. 알고리즘을 생각해내는 방법

19.12.13 22:33 작성 조회수 193

2

#include <iostream>
using namespace std;
int main() {
	int N;
	int i, j;
	int num;
	int a[101] = { 0 };
	int cnt;
	cin >> N;
	for (i = 1; i <= N; i++) {
		cin >> num;	//앞에 자기보다 작은것 제외한 0(빈칸) 개수
		cnt = 0;
		for (j = 0; j < N; j++) {//앞부터 순회
			if (a[j] == 0)
				cnt++;
			if (cnt == num + 1) {
				a[j] = i;
				break;
			}
		}
	}
	for (i = 0; i < N; i++)
		cout << a[i] << " ";
}

안녕하세요, 선생님. 알고리즘을 똑똑하게 구현하고 싶어 질문하였습니다.

제가 짠 알고리즘은 1부터 시작했습니다. 선생님은 원리 상 뒤부터해야 한다고 하셨지만, 저는 하나하나 규칙을 파악해서 현상을 보고 그것을 알고리즘으로 구현한 것입니다.

엄연히 말하면 원리를 이해하진 않은 것입니다.

어떻게 하면 문제가 원하는 원리, 알고리즘을 간파할 수 있을까요? 어떻게 연습을 하면 좋을까요??

답변 2

·

답변을 작성해보세요.

2

본인이 짠 코드의 원리를 정확하게 알고 계십니다. 숫자를 1부터 처리한다면, 현재 처리할려고 하는 숫자보다 먼저 처리된 숫자는 모두 작고 나중에 처리되는 숫자는 모두 크다는 사실을 이용하는 것입니다. 

잘하고 계십니다. 지금과 같이 모든 문제를 본인 스스로 연구하고 풀어본 다음에 제가 풀이한 방법과 비교해 가면서 공부한다면 곧 실력자가 될것 같습니다.

1

선생님 제가 푼 방식을 논리적으로 파악하려고 노력했습니다. 이 논리에 대해서 어떻게 생각하는지 선생님의 의견과 앞으로 어떤식으로 연습하면 좋을지 조언을 구하고 싶습니다.

1부터 시작한다.

1 앞에 (모든 수가 1보다는 크므로) 어떤 수가 오든 1의 위치는 결정된다.

2 앞에 1을 제외하고는 2의 위치가 결정된다.

3 앞에 1, 2를 제외하고는 3의 위치가 결정된다.(3 앞에 3보다 큰게 4개가 있다면 1,2를 카운트하지 않고 4개의 공백 직후에 3을 결정시키는 것입니다.)

이런 식으로..

앞에 고정으로 박아 둔것에 대해서는 카운트 하지 않고 공백에 대해서만 카운트를 해서

그것이 입력받은 자기 자신보다 큰 개수와 비교하여 위치를 결정시키는 알고리즘입니다.