JSH

jsh1223.egloos.com

포토로그

알파벳(BOJ 1987번) Algorithm

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

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
#include <iostream>
 
using namespace std;
 
char map[22][22];
int en[26];
int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
int R, C;
int ans = 0;
 
void dfs(int nowR, int nowC, int step) {
    if (step > ans) ans = step;
 
    for (int i = 0; i < 4; i++) {
        int nR = nowR + dir[i][0];
        int nC = nowC + dir[i][1];
 
        if (nR < 0 || nC < 0 || nR >= R || nC >= C)
            continue;
        if (en[map[nR][nC] - 'A'] == 1)
            continue;
 
        en[map[nR][nC] - 'A'] = 1;
        dfs(nR, nC, step+1);
        en[map[nR][nC] - 'A'] = 0;
    }
}
 
int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        cin >> map[i];
    }
    en[map[0][0] - 'A'] = 1;
    dfs(0, 0, 1);
 
    cout << ans << '\n';
    return 0;
}
cs

최단경로를 구하는 문제처럼 접근하면 안된다.
최단경로를 구하는 것과 달리 목적지가 없어 여러가지 방법으로 순회해도 된다.
if(res[nR][nC] > step+1) 처럼 
다음에 갈 곳의 수가 훨씬 크다면 가지 않는데, 당장은 다음에 갈곳이 작더라도 
순회했을 때 더 멀리 갈 수 있다.

ABCD
EFAD
ASDA
NGHZ 일 경우 
12
 3
 45
876 의 길이 있음에도 불구하고 

12
 3
 47
656 으로 되기 때문에 결과는 7밖에 안나온다.

태그 : , , , ,
트랙백(0)덧글(1)

랜선짜르기 Algorithm

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

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
#include <iostream>
using namespace std;
 
int lan[10000];
 
int main()
{
    int n, k, begin = 1;
    int end = 2000000000;
 
    int ans = -1;
 
    cin >> n >> k;
 
    for (int i = 0; i < n; i++)
    {
        cin >> lan[i];
    }
 
    while (begin <= end)
    {
        int m = (begin + end) / 2;
        int s = 0;
 
        for (int i = 0; i < n; i++)
        {
            s += lan[i] / m;
        }
        if (s < k)
            end = m - 1;
        else
        {
            if (ans < m)
                ans = m;
            begin = m + 1;
        }
    }
    cout << ans << endl;
 
    return 0;
}
cs

