굳건하게

안녕하세요

여행벌입니다.

오늘은 ACM-ICPC 2015 본선 문제인

BOJ 11592번 3-Primes Problem 문제를 다뤄보도록 하겠습니다.

[문제해석]

7 ~ 1000 사이의 양수가 주어졌을 때, 이 양수를 3개의 소수의 합으로 표현할 수 있다면, 3개의 소수를 출력하고, 아니라면 0을 출력하는 알고리즘을 작성하여라.

[알고리즘설계]

1. 에라토스테네스 체를 이용하여 1 ~ 1000 사이의 소수를 먼저 찾는다.

2. 3중 포문을 이용해 주어진 양수(ninput)를 3개의 소수의 합으로 판단할 수 있는지 없는지 판단한다.

* Input 값의 범위가 1000 으로 매우 작다. 따라서, 무식하게 3중 포문을 이용해서 푸는 것이 빠르겠다고 판단하였다.

#include<iostream>

using namespace std;

int main(void) {
	// 에라토스테네스체로 prime부터 찾자.
	bool prime[1001];
	for (int i = 0; i < 1001; i++)
		prime[i] = true;
	for (int i = 2; i * i <= 1000; i++) {
		if (prime[i] == true) {
			for (int j = 2 * i; j <= 1000; j += i) {
				prime[j] = false;
			}
		}
	}

	int test_case;
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		int ninput, j , k , l;
		cin >> ninput;
		for (j = 2; j < 1000; j++) {
			for ( k = 2; k < 1000; k++) {
				for ( l = 2; l < 1000; l++) {
					if (j + k + l > ninput)
						break;
					if (prime[j] && prime[k] && prime[l] && j + k + l == ninput){
						cout << j << ' ' << k << ' ' << l << '\n';
						break;
					}
				}
				if (prime[j] && prime[k] && prime[l] && j + k + l == ninput) {
					break;
				}
			}
			if (prime[j] && prime[k] && prime[l] && j + k + l == ninput) {
				break;
			}
		}
		if (prime[j] && prime[k] && prime[l] && j + k + l == ninput) {
			continue;
		}
		else
			cout << 0 << '\n';
	}
	return 0;
}

input이 작아서 문제에 쉽게 접근할 수 있었지만, input이 크다면 접근하기 어려울 것 같다.

안녕하세요

여행벌입니다.

오늘은 ACM-ICPC 2016 본선 문제인

BOJ 13567번 ROBOT 문제풀이를 해보겠습니다.

[문제파악]

1. (0,0) 위치에서 시작하여 로봇이 주어진 명령에 따라 이동을 한다.

2. 이동 과정에서 주어진 MAP을 벗어난다면, "-1"을 출력하고 아니라면 로봇의 최종 위치를 출력한다.

[알고리즘설계]

1. 현재 로봇의 위치를 x , y 변수에 저장하고, 로봇이 현재 향하고 있는 방향을 direction 변수에 담아주자.

direction 에 0(오) 1(왼) 2(위) 3(아래)를 저장한다.

- TURN 명령은 오른쪽으로 90도 회전, 왼쪽으로 90도 회전 2가지 종류가 있고, direction 변수를 TURN에 맞춰서 새롭게 저장해준다.

- MOVE는 direction이 가리키는 방향으로 이동하며 x , y 변수를 새롭게 저장해준다.

2. 명령을 수행하는 과정에서 MAP을 벗어나는지 체크해주고 벗어난다면 "-1"을 출력하고, 아니라면 명령을 다 수행하고 위치를 출력해준다.

[주의할점]

1. 명령을 하나씩 받으면서 로봇을 이동시켜주려 한다면 중간에 MAP을 벗어나는 상황이 생겨도 일단 명령 입력을 다 받아야 하므로 종료하면 안 된다.

따라서, 명령을 다 입력받고 로봇을 이동시키는 것이 더 편하다.

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

char instruction1[1000][5];
int instruction2[1000];

