백준 자바 10844알고리즘 '쉬운 계단 수' 문제풀이




간단한 노트

DP(dynamic programming) 문제의 경우

숫자가 커질경우

컴퓨터의 중복되는 연산을 제거해주면

문제가 해결되는 경우가 있습니다

이문제는 간단하게

재귀문과 함께

이중배열안에 중복연산 값을 넣어서

해당 문제를 해결하였습니다







코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 10844 문제 링크

More info: 쉬운 계단 수 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




자바 코드

Procedure StairRecursion(int i, ind n)

Inputs :
- i : Value between 0 ~ 9
- n : Digit

Outputs :
- Number of Possibilities that i can have for given n

  1. if a[n][i] exists, then return a[n][i]

  2. if n equals 1 then return 1

  3. a) if i equals 0 then
    save StairRecursion((i + 1), (n - 1)) % 1000000000 to arr[n][i]
    then return arr[n][i]

    b) if i equals 9 then return
    save StairRecursion((i - 1), (n - 1)) % 1000000000 to arr[n][i]
    then return arr[n][i]

    c) if i equals (1 to 8) then return
    save (StairRecursion((i - 1), (n - 1)) + StairRecursion((i + 1), (n - 1))) % 1000000000 to arr[n][i]
    then return arr[n][i]

    1. this will hopefully sum up all the values being returned recursively




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

/*
Made by SONG KIM
2020-10-05
*/

import java.util.Scanner;

public class Main {


static long[][] arr = new long[101][10];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();

long sum = 0;

for (int i = 1; i < 10; i++) {
sum += StairRecursion(i, N);
}
System.out.println(sum % 1000000000);
}

private static long StairRecursion(int i, int n) {
if (arr[n][i] != 0) {
return arr[n][i];
}

if (n == 1) {
return 1;
}

if (i == 0) {
arr[n][i] = StairRecursion((i + 1), (n - 1)) % 1000000000;
return arr[n][i];
} else if (i == 9) {
arr[n][i] = StairRecursion((i - 1), (n - 1)) % 1000000000;
return arr[n][i];
} else {
arr[n][i] = (StairRecursion((i - 1), (n - 1)) + StairRecursion((i + 1), (n - 1))) % 1000000000;
return arr[n][i];
}
}

}











글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

즐겁고 행복한 하루 되세요~






백준 자바 2805 알고리즘 '나무 자르기 문제' 문제풀이





날씨가 많이 쌀쌀해졌군요

추운 날씨속에 학교 앞 자취방에서 코딩을 해봅니다.




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 2805번 문제 링크

More info: 나무자르기 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




첫번째 시도 (시간초과로 틀림)

Procedure findMaxH(long[] a, long p, long r, Long m)

Inputs :
- a : the array to search in
- p : the value we are searching for in a(min) m의 촤소값
- r : the value we are searching for in a(max) m의 최대값
- m : the value we are searching for in a(equal) 잘라야하는 나무의 값

Outputs :
- 잘라야하는 나무 산출량의 최대 높이

  1. 최소값을 0, 최대값을 나무의 최대크기로 정한다.
  2. 최소값 + 최대값의 평균값인 q를 구한다.
  3. q 값일때 나무 산출량을 H를 ValueOfTreeOutput을 통해 구한다.
    a) H가 m 보다 크면 최소값을 q+1로 수정한다
    b) H가 m 보다 작으면 최대값을 q-1로 수정한다
    c) H와m이 같다면 q를 반환한다.
  4. recursive 재귀적으로 돌린다.



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
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Long M = sc.nextLong();
long a[] = new long[N];
long maxLength = 0;


for(int i = 0; i<N; i++){
//Tree length
a[i] = sc.nextLong();
maxLength = Math.max(a[i],maxLength);
}

System.out.println(findMaxH(a, 0, maxLength, M));
}


private static long findMaxH(long[] a, long p, long r, Long m) {
long q = (p+r)/2;

long H = ValueOfTreeOutput(a, q);

if (H > m){
return findMaxH(a,q+1,r,m);
}

else if (H < m){
return findMaxH(a,p,q-1,m);
}

else{
return q;
}
}

