태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.


2014.08.20 06:01

[홍보] LG Code Challenger

https://www.lgcodechallenger.com


LG Code Challenger 는 프로그래밍 경진 대회로 우수한 성적으로 입상하는 사람에게는 서류전형을 면제해주는 채용 프로세스입니다.

(첫 대회는 9월 2일에 시작합니다)


LG전자 Coding Expert 들이 주도적&자발적으로 HR에 직접 건의하여 (회사를 취미로 다니시는 한 분이 구xx 부회장과 온갖 높으신 분들께 Direct로 메일을 쏘기도 하였죠 ^^) 만든 채용 프로세스 입니다.


타겟은 학벌, 학점, 영어점수 등은 부족하지만 탄탄한 CS 백그라운드와 코딩을 잘하는 친구들을 채용하고자 함 입니다.


물론 그 기반에는 학점, 학벌, 토익점수 따위는 실력보다는 당연히 덜 중요하고, 이러한 프로그래밍 경진 대회를 잘 하는 것 만으로도 충분히 CS 백그라운드와 코딩 실력을 검증할 수 있고, 또 그런 친구들이 실무도 잘할 것 이라는 "믿음"이 있습니다.


문제는 아직까지는 "믿음"만 있을 뿐이지 실제적인 "데이터" 가 없다는 것 입니다.


그래서 아직까지는 시범적이고 채용비율도 낮은 편 입니다.


그래서 많은 학생분들에게 관심과 참여를 부탁 드리고 싶습니다.


실력있는 학생들이 많이 응시하고 또 이 경로를 통해 입사해서 성과를 내야 점점 HR에서도 신뢰를 할 것 이고 채용 비율을 늘려가고, 학생들 뿐만 아니라 경력직 채용으로도 확장할 수 있습니다.


그리고 이러한 작은 움직임들이 취업을 위해 과도하게 학점과 영어성적에만 몰두하여 정작 필요한 전공공부는 소홀히 하는 현상을 타파하는데 기여할 수 있지 않을까요. 너무 거창한가요 ^ㅇ^


문의사항은 support@lgcodechallenger.com 으로 메일 주시고 건의사항이나 기타 의견 있으시면 제게 알려주세요.(kwangswei@gmail.com) 취합해서 HR에 전달하도록 하겠습니다.


많은 참여 부탁 드려요!

저작자 표시
신고
Trackback 0 Comment 2
  1. 2014.08.26 10:52 address edit & del reply

    비밀댓글입니다

  2. 2014.08.26 16:04 address edit & del reply

    비밀댓글입니다

2014.03.05 11:13

[손코딩뇌컴파일눈디버깅] 17회. TopCoder SRM 611 대회 같이 참여하기

TopCoder SRM 611 Editorial

500 - LCM Set Easy

Problem Analysis

이 문제는 숫자 집합이 주어졌을 때 아무 조합이나 선택해서 해당 조합의 최소 공배수가 입력으로 주어진 x 를 만들 수 있는 지를 판별하는 문제입니다.

가장 먼저 Brute force 방법으로 접근해보면, 

각 숫자를 조합에 포함시킬 지 말지를 결정하면서 해당 조합의 LSM을 구해서 x와 비교하는 방법이 되겠습니다만,
이 방법은 2가지 힌트를 통해서 정답이 될 수 없음을 알수 있습니다.

  1. 숫자 집합의 최대 크기가 50 이라는 점. 50개의 조합은 총 2^50 만큼이 있고, 이는 10^15 으로 연산량이 너무 많아 시간 초과됩니다.
  2. 각 숫자의 범위가 1~십억 입니다. 즉, 각 숫자들의 곱셈을 통해서 최소 공배수를 구해 답을 구하려는 접근은 연산 오버플로우가 날 수 있습니다.

최소 공배수 구하기

위의 Clue를 가지고 저희는 예제를 분석하면서 최소 공배수를 구하기 위한 소인수 분해에 힌트가 있을 것이라는 직관을 갖고 문제를 분석했고,
최종적으로 정답을 찾긴 했습니다만 그 과정이 너무 오래 걸려 문제 정답을 제출하지를 못했었습니다.

그래서 집에 와서 최소 공배수에 대해 검색해보니 최소 공배수를 구하는 법은 총 3가지가 있더군요.

  1. 수의 공배수 들을 나열한 뒤에 중복되는 가장 작은 공배수를 선택하는 방법
  2. 소인수 분해 한 후에 소인수들을 다 곱하되 각 소인수의 가장 큰 지수들을 택해서 모두 곱해주는 방법
  3. 유클리드 호제법

아마 학창시절에 우리는 3번만 주구장창 배워서 공식으로 외우고 문제를 풀었을 것이라 생각이 드네요.
그래서 최소공배수를 찾는 방법을 찾아내기 까지 애를 먹지 않았나 싶습니다. 
(저는 초중고 시절에 저랬습니다... ㅠ.ㅠ 지금의 공부 방법을 그 때도 알았더라면...흐규규)

어쨌든 위에서 말한 2번째 방법이 이 문제의 Key 이고 저 사실만 알았다면 사실 이 문제는 너무나도 쉽게 풀렸을 것 같습니다...

Design

