(백준 1969번 DNA C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 1탄

그리디 알고리즘에 대한 설명은 라이님 블로그를 참고!!!! 오늘은 DNA 문제를 풀어보고자 한다.

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220775134486&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)

백준 1969번 DNA

https://www.acmicpc.net/problem/1969

1969번: DNA

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

int main() {
	int N, M; char temp;
	scanf("%d %d", &N, &M);

	char** Arr = new char *[N+1]; // (N+1) * M 행렬
	for (int i = 0; i < N+1; i++) Arr[i] = new char[M];

	for (int i = 0; i < N; i++) {
		scanf("%c", &temp);
		for (int j = 0; j < M; j ++) {
			scanf("%c", &Arr[i][j]);
		}
	}
	int Acnt = 0; int Ccnt = 0; int Gcnt = 0; int Tcnt = 0;
	int DNA_MAX = 0;

	for (int j = 0; j < M; j++) {
		Acnt = 0; Ccnt = 0; Gcnt = 0; Tcnt = 0;
		for (int i = 0; i < N; i++) {
			if (Arr[i][j] == 'A') Acnt++;
			else if (Arr[i][j] == 'C') Ccnt++;
			else if (Arr[i][j] == 'G') Gcnt++;
			else  Tcnt++;
		}
		DNA_MAX = std::max({ Acnt, Ccnt,Gcnt, Tcnt });
		if (Acnt == DNA_MAX) {
			Arr[N][j] = 'A'; printf("A");
		}
		else if (Ccnt == DNA_MAX) {
			Arr[N][j] = 'C'; printf("C");
		}
		else if (Gcnt == DNA_MAX) {
			Arr[N][j] = 'G'; printf("G");
		}
		else {
			Arr[N][j] = 'T'; printf("T");
		}
	}

	printf("\n");
	int HD = 0; // Hamming Distance;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Arr[N][j] != Arr[i][j]) HD++;
		}
	}
	
	printf("%d", HD);

	for (int i = 0; i < N+1; i++) delete[]Arr[i];
	delete[] Arr;
	return 0;
}

 

오늘의 실수

new와 delete는 짝궁! new로 동적할당할 때는 행과 열이 어디에 들어가는지 헷갈리지 말자.

아니면 런타임 에러와 메모리 초과 오류를 겁내 많이 만나게 된다...

 

이번 문제에서는 Arr을 N*M행렬이 아닌 (N+1)*M행렬이 되도록 만들었는데, 이 과정에서 오타가 많아서 런타임 에러를 아주^^많이 만났다. 진짜 구세주 김모기가 아니였다면 큰일날 뻔.. 디버깅을 도와준 모기에게 심심한 감사의 인사를 전한다.

 

덕분에 Segmentation fault가 뭔지 알게되었다. 이는 프로그램이 허용되지 않는 메모리에 접근하고자 할 때 생기는 오류인데, 아무래도 동적할당을 하는 new나 delete함수를 사용하면 자주 보이게 된다.

 

이럴때는 내가 제대로 이차원배열의 동적 할당을 했는지, 내 자신을 돌아봐아야 한다.(나처럼)

지금 코드가 정답!

char** Arr = new char *[N+1]; // (N+1) * M 행렬
for (int i = 0; i < N+1; i++) Arr[i] = new char[M];

 

참고로 처음에는 아래와 같이 해놨었다. 

char** Arr = new char *[M]; // (N+1) * M 행렬
for (int i = 0; i < N+1; i++) Arr[i] = new char[M];