private static long ValueOfTreeOutput(long[] a, Long H) {

long sum = 0;

for(int i = 0; i<a.length; i++){

long temp = a[i] - H;

if(temp > 0){
sum += temp;
}
}
return sum;
}
}








n번째 시도 (성공)




위에 코드에서

자바 배열을 오름차순으로 정렬


1
Arrays.sort(a);


재귀문 삭제


While 문 사용을 통해 시간을 줄였습니다


기본적인 틀은 binary search를 사용한다는 점에서 같습니다

문제에서 제시된 값이

매우 크기 때문에 조그마한 차이도 크게 느껴지는것 같습니다
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
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();

int []a = new int[N];

for(int i = 0; i<N; i++){
//Tree lengths
a[i] = sc.nextInt();
}

Arrays.sort(a); // 자바 배열을 오름차순으로 정렬

int p = 1;
int q;
int r = a[N-1];
long CalculatedOutPut = 0;
long GivenOutPut = M;

while (p <= r)
{
q = (p + r)/2;
CalculatedOutPut = 0;

for(int i = 0; i<N; i++){
if(a[i] >= q){
CalculatedOutPut += (a[i] - q);
}
}

if(CalculatedOutPut >= GivenOutPut){
p = q + 1;
}
else if(CalculatedOutPut < GivenOutPut){
r = q - 1;
}

}

System.out.println(r);
}



}




글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.






백준 자바 2346 알고리즘 풍선 터뜨리기 문제' 문제풀이





풍선 터트리기 백준 2346번 문제는

전에 풀었던 요세푸스 문제와 매우 유사합니다

링크드리스트(Linked List) 문제이며.

배열없이 Linked List를 이용해 풀었습니다.

원형 링크드리스트(Circular Linked List) 문제입니다.





백준 1158번 문제 링크

More info: 요세푸스 문제




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 2346번 문제 링크

More info: 풍선 터뜨리기 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘







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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
/*
Made by SONG KIM
2020-10-03
*/

import java.util.Scanner;

public class Main {
static int ValueBeingRemoved = 1;

public static class Node {

int data_row;
Node next;
Node previous;

public void displayNode_data_row(){
System.out.print(data_row);
}

}

public static class CustomLinkedList {
Node first;
Node last;

public CustomLinkedList() {
this.first = null;
this.last = null;
}

// 풍선 값을 입력 및 정렬
public void InsertFirst(int data_row){
Node newNode = new Node();
newNode.data_row = data_row;

if(IsEmpty())
{
last = newNode;
}else {
first.previous = newNode;
}
newNode.next = first;
this.first = newNode;

last.next = newNode;
newNode.previous = last;
}

// 풍선이 비어있는지 확인
public boolean IsEmpty(){
return first == null;
}

// 풍선 정보 출력
public void DisplayAll(){
Node temp = new Node();
temp = last;
Node newNode = new Node();
newNode = first;
if(IsEmpty()!=true)
{
while (temp.data_row != newNode.data_row)
{
// System.out.print(temp.data_row);
// System.out.print(" ");
temp = temp.previous;
}
// System.out.print(temp.data_row);
// System.out.println();
}
}



public int Balloon(int sn, int d){

int counter = 0;

// 처음에는 1을 없앤다
if (sn == 1)
{
counter = d;
}

// start from where data = sn
Node newNode = last;

if(IsEmpty())
{
return 0;
}

// System.out.println();
// System.out.println("first + last");
// System.out.println(first.data);
// System.out.println(last.data);
// System.out.println();

while (newNode.data_row != sn){
newNode = newNode.previous;
}

//System.out.println("d : "+ d);

// find data with d distance away
if(counter > d){
while (counter > d){
newNode = newNode.next;
//System.out.println("counter : " + counter + " newNode : " + newNode.data_row);
counter--;
}
}
else if(counter < d){
while (counter < d-1){
newNode = newNode.previous;
//System.out.println("counter : " + counter + " newNode : " + newNode.data_row);
counter++;
}
}
// if(d == 0){
// System.out.println("0은 적혀있지 않음");
// }

// print number being deleted
// System.out.println();
ValueBeingRemoved = newNode.data_row;
System.out.print(ValueBeingRemoved);

// System.out.println();

// allocation dData
// System.out.println();
// System.out.print("dData : " + newNode.dData);
// System.out.println();

// allocate next number
sn = newNode.previous.data_row;

// delete corresponding Node
// when newNode is last
if(newNode == last){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
last = newNode.previous;
}else {
newNode.next.previous = newNode.previous;
}

// when newNode is first
if(newNode == first){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
first = newNode.next;
}else {
newNode.previous.next = newNode.next;
}
return sn;

}
}

public static void main(String[] args) throws Exception {
CustomLinkedList cll = new CustomLinkedList();

Scanner sc = new Scanner(System.in);

// Number of Elements in the list
int N = sc.nextInt();

// Directional Data
int [] paperNumbers = new int[N+1];

// Initialize List with consecutive order
for (int i = 1; i <= N; i++) {

// Directional Data
paperNumbers[i] = sc.nextInt();
cll.InsertFirst(i);
}

// show all elements
// cll.DisplayAll();

// Starting number
int sn = 1;

//balloon Problem
for (int i = 0; i<N; i++){
//System.out.println();
//cll.DisplayAll();
//System.out.println();
//System.out.println("sn :" + sn);
sn = cll.Balloon(sn, paperNumbers[ValueBeingRemoved]);
if (i == N-1)break;
System.out.print(" ");
}


}
}