아래와 같은 절차로 풀 수 있겠습니다.

  1. X를 소인수 분해해서 각 소인수와 지수 값을 구해 놓는다.
  2. 숫자 셋의 숫자를 각각 소인수 분해해서 각 소인수와 지수 값을 구해 놓는다.
    1. 해당 숫자(N)에는 포함되어 있는 소인수가 X에는 포함되어 있지 않다면 이 수는 곱해져서는 안되므로 후보에서 제외한다.
    2. N과 X의 소인수 집합이 같다 하더라도 X의 지수보다 N의 지수가 크다면 마찬가지로 후보에서 제외한다.
  3. 후보들만 모두 추려낸 후 X의 소인수와 지수 값들이 후보들에 포함되어 있는지 확인하여 모두 포함되어 있으면 Possible, 그렇지 않으면 Impossible

Code


#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
using namespace std;
map<int, int> intgetPrimes( x) {
    map<int, int> result;
    int num = 2;
    int end = sqrt(x) + 2;
    while (num < end && x > 1) {
        if (x % num == 0) {
            result[num]++;
            x /= num;
        }
        else
            num++;
    }
    if (x > 1)
        result[x]++;
    return result;
}
bool isPossible(map<int, int> n, map<int, int> x) {
    for (auto i : n)
        if (x[i.first] == 0 || x[i.first] < i.second)
            return false;
    return true;
}
string include(vector<int> numbers, int x) {
    map<int, int> x_primes = getPrimes(x);
    vector<map<intint,>> primes;
    for (int n : numbers) {
        auto n_primes = getPrimes(n);
        if (isPossible(n_primes, x_primes))
            primes.push_back(n_primes);
    }
    for (auto x : x_primes) {
        bool possible = false;
        int prime = x.first;
        int cnt = x.second;
        for (auto p : primes) {
            if (p[prime] == cnt) {
                possible = true;
                break;
            }
        }
        if (!possible)
            return "Impossible";
    }
    return "Possible";
}
int main() {
    vector<int> test = {100, 200, 300, 400, 500, 600};
    int x = 8000;
    cout << include(test, x) << endl;
    vector<int> test1 = {2,3,4,5};
    int x1 = 20;
    cout << include(test1, x1) << endl;
    vector<int> test2 ={1000000000,999999999,999999998};// {1,2,3,4,5,6,7,8,9,10};
    int x2 = 999999999; //24;
    cout << include(test2, x2) << endl;
    return 0;
}

후기

아무래도 대회는 혼자 차분히 푸는 게 더 좋은 것 같습니다. (sad)

그렇지만 여럿이 푸니 재미는 있더군요. 모여서 풀되 각자가 모두 Registration 하고 각자의 문제에 더 집중할 수 있으면 더 좋을 듯 합니다. (smile)

최소 공배수를 구하는 방법의 아주 기초적인 원리와 개념도 몰랐던 것이 조금 부끄럽습니다. (sad)

그래도 우리가 토론을 통해 최소 공배수를 구하는 방법을 찾아내었다는 것이 만족 스럽습니다. (smile)


저작자 표시
신고
Trackback 2 Comment 0
2013.12.24 17:04

[손코딩뇌컴파일눈디버깅] 8회. The number game

SRM574 Division II 500 - The Number Game


Problem

숫자 A, B 를 고른다. A != 0 && B != 0

목표는 A에서 시작하여 B까지 가는 것.

길은 2가지.

1) A를 10으로 나누거나,

2) A를 뒤집는 것.

만약 12849 라면 1284 or 94821.


A, B가 주어질 때 A로부터 B를 얻을 수 있으면 최소 이동 숫자를, 그렇지 않은 경우 -1 을 반환.


Solution

이번 문제는 여러 풀이 방법이 있겠지만 그 중에서 두가지 풀이 방법을 보겠습니다.


  1. Breadth First Search

  2. Optimized Brute Force


두 풀이 방법 모두, 아니 이 문제 뿐만 아니라 일반적인 전체 탐색 문제에서는 항상 탐색 공간을 화이트보드에 그려보면 좋습니다. 그럼 어떤 것을 고려해야 하는 지 사전에 파악할 수가 있습니다.


만약 A 라는 숫자가 abc 라는 3자리 숫자일 때 탐색 공간은 두 가지 경우로 확장됩니다.

1) 10으로 나눈 ab 가 되거나,

2) 뒤집은 cba 가 되거나.

그리고 각각의 결과인 ab 와 cba 에 대해서 반복하면 아래와 같은 트리 형태가 됩니다.


            abc

ab        cba

a ba    cb abc

    b           ab c          bc    ab              cba


이렇게 트리를 그리다보면 무한 루프에 빠지게 됩니다. 바로 abc -> cba -> abc -> cba ………

따라서 한 번 탐색한 것을 다시 탐색하면 안된다는 사실을 알 수 있습니다.


Optimized Brute Force 도 이것을 이용합니다. 한 번 reverse 했을 경우 다시 reverse 하면 안된다는 것을 토대로 구현하는 것이지요.


제가 이 문제를 처음 풀었을 때는 Optimized Brute Force 를 이용해서 풀었습니다만, 사실 저는 BFS 로 풀 것을 더 권하는 편입니다. BFS 는 정형화된 형태로 구현하기가 용이하고 또 오랜 시간 사용되면서 검증이 되었기 때문에 버그의 확률도 더 낮을 것이고요.


