Skip to content

Commit 53fdd56

Browse files
SunYeong ParkSunYeong Park
SunYeong Park
authored and
SunYeong Park
committed
add
1 parent e6fe8ce commit 53fdd56

File tree

10 files changed

+425
-5
lines changed

10 files changed

+425
-5
lines changed

‎algorithm/dynamic11726.cpp‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
// 단계 하나랑 나머지 전체를 나누는 것
2+
// 점화식 찾기
3+
// D[n] = D[n-1] + D[n-2]
4+
// D[1] = 1
5+
// D[2] = 2
6+
#include <iostream>
7+
using namespace std;
8+
int d[10001];
9+
int main()
10+
{
11+
int n;
12+
cin >> n;
13+
d[1] = 1;
14+
d[2] = 2;
15+
for (int i = 3; i < n + 1; i++)
16+
{
17+
d[i] = d[i - 1] + d[i - 2] + d[i - 2];
18+
d[i] %= 10007;
19+
}
20+
cout << d[n] << '\n';
21+
return 0;
22+
}

‎algorithm/dynamic11727.cpp‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
// 단계 하나랑 나머지 전체를 나누는 것
2+
// 점화식 찾기
3+
// D[n] = D[n-1] + D[n-2] + D[n-2]
4+
// D[1] = 1
5+
// D[2] = 3
6+
int d[1000];
7+
int go(int n){
8+
9+
}

‎algorithm/dynamic1463.cpp‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
#include <iostream>
2+
int d[1000001];
3+
using namespace std;
4+
// 1로 만들기
5+
// N을 1로 만드는 **최소** 연산 횟수
6+
// 3으로 나누는 것이 빠르므로, 2보다 3을 먼저 나눈다. -- 그리디 알고리즘. 예외.
7+
// ** 점화식의 정의를 세워보자 **
8+
// D[N] : N을 작게 만들 수 있는 방법
9+
10+
// 큰문제 단계와 나머지 다시 전체 문제로 나누면 좋다.
11+
// N -> N/3 (1번) 과 N/3 -> 1 (D[N/3])
12+
// N -> N/2 (1번) 과 N/2 -> 1 (D[N/2])
13+
// N -> N-1 (1번) 과 N-1 -> 1 (D[N-1])
14+
// D[N] = min(D[N/3], D[N/2], D[N-1])
15+
// D[1] = 0 // 1->1
16+
17+
//--------- TOP DOWN ----------//
18+
// n에서부터 내려가면서.. 재귀호출
19+
int go(int n)
20+
{
21+
if (n == 1)
22+
return 0;
23+
if (d[n] > 0)
24+
return d[n]; // memoization 기억하고 있는 건 그대로 사용
25+
// D[n-1] : **아무때나** 가능함으로, 아무때나 를 먼저 해서, **비교의 기준**으로 만들어준다.
26+
d[n] = go(n - 1) + 1;
27+
// D[n/2]
28+
if (n % 2 == 0)
29+
{
30+
int temp = go(n / 2) + 1;
31+
if (d[n] > temp)
32+
d[n] = temp;
33+
}
34+
// D[n/3]
35+
if (n % 3 == 0)
36+
{
37+
int temp = go(n / 3) + 1;
38+
if (d[n] > temp)
39+
d[n] = temp;
40+
}
41+
return d[n];
42+
}
43+
44+
int main()
45+
{
46+
int n;
47+
cin >> n;
48+
// cout << go(n) << '\n';
49+
50+
//--------- BOTTOM UP ----------//
51+
d[1] = 0;
52+
for (int i = 2; i <= n; i++)
53+
{
54+
d[i] = d[i - 1] + 1;
55+
if (i % 2 == 0 && d[i] > d[i / 2] + 1)
56+
{
57+
d[i] = d[i / 2] + 1;
58+
}
59+
if (i % 3 == 0 && d[i] > d[i / 3] + 1)
60+
{
61+
d[i] = d[i / 3] + 1;
62+
}
63+
}
64+
cout << d[n] << '\n';
65+
return 0;
66+
}
67+
// 시간 복잡도
68+
// 함수의 호출 횟수 * 함수의 시간 복잡도
69+
// - 문제의 개수 - -문제 1개 푸는데 필요한 시간-
70+
// 점화식: D[N] = min(D[N/3], D[N/2], D[N-1])
71+
// N * O(1)
72+
// 따라서 시간 복잡도: O(n)

‎algorithm/dynamic9095.cpp‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// n을 1,2,3의 합으로 나타내는 방법의 수
2+
// D[n] = D[n-1] + D[n-2] + D[n-3]
3+
#include <iostream>
4+
int d[12];
5+
using namespace std;
6+
// 문자열도 크기가 0인경우도 하나로 셈
7+
// 그래서 0인 경우에는 아무것도 사용하지 않는 방법이 하나
8+
int main()
9+
{
10+
d[0] = 1;
11+
d[1] = 1;
12+
d[2] = 2;
13+
d[3] = 4;
14+
for (int i = 4; i <= 11; i++)
15+
{
16+
d[i] = d[i - 1] + d[i - 2] + d[i - 3];
17+
}
18+
/*
19+
// 이렇게도 짤 수 있다!
20+
for (int i=1; i<=10; i++) {
21+
if (i-1 >= 0) {
22+
d[i] += d[i-1];
23+
}
24+
if (i-2 >= 0) {
25+
d[i] += d[i-2];
26+
}
27+
if (i-3 >= 0) {
28+
d[i] += d[i-3];
29+
}
30+
}
31+
*/
32+
int t;
33+
scanf("%d", &t);
34+
while (t--)
35+
{
36+
int n;
37+
scanf("%d", &n);
38+
printf("%d\n", d[n]);
39+
}
40+
}

