반응형

알고리즘 정렬기법 중 가장 기본적인 정렬 삽입, 버블, 선택 정렬을 정리했다

시간복잡도는 O(N^2)이고, 익숙해질 때까지 소스를 보면서 눈에 익히고 구현에 대해서도 계속 생각해보자.

선택정렬이 제일 헷갈렸다... 처음엔 제일 쉬워보였는데 어렵네

 

삽입정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 1; i < n; i++) {
            tmp = a[i];
            for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            for(j = 0; j < n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
        
    }
}
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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp = 0;
        int j;
        int index;
        
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            index = i;
            for(j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    index = j;
                    tmp = a[i];
                    a[i] = a[index];
                    a[index] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
이진 탐색  (0) 2023.01.07
반응형

1427번 소트인사이드

1427번: 소트인사이드 (acmicpc.net)

 

1427번: 소트인사이드

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

내림차순정렬.
수를 붙여서 준다
그러면 그걸 스플릿으로 잘라서 비교 후 내림차순정렬해보자
int형으로 바로 바꾼 후에 자리수별로 자르는거는 너무 지저분해보일까봐 안하고
String으로 입력받은 후 형변환을 통해 int배열에 입력 이후 비교정렬 실행했다.

--------
hint
Character.getNumericValue(charArray[i])를 활용한 int배열 등록

 

 

---------
solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String N = sc.nextLine();
        int temp;
        
        
        int length = N.length();
        char[] charArray = new char[length];
        int[] b = new int[length];
        
        for(int i = 0; i < N.length(); i++) {
            charArray[i] = N.charAt(i);
        }
        
        for(int i = 0; i < N.length(); i++) {
            b[i] = Character.getNumericValue(charArray[i]);
        }
        for(int j = 0; j < N.length(); j++) {
            for(int i = 0; i < N.length()-1; i++) {
                if(b[i] < b[i+1]) {
                    temp = b[i];
                    b[i] = b[i+1];
                    b[i+1] = temp;
                }
            }
        }
        for(int i = 0; i < N.length(); i++) {
            System.out.print(b[i]);
        }
    }
}
cs


실행시간 - 208ms
정렬을 다른기법을 쓰면 더 좋겠지만 아직 안됨. 직접 내 손으로 구현하는것이 현재목표
일부러 정렬관련 메서드는 사용하지않았다..

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
반응형

순차적으로 정렬되어있을 때 검색하는 가장 기본적인 검색방식이다.

 

방법은 중간값을 원하는 검색 값과 비교해서 검색하는 방식인데, 작을 땐 범위 아래로 내려서 O(logN) 의 시간복잡도를

갖고있다. 모든 자료를 순차로 탐색하는 것보다 효율이 좋아 자주쓰일 듯 하다.

구현도 쉬운편이고, 효율도 어느정도는 나오기에 구현 방식을 잘 기억해둬야겠다.

간단한 그림 예제와 소스코드 예제를 통해 익혀두기.

그림 예제

이 방식의 핵심은 제일 낮은 인덱스, 제일 큰 인덱스, 중간값 이 세 값을 구하는게 중요한데 중간 값(A[Center])비교를 기준으로 설명하자면

Max : 검색 값이 낮을 때 - Center대입

          검색 값이 높을 때 - 그대로

Min : 검색 값이 낮을 때 - 그대로

         검색 값이 높을 때 - Center대입

Center : 항상 (Min + Max) / 2를 해주면 중간값을 정할 수 있다.

첫번째 구역 나누기
두번째 구역 나누기

 

세번째 구역 나누기
네번째 구역 나누기

마지막 A[0]의 값이 찾는 값과 같다면 "값을 찾았습니다!"

아니라면 "찾는 값이 없어요"가 출력된다.

 

 

