굳건하게

안녕하세요

여행벌입니다.

오늘은 GoLatin 문제에 대해서 스터디를 진행할 때,

알고리즘 고수... 갓웅님의 코드를 보면서 배운 점에 대해서 정리해보겠습니다.

(기존 여행벌의 코드)

https://travelbeeee.tistory.com/6 

[배운점]

1. 테이블을 활용해 문자들을 치환하면 훨씬 더 간편하게 코드를 구현할 수 있다.

-갓웅코드

#include <iostream>
#include <cstring>

using namespace std;

const char eng[12][3] = {"a", "i", "y", "l", "n", "ne", "o", "r", "t", "u", "v", "w"};
const char latin[12][5] = {"as", "ios", "ios", "les", "anes", "anes", "os", "res", "tas", "us", "ves", "was"};

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        char str[40];
        cin >> str;

        int len = strlen(str);

        int j;
        for(j=0; j<12; j++) {
            // if same
            if(strcmp(str+(len-strlen(eng[j])), eng[j]) == 0) {
                str[len-strlen(eng[j])] = 0;
                cout << str << latin[j] << endl;
                break;
            }
        }

        if(j == 12) {
            cout << str << "us" << endl;
        }
    }
    return 0;
}

-내코드

		char list1[31];
		scanf("%s", list1);
		switch (list1[strlen(list1) - 1]) {
		case 'a':
			printf("%ss\n", list1); break;
		case 'i':
			printf("%sos\n", list1); break;
		case 'y':
			list1[strlen(list1) - 1] = '\0';
			printf("%sios\n", list1); break;
		case 'l':
			printf("%ses\n", list1); break;
		case 'n':
			list1[strlen(list1) - 1] = '\0';
			printf("%sanes\n", list1); break;
		case 'e':
			if (list1[strlen(list1) - 2] == 'n') {
				list1[strlen(list1) - 1] = '\0';
				list1[strlen(list1) - 1] = '\0';
				//조심! 위에서 마지막 글자를 이미 날려서, strlen이 하나 줄었음!
				printf("%sanes\n", list1);
			}
			else
				printf("%sus\n", list1);
			break;
		case 'o':
			printf("%ss\n", list1); break;
		case 'r':
			printf("%ses\n", list1); break;
		case 't':
			printf("%sas\n", list1); break;
		case 'u':
			printf("%ss\n", list1); break;
		case 'v':
			printf("%ses\n", list1); break;
		case 'w':
			printf("%sas\n", list1); break;
		default:
			printf("%sus\n", list1); break;
		}

하나하나 switch문을 통해서 모든 case를 다루다 보니 코드가 길어지고 가동성이 떨어지고 당연히 코딩하면서 실수가 되게 많이 발생할 수 밖에 없었다. 하지만 갓웅은 테이블에 미리 치환할 문자들을 담아두고, pseudo-latin인지 아닌지 체크만 하고 치환할 문자들을 간단하게 출력해줌으로써 훨씬 가독성 좋고 깔끔한 코드를 구현했다.

공부하자..

안녕하세요

여행벌입니다.

오늘은 HappyNumber 문제에 대해서 스터디를 진행할 때,

알고리즘 고수... 갓웅님의 코드를 보면서 배운 점에 대해서 정리해보겠습니다.

(기존 여행벌의 코드)

https://travelbeeee.tistory.com/5

[배운점]

1. 자릿수를 구해서 제곱해서 더하는 과정.

-갓웅코드

int f(int n)
{
    int sum = 0;

    while(n > 0) {
        sum += (n % 10) * (n % 10);
        n = n / 10;
    }

    return sum;
}

-내코드

/* 자리수별로 자른다. */
/* 자리수별로 제곱해서 더한 값을 return해준다. */
int divide(int ninput) {
	/* 이 부분 예외처리 안해서 틀렸음.*/
	if (ninput < 10) {
		return ninput * ninput;
	}
	int out = 0;
	nlist[0] = ninput / 1000000000;
	nlist[1] = (ninput % 1000000000) / 100000000;
	nlist[2] = (ninput % 100000000) / 10000000;
	nlist[3] = (ninput % 10000000) / 1000000;
	nlist[4] = (ninput % 1000000) / 100000;
	nlist[5] = (ninput % 100000) / 10000;
	nlist[6] = (ninput % 10000) / 1000;
	nlist[7] = (ninput % 1000) / 100;
	nlist[8] = (ninput % 100) / 10;
	nlist[9] = (ninput % 10);
	for (int i = 0; i < 10; i++) {
		if (nlist[i] != 0)
			out += nlist[i] * nlist[i];
	}
	return out;
}