‎dataStructure/queue10845.cpp‎

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
#include <iostream>
2+
#include <string>
3+
using namespace std;
4+
struct Queue
5+
{
6+
int data[10000];
7+
int begin, end;
8+
Queue()
9+
{
10+
begin = 0;
11+
end = 0;
12+
}
13+
void push(int num)
14+
{
15+
data[end] = num;
16+
end += 1;
17+
}
18+
bool empty()
19+
{
20+
if (begin == end)
21+
{
22+
return true;
23+
}
24+
else
25+
{
26+
return false;
27+
}
28+
}
29+
int size()
30+
{
31+
return end - begin;
32+
}
33+
int front()
34+
{
35+
return data[begin];
36+
}
37+
int back()
38+
{
39+
return data[end - 1];
40+
}
41+
int pop()
42+
{
43+
if (empty())
44+
{
45+
return -1;
46+
}
47+
begin += 1;
48+
return data[begin - 1];
49+
}
50+
};
51+
52+
int main()
53+
{
54+
int n;
55+
cin >> n;
56+
Queue q;
57+
58+
while (n--)
59+
{
60+
string cmd;
61+
cin >> cmd;
62+
if (cmd == "push")
63+
{
64+
int num;
65+
cin >> num;
66+
q.push(num);
67+
}
68+
else if (cmd == "pop")
69+
{
70+
if (q.empty())
71+
{
72+
cout << -1 << '\n';
73+
}
74+
else
75+
{
76+
cout << q.front() << '\n';
77+
q.pop();
78+
}
79+
}
80+
else if (cmd == "size")
81+
{
82+
cout << q.size() << '\n';
83+
}
84+
else if (cmd == "empty")
85+
{
86+
cout << q.empty() << '\n';
87+
}
88+
else if (cmd == "front")
89+
{
90+
if (q.empty())
91+
{
92+
cout << -1 << '\n';
93+
}
94+
else
95+
{
96+
cout << q.front() << '\n';
97+
}
98+
}
99+
else if (cmd == "back")
100+
{
101+
if (q.empty())
102+
{
103+
cout << -1 << '\n';
104+
}
105+
else
106+
{
107+
cout << q.back() << '\n';
108+
}
109+
}
110+
}
111+
return 0;
112+
}

‎dataStructure/queue1158.cpp‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// 순환큐
2+
#include <cstdio>
3+
#include <queue>
4+
using namespace std;
5+
int main()
6+
{
7+
int n, m;
8+
scanf("%d %d", &n, &m);
9+
queue<int> q;
10+
for (int i = 1; i <= n; i++)
11+
{
12+
q.push(i);
13+
}
14+
printf("<");
15+
for (int i = 0; i < n - 1; i++)
16+
{
17+
for (int j = 0; i < m - 1; j++)
18+
{
19+
q.push(q.front()); // 앞에꺼를 뒤로 밀어넣기
20+
q.pop();
21+
}
22+
printf("%d, ", q.front());
23+
q.pop();
24+
}
25+
printf("%d\n", q.front()); // 마지막 꺼 빼기
26+
return 0;
27+
}

‎dataStructure/queue_stack.cpp‎

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,27 @@
1-
// 스택을 이용해 큐 구현하기
1+
// 큐 이용해서 스택 구현하기
2+
#include <cstdio>
3+
#include <cstring>
4+
#include <queue>
5+
6+
using namespace std;
7+
char a[60000];
8+
int main()
9+
{
10+
scanf("%s", a);
11+
queue<char> first, second;
12+
int n = strlen(a);
13+
for (int i = 0; i < n; i++)
14+
{
15+
first.push(a[i]);
16+
}
17+
for (int i = 0; i < n; i++)
18+
{
19+
second.push(first.front());
20+
first.pop();
21+
}
22+
for (int i = 0; i < n; i++)
23+
{
24+
second.front();
25+
second.pop();
26+
}
27+
}

‎dataStructure/stack 1406.cpp‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
// stack 2개를 이용하면 풀 수 있다.
2+
#include <cstdio>
3+
#include <cstring>
4+
#include <stack>
5+
using namespace std;
6+
char a[600000];
7+
int main()
8+
{
9+
scanf("%s", a); // scanf로 일단 입력을 받는다.
10+
stack<char> left, right;
11+
int n = strlen(a);
12+
for (int i = 0; i < n; i++)
13+
{
14+
left.push(a[i]);
15+
}
16+
int m;
17+
scanf("%d", &m);
18+
while (m--)
19+
{
20+
char what;
21+
scanf(" %c", &what);
22+
if (what == 'L')
23+
{
24+
if (!left.empty())
25+
{
26+
right.push(left.top());
27+
left.pop();
28+
}
29+
}
30+
else if (what == 'D')
31+
{
32+
if (!right.empty())
33+
{
34+
left.push(right.top());
35+
right.pop();
36+
}
37+
}
38+
else if (what == 'B')
39+
{
40+
if (!left.empty())
41+
{
42+
left.pop();
43+
}
44+
}
45+
else if (what == 'P')
46+
{
47+
char c;
48+
scanf(" %c", &c);
49+
left.push(c);
50+
}
51+
}
52+
while (!left.empty())
53+
{
54+
right.push(left.top());
55+
left.pop();
56+
}
57+
while (!right.empty())
58+
{
59+
printf("%c", right.top());
60+
right.pop();
61+
}
62+
printf("\n");
63+
return 0;
64+
}

0 commit comments

Comments
 (0)