inflearn logo
강의

講義

知識共有

it 就職のためのアルゴリズム問題プール入門 (with C/C++) : コーディングテスト対比

38. Inversion Sequence (挿入整列コードスタイル)

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

解決済みの質問

398

CHANGJUN KIM

投稿した質問数 8

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부터 시작했습니다. 선생님은 원리 상 뒤부터해야 한다고 하셨지만, 저는 하나하나 규칙을 파악해서 현상을 보고 그것을 알고리즘으로 구현한 것입니다.

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

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

C++ 코테 준비 같이 해요!

回答 2

3

codingcamp

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

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

1

CHANGJUN KIM

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

1부터 시작한다.

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

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

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

이런 식으로..

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

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

테스트 케이스 질문

0

373

1

병합정렬 시간복잡도 질문

0

462

1

41.연속된 자연수의 합 문제풀이에서 수학적인 원리를 모르고 있습니다.

0

1345

2

질문드립니다.

0

376

1

질문드립니다!

0

430

1

dev 프로그램 질문

0

275

1

문제가 이해가 안되요

0

376

1

4번 나이차이 문제 접근법 질문 드립니다.

0

307

1

source file not compiled

0

1047

3

59번 질문드립니다.

0

372

1

25번 문제 질문

0

349

1

4. 나이차이 문제 질문입니다.

0

372

1

90번 라이언 킹 심바 1번 테스트 케이스

0

470

1

71번 문제 전역 변수 질문 있습니다

0

365

1

75번, 79번 priority_queue관련

1

356

1

75.최대 수입 스케줄

0

400

2

복면산 정답의 수

0

431

1

테스트 케이스에 대해서

0

445

1

수업 내용 질문입니다!

1

232

1

풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!

0

822

2

12. 플로이드-와샬(그래프 최단거리) . 27:25초

0

255

1

다른 풀이 방식

0

317

1

크루스칼 vs 프림

0

306

1

숫자 총개수 small 질문있습니다.

0

243

1