How We Coding

Week 2-1 : How to code Recursive function2

Tutoring/18-1 DS2018. 4. 4. 00:38

<180403>


1) 배열의 요소들 중 두번째 최대값 구하기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
int max;
 
int f2(int arr[], int n)
{
    int k;
    if(n == 1) {
        max = arr[n] > arr[n-1] ? arr[n] : arr[n-1];
        return arr[n] > arr[n-1] ? arr[n-1] : arr[n];
    }
    k = f2(arr, n-1);
    
    if(arr[n] < k) return k;
    if(arr[n] > max) { int t=max; max=arr[n]; return t; }
    return arr[n];
}
 
int main()
{
    int arr[] = {50, 10, 2, 30, 11, 33};
 
    printf("%d\n", f2(arr, 5));
    return 0;
}
cs


>> n 은 마지막 인덱스

>> 12 : k 에는 n-1번째 요소들까지에서의 두번째 최대값이 저장된다.


>> 14 : n번째 요소가 두번째 최대값보다 작은 경우.
>> 15 : n번째 요소가 최대값인 경우, 기본의 max값이 두번째 최대값이 된다.
>> 16 : 나머지 경우(n번째 요소가 두 번째 최대값)


2) 팰린드롬인지 판단한는 함수 재귀함수로 구현하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <string.h>
 
int isP(char str[], int s, int e)
{
    if(s >= e) return 1;
    return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
}
 
int main()
{
    char str[100];
    scanf("%s", str);
    isP(str, 0, strlen(str)-1) ? puts("True") : puts("False");
    return 0;
}
 
cs


>> 첫번째 인덱스와 마지막 인덱스의 문자가 같을때, 그 안의 문자열이 팰린드롬이면 팰린드롬이다.

>> noon, eye, 다시합창합시다 와 같은 문자열은 모두 팰린드롬이다.



3) 하노이 타워 이동 순서. 

- Hanoi(n, from, by, to) : n개의 쟁반을 from 에서 by를 거쳐 to로 옮기는 과정을 출력하는 함수.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
void Hanoi(int n, char from, char by, char to)
{
    if(n == 1) {
        printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to);
        return ; 
    }
    Hanoi(n-1, from, to, by);
    printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to);
    Hanoi(n-1, by, from, to);
}
 
int main()
{
    Hanoi(3, 'A', 'B', 'C');
    return 0;
}
cs


>> A 에 있는 n 개의 쟁반을 C에 옮기려고 함.


>> A 에 있는 n개의 쟁반들 중, n-1개의 쟁반을 B에 옮기고,

>> A 에 있는 n번째 쟁반을 C로 옮긴다.

>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기면 된다.


>> A 에 있는 쟁반들 중, n-1개의 쟁반을 B에 옮기는 과정을 출력하고,

>> A 에 있는 n번째 쟁반을 C로 옮긴다.

>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기는 과정을 출력한다.



>> 실행결과

1
2
3
4
5
6
7
1번 쟁반을 A에서 C로 이동.
2번 쟁반을 A에서 B로 이동.
1번 쟁반을 C에서 B로 이동.
3번 쟁반을 A에서 C로 이동.
1번 쟁반을 B에서 A로 이동.
2번 쟁반을 B에서 C로 이동.
1번 쟁반을 A에서 C로 이동.
cs



4) 별찍는 순서.


4-1)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    printf("*");
    f(n-1);
}
cs




4-2)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    f(n-1);
    printf("*");
}
cs



4-3)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    printf("*");
    f(n-1);
    f(n-1);
}
cs



'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05
Week 1-2 : How to code Recursive function  (0) 2018.03.30
Week 1-1 : C Lang review  (0) 2018.03.28

Week 6 - BFS (숨박꼭질)

Tutoring/PS2018. 3. 30. 13:29

<180331>   


Week 6 - BFS


[12851] 숨박꼭질2 (http://boj.kr/12851)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
c#include <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    
    int ok=0, ans=-1, cnt=0;
    while(!q.empty()) {
        int sz = q.size();
        ans++;
        for(int i=0; i<sz; i++) {
            int cur = q.front(); q.pop();
            visited[cur] = 1;
           
            if(cur == k) {
                ok = 1;
                cnt++;
                continue;
            }
 
            int next = cur+1; 
            if(next < MAX && !visited[next]) { q.push(next); }
 
            next = cur-1;
            if(0 <= next && !visited[next]) { q.push(next); }
            
            next = cur*2;
            if(next < MAX && !visited[next]) { q.push(next); }
        }
        if(ok) break;
    }
    printf("%d\n%d\n", ans,  cnt); 
}
cs


>> 방문체크를 꺼내면서 해야한다. 

>> ans 는 트리에서 레벨수회를 할 때 그 레벨을 세는 역할을 한다고 생각하면 될 것 같다.



[13529] 숨박꼭질3 (http://boj.kr/13549)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        int next = cur+1;
        if(next < MAX && (!visited[next] || visited[next]>visited[cur]+1)) {
            q.push(next);
            visited[next] = visited[cur]+1;
        }
        
        next = cur-1;
        if(0 <= next && (!visited[next] || visited[next]>visited[cur]+1)) {
            q.push(next);
            visited[next] = visited[cur]+1;
        }
        
        next = cur*2;
        if(next < MAX && (!visited[next] || visited[next]>visited[cur])) {
            q.push(next);
            visited[next] = visited[cur];
        }
    }
    printf("%d\n", visited[k]-1);
}
cs


>> 정답이 언제든 갱신될 수 있다고 생각했다. 그래서 다 돌리고 난 뒤에 저장되어 있는 값이 정답이라고 생각한 것을 코드로 옮겼다.

>> 다음에 방문할 위치가 현재위치보다 적은 시간에 방문할 수 있다면 다시 방문해야한다.