소스코드 예제

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[] a = {39, 41, 53, 55, 68, 72, 84, 88, 92, 97, 102};
        
        Scanner sc = new Scanner(System.in);
        
        int b = sc.nextInt();
        int center = 0;
        
        int max = a.length;
        int min = 0;
        
        center = a.length/2;
        
        while(true) {
            if(b == a[center]) {
                System.out.println("값을 찾았습니다!");
                break;
            }
            else if(center == 0) {
                System.out.println("찾는 값이 없어요");
                break;
            }
            else if(b < a[center]) {
                //min 안건드림
                max = center;
                center = (min + max) / 2;
                
                System.out.println("b가 작아 min : " + min + "| max : " + max + "| center : " + center);
            }
            else if(b > a[center]) {
                min = center;
                //max 안건드림
                center = (min + max) / 2;
                
                System.out.println("b가 커 min : " + min + "| max : " + max + "| center : " + center);
            }
        }
    }
}
 
cs

-------------

위에 있는 소스는 23.01.14 다른 문제를 풀다 알게된건데 틀린 예제입니다.

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] a = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        int left;
        int right;
        int center;
        
        long key = 0;
        int isTrue = 0;
        
        for(int i = 0; i < m; i++) {
            key = Integer.parseInt(st.nextToken());
            left = 0;
            right = a.length - 1;
            center = right / 2;
            isTrue = 0;
            while(left <= right) {
                if(a[center] == key) {
                    System.out.println("1");
                    isTrue = 1;
                    break;
                }
                else if(a[center] > key) {
                    right = center - 1;
                    center = (left + right) / 2;
                }
                else if(a[center] <key) {
                    left = center + 1;
                    center = (left + right) / 2;
                }
                
            }
            if(isTrue == 0) {
                System.out.println("0");
            }
        }
    }
}
cs

일단 간단한 예제를 올리기 전에 고쳐놓기....

요건 제 기준 어려운 예제임당...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
반응형

2563번 색종이

2563번: 색종이 (acmicpc.net)

 

2563번: 색종이

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록

www.acmicpc.net

다차원배열 단계에서 나온 색종이다.

가로세로어쩌구... 다차원 배열을 사용하라해서 배열에 0값에서 칠한것만 1로 바꾸고 하는 방식
중복되는 곳은 안바꾸면 그만 나중에 넓이출력은 전체탐색으로 1의 값을 갖고있는 것만 카운트하면될듯?

색종이의 수는 100이하 = 100개의 배열생성 후 쭉 추가하면될듯? 필요없을수도있고

일단 색종이의 넓이는 정사각형으로 한변이 10짜리다.즉 좌표값을 얻고 해당 좌표에서 +10까지 1을 넣어주면 된다.

hint
for(int j = x[i]; j < x[i]+10; j++) // 가로x축
for(int g = y[i]; g < y[i]+10; g++) // 세로y축값
색종이의 길이만큼만 1로 채우기

solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[][] a = new int[100][100];
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int count = 0;
        int[] x = new int[n];
        int[] y = new int[n];
        
        for(int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n; i++) { // n번 색칠하는거에 의미가 있는 for문
            
            for(int j = x[i]; j < x[i]+10; j++) { // 가로x축
                for(int g = y[i]; g < y[i]+10; g++) { // 세로y축값
                    if(a[j][g] == 0) {
                        a[j][g] = 1;
                    }
                }
            }
        }
        
        for(int i = 0; i < 100; i++) {
            for(int j = 0; j < 100; j++) {
                if(a[i][j] == 1) {
                    count++;
                }
            }
        }
        
        System.out.println(count);
    }
}
cs


실행시간 - 224ms

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
반응형

17478번 재귀함수가 뭔가요?

악명높은 재귀함수가 시작됐다...
지식인분들의 추천으로 정렬 전에 재귀함수를 하라하셔서 재귀부터 뿌셔보고 정렬을 다시 정복하려한다.
수 정렬하기는 브론즈1이였는데 이왜실5?

재귀횟수 1<=N<=50
재귀횟수에 따른 챗봇의 응답을 출력
ㅋㅋㅋㅋㅋ출력이 웃기다 근데 저걸 어케 구현하지?