BFS 로 풀 때의 절차는 아래와 같습니다.

1. 숫자,  이동횟수 를 담을 queue 를 준비한다.

2. 숫자 A 를 queue 에 넣는다

3. queue 에서 숫자 한 개를 꺼낸다.

4. 답과 같은지 비교한다.

5. 답이 아닌 경우 가능한 2가지 숫자를 queue 에 넣는다. 이 때 중복 체크를 반드시 한다.

6. queue 가 비어 있을 경우 -1 을 반환한다.


한 단계 더 나아가서 좀 더 디테일하게 작성하면 더 좋겠지만 여기까지…!


Code


int reverse(int num) {
	int result = 0;
	while (num) {
		result += result * 10 + num % 10;
		num /= 10;
	}
	return result;
}

int getMinimumMoves(int A, int B) {
	queue<pair<int,int> > q;
	set<int> s;
	
	q.push(make_pair(A, 0));
	s.insert(A);
	
	while (!q.empty()) {
		int a = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		if (a == B)
			return cnt;
		
		int a1 = a / 10;
		int a2 = reverse(a);
		
		if (s.find(a1) == s.end()) {
			q.push(make_pair(a1, cnt+1));
			s.insert(a1);
		}
		if (s.find(a2) == s.end()) {
			q.push(make_pair(a2, cnt+1));
			s.insert(a2);
		}
	}
	
	return -1;
}

Test

저는 아래 5가지 경우를 체크해봤습니다.

  1. A/10 만으로 답이 나오는 경우 : A(123), B(1)

  2. Reverse(A) 만으로 답이 나오는 경우 : A(123), B(321)

  3. 두가지 조합으로 답이 나오는 경우 순서에 따라 2개 : A(123), B(21) 와  A(123), B(32)

  4. 답이 없는 경우 : A(123), B(4)


어떤 테스트 케이스가 더 필요할까요?

Feedback

  • 문제를 풀 때 작은 케이스에 대해서 abc 와 같이 symbol을 사용하여 정리하니 훨씬 이해하기가 좋은 듯 하다.

  • 전체 탐색 문제는 항상 탐색 공간을 그림을 그려보기를 추천!!

  • 개인적으로는 4명이서 오븟하게 하다 보니 많은 이야기를 할 수 있어서 좋았습니다.
    Test 관련 이야기, Optimized Brute Force 로도 풀어보고, BFS 로도 풀어보고, 각각의 개념에 대해서 이야기 해보고,
    또 Dynamic Programming 이야기가 나와서 그걸로도 해보고, DFS 와 BFS 의 차이에 대해서 이야기 해보고,
    재귀의 경우 Depth 가 깊어질 테고, BFS 는 별도의 queue와 set 이 필요한 데 어떤게 좋을지에 대해 이야기 해보고 등등등
    사람이 많을 때보다 더 많은 이야기를 할 수 있어서 좋았던 것 같습니다.
    무튼 앞으로도 3명 이상이면 무조건 고고 입니다. 



저작자 표시
신고
Trackback 0 Comment 0
2013.12.11 13:25

[손코딩뇌컴파일눈디버깅] 6회. WorfDelayMaster

지난 5회 모임 때는 글을 올리고 나서 기존 참여자분들께 메일을 드렸더니 약 20분 만에 거의 신청이 마감되어서
게시판에 공지글을 올리지 않았었습니다. 그 결과 처음 참여하시는 분들이 한 분도 안 계셨었는데요.
새로운 분들의 참여를 유도하고자 이번 회에는 별도로 메일을 드리지 않을 예정입니다. (smile)

11월 월례조회 때 현 소프트웨어플랫폼 연구소장님이신 민경오 연구소장님께서
"제가 생각하는 바람직한 소프트웨어 엔지니어가 갖추어야 할 역량" 으로
Programming Skill, Domain Knowledge, Communication Skill 을 꼽으셨습니다.

저희 손코딩뇌컴파일눈디버깅은,
문제의 솔루션을 타인과 토론하고 검증하고 결론을 도출해내는 과정을 통해 Communication Skill 을 키우고,
솔루션을 간단하고 정확하게 손으로 화이트보드에 구현하는 연습을 통해 Programming Skill 을 연습하는 모임입니다.

Welcome to 손코딩뇌컴파일눈디버깅!!!!

 

모임 안내

  • 일시 : 2013.12.10(화) 18:30 ~ 21:00  (매주 화요일에 있습니다.)
  • 장소 : 서초R&D센터 14층 교육실 1.
  • 참가자 : 하광성, 김선갑, 박주용, 정상범, 박지연, 장정훈, 배성호, 맹상우, 이준우, 전찬훈, 양종열, 이영한, 김용헌, 김명철, 권준호, 하명환,
  • 간식 : 김밥 및 음료 (110,455 + 19,500 = 129,955)

Editorial

문제

[6회] TopCoder SRM 593 Division Two - Level Two - WolfDelaymaster
http://community.topcoder.com/stat?c=problem_statement&pm=12778&rd=15705 

  

