Skip to content

9주차 알고리즘 문제 풀이 - 황희정 #36

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
hwangheejung wants to merge 4 commits into
base: main
Choose a base branch
from
Open

9주차 알고리즘 문제 풀이 - 황희정 #36

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
736a094
BOJ_1912
hwangheejung Aug 21, 2024
2eba56f
BOJ_1003
hwangheejung Aug 23, 2024
a7b8c6a
BOJ_2193
hwangheejung Aug 23, 2024
8311464
BOJ_1932
hwangheejung Aug 23, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
44 changes: 44 additions & 0 deletions src/heejung/boj/DP/_1003/1003.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,44 @@
#include<iostream>
#include<vector>
using namespace std;

int arr[40];
int zero = 0, one = 0;
int fibonacci(int n) {
if (n == 0) {
zero = zero + 1;
return 0;
}
else if (n == 1) {
one = one + 1;
return 1;
}
else {
int x = n - 1;
int y = n - 2;
return fibonacci(x) + fibonacci(y);
}
}

int main() {
int t;
cin >> t;
vector<pair<int, int>> result;
result.push_back({ 1,0 }); //0 ����
result.push_back({ 0,1 });//1 ����
for (int i = 0;i < t;i++) {
cin >> arr[i];

}

for (int i = 0;i < t;i++) {
if(arr[i]>result.size()-1) {
for (int j = result.size();j <= arr[i];j++) {
result.push_back({ result[j - 1].first + result[j - 2].first,result[j - 1].second + result[j - 2].second });
}
}

cout << result[arr[i]].first<<" "<<result[arr[i]].second << "\n";

}
}
36 changes: 36 additions & 0 deletions src/heejung/boj/DP/_1912/1912.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,36 @@
#include<iostream>
#include<vector>
using namespace std;

int maxfun(int a, int b) {
if (a > b)
return a;

else
return b;
}

int main() {
int c;
cin >> c;
vector<int> vec;
for (int i = 0;i < c;i++) {
int t;
cin >> t;
vec.push_back(t);
}
int max = -1000;
int sum = 0;

for (int i = 0;i < c;i++) {
if (vec[i] > sum + vec[i]) {
sum = vec[i];
max = maxfun(sum, max);
}
else {
sum += vec[i];
max = maxfun(sum, max);
}
}
cout << max <<"\n";
}
45 changes: 45 additions & 0 deletions src/heejung/boj/DP/_1932/Main.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,45 @@
package _1932;

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

패키지 경로가 이상한데 한번 확인이 필요해 보여요!

package heejung.boj.DP._1932; 가 되어야 해요!


import java.io.*;
import java.sql.Array;

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

문제 풀이에 사용 되지 않은 코드로 삭제가 필요해 보여요.. 🥹

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

import java.sql.Array; 이 부분 입니당

import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

문제 풀이에 사용 되지 않은 코드로 삭제가 필요해 보여요.. 🥹

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

StringBuilder sb = new StringBuilder(); 이 부분 입니당


int n = Integer.parseInt(br.readLine());
int [][] arr = new int[n][n];
StringTokenizer st;
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<=i;j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
Comment on lines +12 to +20

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

저는 StringTokenizer를 사용하지 않고 배열을 활용하고, 입력 받는 라인을 곧 바로 stream을 활용해 input 값을 초기화하곤 해요. 그러면 한번에 처리가 가능해서 생산성도 높아지고 가독성도 높아지더라구요!

아래의 코드는 제가 사용하는 방법인데 스타일에 따라 참고 해보셔도 좋을 것 같습니다! (코드가 틀렸다는 것은 아니에요!)

int n = Integer.parseInt(br.readLine()); // Input Line 1 

int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) { // n번 반복
    arr[i] = Arrays.stream(br.readLine().split(" ")) // 1) Input을 통해 공백(" ")을 기준으로 나누기
                            .mapToInt(Integer::parseInt) // 2) 나눈 값을 Integer 타입으로 매핑(String -> Integer)
                            .toArray(); // 배열로 만들기
}

int result[][] = new int[n][n];
result[0][0] = arr[0][0];
int max=arr[0][0];
for(int i=1;i<n;i++){
for(int j=0;j<=i;j++) {
if (j == 0) {
result[i][j] = result[i-1][j]+arr[i][j];
} else if(j==i){
result[i][j] = result[i-1][j-1]+arr[i][j];
} else{
result[i][j] = Math.max(result[i - 1][j] + arr[i][j],result[i-1][j-1]+arr[i][j] );


if(max<result[i][j]){
max = result[i][j];
}
}

}
Comment on lines +24 to +39

@IToriginal IToriginal Aug 27, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

코드를 한번 점검해 볼 필요가 있을 것 같아요!(띄워쓰기, 코드 다음 라인 줄 맞춤..)
else 문 안에서 최대 값을 한번 result[i][j]에 초기화 하고 있기 때문에 매번 else 문 실행에서 if 조건을 확인할 필요가 없어 보여요.
그래서 else 문 밖(1라인의 for문이 돌았을 때)에서 라인의 최대값이 저장된 result[i][j]를 아래와 같이 max값과 비교해서 값을 변경해줘도 될 것 같다는 생각이 들었어요!

for (int i = 1; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        if (j == 0) {
            result[i][j] = result[i - 1][j] + arr[i][j];
        } else if (j == i) {
            result[i][j] = result[i - 1][j - 1] + arr[i][j];
        } else {
            result[i][j] = Math.max(result[i - 1][j] + arr[i][j], result[i - 1][j - 1] + arr[i][j]);
        }
        max = Math.max(max, result[i][j]);
    }
}

추가로 위에서 아래로 문제를 해결하신 것으로 보이는데 저는 아래에서 위로 문제를 해결하여서 저와 다른 방향의 문제 풀이 방법이라 참고하시면 서로 도움될 것 같아요!


System.out.println(max);


}
}
21 changes: 21 additions & 0 deletions src/heejung/boj/DP/_2193/2193.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,21 @@
#include<iostream>
using namespace std;
int main() {
long long arr[91][2] = { {0,0},{0,1},{1,0} };

int n;
cin >> n;

int sum = 0;
for (int i = 2; i <= n; i++)
{
arr[i][0] = arr[i - 1][0] + arr[i - 1][1];
arr[i][1] = arr[i - 1][0];




}
cout << arr[n][0] + arr[n][1] << "\n";
return 0;
}