[13913] 숨박꼭질4 (http://boj.kr/13913)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int n, k, from[MAX];
 
void trace(int cur)
{
    if(cur == n) { 
        printf("%d", cur);
        return ;
    }
    trace(from[cur]);
    printf(" %d", cur);
}
 
int main()
{
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        int next = cur+1;
        if(next < MAX && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
        
        next = cur-1;
        if(0 <= next && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
        
        next = cur*2;
        if(next < MAX && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
    }
    printf("%d\n", visited[k]-1);
    trace(k);
}
cs


>> from 배열에 주목하자.

>> from[next] = cur; 은 next 의 이전 위치는 cur 이란 뜻이다.

'Tutoring > PS' 카테고리의 다른 글

Week 1 - DP1  (0) 2018.06.26
Week 7 - DFS+BFS  (0) 2018.04.07
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

Week 1-2 : How to code Recursive function

Tutoring/18-1 DS2018. 3. 30. 00:35

<180329>


- 재귀함수 만들기


1) 함수를 잘 정의하고, 그 정의를 그대로 활용하기

2) 어떻게 쪼갤지 생각하기..

3) 언제까지??(재귀의 종료, 탈출조건)

4) 점화식을 알고 있다면 그대로 표현하기.



- 구현해보기.


1) Sum(n) : 1부터 n까지의 합을 구하는 함수.


1
2
3
4
5
int Sum(int n)
{
    if(n < 1) return 0;
    return n + Sum(n-1);
}
cs


>> 1부터 n까지의 합은 1부터 n-1까지의 합에 n을 더하면 된다.

>> 1보다 작은 수가 들어오면 0을 리턴하면 될 것 같다.



2) evenSum(n) : 1부터 n까지의 수 중 짝수의 합 구하기.


1
2
3
4
5
6
int evenSum(int n)
{
    if(n < 1) return 0;
    if(n&1) n--;
    return n + evenSum(n-2);
}
cs


>> n이 짝수인 경우, 1부터 n까지의 수 중 짝수의 합은 1부터 n-2까지의 수중 짝수의 합에 현재 값을 더하면 된다.

>> n이 홀수일 수도 있으므로, 4번 라인에서 예외처리를 한번 더 한다.

>> 홀수의 경우 마지막 비트는 항상 1이다. 그러므로 홀수와 1을 비트연산을 하면 1이 나온다. 조건식에서 1은 참..!!



3) combi(n, r) : n개의 수 중 r개의 수를 뽑는 방법의 수.


1
2
3
4
5
int combi(int n, int r)
{
    if(r == 0 || n == r) return 1;
    return combi(n-1, r-1) + combi(n-1, r);
}
cs


>> 우리는 nCr = n-1Cr + n-1Cr-1 이라는 점화식을 알고있다....ㅎㅎ

>> 해당 점화식을 그대로 표현했을 뿐이다. 

>> 즉, n개의 수 중 r개의 수를 뽑는 방법의 수는 

     임의의 수 하나를 무조건 뽑는 다고 생각했을 때인, n-1개의 수 중 r-1 개를 뽑는 방법에 수와 

     그 임의의 수 하나를 무조건 안뽑는다고 생각햇을 때인, n-1개의 수 중 r 개를 뽑는 방법에 수를 더하면 된다.

>> 그리고 우리는 nC0 == nCn == 1 이라는 것을 알고 있다. 그대로 탈출조건에 적용하면 된다.



4) print1(n) : 1부터 n까지 출력하는 함수


1
2
3
4
5
6
void print1(int n)
{
    if(n < 1) return ;
    print1(n-1);
    printf("%d\n", n);
}
cs


>> 1부터 n까지 출력하는 것은 1부터 n-1까지 출력한 다음에 n만 출력하는 것과 같다.



5) print2(n) : n부터 1까지 거꾸로 출력하는 함수.


1
2
3
4
5
6
void print2(int n)
{
    if(n < 1) return ;
    printf("%d\n", n);
    print1(n-1);
}
cs


>> n부터 1까지 거꾸려 출력하는 것은 n을 먼저 출력하고 n-1부터 1까지 거꾸로 출력하는 것과 같다.



6) arrSum(int arr[], int n) : 배열 arr에서 0번째 값에서 n번째 값까지의 합을 구하는 함수.


1
2
3
4
5
int arrSum(int arr[], int n)
{
    if(n == 0) return arr[0];
    return a[n] + arrSum(arr, n-1);
}
cs


>> 배열 arr에서 0값 요소에서 n번째 값까지의 합은 배열 arr에서 0번째 값에서 n-1번째 값까지의 합에 n번째 값을 더하면 된다.



7) arrMax(int arr[], int n) :  배열 arr에서 0번째 값에서 n번째까지의 값 중 최대값을 구하는 함수


1
2
3
4
5
6
7
int arrMax(int arr[], int n)
{
    int k;
    if(n == 0) return arr[0];
    k = arrMax(arr, n-1);    
    return a[n] > k ? a[n] : k;
}
cs


>>  배열 arr에서 0번째 값에서 n-1번째까지의 값 중 최대값이 k라고 하자.

      then, k와 a[n] 중에서의 최대값이 배열 arr에서 0번째 값에서 n번째까지의 값 중에서 최대값이 된다.

>> 시각적인 이미지 참고 블로그(전에 설명 들은 동생이 정리해놨다..ㅎㅎ) : http://mattlee.tistory.com/17?category=680710



- 숙제 : 배열의 값들 중 두번째 최대값 구하기.

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05
Week 2-1 : How to code Recursive function2  (0) 2018.04.04
Week 1-1 : C Lang review  (0) 2018.03.28

Week 02

Tutoring/18-1 C Lang2018. 3. 28. 18:46

< 180328 >