문자열이 주어졌을 때 이 문자열이 Valid 한 지를 체크하는 함수를 구현하는 것!


Valid 조건
1) 양의 정수 n 에 대해서 n개의 ‘w’, ‘o’, ‘l’, ‘f’ 가 이어지면 Valid!
2) valid 한 문자열끼리 이어 붙여 놓은 것 역시 Valid!


예를 들면, 
조건 1) 에 의해서 “wolf”, “wwoollff”, “wwwooolllfff” 는 Valid!
조건 2) 에 의해서 “wolfwwoollff” 는 Valid! 반복적으로 적용해보면 “wwwooolllfffwolfwwoollff” 도 Valid!


함수 정의 : string check(string str) 
- 모임에서는 제가 bool isValid(string str) 이라고 드렸는데 문자열을 반환하는 거였네요. 몹쓸 기억력…. 뭐 “VALID” “INVALID” 대신 true, false 반환 하는 정도니 큰 문제 없겠죠? :)


문제 이해 및 제약 조건 확인 하기

질문) 문자열의 길이는?
1 <= str.size() <= 50 (길이가 0인 문자열은 없다고 가정할게요~)


질문) 시간, 공간 복잡도는?
시간은 1초, 공간은 메모리 허용 범위 내


질문) 대소문자 구분은?
없음!


질문) ‘w’, ‘o’, ‘l’, ‘f’ 외에 다른 문자가 있는지?
없음!


질문) 문자열의 길이가 50을 초과하면??
그런 경우는 없다고 가정!

문제 풀이.

모임에 여러 번 나오신 분들은 이번 모임 문제는 상대적으로 생각할 것도 적은 것 같고 문제도 쉽다고 느끼셨을 것 입니다. 
실제로도 문제 제약 사양도 충분히 드렸고요. 
입력 문자열 50개에 1초 정도면 O(N^3) 으로 돌려도 충분할 정도의 크기이고 메모리도 제한이 없도록 했습니다.


Why???

이번 모임에서는 “구현의 용이성 & 가독성” 을 강조하고 싶었기 때문입니다. :)

  


우선 이 문제에서 중요한 포인트는 각 문자 별 연속되는 개수가 동일해야 한다는 점.
그리고 그 문자들의 순서가 중요하다는 점.


이 두가지 포인트를 만족하는 솔루션들은 여러가지가 나올 수 있습니다.
(
모임에서 각 조마다 다른 솔루션의 구현이 나와서 개인적으로는 좋았습니다.)

  1. w, o, l, f 각각의 개수를 일단 센 다음에 그 개수가 일치하는 지 체크하는 방법.

    1. 현재 위치에서부터 연속된 w의 개수를 센다.

    2. 계속해서 연속된 o 의 개수를 센다. l, f 도 동일하게 센다.
    3. 각 4문자의 연속된 개수들이 같은지 확인한다.

  2. State Machine

    1. 아무래도 순서가 중요하다보니 state machine 을 떠올릴 수 있을 것 같습니다.

    2. 실제 제가 이 문제를 화이트 보드에 풀었을 때 제일 먼저 떠오른 솔루션 역시 State machine 이었습니다. :)

  3. w의 개수를 먼저 센 다음에 그 개수만큼 o, l, f 를 세면서 만족하는 지 체크하는 방법.

    1. w의 개수를 먼저 센다.

    2. 다음 인덱스부터 차례대로 o, l, f 가 w의 개수만큼 나오는 지 확인한다.

  4. Valid 한 문자열 셋을 마련해놓고 재귀적으로 문자열 비교를 통해 구현하는 방법.

    1. 처음에는 wolf 와 문자열의 앞 부분을 비교한다.

    2. invalid 면 다음 문자열인 wwoollff 와 비교하고를 반복.

    3. valid 면 문자열의 뒷 부분이 재귀적으로 valid 한 지 체크.

  

이렇게 다양한 솔루션들이 나왔을 때 보통 직관적으로 어떤 게 좋겠다 판단해서 구현을 하는데 사실 정확한 “직관” 을 키우기 위해서는 많은 훈련이 필요한 것 같습니다.


물론 가장 좋은 것은 “모두 구현한 후에 비교해보기” 입니다. 굉장히 많은 도움이 되고 추천 드리고 싶은 방법인데 문제는 시간이 많이 소요 되겠죠.


제 생각에는 이런 식으로 훈련할 수 있을 것 같습니다.
1) 솔루션을 최대한 구현에 가깝게 말 또는 글로 표현해본다.
2) 이 때 필요한 기능은 무엇이고, 그 기능을 어떻게 구현하면 될 지 간략하게 생각해본다.
3) 각 기능 구현을 위해 필요한 자료형이 무엇이고, 내가 추출해야 하는 데이터는 무엇인지, 혹은 관리해야 하는 자료는 무엇인지, 각 기능 별로 독립적인지 등등을 파악한다.
4) 이렇게 비교할 Factor 들이 추려지면 비교하여 선택!


사실 글로 풀어보니 장황한 것 같은데 많은 분들이 머리 속에서 이미 이와 같은 작업을 하고 선택을 하셨을 겁니다. 