글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

오늘하루도 즐거운 하루 되세요~






백준 자바 1158 알고리즘 '요세푸스 문제' 문제풀이





코드를 보다보니 어느새 새벽이 되었네요.

새벽에 우는 귀뚜라미? 소리를 들으며 가을의 바람을 느껴봅니다

선선한 바람을 맞으며 푸는 코드

링크드리스트(Linked List) 문제를 배열없이 Linked List를 이용해 풀었습니다.

원형 링크드리스트(Circular Linked List) 문제입니다.




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 1158번 문제 링크

More info: 요세푸스 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




간단한 노트




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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

/*
Made by SONG KIM
2020-10-03
*/

import java.util.Scanner;

public class Main {

public static class Node {

int data;
Node next;
Node previous;

public void displayNode(){
System.out.println(data);
}

}

public static class CustomLinkedList {
Node first;
Node last;

public CustomLinkedList() {
this.first = null;
this.last = null;
}

public void InsertFirst(int data){
Node newNode = new Node();
newNode.data = data;

if(IsEmpty())
{
last = newNode;
}else {
first.previous = newNode;
}
newNode.next = first;
this.first = newNode;

last.next = newNode;
newNode.previous = last;
}

public boolean IsEmpty(){
return first == null;
}

public void DisplayAll(){
System.out.print("<");
Node temp = new Node();
temp = last;
Node newNode = new Node();
newNode = first;
if(IsEmpty()!=true)
{
while (temp.data != newNode.data)
{
System.out.print(temp.data);
System.out.print(", ");
temp = temp.previous;
}
System.out.print(temp.data);
System.out.print(">");
}
}

public int Josephus(int sn, int d){

int counter = 1;

// start from where data = sn
Node newNode = new Node();
newNode = last;

if(IsEmpty())
{
return 0;
}

// System.out.println();
// System.out.println("first + last");
// System.out.println(first.data);
// System.out.println(last.data);
// System.out.println();

while (newNode.data != sn){
newNode = newNode.previous;
}


// find data with d distance away
while (counter != d){
newNode = newNode.previous;
++counter;
}





// print number being deleted
System.out.print(newNode.data);


// allocate next number
sn = newNode.previous.data;

// delete corresponding Node
// when newNode is last
if(newNode == last){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
last = newNode.previous;
}else {
newNode.next.previous = newNode.previous;
}

// when newNode is first
if(newNode == first){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
first = newNode.next;
}else {
newNode.previous.next = newNode.next;
}


return sn;


}
}

public static void main(String[] args) throws Exception {
CustomLinkedList cll = new CustomLinkedList();

Scanner sc = new Scanner(System.in);

// Number of Elements in the list
int N = sc.nextInt();

// Number of Elements to be jumped
int K = sc.nextInt();

// Initialize List with consecutive order
for (int i = 1; i <= N; i++) {
cll.InsertFirst(i);
}

// show all elements
//cll.DisplayAll();

// Starting number
int sn = 1;

//Josephus Problem

System.out.print("<");
for (int i = 0; i<N; i++){
//cll.DisplayAll();
//System.out.println();
sn = cll.Josephus(sn, K);
if (i == N-1)break;
System.out.print(", ");
}
System.out.print(">");


}
}




