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

 

17478번: 재귀함수가 뭔가요?

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대��

www.acmicpc.net

 

뭐지 왜 나보고 이걸 풀어보라고 한것이지 무엇을 암시하는 것이지

 

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
#include <iostream>
 
int n;
 
void input()
{
    std::cin >> n;
    std::cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
}
 
void print(const char* str, int stk)
{
    for (int j = 0; j < stk; ++j)
    {
        std::cout << "____";
    }
    std::cout << str;
}
 
void solve(int stk)
{
    print("\"재귀함수가 뭔가요?\"\n", stk);
    if (stk == n)
    {
        print("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n", stk);
    }
    else
    {
        print("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", stk);
        print("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", stk);
        print("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n", stk);
        solve(stk + 1);
    }
    print("라고 답변하였지.\n", stk);
}
 
int main()
{
    input();
    solve(0);
    return 0;
}
cs

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준 14888 : 연산자 끼워넣기  (0) 2020.06.23
백준 14502 : 연구소 (브루트포스)  (0) 2020.06.19
탐색공간의 배제  (0) 2020.06.18
백준 14501 : 퇴사  (0) 2020.06.18
백준 2661 / koi : 좋은 수열  (0) 2020.06.16

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

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

www.acmicpc.net

 

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
#include <iostream>
 
int n;
std::pair<int, int> schedule[20];
int ans;
 
void input()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> schedule[i].first >> schedule[i].second;
    }
}
 
void solve(int date, int profit)
{
    if (n < date)
    {
        return;
    }
    if (n == date)
    {
        ans = ans < profit ? profit : ans;
        return;
    }
 
    solve(date + schedule[date].first, profit + schedule[date].second);
    solve(date + 1, profit);
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve(0, 0);
    output();
    return 0;
}
 cs

 

나도 퇴사시켜줘

 

입사도 못해봤지만

 

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준 17478 : 재귀함수가 뭔가요?  (0) 2020.06.19
탐색공간의 배제  (0) 2020.06.18
백준 2661 / koi : 좋은 수열  (0) 2020.06.16
koi : 경찰차  (0) 2020.06.13
koi : 전기줄, 전깃줄 / 백준 2631 : 줄세우기 / 백준 2565 : 전깃줄  (0) 2020.06.13

http://koistudy.net/?mid=prob_page&NO=1980&SEARCH=0

 

KOISTUDY

 

koistudy.net

 

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
#include <iostream>
 
int B;
int n;
int arr[22];
int max_val = 0;
 
constexpr int max(int first, int second)
{
    return first > second ? first : second;
}
 
void input()
{
    std::cin >> B >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
    }
}
 
void solve(int cur, int money)
{
    if (money <= B)
    {
        max_val = max(money, max_val);
    }
    else
    {
        return;
    }
    if (cur == n)
    {
        return;
    }
 
    for (int i = cur; i < n; ++i)
    {
        solve(i + 1, money + arr[i], i);
    }
}
 
void output()
{
    std::cout << max_val;
}
 
int main()
{
    input();
    solve(0, 0, 0);
    output();
    return 0;
}
 cs

클래식한 문제

 

끝구간을 자꾸 건너뛰어버려서 당황했다.

 

기초가 가장 중요한 법이지..

 

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
#include <iostream>
 
int B;
int n;
int arr[22];
int max_val = 0;
 
constexpr int max(int first, int second)
{
    return first > second ? first : second;
}
 
void input()
{
    std::cin >> B >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
    }
}
 
void func(int i, int sum)
{
    if (i == n)
    {
        if (sum <= B && sum > max_val)
        {
            max_val = sum;
        }
        return;
    }
 
    func(i + 1, sum + arr[i]);
    func(i + 1, sum);
}
 
void output()
{
    std::cout << max_val;
}
 
int main()
{
    input();
    func(0, 0);
    output();
    return 0;
}
 cs

교재상의 정답

 

배열이 최대 21개라 가능하겠지만...

 

재귀의 근-본이라는 느낌이라고 해야하나

 

이렇게 정의를 설계해서 짜는게 진짜 재귀를 쓰는 실력이 아닌가 한다

 

난 그냥 막 짜는데...

저작자표시

'알고리즘' 카테고리의 다른 글

koi : 저울 추  (0) 2020.06.12
koi : 배낭 문제  (0) 2020.05.15
koi : 거스름 돈  (0) 2020.05.14
koi : 계단 오르기  (0) 2020.05.14
koi : maximum sum  (0) 2020.05.07

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

 