다만 내 머릿 속에 있는 것보다 더 꼼꼼하게 표현해보지 않으면 놓치고 가는 부분이 많을 것이고, 그러다 보면 코드로 풀어낼 때 복잡도는 예상치 못한 만큼 증가하겠지요. 

머릿 속에 있는 생각을 코드로 풀어내는 과정에서 복잡도는 엄청 상승한다는 것!


구현.

이번 모임의 주제가 구현의 용이성 및 가독성 인만큼 4가지를 모두 구현해서 비교해보도록 하겠습니다.


먼저 구현에 들어가기 전에 간단한 설문 조사를 했었지요. 어떤 솔루션이 가장 구현이 쉽고 가독성이 좋을 것 같냐는 질문에
1번은 0명.
2번은 약 2명
3번도 2~3분
4번이 무려 6분 정도 였습니다.


먼저 첫 번재로 제가 스터디에서 풀었던 방법 입니다. 안타깝게도 0표를 받은 1번 방식입니다.

저는 나름 직관적이고 구현하기 편하겠다 생각했는데 의외의 투표 결과가…. ㅋㅋ


string check(string str) {     int index = 0;     while (index < str.size()) {         int w_cnt = get_count(str, index, 'w');         int o_cnt = get_count(str, index, 'o');         int l_cnt = get_count(str, index, 'l');         int f_cnt = get_count(str, index, 'f');         if (w_cnt != o_cnt || w_cnt != l_cnt || w_cnt != f_cnt || w_cnt == 0)             return "INVALID";     }     return "VALID"; }

int get_count(string from, int& index, char c) {     int cnt = 0;     while (index < from.size() && from[index] == c) {     index++;     cnt++;     }      return cnt; } 


두 번째로 State machine 입니다.

저는 이 코드를 구현하면서 확신했습니다. 아 이건 아니다….. 이실직고 하자면 겁나 오래 걸렸습니다. 쳐다보기도 싫군요…..


string check(string str) {     map<char, char> prev_state = {{'w', 'f'}, {'o', 'w'}, {'l', 'o'}, {'f', 'l'}};     int cnt = 0;     int w_cnt = 0;     char state = 'f';     for (int i = 0; i < str.size(); ++i) {         if (prev_state[str[i]] != state && str[i] != state)             return "INVALID";         if (str[i] == state) {              cnt++;          }         else if (prev_state[str[i]] == state) {             if (str[i] == 'o')                 w_cnt = cnt;              if (w_cnt != cnt)                  return "INVALID";              cnt = 1;              state = str[i];          }      }      return state == 'f' && w_cnt == cnt ? "VALID" : "INVALID"; }


세 번째로 w의 개수를 세고 나서 o, l, f 가 그 개수만큼 만족하는 지 체크하는 방법.
구현에 따라 달라지겠지만 매번 index 를 주의 깊게 체크해야 한다는 점! 
조심해야겠습니다.


이 방법도 구현하고 보니 그리 복잡해보이지는 않네요.


아 그리고 모임할 때는 미처 잡지 못했는데 많은 분들이 구현하실 때 w 의 개수를 세어본 다음에 w의 개수가 0이면 invalid 처리를 하셨는데요. 
w의 개수를 세어볼 필요 없이 먼저 첫 글자가 ‘w’ 인지를 확인해서 아니면 invalid 처리하는 게 비교문을 한 번이라도 줄일 수 있겠네요!

 

string check(string str) {      char comp[3] = {'o', 'l', 'f'};      int index = 0;      while (index < str.size()) {          if (str[index] != 'w')              return "INVALID";           int w_cnt = 0;          while (str[index] == 'w' && index < str.size()) {               w_cnt++; index++;          }              for (int i = 0; i < 3; ++i) {              for (int j = 0; j < w_cnt; ++j) {                  if (index >= str.size() || str[index] != comp[i])                      return "INVALID";                  index++;              }          }     }      return "VALID"; }



네 번째로 재귀!

아…. 다시는 이런 무모한 짓 하지 않겠습니다…….
“이건 숙제로 남기겠습니다” 라는 좋은 방법이 있는데…….

string get_comp(int i) {      return string(i, 'w') + string(i, 'o') + string(i, 'l') + string(i, 'f'); }

string check(string str) {      if (str.size() == 0)          return "VALID";      for (int i = 1; i <= str.size() / 4; ++i) {          string comp = get_comp(i);          if (str.compare(0, i*4, comp) == 0)              return check(str.substr(i*4));      }      return "INVALID";  

} 



휴우!!!!!

제 나름대로 신경 쓴다고 생각하고 구현해봤습니다.

각 방법 간의 장, 단점 및 성능 등의 평가, 코드 리뷰, 버그 찾기 등은 숙제로 남기겠습니다..... ㅋㅋ

이제 다시 투표를 해보실까요? 
어떤 코드를 더 선호하시는지요??

  