글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.






백준자바 1021 알고리즘 '회전하는큐' 문제풀이





오늘도 상쾌한 마음으로 백준 문제를 풀었습니다.

링크드리스트(Linked List) 문제를 배열없이 Linked List를 이용해 풀었습니다.




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 1021번 문제 링크

More info: 회전하는 큐





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/*
Made by SONG KIM
2020-10-02
*/

import java.util.Scanner;

public class Main {

public static class Node {
int data;
Node next;
Node previous;

public void displayNode(){
System.out.println("{ " + data + " }" );
}
}

public static class CustomLinkedList {
Node first;
Node last;

public CustomLinkedList() {
this.first = null;
this.last = null;
}

public void InsertFirst(int data){
Node newNode = new Node();
newNode.data = data;

if(IsEmpty())
{
last = newNode;
}else {
first.previous = newNode;
}
newNode.next = first;
this.first = newNode;
}

public void InsertLast(int data){
Node newNode = new Node();
newNode.data = data;

if(IsEmpty())
{
first = newNode;
}else {
last.next = newNode;
}
newNode.previous = last;
this.last = newNode;
}

public Node DeleteFirstNode(){
Node temp = first;
if(first.next == null){
last = null;
}else {
first.next.previous = null;
}
first = first.next;
return temp;

}

public boolean IsEmpty(){
return (first == null);
}

//앞쪽 부터 몇번 리스트를 움직여야 해당 숫자를 없애는지 체크크
public int StepsFromFirst(int data){
int k = 0;
Node Current = first;
while (Current != null)
{
if(Current.data == data) {
return k;
}
Current = Current.next;
k++;
}
return k;
}

//given List is not empty;
public void RearrangeListToHaveDataFirst(int data){
Node Current = first;
while (Current != null){
if(Current.data == data){
break;
}
// DeleteFirstNode
if(first.next == null){
last = null;
}else {
first.next.previous = null;
}
first = first.next;

// InsertLast
Node newNode = new Node();
newNode.data = Current.data;
if(IsEmpty())
{
first = newNode;
}else {
last.next = newNode;
}
newNode.previous = last;
this.last = newNode;

//
Current = Current.next;
}
}

public void displayForward(){
System.out.println("List (first --> last) ");
Node Current = first;
while (Current != null){
Current.displayNode();
Current = Current.next;
}
System.out.println();
}


}

public static void main(String[] args) throws Exception {
CustomLinkedList cll = new CustomLinkedList();

Scanner sc = new Scanner(System.in);

// Number of Elements in the list
int N = sc.nextInt();

// Number of Elements to be removed
int M = sc.nextInt();

// Initialize List with consecutive order
for(int i =N;i>0;i--){
cll.InsertFirst(i);
}

//cll.displayForward();

// Count steps 2 and 3
int counter = 0;

for(int i=0;i<M;i++){
// Element to be removed
int a = sc.nextInt();

// Number of steps from the First element
int k = cll.StepsFromFirst(a);

if((N-i-k) > k){
counter += k;
}else{
counter += (N-i-k);
}

cll.RearrangeListToHaveDataFirst(a);
cll.DeleteFirstNode();
//cll.displayForward();


}

System.out.println(counter);
}

}




글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.