/* direction 에 0(오) 1(왼) 2(위) 3(아래)를 저장한다.*/
int main(void) {
	int length, ninstruction, x = 0, y = 0, direction = 0;
	scanf("%d %d", &length, &ninstruction);

	for (int i = 0; i < ninstruction; i++) {
		scanf("%s %d", instruction1[i], &instruction2[i]);
	}

	for (int i = 0; i < ninstruction; i++) {
		if (strcmp(instruction1[i], "TURN") == 0) {
			// 왼쪽으로 90도 회전
			if (instruction2[i] == 0) {
				if (direction == 0) {
					direction = 2;
				}
				else if (direction == 1) {
					direction = 3;
				}
				else if (direction == 2) {
					direction = 1;
				}
				else if (direction == 3) {
					direction = 0;
				}
			}
			// 오른쪽으로 90도 회전
			else if (instruction2[i] == 1) {
				if (direction == 0) {
					direction = 3;
				}
				else if (direction == 1) {
					direction = 2;
				}
				else if (direction == 2) {
					direction = 0;
				}
				else if (direction == 3) {
					direction = 1;
				}
			}
		}
		else if (strcmp(instruction1[i], "MOVE") == 0) {
			if (direction == 0) {
				for (int j = 0; j < instruction2[i]; j++) {
					x++;
				}
			}
			else if (direction == 1) {
				for (int j = 0; j < instruction2[i]; j++) {
					x--;
				}
			}
			else if (direction == 2) {
				for (int j = 0; j < instruction2[i]; j++) {
					y++;
				}
			}
			else if (direction == 3) {
				for (int j = 0; j < instruction2[i]; j++) {
					y--;
				}
			}
		}
		if(x < 0 || x > length || y < 0 || y > length){
			printf("%d", -1);
			return 0;
		}
	}
	printf("%d %d", x, y);
	return 0;
}

안녕하세요

여행벌입니다.

오늘은 ACM-ICPC 2016 본선 문제인

13565번 Percolation 문제 풀이를 해보겠습니다.

[문제해석]

1. M x N 2차원 지도가 입력으로 들어온다.

2. 0이면 지나갈 수 있고, 1이면 지나갈 수 없다.

3. 위에서부터 시작해 맨 아래에 도달할 수 있는지 판별하는 알고리즘을 구현해라.

[알고리즘설계]

1. 입력을 String으로 받아서 Int로 한 글자씩 쪼개서 2차원 int형 배열에 저장해준다.

2. 제일 위에 줄에서 0인 값들을 queue에 저장한다.

3. queue를 이용해 BFS 탐색을 진행하고, BFS 탐색이 끝나기 전에 아래에 도달하면 "YES", 아래에 도달하지 못하고 BFS 탐색이 끝나면 "NO"를 출력한다.

#include<iostream>
#include<queue>
#include<string>

int map[1000][1000];
bool visited[1000][1000];

using namespace std;

int main(void) {
	int row, column;
	string input;
	queue<int> x;
	queue<int> y;

	cin >> row >> column;
	
	// 입력을 받고, 시작 점들을 셋팅한다.
	for (int i = 0; i < row; i++) {
		cin >> input;
		for (int j = 0; j < column; j++) {
			map[i][j] = int(input[j] - '0');
			if (i == 0 && map[i][j] == 0) {
				x.push(i);
				y.push(j);
				visited[i][j] = true;
			}
		}
	}
	// BFS 탐색을 하자.
	while (!x.empty() && !y.empty()) {
		// 오른쪽으로 갈 수 있는지 Check 하자.
		if (y.front() != (column - 1) && visited[x.front()][y.front() + 1] == false && map[x.front()][y.front() + 1] == 0) {
			x.push(x.front());
			y.push(y.front() + 1);
			visited[x.front()][y.front() + 1] = true;
		}
		// 왼쪽으로 갈 수 있는지 Check 하자.
		if (y.front() != 0 && visited[x.front()][y.front() - 1] == false && map[x.front()][y.front() - 1] == 0) {
			x.push(x.front());
			y.push(y.front() - 1);
			visited[x.front()][y.front() - 1] = true;
		}
		// 위로 갈 수 있는지 Check 하자.
		if (x.front() != 0 && visited[x.front() - 1][y.front()] == false && map[x.front() - 1][y.front()] == 0) {
			x.push(x.front() - 1);
			y.push(y.front());
			visited[x.front() - 1][y.front()] = true;
		}
		// 아래로 갈 수 있는지 Check 하자.
		if (x.front() != (row - 1) && visited[x.front() + 1][y.front()] == false && map[x.front() + 1][y.front()] == 0) {
			if (x.front() == (row - 2)) {
				cout << "YES";
				return 0;
			}
			x.push(x.front() + 1);
			y.push(y.front());
			visited[x.front() + 1][y.front()] = true;
		}
		x.pop();
		y.pop();
	}
	cout << "NO";
	return 0;
}

문제가 쉬워서 코딩도 금방 할 수 있었지만, 코드에 반성해야 할 부분이 많은 것 같다...

안녕하세요

여행벌입니다.

오늘은 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) 이라는 말도 안 되는 차이를 가진 알고리즘이 만들어졌다.

공부하자...