그 밖의 코멘트 또는 피드백

  • 운영 방식 두 가지 모두 장단점이 있는 듯.

    • 같이 토론하는 방식은 서로가 많이 커뮤니케이션을 해볼 수 있다.

    • 솔루션을 공유하고 하면 코딩에 좀 더 집중할 수 있다.

    • 당분간 섞어서 운영.

  • 말과 글로 화이트 보드에 구현 전략(각 단계에 대한 설명)을 반드시 써보도록 가이드 하자.

  • 구현 전략은 코드 리뷰 시에는 가급적 보지 않고 이해하도록 해보고, 잘 모르겠으면 질문을 하자!

  • 알고리즘 선택 시 기준을 정의해보자.

    • 구현 방법이 여러개 일때 선택하는 것은 직관에 의해서 선택이 되고는 하지만 그 직관이라는 것은 연습에 의해 키울 수 밖에 없다.

    • 따라서 알고리즘 별로 필요한 기능, 데이터, 예외 등을 체크해서 선택하는 것이 좋겠다.

    • But, 제일 좋은 건 다 구현해보는 것! (은 취소하고 싶어지네요 갑자기…)

  • 코드가 올바른 결과를 내는지 증명하기 위해서는,

    • 코드의 변경점(루프의 경우 루프 불변식, 루프 횟수, 조건문의 각 조건별 동작 등등)에 대해서 증명이 필요한 데 당연히 증명할 게 적을수록 버그가 없을 확률이 높고 시간도 더 적게 걸릴테니 이런 관점에서 비교해보는 것도 좋을 듯!

  • 좀 더 어려운 문제도 있었으면!!

    • 다양한 솔루션이 나올 수 있으면서 솔루션 간에 난이도도 좀 다를 수 있는 문제면 좋을 듯???

  • 문제가 쉬워서 코딩에 집중할 수 있었다. 모임에서 강조하고자 하는 바를 잘 반영하는 문제 선정이 되면 좋겠다.

    • 네! :)

    • 모임에서 다뤘으면 하는 문제 카테고리에 대해서 피드백을 주면 적극 반영하겠음!

  • 코드 리뷰 시에 막연히 버그 잡고 질문하라고 하니 서로가 조용한 것 같다.

    • 조를 나눠서 한 조는 테스트케이스 1을 테스트 하고, 다른 조는 테스트 케이스 2를 테스트하고, 한 조는 최적화에 집중해보고, 
      한 조는 또 다른 포인트에 집중해서 보는 등, 코드 리뷰 방법의 개선이 필요하다는 생각을 했음.

    • 성능 및 최적화 분석이 필요한 문제도 다뤄보면 좋겠다는 생각도 했음.



저작자 표시
신고
Trackback 1 Comment 1
  1. XRumerTest 2013.12.23 04:31 신고 address edit & del reply

    Hello. And Bye.

2013.12.04 09:12

[손코딩뇌컴파일눈디버깅] 5회. Batch System

[5회] TopCoder SRM 481 Division Two - Level Three - Batch System


문제
http://community.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234


한 번에 한 가지 job을 처리할 수 있는 컴퓨터가 있다. 컴퓨터가 처리해야 하는 job은 int [] duration 과 string[] user 로 주어진다.

duration[i] 는 i번째 job 을 처리하는데 드는 시간(분) 이고, user[i] 는 해당 job 을 요청한 유저의 이름이다. 유저는 여러 개의 job을 요청할 수도 있다.

한 유저의 대기시간은 해당 유저가 요청한 일이 모두 끝날 때까지 기다리는 시간의 합을 의미한다. 모든 유저의 평균 대기 시간이 가장 짧도록 스케쥴링을 하는 것이 목적이다.


int [] duration 과 string[] user 가 주어졌을 때 평균 대기 시간이 가장 짧도록 수행해야 하는 job들의 순서 int [] 를 반환하도록 프로그램하라.


Method signature: vector<int> schedule(vector<int> duration, vector<string> user)



질문) 답이 여러 개 일 경우는? -> 사전 순서대로 출력. 즉, 인덱스가 작은 것 부터.

질문) 값의 범위는??

1 <= duration.size() <= 50.

1 <= duration[x] <= 1,000,000,000

질문) user 이름의 길이나 대소문자 구분은? -> 이름은 50자 이하이고, 대소문자는 구분한다.

질문) 대기시간의 정의는? -> 시작 시간부터 내가 요청한 모든 job 이 끝날 때까지의 누적 시간.


문제 풀이.


먼저 단순한 케이스부터 고려해봅시다.

만약 User 별로 1개의 작업만 요청할 수 있다고 가정해보지요. 어떻게 하면 각 User의 평균 대기 시간을 짧게 할 수 있을까요.


평균 대기시간을 짧게 한다는 것은 곧 모든 유저의 대기시간의 합을 최소화하는 것과 같습니다.


user1, user2, user3 의 job 을 각각 a, b, c 라고 해봅시다.

이 경우 각 user 별 대기 시간은,

user1 = a

user2 = a + b

user3 = a + b + c

즉, 모든 user의 대기시간의 합은 3a + 2b + c.

따라서 a <= b <= c 인 경우에 대기 시간의 합이 최소가 될 수 있습니다. 그러므로 가장 짧은 Job 부터 처리해야 합니다.


그렇다면 이제 각 User 별 여러 개의 Job 이 존재할 때의 경우를 생각해봅시다.

user1 에게 a, b 의 job 이 있고, user2 에게 c 의 job 이 있다고 합시다. a, b, c의 절대적인 duration 값은 모른다고 할 때, 일을 처리하는 방식은 크게 3가지로 나눌 수 있을 것 같습니다.