일단 메서드부터 만들어서 Depth에 따른 출력값을 정해보자...

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

까지가 기본 출력값이라 생각된다.
이걸 함수 depth에 따라 나눠야하는데 위치가 중요할 것이다. 잘 고민해서 넣어보자

--------


hint
1depth당 ____(언더바임 사이드바 아님)이 들어간다. 참고해서 잘 보자

재귀하는 부분을 기준으로 위 아래로 나뉜다.

 

위

----

아래

이후 마지막 depth에 정답 호출과 첫 값 출력에 잊지말자.

--------

solution

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
import java.util.Scanner;
 
public class Main {
        static int repeatn;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        repeatn = n;
        
        myrepeat(0, n);
    }
    
    public static void myrepeat(int num, int n) {
        String s = "____";
        if(n >= 0) {
            for(int i = 0; i < num; i++) {
                System.out.print(s);
            }
            System.out.println("\"재귀함수가 뭔가요?\""); // s.repeat() 이건 자바11에서만사용
            if(n != 0) {
            
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
                
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
                
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
            }
            
            myrepeat(num+1,n-1);
            
            if(n == 0) {
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            }
            
            for(int i = 0; i < num; i++) {
                System.out.print(s);
            }
            
            if(num == 0) {
                System.out.println("라고 답변하였지.");
            }else {
                System.out.println("라고 답변하였지.");
            }
        }
    }
}
cs

 


실행시간 - 332ms

머릿속에서 한번에 생각해서 구현은 참.... 어렵다...
하다가 포기하고 구현하면서 생각 계속한거같다
결국 재귀함수에 두개의 정수를 입력받아야 구현이 됐다...
이것도 역시 깔끔하지 못해 아쉽지만 지금은 구현에 만족!!!

ps. 오타도 복붙해서 없고 문제될게 없는데 했는데... 하이픈(-)이 아니라 언더바(_)였다.... 아니 저거 누가봐도 띄엄띄엄 있어서 하이픈인줄.....

이거때문에
시간을 얼마나 먹은건지... 문제의 조건을 잘 봐야한다는 것을 이번에도 또 느끼게 됐다...

또, 조건에서 언더바말고도 마지막에 \n들어가는게 문제인가 해서 해당 조건도 추가해놨는데 그 부분은 문제가 없었다.

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20
반응형

10989번 수 정렬하기

n개의 수를 입력받고
n만큼 배열생성 후

오름차순출력 생각하고 같거나 높을 때 뒤로 내리는 정렬식
해봅시다

처음에는 순차정렬같은거로 해보고

두번째 구현때는 끝값기준으로 비교하는 정렬을 해보자.(이건 책에서 우연히 봄)

결국 시간초과됨ㅋㅋ
일단 대가리를 열심히 굴려서 구현한게 버블정렬 비스무리하게 만들었는데 완전한 버블이였으면 맞췄을거 버블을 제대로 구현하지 못해 시간초과가 계속 나왔다.

결국은 내장메서드 Arrays.sort()를 사용해서 해결...
이것도 나중엔 복수하러 온다.

--------

hint - 시간이 상당히 빡빡하니 속도최적화를 최우선시 해야한다
ex) BufferedReader, StringBuffer 등등 사용

--------
solution

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {// 순차정렬할것
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        int[] arrayInt = new int[n];
        
        for (int i = 0; i < n; i++) {
            arrayInt[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arrayInt);
        
        
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<arrayInt.length;i++){
            sb.append(arrayInt[i]+"\n");
        }
        System.out.println(sb);
    }
}
cs


실행시간 - 2700ms

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1712번 손익분기점 자바로 풀어 본 짧은 글  (0) 2022.12.20
반응형

2798번 블랙잭

첫째줄 입력 : n M
둘째줄 입력 : n의 갯수만큼의 넘버

알고리즘
해당 수 중에서 3개의 수 합이 M에 가장 가까운 합을 구해야한다 때문에 고민을 좀 했었는데 지금 생각나는건 전체탐색(브루트포스) 을 하는데 정답 값이 나왔을 때에만 종료조건을 달아서 해결하는 방식이다.