1) 두 변수의 값 변경


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
int main()
{
    int a = 5;
    int b = 7;
 
    int t = a;
    a = b;
    b = t;
 
    printf("%d %d\n", a, b);
 
    a = 5;
    b = 7;
 
    a = a+b;
    b = a-b;
    a = a-b;
    printf("%d %d\n", a, b);
 
    return 0;
}
cs


>> a 컵에는 콜라, b컵에는 쥬스가 담겨있는 상황에서, 두 잔의 내용물을 바꾸고 싶을 때, 새로운 잔(t)를 이용하면 된다..!!

>> 17-19 는 새로운 변수 없이 두 정수값을 바꾸는 테크닉..?? 학교 교재에 있는 내용이라고 함..



2) sizeof 연산자 활용하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
 
int main()
{
    char ch = 'A';
    int n = 5;
    double d = 3.14;
 
    printf("char: %dbyte\n", sizeof(char));             // 1
    printf("int: %dbyte\n", sizeof(int));               // 4
    printf("flot: %dbyte\n", sizeof(float));            // 4
    printf("double: %dbyte\n", sizeof(double));         // 8
    printf("long: %dbyte\n", sizeof(long));             // 8
    printf("long long: %dbyte\n", sizeof(long long));   // 8
 
    printf("1: %dbyte\n", sizeof(1));           // 4
    printf("'A': %dbyte\n", sizeof('A'));       // 4
    printf("3.14: %dbyte\n", sizeof(3.14));     // 8
    printf("1LL: %dbyte\n", sizeof(1LL));       // 8
 
    printf("ch: %dbyte\n", sizeof(ch));         // 1
    printf("n: %dbyte\n", sizeof(n));           // 4
    printf("d: %dbyte\n", sizeof(d));           // 8
 
    return 0;
}
cs


>> 17 번 라인이 좀 특이하다. 1바이트를 기대했는데 4바이트가 나온다.

>> 관련 내용은 여기를 참고..!! (http://hashcode.co.kr/questions/76/cc에서-sizeofa의-차이)



3) 문자가 데이터에 어떻게 저장되는지..??


1
char ch = 'A';
cs


위 코드의 경우 ch 라는 변수는 메모리 1바이트(8비트)를 차지한다.

그리고 해당 8비트에서 최 상위 비트는 부호비트를 나타낸다. 0은 양수, 1은 음수..!!


'A' 의 정체는 아스키 코드값 10진수로 65에 해당한다.

65는 이진수로 01000001 이다

즉, 8비트 기준으로 01000001 의 형태로 저장이 된다.


상위 1비트는 부호비트 이므로 char 타입의 변수에는 -128 ~ 127 까지의 값을 저장할 수 있다. 

즉 256 개의 데이터를 저장할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    char a = 127;
 
    printf("%d\n", a);  // 127
 
    a = a+1;
    printf("%d\n", a); // -128
 
    return 0;
}
cs


>> 7 번라인의 결과는 127이다. 하지만 10의 결과는 128이 아닌 -128이 출력이 된다.


>> 127 은 2진수로 표현하면 01111111 이다. 여기에 1을 더하면 10000000 이 된다.

>> 최상위 비트는 부호비트인데 부호비트가 0에서 1로 변경되었다. 즉 음수가 되었다.


>> 다음 내용을 설명하기 전에, -1 이란 값에 대해 알아보자. 

>> -1은 8비트 기준 11111111 이며, 32비트 기준 11111111 11111111 11111111 11111111 과 같이 표현한 수 있다.

>> 즉 1로만 가득채워진다.

>> 증명 :  위 값에 1을 더하면 0이된다. 8비트 기준 100000000 이 되는데, 1는 비트 범위를 넘어가므로 버리게 되므로 00000000, 즉 0이 된다.


>> 그렇다면 11111111을 이용해서 10000000 을 만들어보자.

>> 11111111 에서 01111111 을 빼면 10000000 이 된다.

>> 즉 -1에서 127을 뺀 결과이며 위 결과는 정확하게 -128이 나오게 된다. 



4) 최상위 비트를 부호비트로 사용하지 않고싶다면..?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
int main()
{
    unsigned char a = 127;
 
    printf("%d\n", a);  // 127
 
    a = a+1;
    printf("%d\n", a); // 128
 
    a = 255;
    printf("%d\n", a); // 255
 
    a = a+1;
    printf("%d\n", a); // 0
 
    return 0;
}
cs


>> 변수를 선언할 때, 자료형 앞에 unsigned 를 추가로 선언하면 된다.

>> 11111111 은 255라는 값이 되며, 여기서 1을 더하면 0이 된다.



5) '1' vs 1


그러다면 위의 결과는..?


'1' 은 1바이트이며, '1'은 아스키코드값 10진수로 49에 해당한다. 

49는 이진수로 110001 이므로 00110001 의 형태로 저장이 된다.


1은 정수이므로 4바이트가 필요하다. 그리고 1은 이진수로 1이다

그렇기 때문에 00000000 00000000 00000000 00000001 의 형태로 저장이 된다. 



<숙제>


- 2의 보수 검색해보기.

- 오버플로우 검색해보기

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 06  (0) 2018.04.23
Week 05  (0) 2018.04.18
Week 04  (0) 2018.04.11
Week 03  (0) 2018.04.04
Week 01  (0) 2018.03.21

Week 1-1 : C Lang review

Tutoring/18-1 DS2018. 3. 28. 01:17

<180327>


- C Lang review


8-3) 문자열 복사하기. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
void myStrcpy(char *to, char *from)
{
    while(*from) 
        *(to++) = *(from++);
    *to = 0;
}
 
int main()
{
    char a[]="HS_Turoring";
    char b[100];
 
    myStrcpy(b, a);
    puts(b);
    
    return 0;
}
cs


>> 조건식에서의 참, 거짓.

>> 널문자의 아스키 코드값 == 0

>> 널문자 따로 넣어주기 (7번 라인)

>> 포인터 연산의 원리 생각해보기.

>> 배열의 이름은 상수형태의 포인터.