13265번: 색칠하기

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

www.acmicpc.net

 

koi 색칠하기에서 살짝만 바뀐 문제.

 

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <vector>
 
int T, n, m;
 
std::vector<std::vector<int>> vec;
int visited[1001];
 
bool chk_visit[1001];
 
void input()
{
    std::cin >> n >> m;
    vec = std::vector<std::vector<int>>(n);
    int first, second;
    for (int i = 0; i < m; ++i)
    {
        std::cin >> first >> second;
        //연결된 정점들을 반열린구간으로 맞춰주기 위해 --
        --first;
        --second;
        vec[first].push_back(second);
        vec[second].push_back(first);
    }
}
 
void output(bool ans)
{
    if (ans == 0)
    {
        std::cout << "impossible\n";
    }
    else
    {
        std::cout << "possible\n";
    }
    return;
}
 
void dfs_visit(int vertex, int color)
{
    //이 정점에 방문했었다.
    chk_visit[vertex] = true;
    visited[vertex] = color;
    int can = 1;
    for (int i = 0; i < vec[vertex].size(); ++i)
    {
        //해당 정점(vec[vertex][i])에 연결되어있는 다른 정점들을 순회하는
        //i를 둘러보면서, 연결되어있는 다른 정점들이 color로 칠해져있는지
        //visited[vertex에 연결된 다른 정점들]을 확인하면서
        //만약 칠이 되어 있다면 문제 조건에 의해 인접한 같은 색이 되므로
        //빠꾸를 먹여야 하니 플래그 can을 0으로 만들어주자.
        if (visited[vec[vertex][i]] == color)
        {
            can = 0;
        }
    }
    if (can == false)
    {
        //하지만 이 정점은 색칠이 불가능한 정점.
        //따라서 방문은 했으나 색칠은 못하게 됨
        //chk_visit[vertex] = false; 가 여기에 없는 이유
        visited[vertex] = 0;
        return;
    }
    for (int i = 0; i < vec[vertex].size(); ++i)
    {
        //이미 위에서 색칠이 가능한 정점에 대해 검증을 마친 상태
        //따라서 재귀를 호출하는데 필요한 조건은
        //해당 정점을 이미 접근했는가? 뿐이다
        if (visited[vec[vertex][i]] == 0)
        {
            dfs_visit(vec[vertex][i], 1);
        }
        //따라서 1을 이미 칠했고, 그 정점이 올바른 색을 칠한거라면
        //visited[vec[vertex][i]]는 0이 아닐 것.
        //만약 0이라면 위의 검증 코드에서 빠꾸를 먹었을테니 2를 칠해주면 된다.
        if (visited[vec[vertex][i]] == 0)
        {
            dfs_visit(vec[vertex][i], 2);
        }
    }
}
 
void solve()
{
    for (int i = 0; i < n; ++i)
    {
        if (visited[i] != 0)
        {
            continue;
        }
 
        dfs_visit(i, 1);
 
        for (int j = 0; j < n; ++j)
        {
            //i가 n까지 도는데, 초기화하지 않는다면
            //색칠할 수 없어 그대로 놔둔 visited[j]가
            //방문했던 모든 정점을 기록한 chk_visit[j]에 걸려
            //output(false)를 호출하게 될 것이다.
            if (chk_visit[j] != false && visited[j] == 0)
            {
                output(false);
                return;
            }
        }
    }
    output(true);
    return;
}
 
void clear()
{
    vec.clear();
    for (int i = 0; i < n; ++i)
    {
        visited[i] = 0;
        chk_visit[i] = false;
    }
}
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    
    std::cin >> T;
    for (int i = 0; i < T; ++i)
    {
        input();
        solve();
        clear();
    }
    return 0;
}
 cs

색칠하는 부분은 내가 직접 다 짠건 아니고... 교재 보고 확인해서 좀 바꿨다.

 

내가 생각해서 짜본것도 얼추 맞을것같다는 생각은 드는데, 인접리스트가 아니라 인접 행렬이기도 하고

 

또 틀리면 한참 삽질할것같고 그래서... 아이고야

 

이게 참, 그렇구만

저작자표시

'알고리즘' 카테고리의 다른 글

koi : 계단 오르기  (0) 2020.05.14
koi : maximum sum  (0) 2020.05.07
koi & 백준 2638, 2638 : 치즈  (0) 2020.05.05
koi : 앱(small)  (0) 2020.05.01
koi : 최소합  (0) 2020.04.28

+ Recent posts

티스토리툴바