--------

hint

3중for문 이후 if(i != j && i != g && j != g)
3중for문으로 계속 탐색하는데 i,j,g가 서로 같을 때는 연산x
이후 만약에 정답 수가 나오면 그대로 중첩for문을 나오게끔해서 약간의 최적화 시도

--------

solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n, M;
        int a;
        int maxTmp = 0;
        int end = 0;
        
        n = sc.nextInt();
        M = sc.nextInt();
        
        
        int[] intArray = new int[n];
        
        for(int i = 0; i < n; i++) {
            intArray[i] = sc.nextInt();
        }
        //3중for문으로 확인작업
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int g = 0; g < n; g++) {
                    if(i != j && i != g && j != g) {
                        
                        a = intArray[i] + intArray[j] + intArray[g];
                        
                        if(M >= a) {
                            if(maxTmp < a) {
                                maxTmp = a;
                            }
                            if(maxTmp == M) {
                                end = 1;
                                break;
                            }
                        }
                    }
                }
                if(end == 1){break;}
            }
            if(end == 1){break;}
        }
        System.out.println(maxTmp);
    }
}
cs

실행시간 - 232ms

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1712번 손익분기점 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1193번 분수찾기 자바로 풀어 본 짧은 글  (0) 2022.12.20
반응형

2292번 벌집

처음 문제 마주했을 때 숨이 막혔는데 생각보다 난이도가 쉬워보인다.
첫번째 칸 기준으로 점차 늘어나는걸 잘 캐치해야할듯
분수찾기의 쉬운버전같음

 

--------
hint

답이 없는 줄 알았는데, 규칙이 생각보다 쉽다.
중앙 1 기준으로  첫번째 depth = 6
두번째 depth = 12
세번째 depth = 18
....
해당 범위에 맞게 하면 됨

규칙성을찾고
a + 1이 입력값 n을 넘겼을 때 종료 후 depth 출력

--------

Solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args){
        int n;
        Scanner sc = new Scanner(System.in);
        int a = 1;
        int b = 0;
        n = sc.nextInt();
        int count = 0; // depth대신 count사용
        if(n == 1) {
            System.out.println(1);
        }
        else {
            while(true) {
                a = a + b;
                b = b + 6;
                count++;
                if(n < a + 1) {
                    break;
                }
            }
            System.out.println(count);
        }
    }
}
cs

실행시간 - 204ms

break하는 위치를 찾는데 약간 애먹었다.

처음 1을 갖고 시작하기 때문에 n이 a+1보다 적어질 때의 카운트를 출력하면 된다.

아직도 상당히 범위도 잡기 어렵고 규칙을 코드로 구현하기에 헷갈리지만 계속 형태와 방식에 익숙해져야 한다...

수학부분 너무 어렵다

 

 

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
백준 1712번 손익분기점 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1193번 분수찾기 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 2869번 달팽이는 올라가고 싶다 자바로 풀어 본 짧은 글  (0) 2022.12.18
반응형

1712번 문제 손익분기점


고정비용 : A
노트북 한대 가변비용 : B
노트북 판매가격 : C

A + B - C < 0이 되었을 때 끝남.
달팽이랑 비슷한거같은데?

조건 : 21억 이하 자연수면 int로 가능
분기점 존재하지않으면 -1 or 손익분기점 판매수

--------
hint
앞서 올린 달팽이와 상당히 유사함
조건만 잘 따져서 해보자

--------
Solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args){
        int A, B, C;
        Scanner sc = new Scanner(System.in);
        int sellmoney;
        int sonik;
        int count;
        
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        
        //구현부
        if(B < C) {
            sellmoney = C - B; // 판매시 순 이익
            
            sonik = A / sellmoney;
            count = sonik + 1; // 마지막 하나 더 팔아야 분기점 돌파
            System.out.println(count);
        }else {
            System.out.println(-1);//손익분기점 미존재
        }
    }
}
cs