같은 작업을 하고 있지만, 누가 봐도 갓웅의 코드가 훨씬 간결하고 가독성이 좋다.

for문 , % , / 를 이용하면 정말 짧고 간단한 코드로 자릿수를 구할 수 있다는 것을 깨달았다.

2. 순환(Cycle)이 생기는지 안 생기는지 체크하는 과정.

-갓웅코드

    if(n <= 729) 
    	v[n] = true;

    while(true) {
        int sum = f(n);
        if(sum == 1) {
            cout << "HAPPY";
            break;
        }
        else {
            if(v[sum] == true) {
                cout << "UNHAPPY";
                break;
            }
            v[sum] = true;
            n = sum;
        }
    }

-내코드

// 지금까지나왔던 값 중에서 현재 값이 있는지 없는지 확인한다.
bool check_repeat(int ninput, int count) {
	for(int i =0 ; i< count; i++){
        if(repeat[i] == ninput)
            return true;
    }
    return false;
}

갓웅은 자릿수의 제곱의 합이 가장 큰 숫자가 999,999,999일 때 729인 것을 캐치하고 v[730]라는 bool 리스트를 만들었다. 그리고 각 자릿수의 제곱의 합을 구해나가면서 그에 해당하는 index를 true 값을 주었고, 다시 한번 true가 나오면 UNHAPPY를 출력해주는 방법으로 진행했다.

나는 기존의 값들을 int형 리스트에 담아두었다가, 순회하면서 다시 나온 숫자가 없는지 찾아줬다.

따라서 갓웅 O(1) vs 여행벌 O(n) 이라는 말도 안 되는 차이를 가진 알고리즘이 만들어졌다.

공부하자...

안녕하세요.

여행벌입니다.

오늘은 백준 16360번 Go Latin 문제풀이를 해보려고 합니다.

ACM-ICPC 2018 본선 문제로 ACM-ICPC 문제 치고는 되게 쉬웠던 것 같습니다.

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

문제는 'n개의 단어가 주어졌을 때,  pseudo-latin 단어로 바꿔서 출력해주는 알고리즘을 구현하라.' 입니다.

단어의 끝 문자가 위의 테이블에 해당되면, pseudo-latin 문자로 바꿔서 출력해주면 되는데요.

다른 더 좋은 알고리즘이 있을 수도 있지만, 저는 간단한 문제라 더 생각 안 하고 if 문을 통해

간단하게 알고리즘 구현할 수 있었습니다.

[알고리즘설계]

1. switch 문을 통해 입력받은 string의 끝 문자 들을 다 체크한다. 이때, Pseudo-Latin으로 바꿔줘야 하는 문자가 있다면, 바꿔주면서 출력한다. 다만 -n, -ne를 제외하고 모두 원래의 단어에 글자를 추가해주면 되므로 원래의 string을 출력하고 뒤에 추가로 char을 출력해준다.

#include<stdio.h>
#include<string.h>

int main(void) {
	int total_number;
	scanf("%d", &total_number);
	while (total_number > 0) {
		char list1[31];
		scanf("%s", list1);
		switch (list1[strlen(list1) - 1]) {
		case 'a':
			printf("%ss\n", list1); break;
		case 'i':
			printf("%sos\n", list1); break;
		case 'y':
			list1[strlen(list1) - 1] = '\0';
			printf("%sios\n", list1); break;
		case 'l':
			printf("%ses\n", list1); break;
		case 'n':
			list1[strlen(list1) - 1] = '\0';
			printf("%sanes\n", list1); break;
		case 'e':
			if (list1[strlen(list1) - 2] == 'n') {
				list1[strlen(list1) - 1] = '\0';
				list1[strlen(list1) - 1] = '\0';
				//조심! 위에서 마지막 글자를 이미 날려서, strlen이 하나 줄었음!
				printf("%sanes\n", list1);
			}
			else
				printf("%sus\n", list1);
			break;
		case 'o':
			printf("%ss\n", list1); break;
		case 'r':
			printf("%ses\n", list1); break;
		case 't':
			printf("%sas\n", list1); break;
		case 'u':
			printf("%ss\n", list1); break;
		case 'v':
			printf("%ses\n", list1); break;
		case 'w':
			printf("%sas\n", list1); break;
		default:
			printf("%sus\n", list1); break;
		}
		total_number--;
	}
}