1) a, b, c (앞 부분에 연속적으로 수행하는 방법)

2) a, c, b (둘을 떨어뜨려 놓는 방법)

3) c, a, b (뒷 부분에 연속적으로 수행하는 방법)


1)의 경우 대기시간의 총합은, a + b + a + b + c = (a + b + c) + (a + b)

2)의 경우 대기시간의 총합은, a + b + c + a + c = (a + b + c) + (a + c)

3)의 경우 대기시간의 총합은, c + a + b + c = (a + b + c) + c


여기서 우리가 알 수 있는 대소 관계는 2) > 3) 이라는 것 입니다.

즉 둘을 떨어뜨려 놓는 방법보다는 항상 대기시간이 더 짧은 둘을 연속적으로 실행하는 방법이 존재한다는 것 입니다.


따라서 이 문제는,

각 User의 Job별 duration의 합이 가장 짧은 User의 Job부터 수행하는 것이 최적이 됩니다.


단계 별로 정리하자면,

1) 각 User 별로 Job의 duration 의 누적합을 구한다.

2) duration의 누적합 순으로 정렬한다.

3) duration의 누적합이 작은 User 별로 job index 를 결과에 저장한다.


Data Structure 설계.

이번 문제의 핵심은 “Data Structure의 설계” 입니다.

Data structure 는 알고리즘에 절대적인 영향을 미치는 요인 입니다.


“생각하는 프로그래밍” 이라는 매우 유명한 고전 서적의 칼럼3의 제목은 “프로그램의 구조를 결정하는 데이터” 입니다. 즉, 데이터를 어떻게 표현하느냐에 따라 전체 프로그램이 달라진다는 것이지요. 이런 표현도 있습니다. “훌륭한 프로그래머는 코드를 작성하기 전에 그 프로그램이 사용할 입력과 출력, 그리고 중간의 데이터 구조에 대해 전반적으로 이해한다.” 바로 우리가 이번 모임에서 연습해야 할 Key Point 입니다.


아마 이 문제를 보고 처음부터 구조체를 정의해야 겠다라고 생각하고 시작하신 분들도 있을 것이고, 1번 단계만 보고 User 별로 duration 합을 구해야 겠다 싶어서 Map 과 같은 자료구조를 사용해서 하다가 2번 단계에서 Map은 정렬이 안되는 것을 보고 별도의 자료구조를 추가한 분들도 있을 것 입니다.


가급적이면 새로운 자료구조를 정의하기 전에 내가 필요한 데이터 표현은 어떤 것이고, 그 데이터를 표현하는 데에 기존의 자료구조를 활용할 수 없는지를 살펴 보고 그 후에 새로운 자료구조를 도입하는 것이 좋지 않나 싶습니다. 그래야 제대로 된 자료구조를 설계할 수 있을테니까요.


이번 문제에서 각 단계 별로 필요한 데이터 형태는 아래와 같습니다.


  1. User 별 duration 의 누적합.

    1. user 별로 저장하고 있어야 하므로 string-long long 의 짝이 필요하겠죠. Map<string, long long> 이나 vector<pair<string, long long> > 등을 사용해도 되겠지요.

  2. duration의 누적합 별로 정렬.

    1. 이 단계에서 아! Map 은 안되겠구나 싶은 생각이 드실 겁니다. Map은 이미 Key 로 정렬되어 있는 자료구조인데, duration 의 총합으로 정렬할 수는 없는 자료구조입니다. 그런데 여전히 vector<piar<string, long long> >은 사용할 수 있을 것 같습니다.

  3. User 별 job 목록.

    1. 여기서 vector<pair<string, long long> >을 사용할 수 없게 되었습니다. User 별로 총 duration의 합을 구할 때 어떤 job index 들이 포함되었는 지를 기억할 필요성이 생겼습니다. 따라서 vector<piar<string, long long> > 도 사용할 수 없게 되었습니다.


만약 1) 단계만 보고, 아! 이 자료형이면 충분하겠네~ 하며 구현을 시작했다면 단계3)에 다다랐을 때에는 새로운 자료구조를 도입해서 보완하거나 코드를 완전히 뒤엎어야 하는 상황이 될 수도 있습니다.


따라서 구현에 들어가기 전에 여러분은 각 단계에서 필요한 데이터를 뽑아보고, 그 데이터 표현이 다음 단계의 Input으로 사용해도 손색이 없는 지, 다음 단계에 어떤 영향을 미치는 지를 구현 전에 미리 검토해야 할 것 입니다.

또한 어떤 데이터 타입은 특정 단계의 구현은 쉽게 만들어주는 반면에 특정 단계에는 추가적인 처리가 필요해진다거나 등등의 Trade-off 가 발생할 수 있습니다. 그 경우에도 필요에 따라 의사 결정을 해야 할 것 입니다.


구현.

별도의 자료구조를 정의하기로 하여 아래와 같은 User 타입의 구조체를 정의하였습니다.

Object 와 Data structure의 차이는 도서 “Clean Code” 의 객체와 자료구조 챕터를 참조하세요. (지금 책이 없어서 정리를 못해드리겠네요 ^^;;; )