>> 포인터(변수)는 말그대로 변수이므로, 주소값이 바뀔 수 있다.



8-5) 문자열 뒤집기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
 
int myStrlen(char *s)
{
    int i=0;
    while(s[i]) i++;
    return i;
}
 
void reverse(char *to, char *from)
{
    int idx=0;
    int len=myStrlen(from);
    for(int i=len-1; i>=0; i--)
        to[idx++] = from[i];
    to[idx] = 0;
}
 
int main()
{
    char a[]="HS_Turoring";
    char b[100];
 
    reverse(b, a);
    puts(b);
    
    return 0;
}
cs


>> 널문자 삽입 코드 필수.

>> 배열의 이름[문자열의 길이] 에는 널문자가 들어있다.

>> 문자열의 길이는 reverse() 에서 구한다음 진행하면 됨.



9) 순환함수.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
int mul(int n)
{
    if(n == 1) return 1;
    return n * mul(n-1);
}
 
int mulEven(int n)
{
    if(n < 1) return 1;
    if(n%2 == 1) n--;
    return n * mul(n-2);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", mul(n)); 
    printf("%d\n", mulEven(n));
    return 0;
}
cs


>> 함수를 잘 정의하고, 그 정의를 그대로 활용하기.

>> 어떻게 쪼개서 생각할 수 있을까? 고민해보기.

>> 생각한 것을 그대로 코드로 옮기기. 함수의 기능을 그대로 활용해서..!!

>> 탈출조건 고민해보기. 



2-4) is직각삼각형?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int isTri(int max, int a, int b)
{
    return max*max == a*a + b*b;
}
 
int main()
{
    int a, b, c;
    int tri;
    scanf("%d%d%d", &a, &b, &c);
    if(a > b && a > c) tri = isTri(a, b, c);
    else if(b > a && b > c) tri = isTri(b, a, c);
    else tri = isTri(c, a, b);
 
    tri ? puts("직각") : puts("ㄴㄴ");
 
    return 0;
}
cs


>> 큰값만 알면 되므로..

>> 함수를 사용해야 하는 이유 생각해보기..!!




'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05
Week 2-1 : How to code Recursive function2  (0) 2018.04.04
Week 1-2 : How to code Recursive function  (0) 2018.03.30

시대를 초월할 마음 Ep.01-02

Play the guitar.2018. 3. 24. 23:21

Ep.01


Youtube : https://www.youtube.com/watch?v=g4ltrHgqwGU



4 Capo


3F6S : 6, 2, 1


7F1S : 1 then 5F slide


2F1S : 1


3F2S : 2


2F5S, 2F3S : 5, 4, 2, 3


4F4S : 4


open : 4



Ep.02


Youtube : https://www.youtube.com/watch?v=4YDzURJGLtg


3F1S : 1, 2


2F3S, 2F1S : 1, 3


3F2S : 2, 4


2F5S : 2, 5


open : 3


4F4S : 4 


open : 4, then  5 


2F5S : 5

'Play the guitar.' 카테고리의 다른 글

<1-2> How To Play "River Flows In You" On Guitar (arranged by Sunga Jung) (guitar lesson / tutorial) Part 2  (0) 2018.02.12
<1-1> How To Play River Flows In You On Guitar (arranged by Sunga Jung) (guitar lesson / tutorial) Part 1  (0) 2018.01.29

Week 5 - BFS

Tutoring/PS2018. 3. 24. 11:31

<180324>



Week5 - BFS