너무 간단한 문제라 여기서 해설 마치겠습니다.

안녕하세요

여행벌입니다.

오늘은 백준 14954번 ACM 2017 본선 D번 문제 풀이를 해보겠습니다.

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

문제는 '어떤 숫자가 주어졌을 때, HappyNumber인지 아닌지 구분해주는 알고리즘을 구현하라.' 입니다.

이 때, HappyNumber 란 숫자가 주어졌을 때, 각 자릿수의 제곱을 더해나가고 이 과정을 거쳐 최종적으로 1에 도달할 수 있는 수를 뜻합니다.

예를 들어,

3이란 숫자가 주어지면 19 -> 82 -> 68 -> 100 -> 1 로 HappyNumber인 것을 확인할 수 있습니다.

4라는 숫자는 4 -> 16 -> 37 -> 56 -> 61 -> 37 순환(Cycle) 고리가 생겨 UnHappyNumber인 것을 볼 수 있습니다.

따라서, 우리는 다음과 같이 알고리즘을 설계할 수 있습니다.

[알고리즘 설계]

1. 어떤 숫자가 주어졌을 때, 각 자릿수를 구하고 제곱해서 더한 값을 return 해주는 함수.

2. 각 자리수를 구하고 제곱해서 더해나가다가 순환(recycle) 고리가 생기는지 체크해주는 함수. 

3. 순환 고리가 생긴다면 UNHAPPY / 순환 고리가 생기지 않고 1이란 숫자가 나타나면 HAPPY 를 출력해주는 함수.

총 3가지 작업이 필요하다는 것을 확인할 수 있습니다.

설계한 알고리즘을 구현해보겠습니다.

#include<iostream>

using namespace std;

int nlist[10] = {};
int repeat[10000000] = {};

int divide(int);
bool check_repeat(int, int);

int main(void) {
	int ninput, count = 0;
	cin >> ninput;
	while (1) {
		repeat[count] = ninput;
		if (ninput == 1) {
			cout << "HAPPY";
			break;
		}
		if (check_repeat(ninput, count) || count == 9999999) {
			cout << "UNHAPPY";
			break;
		}
		ninput = divide(ninput);
		//cout << count << "번 째 : " << ninput << endl;
		count++;
	}
}

/* 자리수별로 자른다. */
/* 자리수별로 제곱해서 더한 값을 return해준다. */
int divide(int ninput) {
	/* 이 부분 예외처리 안해서 틀렸음.*/
	if (ninput < 10) {
		return ninput * ninput;
	}
	int out = 0;
	nlist[0] = ninput / 1000000000;
	nlist[1] = (ninput % 1000000000) / 100000000;
	nlist[2] = (ninput % 100000000) / 10000000;
	nlist[3] = (ninput % 10000000) / 1000000;
	nlist[4] = (ninput % 1000000) / 100000;
	nlist[5] = (ninput % 100000) / 10000;
	nlist[6] = (ninput % 10000) / 1000;
	nlist[7] = (ninput % 1000) / 100;
	nlist[8] = (ninput % 100) / 10;
	nlist[9] = (ninput % 10);
	for (int i = 0; i < 10; i++) {
		if (nlist[i] != 0)
			out += nlist[i] * nlist[i];
	}
	return out;
}

// 지금까지나왔던 값 중에서 현재 값이 있는지 없는지 확인한다.
bool check_repeat(int ninput, int count) {
	for(int i =0 ; i< count; i++){
        if(repeat[i] == ninput)
            return true;
    }
    return false;
}

각 자릿수를 구하는 divide 함수는 https://travelbeeee.tistory.com/4 기존의 포스팅 글을 참고하시면 될 것 같습니다. 

check_repeat 함수는 지금까지 결과로 나왔던 값들을 순회하며 공통된 값이 존재하면 순환(Cycle)고리가 형성된 것이므로 true 아니면 false를 return 해주는 함수입니다.

아마 2017 ACM-ICPC 예선에서 가장 쉬운 문제가 아닐까 싶습니다.

알고리즘 설계하기 굉장히 쉬웠고, 예외만 잘 잡아준다면 쉽게 풀 수 있는 문제인 것 같습니다.