[Today's issue]
주어진 값의 범위 잘 확인할 것.
또한 범위가 주어지지 않는 값도 존재한다
최대값 잘 설정하기

트랙백(0)덧글(0)

LIS Algorithm


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
#include <iostream>
 
using namespace std;
 
int proc(int n)
{
    int inputs[501] = { 0, }; // 1~n까지 값을 받으니까 501개로 잡는다. 여유롭게 잡는 것을 추천
    int res[501] = { 0, };
 
    for (int i = 1; i <= n; i++)
    {
        cin >> inputs[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++) //0부터 시작해야지 첫 res값이 1부터 된다.
        {
            if (inputs[j] < inputs[i])
            {
                if (res[j] + 1 > res[i])
                {
                    res[i] = res[j] + 1;
                }
            }
        }
    }
 
    //max값 찾기
    int max = 0;
    for (int i = 1; i <= n; i++)
    {
        if (max < res[i])
        {
            max = res[i];
        }
        
    }
 
    return max;
}
int main()
{
    int testCase = 0;
    cin >> testCase;
 
    while (testCase-- > 0)
    {
        int n = 0;
        cin >> n;
        cout << proc(n) << endl;
    }
 
    return 0;
}
cs

[Today's issue]
1. DP는 이전값을 보고 현재값을 알 수 있는 건데, 1부터 값을 저장하는 이유는 맨 첫번째 값의 이전값(0)을 만들기 위해
2. 1~n까지 받도록 했을 때, 배열의 크기를 n으로 해서 문제가 됬음음. 배열[n]에 입력 받는다면 배열[n+1]로 선언해야함
   배열의 크기를 넉넉하게 잡는 것을 추천!
3. for (int j = 0; j < i; j++) //0부터 시작해야지 첫 res값이 1부터 된다
   for (int j = 1; j < i; j++)로 했을 경우 결과 값이 1 모자르게 나왔다.
   => 1부터 시작하면 첫번 째 값의 경우 이전 값이 없기 때문에 이전 값을 통해 현재 값을 알 수 없다. 
트랙백(0)덧글(0)

NQueen Algorithm

https://algospot.com/judge/problem/read/NQUEEN

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
#include <iostream>
 
using namespace std;
 
int c, n;
int arr[12][12];
int res;
 
bool chk(int cur, int loc)
{
    int gap = 0; 
    for (int i = cur - 1; i >= 0; i--) //현재 줄에서 첫 줄까지 탐색
    {
        gap++; //for문이 줄이동이라면 gap은 줄이동에 따른 대각선위치를 찾기위한 간격
        if (arr[i][loc] == 1) //위에 퀸이 있니
            return false;
        if (loc - gap >= 0 && arr[i][loc - gap] == 1) //왼쪽대각선에 퀸이 있니, 왼쪽의 끝부터 가능하니까 0이상
            return false;
        if (loc + gap < n && arr[i][loc + gap] == 1) //오른쪽대각선에 퀸이 있니, 오른쪽이 끝이하로 가능하니까 n이하 => 배열이므로 n-1까지니까 n보다 작은지를 검사
            return false;
    }
    return true; // 상위, 왼쪽대각선, 오른쪽대각선에 퀸 없음 = 놓을 수 있는 자리
}
 
void proc(int cur)
{
    if (cur == n)
    {
        res++;
        return;
    }
 
    for (int i = 0; i < n; i++) // 현재 cur줄에서 퀸을 놓을 자리를 탐색한다
    {
        if (chk(cur, i) == false) //  퀸을 놓을 수 있는 자리인지 판단. false면 놓을 수 없으므로 다음 칸 이동
            continue;
        arr[cur][i] = 1; // 현재 cur줄에서 퀸을 놓은 자리에 1로 표시
        proc(cur + 1);
        arr[cur][i] = 0;
    }
}
int main()
{
    cin >> c;
    while (c-- > 0)
    {
        cin >> n;
        res = 0;
        proc(0);
        cout << res << endl;
 
    }
    return 0;
}
 
[Today's issue]
1. Testcase를 크게 잡고 같은 입력 값을 여러번 실행 해도 결과가 같은지 확인해 볼 것
2. 디버깅 시, 브레이크포인트 잡고 실행은 F5로 하면 해당 줄에 멈춘다
cs
트랙백(0)덧글(0)

배열의 크기는 2의 거듭제곱으로 etc

arr[10], arr[20], arr[30], arr[40], arr[50], arr[100]  보다는
arr[8], arr[16], arr[32], arr[64] ........................................... 이렇게 2의 거듭제곱으로 할 것.




 2의 거듭제곱이 컴퓨터의 연산 속도가 훨씬 빠르다.



21
=
2     
211
=
2,048     
221
=
2,097,152     
231
=
2,147,483,648
22
=
4
212
=
4,096
222
=
4,194,304
232
=
4,294,967,296
23
=
8
213
=
8,192
223
=
8,388,608
233
=
8,589,934,592
24
=
16
214
=
16,384
224
=
16,777,216
234
=
17,179,869,184
25
=
32
215
=
32,768
225
=
33,554,432
235
=
34,359,738,368
26
=
64
216
=
65,536
226
=
67,108,864
236
=
68,719,476,736
27
=
128
217
=
131,072
227
=
134,217,728
237
=
137,438,953,472
28
=
256
218
=
262,144
228
=
268,435,456
238
=
274,877,906,944
29
=
512
219
=
524,288
229
=
536,870,912
239
=
549,755,813,888
210
=
1,024
220
=
1,048,576
230
=
1,073,741,824
240
=
1,099,511,627,776

트랙백(0)덧글(0)
1 2 3 4 5 6 7 8 9 10 다음
jsh1223.egloos.com is powered by Egloos. Subscribe to RSS Skin design by egloos.