[6593] 상범빌딩 (http://boj.kr/6593)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int L, R, C; };
 
int L, R, C;
int dl[]={1, -1, 0, 0, 0, 0};
int dr[]={0, 0, 1, -1, 0, 0};
int dc[]={0, 0, 0, 0, 1, -1};
 
bool safe(int l, int r, int c)
{
    return (0 <= l && l < 30) && (0 <= r && r < 30) && (0 <= c && c < 30);
}
 
int main()
{
    while(1) {
 
        scanf("%d%d%d", &L, &R, &C);
 
        if(!L && !R && !C) break;
 
        P s, e;
        char g[31][31][31];
        for(int l=0; l<L; l++) {
            for(int r=0; r<R; r++) 
                scanf("%s", g[l][r]);
            for(int r=0; r<R; r++) {
                for(int c=0; c<C; c++) {
                    if(g[l][r][c] == 'S')
                        s = (P){l, r, c};
                    if(g[l][r][c] == 'E') {
                        g[l][r][c] = '.';
                        e = (P){l, r, c};
                    }
                }
            }
        }
 
        queue<P> q;
        q.push(s);
        
        int visited[31][31][31]={0};
        visited[s.L][s.R][s.C] = 1;
 
        while(!q.empty()) {
            int curL = q.front().L;
            int curR = q.front().R;
            int curC = q.front().C; q.pop();
            
            if(curL == e.L && curR == e.R && curC == e.C) break;
 
            for(int k=0; k<6; k++) {
                int nL = curL+dl[k];
                int nR = curR+dr[k];
                int nC = curC+dc[k];
                if(safe(nL, nR, nC) && g[nL][nR][nC]=='.' && !visited[nL][nR][nC]) {
                    visited[nL][nR][nC] = visited[curL][curR][curC]+1;
                    q.push((P){nL, nR, nC});
                }
            }
        }
        
        int ans = visited[e.L][e.R][e.C];
        if(!ans) puts("Trapped!");
        else printf("Escaped in %d minute(s).\n", ans-1);
    }
}
cs


>> 3차원을 확장되었을 뿐, 이전 문제들과 동일하다.

>> 36번줄에 대해 처리를 안하면 답이 안나온다...



[5014] 스타트링크 (http://boj.kr/5014)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int F, S, G, U, D;
int visited[1000001];
 
int main()
{
    scanf("%d%d%d%d%d", &F, &S, &G, &U, &D);
 
    queue<int> q;
    q.push(S);
    visited[S] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        
        if(cur == G) break;
 
        int next = cur+U;
        if(next < 1000001 && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
 
        next = cur-D;
        if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
    }
    
    if(!visited[G]) puts("use the stairs");
    else printf("%d\n", visited[G]-1);
}
cs




[]

'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS  (0) 2018.04.07
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 2 - DFS  (0) 2018.02.21

[교양] 링크 소프트웨어 세상 (Link Software)

Etc.2018. 3. 22. 01:39

- 개인적으로 컴공과 신입생들이 봤으면 하는 교양스런 영상 

- 하나당 5분이 안된다. 시간내서 봅시다.



EP 01 :  소프트웨어, 세상에 로그인하다. (http://tv.naver.com/v/497091)


EP 02 : 비트, 디지털 세상을 열다 (http://tv.naver.com/v/502649)


EP 03 : 세상을 밝힌 논리식 (http://tv.naver.com/v/515433)


EP 04 : 인공지능. 인간은 아니지만, 인간처럼. (http://tv.naver.com/v/562737)


EP 05 : 컴퓨터의 스무고개(섀넌의 정보이론) (http://tv.naver.com/v/532789)


EP 06 : 클릭, 컴퓨터 속으로. (http://tv.naver.com/v/541908)


EP 07 : 쌓고 줄 세우는 데이터, 스택과 큐 (http://tv.naver.com/v/549384)


EP 08 : 눈에 보이는 데이터 정렬 (http://tv.naver.com/v/559460)


EP 09 : 숨어있는 데이터를 찾아라, 탐색. (http://tv.naver.com/v/568786)


EP 10 : 가장 빠른 길을 찾아라. 최단경로 알고리즘. (http://tv.naver.com/v/578993)


EP 11 : 검색창 뒤의 순위전쟁. (http://tv.naver.com/v/588454)


EP 12 : 암호, 키를 공개하다. (http://tv.naver.com/v/597886)


EP 13 : 공간과 시간의 마법 데이터 압축. (http://tv.naver.com/v/608328)


EP 14 : 컴퓨터 오류 수정의 비밀. (http://tv.naver.com/v/617890)


EP 15 : 기본 위에 세워진 신뢰성. 데이터베이스. (http://tv.naver.com/v/629482)


EP 16 : 사이버 전쟁, 창과 방패의 대결. (http://tv.naver.com/v/639689)


EP 17 : 컴퓨터, 창작에 날개를 달다. (http://tv.naver.com/v/648823)


EP 18 : 컴퓨터와 소통을 꿈꾸다. (http://tv.naver.com/v/658118)


EP 19 : 로봇. 따뜻한 기술로 태어나다. (http://tv.naver.com/v/667595)


EP 20 : 새로운 혁명의 시작. (http://tv.naver.com/v/676289)



'Etc.' 카테고리의 다른 글

<181020> LG CNS CODE MONSTER 2018 본선 후기(Off-line TEST)  (0) 2018.10.20
<180518> 배민 코테 1차  (0) 2018.05.19
<180310> 삼성 S/W 테스트 A형 후기(합격)  (0) 2018.03.11

Week 01

Tutoring/18-1 C Lang2018. 3. 21. 17:29

< 180321 >




- C 언어는 main() 에서부터 시작한다..!!



- 첫 프로그래밍


1
2
3
4
5
6
7
#include <stdio.h>
 
int main()
{
    printf("Hello World"); 
    return 0;
}
cs


>> 1 : 헤더파일 선언, #include <stdio.h> 에서 stdio는 standard input output 의 약자.



- 주석처리


1
2
3
4
5
6
7
//#include <stdio.h>
 
int main()
{
    printf("Hello World"); 
    return 0;
}
cs


>> 1 : // 는 한줄을 주석처리 한다. 주석처리 하면 해당 라인을 무시한다.

>> 위의 경우 1번 라인을 무시하게 되면 printf() 를 사용할 수 없게 된다.



- 서식문자 : %d, %c, %lf


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    printf("int : %d\n", 20);
    printf("char : %c\n", 'A');
    printf("double : %lf\n", 3.141592);
    return 0;
}
cs


>> 20 은 상수형 정수

>> 'A' 는 상수형 문자

>> 3.141592 는 상수형 실수

>> printf() 에서 정수를 출력하고 싶을 땐 서식문자 %d를, 문자는 %c, 실수는 %lf 를 사용한다.


>> 위의 경우 세종류의 데이터가 있다. 정수형, 문자형, 실수형



- 변수를 선언하고, 값을 대입하고 출력하기.


1) 정수


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    int num;
    num = 3;
    printf("num = %d\n", num);
    return 0;
}
cs


>> 5 : 정수형 변수 선언. 정수형 데이터를 담는 변수를 선언하기 위해서는 int 라는 자료형을 선언하고 한칸 띄고 변수 이름을 쓴다. (변수이름은 마음데로, 하지만 작명규칙이 존재, 찾아볼것.)

>> 6 : 정수값을 num 이란 변수에 대입. 여기서 = 는 대입연산자 이다.


1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    int num;
    num = 3;
    printf("num = %d\n", num); // num = 3
 
    num = 7;
    printf("num = %d\n", num); // num = 7
    return 0;
}
cs


>> 9 : num 이란 변수에 7을 대입. 10 라인에서 num = 7 이란 결과가 출력

>> 변수 vs 상수 : 변수는 변하는 값. 어떤 값을 대입하냐에 따라 값이 바뀔 수 있다. 하지만 상수는 그 값 자체로만 사용이 가능. 그래서 상수.



2) 문자


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    char ch;
    ch = 'A';
    printf("ch = %c\n", ch); // ch = A
    return 0;
}
cs


>> 5 : 문자를 담는 변수를 선언하기 위해서는 자료형 char 을 사용



3) 실수


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    double dnum;
    dnum = 3.14;
    printf("dnum = %lf\n", dnum); // dnum = 3.140000 
    return 0;
}
cs


>> 5 : 실수를 담는 변수를 선언하기 위해서는 자료형 double 를 선언한다.

>> 7 : 실행결과는 dnum = 3.140000 , 기본적으로 소수점 6자리까지 출력한다.



- 문자의 정체


1
2
3
4
5
6
7
8
#include <stdio.h>
 
int main()
{
    char ch = 'b'-'a';
    printf("ch = %d\n", ch); // ch = 1
    return 0;
}
cs


>> 5 : 변수 ch를 선언과 동시에 'b'-'a' 값으로 초기화

>> 여기서 'b'-'a' 라는 연산이 가능하다...!!


1) 문자의 정체는 정수. 실제로 어떤 문자는 어떤 정수의 값으로 매핑(매칭)되어 있다. (아스키 코드표 참조)


2) 아스키 코드값의 특징

>> 문자인 숫자는 '0', '1', '2', ... '9' 의 순서로 되어 있다. 얼마에 매핑되어 있는지는 외울 필요 없음.

>> 알파벳 대문자는 'A', 'B', 'C', ... , 'Z' 순으로 되어있다.

>> 알파벳 소문자는 'a', 'b', 'c', ... , 'z' 순으로 되어 있따.

>> 알파벳 대문자가 소문자보다 앞선다. (작은 값을 갖는다.)

>> 'a' 와 'A'의 차이, 'b' 와 'B'등 소문자와 대문자 사이의 아스키코드 값 차이는 일정하다.

>> 널문자의 아스키 코드값은 0 (알아두면 좋음.)



- 소문자를 대문자로, 대문자를 소문자로 변경해서 출력하기.


1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main()
{
    char ch1 = 'a';
    char ch2 = 'A';
    char diff = 'a'-'A';
    printf("a => %c\n", ch1-diff); // a => A
    printf("A => %c\n", ch2+diff); // A => a
    return 0;
}
cs


>> 소문자와 대문자의 차이가 일정하기 때문에, 그 일정한 값을 대문자에서 더해주면 소문자가 되고, 소문자에서 빼주면 대문자가 된다...!!



- 문자 '9' 를 정수 9로 표현하기.


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    char num = '9';
    printf("num = %c\n", num); 
    printf("num = %d\n", num-'0'); 
    return 0;
}
cs


>> 6, 7번라인 모두 9를 출력한다. 6의 결과는 문자형태의 9, 7의 결과는 정수형태의 9.

>> '1' 과 '0' 의 차이는 1 이다.

>> '2' 와 '1'의 차이도 1 이다.

>> '2' 와'0'의 차이는 2이다. >> '9' 와 '0'의 차이는 9 가 된다..!!



- 기타

1) 검색은 구글에서.

2) 소스코드를 실행했을 때 뜨는 창의 이름은 콘솔창.

3) VS2017 에서 빌드하고 컴파일 할때 단축시 사용하기..!! 

4) C 언어의 소스코드 확장자는 .c

5) 과제는 기왕이면 해와서 튜터링 시간에 맞춰보기.



- 숙제


1) 1 vs '1' 의 차이 알아보기.



'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 06  (0) 2018.04.23
Week 05  (0) 2018.04.18
Week 04  (0) 2018.04.11
Week 03  (0) 2018.04.04
Week 02  (2) 2018.03.28

BOJ 채점현황 속도 올리기

Article2018. 3. 11. 19:05

출처 : https://startlink.blog/2018/03/09/%EC%B1%84%EC%A0%90-%ED%98%84%ED%99%A9-%EC%86%8D%EB%8F%84-%EC%98%AC%EB%A6%AC%EA%B8%B0/


BOJ의 채점 현황은 유저가 제출한 솔루션의 정보를 볼 수 있는 페이지입니다.

주소: https://www.acmicpc.net/status

검색도 지원합니다.

페이지에서 직접 선택/입력할 수 있는 항목은 다음과 같습니다.

  1. 문제 번호
  2. 아이디
  3. 언어
  4. 결과

다른 메뉴를 통해서 설정할 수 있는 항목은 대회, 문제집, 문제 출처, 학교/회사, 그룹 등이 있긴 하지만, 이번 글에서는 중요한 정보가 아니기 때문에, 생략하겠습니다.

유저의 솔루션을 담고 있는 테이블 solution은 아래와 같이 생겼습니다. (BOJ에서 사용하는 테이블은 아니고, 이번 포스팅을 위해 만든 테이블)

+---------------+------------+------+-----+---------+----------------+
| Field         | Type       | Null | Key | Default | Extra          |
+---------------+------------+------+-----+---------+----------------+
| solution_id   | int(11)    | NO   | PRI | NULL    | auto_increment |
| problem_id    | int(11)    | NO   | MUL | 0       |                |
| result        | tinyint(4) | NO   | MUL | 0       |                |
+---------------+------------+------+-----+---------+----------------+

result는 채점 결과를 담고 있으며, 0부터 13까지 총 14개의 값 중 하나입니다.

채점 현황의 첫 페이지를 조회하려면 아래와 같은 쿼리면 될 것 같습니다. 한 페이지에는 20개의 결과만 보여준다고 가정합니다.

SELECT * FROM `solution` WHERE 1 ORDER BY `solution_id` DESC LIMIT 20

채점 현황에서 페이지의 개수는 의미가 없습니다. 또, 몇 페이지에 무슨 정보가 있는지도 중요한 정보가 아닙니다.

따라서, 현재 페이지 첫 결과의 채점 번호를 이용해서 화면을 구성합니다.

페이지의 첫 채점 번호는 top, 마지막 채점 번호는 bottom이라고 하겠습니다.

현재 페이지의 다음 페이지를 조회하려면 어떻게 해야할까요?

현재 페이지에 보이는 채점 번호가 7951563 ~ 7951544 라고 한다면, 다음 페이지의 top은 7951543이 되어야 합니다.

따라서, 다음과 같은 쿼리를 이용해 다음 페이지를 조회할 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` <= 7951543 ORDER BY `solution_id` DESC LIMIT 20

하지만 검색이 적용되었다면, 다음 페이지의 top이 현재 페이지의 bottom - 1이 아닐 수도 있습니다.

결과가 4 (맞았습니다!) 인 것을 검색한다면, 다음과 같은 쿼리를 이용해야 합니다.

SELECT * FROM `solution` WHERE `result` = 4 ORDER BY `solution_id` DESC LIMIT 20

bottom이 7951655인 경우에 다음 페이지를 조회하는 쿼리는 아래와 같습니다.

SELECT * FROM `solution` WHERE `result` = 4 AND `solution_id` <= 7951654 ORDER BY `solution_id` DESC LIMIT 20

하지만, 다음 페이지의 top이 7951654가 아닐 수도 있기 때문에, 올바른 쿼리라고 할 수 없습니다.

올바른 다음 페이지의 top값을 구하기 위해서 현재 페이지의 쿼리를 수정했습니다.

SELECT * FROM `solution` WHERE `result` = 4 ORDER BY `solution_id` DESC LIMIT 21

LIMIT 20을 LIMIT 21로 수정해 마지막 결과는 화면에 보여주지 않고, 다음 페이지 링크를 만드는데 이용할 수 있습니다.

그런데…

사실 생각해보면 다음 페이지의 top 값은 그렇게 정확할 필요가 없습니다. 위에서 설명한 두 방법 모두 같은 결과를 보여주기 때문입니다.

LIMIT 21을 사용한 방법의 장점은 다음 페이지가 있는지 없는지를 알 수 있다는 장점이 있습니다. 만약, 다음 페이지 링크를 눌렀는데, 다음 페이지가 빈 결과라면 오류가 난 것인지, 진짜 결과가 없는 것인지 알 수 없습니다. 따라서, 다음 페이지의 top은 LIMIT 21의 마지막 값을 이용하는 것으로 했습니다.

이제 이전 페이지 링크를 만들어 봅시다.

이전 페이지의 top값은 어떻게 구해야 할까요?

가장 쉬운 방법은 다음 페이지의 주소에 prevtop을 추가하는 것 입니다. 어떤 페이지에 다음 페이지 링크를 통해서 왔다면, 이전 페이지의 주소를 만들 때, prevtop을 이용하는 방법이 있습니다.

이 방법은 hustoj를 기반으로 하는 온라인 저지 사이트 (Judgeon, CodeUp) 에서 사용하고 있습니다.

단점으로는 다음 페이지 링크를 통하지 않은 경우에 prevtop을 구할 수 없다는 것이 있습니다.

다른 방법은 bottom을 이용하는 것 입니다.

어떤 페이지의 top이 7951563 이고, bottom이 7951544라면, 이전 페이지의 bottom은 7951564이기 때문에, 쿼리를 다음과 같이 만들 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` >= 7951564 ORDER BY `solution_id` ASC LIMIT 20

그런데, 채점 현황은 채점 번호가 내림차순이 되어야 합니다. 따라서, 결과의 순서를 뒤집어주는 과정이 필요합니다.

이 방법은 POJ, Lavida에서 사용하고 있습니다.

주소에 top과 bottom이 동시에 있는 경우, 이전 페이지의 존재 여부를 확인할 수 없다는 단점이 있습니다.

이전 페이지의 top을 올바르게 구하기 위해서, 그냥 쿼리를 한 번 더 사용하기로 했습니다.

현재 페이지의 top이 7951654라면, 아래와 같은 쿼리로 이전 페이지의 top을 구할 수 있습니다.

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 19,1

그런데, 이 쿼리는 이전 페이지 결과의 개수가 20개 미만인 경우에는 top을 구할 수 없기 때문에, LIMIT 19,1 대신 LIMIT 20을 사용하고, 마지막 채점 번호를 이용해 top을 구하기로 합시다.

정리해보면, 어떤 페이지의 top이 7951654 라면, 다음 두 방법으로 다음 페이지의 top과 이전 페이지의 top을 구할 수 있습니다

현재 페이지 및 다음 페이지의 top (21번째 채점 번호, 없으면 다음 페이지 없음)

SELECT * FROM `solution` WHERE `solution_id` <= 7951654 ORDER BY `solution_id` DESC LIMIT 21

이전 페이지의 top (마지막 채점 번호)

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 20

이제, 쿼리를 수행하는데 걸리는 시간을 재보려고 합니다.

전체 제출이 약 8백만개인 경우에 임의의 top을 고르고, 두 쿼리를 수행하는데 걸리는 조사해봤습니다.

  • top = 3456453
    • 현재 페이지 및 다음 페이지: 0.11초
    • 이전 페이지: 0.09초
  • top = 2133432
    • 현재 페이지 및 다음 페이지: 0.08초
    • 이전 페이지: 0.08초
  • top = 7777777
    • 현재 페이지 및 다음 페이지: 0.08초
    • 이전 페이지: 0.09초

이정도면 충분히 빠른 것 같습니다.

이번에는 결과가 4 (맞았습니다!) 인 것을 검색하는 경우 시간을 조사해봤습니다.

  • top = 3456453
    • 현재 페이지 및 다음 페이지: 7.23초
    • 이전 페이지: 0.21초
  • top = 2133432
    • 현재 페이지 및 다음 페이지: 6.01초
    • 이전 페이지: 0.09초
  • top = 7777777
    • 현재 페이지 및 다음 페이지: 0.21초
    • 이전 페이지: 0.04초

쿼리 하나가 6~7초 정도가 걸리는 것은 매우 절망적입니다.

그런데, 현재 페이지 및 다음 페이지는 느린데, 왜 이전 페이지는 빠를까요?

EXPLAIN을 이용해 현재 페이지 및 다음 페이지 쿼리가 오래걸리는지 조사해봤습니다.

EXPLAIN SELECT * FROM `solution` WHERE `result` = '4' AND `solution_id` <= 3456453 ORDER BY `solution_id` DESC LIMIT 21;
+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref   | rows    | Extra       |
+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+
|  1 | SIMPLE      | solution | ref  | PRIMARY,res   | res  | 2       | const | 1462378 | Using where |
+----+-------------+----------+------+---------------+------+---------+-------+---------+-------------+

여기서 res는 result의 인덱스 이름입니다.

세상에 1462378개라니… 쿼리가 느릴 수 밖에 없네요.

이전 페이지 쿼리는 어떨까요?

+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref   | rows    | Extra                              |
+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+
|  1 | SIMPLE      | solution | ref  | PRIMARY,res   | res  | 2       | const | 3635748 | Using index condition; Using where |
+----+-------------+----------+------+---------------+------+---------+-------+---------+------------------------------------+

이전 페이지는 어떤 값보다 큰 것 중에 오름차순으로 20개를 고르는 쿼리라 인덱스를 이용해 빠르게 검색할 수 있습니다.

하지만, 현재 페이지 및 다음 페이지는 작거나 같은 값 중에서 채점 번호 순으로 내림차순으로 21개를 고르는 쿼리이기 때문에 인덱스를 사용하지 못합니다.

BOJ는 MySQL 5.6을 사용하고 있습니다. 인덱스와 관련된 MySQL 메뉴얼을 보면, 분명 index_col_name에 DESC를 입력할 수 있습니다. 하지만, 하단의 내용을 보면 이런 내용이 있습니다.

An index_col_name specification can end with ASC or DESC. These keywords are permitted for future extensions for specifying ascending or descending index value storage. Currently, they are parsed but ignored; index values are always stored in ascending order.

안타깝게도 현재 버전에서 인덱스는 항상 오름차순으로 저장된다고 합니다. MySQL 8.0은 내림차순 인덱스를 지원하지만, 아직 나오지도 않은 버전입니다. 또한, RDS에서 지원하지도 않습니다.

어쩔 수 없이 다른 방법을 생각해봐야 합니다.

첫 번째로 생각한 방법은 내림차순 인덱스를 지원하는 Oracle을 사용하는 것입니다. 하지만, 너무 할 일이 많아지고, RDS 비용도 두 배 증가하기 때문에 이 방법은 스킵하겠습니다.

두 번째로 생각한 방법은 solution_desc라는 테이블을 만들고, solution 테이블과 동일한 결과를 갖지만, 제출 번호 (solution_id)만 음수로 저장하는 것입니다.

이건 너무 복잡하고 번거로운 방법입니다.

BOJ에서 선택한 방법은 DB의 구조를 변경하는 것 입니다. solution_desc를 추가하고, 항상 solution_id의 음수값을 저장하는 것입니다.

+---------------+------------+------+-----+---------+----------------+
| Field         | Type       | Null | Key | Default | Extra          |
+---------------+------------+------+-----+---------+----------------+
| solution_id   | int(11)    | NO   | PRI | NULL    | auto_increment |
| problem_id    | int(11)    | NO   | MUL | 0       |                |
| result        | tinyint(4) | NO   | MUL | 0       |                |
| solution_desc | int(11)    | NO   | MUL | 0       |                |
+---------------+------------+------+-----+---------+----------------+

이제 쿼리를 변경해야 합니다.

현재 페이지 및 다음 페이지의 top (21번째 채점 번호, 없으면 다음 페이지 없음)

SELECT * FROM `solution` WHERE `solution_desc` >= -7951654 ORDER BY `solution_desc` ASC LIMIT 21

이전 페이지의 top (마지막 채점 번호)

SELECT * FROM `solution` WHERE `solution_id` > 7951654 ORDER BY `solution_id` ASC LIMIT 20

두 쿼리 모두 ASC를 사용하기 때문에, 속도가 빠를 것으로 예상됩니다.

이제, 각 쿼리가 걸리는 시간을 재봅시다.

  • top = 3456453
    • 현재 페이지 및 다음 페이지: 7.23초 → 0.12초
    • 이전 페이지: 0.21초
  • top = 2133432
    • 현재 페이지 및 다음 페이지: 6.01초 → 0.05초
    • 이전 페이지: 0.09초
  • top = 7777777
    • 현재 페이지 및 다음 페이지: 0.21초 → 0.05초
    • 이전 페이지: 0.04초

채점 현황의 속도가 매우 빨라졌습니다.

마지막으로 다른 방법이나 더 좋은 방법, 또는 더 개선할 점이 있으면 댓글로 달아주세요.

P.S. 내림차순이 귀찮을 때, 정수에 -1을 곱해서 오름차순으로 사용하는 방법은 알고리즘 문제를 풀 때 자주 사용하는 방법입니다.

대표적으로 C++에서 std::priority_queue는 큰 값이 먼저 나오기 때문에, 최소값부터 나오게 하려면 -1을 곱해서 큐에 넣고, 큐에서 뺀 다음에 -1을 곱해서 사용할 수 있습니다. 물론, 이 방법은 큐에 넣어야하는 정수의 범위가 int범위라면 사용할 수 없습니다. 이유는 -2147483648에 -1을 곱하면 -2147483648이기 때문입니다.

–> 조금 귀찮긴 하지만, integer 범위에서 돌아가게 할 수 있습니다.

v = INT_MIN일때는 INT_MAX, 다른 값일때에는 -v-1 을 사용하면 됩니다

'Article' 카테고리의 다른 글

[Artcle] 실무 개발자에게 알고리즘은 덜 중요할까?  (0) 2018.11.02

티스토리툴바