아래와 같이 operator< 를 재정의 하면 사용자 정의 타입도 std::sort() 에 의해 원하는 순서로 정렬을 할수 있습니다.

또한 operator== 를 재정의 해서 std::find() 도 사용하고 있고요.


schedule 함수의 내부가 3단계로 비교적 명확하게 구분이 되고 있습니다.

Python 과 같은 자료구조가 풍부하고 언어 차원에서 많은 소소한 것들을 처리해주는 언어들이 제공하는 장점을 언급할 때 빠지지 않고 나오는 말이 “로직에 집중할 수 있다” 라는 말이 있습니다.  이 코드도 자료구조를 잘 정의 했기 때문에 schedule 함수의 로직이 쉽게 눈에 들어올 것 입니다.



     struct User {

string name; long long duration; vector<int> jobs; User(string n, int d, int job) : name(n), duration(d) { jobs.push_back(job); } bool operator<(const User& other) const { return (duration == other.duration) ? jobs[0] < other.jobs[0] : duration < other.duration; } bool operator==(const User& other) const { return name == other.name; } }; vector<int> schedule(vector<int> duration, vector<string> user) { vector<User> users; for (int i = 0; i < duration.size(); ++i) { User u(user[i], duration[i], i); auto itor = find(users.begin(), users.end(), u); if (itor != users.end()) { itor->duration += u.duration; itor->jobs.push_back(i); } else { users.push_back(u); } } sort(users.begin(), users.end()); vector<int> result; for (int i = 0; i < users.size(); ++i) result.insert(result.end(), users[i].jobs.begin(), users[i].jobs.end()); return result; }




참고로 아래 코드는 별도의 자료구조를 정의하지 않고 구현한 TopCoder 에서 제공한 솔루션 입니다. 어떠신가요?



public int[] schedule(int[] duration, String[] user) {
    int n = duration.length, c = 0;
    int [] res = new int[n];
    boolean [] used = new boolean[n];
    
    while (c < n) {
        int pick = 0;
        long lowestDuration = Long.MAX_VALUE;
        for (int i=0; i<n; i++) {
            if( !used[i] ) {
                long dr = 0;
                for (int j=0; j<n; j++) {
                    if( user[i].equals(user[j]) ) {
                        dr += duration[j];
                    }
                }
                if (dr < lowestDuration ) {
                    pick = i;
                    lowestDuration = dr;
                }
            }
        }
        for (int i=0; i<n; i++) {
            if ( user[i].equals(user[pick]) ) {
                res[c++] = i;
                used[i] = true;
            }
        }
    }
    return res;
}



그 밖의 코멘트.

  • 각 단계 별 자료구조의 고민 없이 구현에 들어갔다가 코드를 뒤 엎는 경험. 자료구조는 알고리즘 및 프로그램의 전반적인 부분에 상당한 영향을 미친다는 것!

  • 언어의 특성을 떠나서 Data structure 에 대한 이해가 필요하다는 것. 데이터의 표현이 프로그램에 있어서 중요한 만큼 어떤 형태로 표현할 수 있는지, Data structure 에 대한 기본적인 이해가 중요하다는 것.

  • 내가 특정 기능의 세부적인 것까지 다 기억하고 있을 필요는 없지만 적어도 이런 기능이 있다라는 것은 인지하고 있어야 한다는 것. 따라서 이를 위해서는 좋은 코드를 많이 읽는 것이 필요하다.

  • 다양한 언어에 대한 이해가 필요하다. 풍부한 자료구조를 제공하는 언어에서는 로직에 집중할 수 있고, 데이터를 표현하고 처리하는 방식에 있어서 다양한 시각을 가질 수 있다.

  • 항상 강조하는 부분이고, 책에 좋은 표현이 있어 덧붙입니다.
    “코딩 기술은 정확한 프로그램을 작성하는 데 있어 작은 한 부분에 지나지 않는다. 작업의 대부분은…….. 문제 정의, 알고리즘 디자인, 데이터 구조의 선택이다. 이 작업들을 잘 해낼 수 있다면, 정확한 코드의 구현은 쉬운 것이 보통이다.
    ” - 생각하는 프로그래밍 p73.
    항상 고수준의 언어(잘 정리된 글이라던가 아니면 수도코드)로 문제를 잘 표현하면 그 표현 그대로 코드로 나타난다는 것을 연습해보면 좋겠습니다.

  • 소프트웨어 플랫폼 연구소장님이신 민경오 소장님께서 11월 월례회에서 “제가 생각하는 바람직한 소프트웨어 엔지니어가 갖추어야 할 역량” 으로 programming skill, domain knowledge, communication skill을 꼽으셨습니다. 손코딩뇌컴파일눈디버깅 모임은 programming skill과 communication skill을 연습할 수 있는 굉장히 좋은 Tool 이라 믿어 의심치 않습니다!! (깨알홍보)


저작자 표시
신고
Trackback 0 Comment 1
  1. Chanhun 2013.12.04 22:39 신고 address edit & del reply

    코드가 눈에 쏙쏙 들어오니 깔끔하네 ㅋ
    문제 자체는 매우 쉬워보이지만 자료구조에 메세지가 확실히 전달되어 참 좋았음 :)



티스토리 툴바