글 읽기 - 제 코드가 런타임 에러가 나는게 당연한 것인가요?

seonjoo2030 5년 전 0

우선,

QWEQWE

WERQWE

이런 문자열들이 입력으로 들어왔다면,

첫 번째 문자열의 첫 번째 단어부터 선택하여 두 번째 문자열과 비교합니다.

그리고 같은 부분이 있으면 문자를 배열에 저장시키고, 두 번째 문자열에서 같은 단어가 나온 다음 부분부터

첫 번째 문자열의 두 번째 문자와 비교합니다.

이런 방법으로 첫 번째 문자열을 기준으로 비교하고, 다음으로 두 번째 문자열을 기준으로 다시 검사합니다.

그런 다음 그 중에 최장길이인 것을 찾아 출력하게 했습니다.

AAAA

이거나 혹은 그 반대도 제대로 나오긴 합니다.

상식적으로 생각해 봤을 때, 최악의 경우, 1000개의 문자를 각각 1000번 씩 검사하고, 반대로 또 검사해서

엄청 많이 검사를 해야 하는 것이라 런타임 에러가 나는 것 같은데, 이 이유 때문에 LCS 알고리즘을 사용할 수 밖에

없는 것인가요??

#include <stdio.h>
#include <string.h>
char fst[1001];  //첫 번째 입력받는 문자열
char sec[1001]; //두 번째 입력받는 문자열
char res[1001][1001];  // 첫 번째 문자열의 각각 문자에 대한 결과 값 저장
int result[2001];  // 최장 공통 부분 수열의 길이 저장하는 배열

int main()
{
	scanf("%s %s", fst, sec);  // 문자열 입력받음
	int size = strlen(fst);  // 첫번째 문자열의 길이
	int size2 = strlen(sec);  //두 번째 문자열의 길이

	int j = 0;  // 두 번째 문자열의 위치 지정할 변수
	int r = 0;  // 결과 값을 저장하기 위해 배열 위치를 지정할 변수

	for (int t = 0; t < size; t++)
	{
		for (int i = t; i < size; i++)
		{
			for (int k = j; k < size2; k++)
			{
				if (fst[i] == sec[k])  // 첫 번째 문자의 단어와 같은 단어 만나면 
				{
					res[t][r] = fst[i];  // 결과 배열에 저장
					r++;  // 결과 배열의 다음 칸으로 이동
					j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
					break;
				}
			}
		}
		result[t] = strlen(res[t]);  // 첫번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;  
		r = 0;
	}
	
	for (int t = 0; t < size2; t++)
	{
		for (int i = t; i < size2; i++)
		{
			for (int k = j; k < size; k++)
			{
				if (sec[i] == fst[k])  // 두 번째 문자의 단어와 같은 단어 만나면 
				{
					res[t + size][r] = sec[i];  // 결과 배열에 저장
					r++;  // 결과 배열의 다음 칸으로 이동
					j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
					break;
				}
			}
		}
		result[t + size] = strlen(res[t + size]);  // 두번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;
		r = 0;
	}

	int max = result[0];  //가장 긴 최장 공통 수열을 찾기 위한 변수
	int check = 0;
	for (int i = 1; i < size + size2; i++)  // 최대값 찾기
	{
		if (max < result[i])
		{
			max = result[i];
			check = i;
		}
	}
	printf("%d\n", max);  // 갯수 출력
	for (int i = 0; i < max; i++)  // 해당 문자열 출력
		printf("%c", res[check][i]);
	printf("\n");
}

djm03178 5년 전 0

검사를 엄청 많이 하는 것은 런타임 에러와는 무관합니다. 단순히 너무 많은 작업을 하는 게 문제라면 시간 초과를 받습니다. 런타임 에러는 프로그램에게 허용되지 않은 동작을 해야 납니다.

의심이 가는 곳은 45번째 줄인데, t + size는 res에 할당된 메모리 범위를 초과할 수 있어 보입니다.

seonjoo2030 5년 전 0

감사합니다. 해당 부분 배열 길이를 늘려 수정을 했습니다.

런타임 에러는 사라졌지만, 틀렸다고 나옵니다..

아무리 생각해도 어디가 틀린 것인지 잘 모르겠습니다.

첫 번째 문자열과 두 번째 문자열에 모든 문자에 대해서 경우의 수를 다 구한 것 같은데 제가 실수한 부분이 어딘지 모르겠습니다 ㅜㅜ

#include <stdio.h>
#include <string.h>
char fst[1001];  //첫 번째 입력받는 문자열
char sec[1001]; //두 번째 입력받는 문자열
char res[3001][3001];  // 첫 번째 문자열의 각각 문자에 대한 결과 값 저장
int result[2001];  // 최장 공통 부분 수열의 길이 저장하는 배열

int main()
{
	scanf("%s %s", fst, sec);  // 문자열 입력받음
	int size = strlen(fst);  // 첫번째 문자열의 길이
	int size2 = strlen(sec);  //두 번째 문자열의 길이

	int j = 0;  // 두 번째 문자열의 위치 지정할 변수
	int r = 0;  // 결과 값을 저장하기 위해 배열 위치를 지정할 변수

	for (int t = 0; t < size; t++)
	{
		for (int i = t; i < size; i++)
		{
			for (int k = j; k < size2; k++)
			{
				if (fst[i] == sec[k])  // 첫 번째 문자의 단어와 같은 단어 만나면 
				{
					res[t][r] = fst[i];  // 결과 배열에 저장
					r++;  // 결과 배열의 다음 칸으로 이동
					j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
					break;
				}
			}
		}
		result[t] = strlen(res[t]);  // 첫번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;  
		r = 0;
	}
	
	for (int t = 0; t < size2; t++)
	{
		for (int i = t; i < size2; i++)
		{
			for (int k = j; k < size; k++)
			{
				if (sec[i] == fst[k])  // 첫 번째 문자의 단어와 같은 단어 만나면 
				{
					res[t + size][r] = sec[i];  // 결과 배열에 저장
					r++;  // 결과 배열의 다음 칸으로 이동
					j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
					break;
				}
			}
		}
		result[t + size] = strlen(res[t + size]);  // 첫번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;
		r = 0;
	}

	int max = result[0];  //가장 긴 최장 공통 수열을 찾기 위한 변수
	int check = 0;
	for (int i = 1; i < size + size2; i++)  // 최대값 찾기
	{
		if (max < result[i])
		{
			max = result[i];
			check = i;
		}
	}
	printf("%d\n", max);  // 갯수 출력
	for (int i = 0; i < max; i++)  // 해당 문자열 출력
		printf("%c", res[check][i]);
	printf("\n");
}

djm03178 5년 전 1

반례들입니다.

ACBBAABCCA
CBACAAACBC
wrong length; expected 6 (CBAACC), found 5 (BAABC)

CCABBABA
AABAABBAC
wrong length; expected 5 (ABABA), found 4 (ABBA)

BBABABAC
BACCCBBA
wrong length; expected 5 (BABBA), found 4 (BABA)

seonjoo2030 5년 전 0

감사합니다 ㅜㅜ

이런 반례들을 찾기가 너무 어렵네요...

최적해의 일부분이 최적해가 되지 않는 경우가 있더군요...

그냥 LCS알고리즘으로 풀어야 하나 봅니다...ㅜㅜ

아무튼 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 코드가 런타임 에러가 나는게 당연한 것인가요?

seonjoo2030 5년 전 0

djm03178 5년 전 0

seonjoo2030 5년 전 0

djm03178 5년 전 1

seonjoo2030 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말