실행시간 - 204ms

고정비용 : A
노트북 한대 가변비용 : B
노트북 판매가격 : C

sellmoney = C - B; // 판매시 순 이익

sonik = A / sellmoney;

B < C 일 때는 -1출력

달팽이의 힘.... 정말 쉽게풀었따

 

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1193번 분수찾기 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 2869번 달팽이는 올라가고 싶다 자바로 풀어 본 짧은 글  (0) 2022.12.18
백준 2204번 도비의 난독증 테스트 자바로 풀어 본 짧은 글  (0) 2022.12.18
반응형

1193번 분수찾기 문제

생각

처음 시도한 방법 : 칸을 생각하지 않고 분자와 분모의 규칙성을 찾아내서 

1 - 1 - 2 - 3 - 2 - 1 - 1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 – 1 - 1– 2 – 3 – 4 – 5 – 6 – 7 – 6 – 5 – 4 – 3 – 2 - 1

분자 A 규칙 : 1 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복

1 – 2 – 1 – 1 – 2 – 3 – 4 – 3 – 2 – 1 – 1 – 2 – 3 – 4 – 5 – 6 – 5 – 4 – 3 – 2 - 1

분모 규칙 : 0 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복

이러한 패턴을  알게 돼서 구현만 하면 될줄 알았는데 나중에 확인해보니 시간제한이 0.5초였다.

또 내가 수학적 생각을 안하고 무대포로 풀 생각만 했구나 싶었다.

결과적으로 저렇게 연산을 했을 때 시간이 부족해서 필히 문제가 생겼을 것이다.

아무리 생각해도 정확한 정답이 나오지 않아 결국 다른 분들의 풀이를 봤다.

-------

hint

이걸 보면서 규칙성 확인

 

-------

Solution

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        
        int a = 0;
        int count = 1;
        int b = 0;
        int tmp = 0;
        int mother, child;
        
        while(true) {
            if( a >= n ) {
                b = a - n - 1;
                
                mother = n - tmp;
                child = count - mother;
                if(child < 0) {
                    child *= -1;
                }
                
                child = count - mother;
                if(count % 2 == 1) {
                    System.out.println(mother + "/" + child);
                }
                else {
                    System.out.println(child + "/" + mother);
                }
                break;
            }
            
            tmp = a;
            a += count;
            count++;
        }
    }
}
 
// 2 3 4  5  6  7  8
//1 3 6 10 15 21 28 36
cs

실행시간 - 224ms


위의 hint그림 처럼 대각선 기준으로 정방향 역방향으로 1부터 순차증가가 된다.
이 부분을 체크해서 각 대각라인 별 갯수가 1 - 3 - 6 - 10 - 15 - 21 순으로 증가하는데,
a(0) = a + 대각라인 으로 총 갯수를 파악 가능하며, 
child / mother라 했을 때 mother = n - tmp로 해당 번호의 순번, 즉 분자나 분모의 값 하나를 구할 수 있고
이후 count - mother를 통해 다른 분자나 분모의 값을 구할 수 있다.
count - mother가 가능한 이유는 각 대각라인 순번별로 2부터 시작해 합이 1씩 증가한다. 그 합은 child + mother 이다.

---
수학 문제는 난이도가 쉽게 나와도 정말 풀기 어려운 듯 하다 최적화를 떠나서 구현 자체가 너무 힘듦
이후에도 해당 문제는 계속 들여다볼 것 같다.

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 1712번 손익분기점 자바로 풀어 본 짧은 글  (0) 2022.12.20
백준 2869번 달팽이는 올라가고 싶다 자바로 풀어 본 짧은 글  (0) 2022.12.18
백준 2204번 도비의 난독증 테스트 자바로 풀어 본 짧은 글  (0) 2022.12.18
백준 4447번 좋은놈 나쁜놈 자바로 풀어 본 짧은 글  (0) 2022.12.18

+ Recent posts

티스토리툴바