Spring이란?

  • Java언어 기반의 프레임워크
  • Java로 다양한 어플리케이션을 만들기 위한 프로그래밍 틀

프레임워크❓

  • 프로그램 기본 구조(뼈대)
  • 원하는 기능 구현에만 집중하여 빠르게 개발할 수 있도록 기본적으로 필요한 기능을 갖추고 있는 것.

쉽게 이해할 수 있도록 집을 짓는 것으로 비유를 해보자.

사용자가 집을 직접 짓기 위해 설계도를 직접 그리고 각각의 기초 작업들을 일일이 하는 것 보다, 전문가들의 도움을 받아 작업을 하면 더욱 쉽고 효율적으로 집을 지을 수 있는 것처럼 프레임워크를 사용한다면 프레임워크가 제공하는 여러 기능들을 사용해서 빠르고 효율적으로 프로그램을 구축할 수 있을 것이다.

 

프레임워크를 사용하면 뭐가 좋을까❓

개발 프로세스 간소화

프레임워크에서 제공하는 여러 도구와 패키지는 개발자가 스크립트를 처음부터 작성할 필요가 없고, 이미 만들어진 코드를 재사용하게 되므로 재사용성을 높이고, 시간과 비용을 아낄 수 있다.

 

유지보수 용이

프레임워크를 사용한다면 코드가 체계적이고 상대적으로 정형화되기 때문에, 개발자가 중간에 교체되더라도 위험이 적고, 이후 소스코드의 유지보수도 상당히 용이해진다.

 

보안

개발자는 일반적으로 SQL Injection, CSRF 등 외부 공격을 방어하기 위한 추가적인 소스코드를 작성해야하지만, 프레임워크를 사용하면 이러한 일들을 할 필요가 없다. 대부분의 프레임워크와 함께 제공되는 보안 기능들은 개발자가 웹 사이트 혹은 애플이케이션을 보호할 수 있는 방법을 제공하기 때문이다.

 

그럼 프레임워크의 단점은 없을까❓

사전학습

다양한 기능을 제공하고, 미리 만들어져있는 기능을 사용하기 위해서는 학습이 필요하다. 새로운 프레임워크를 학습하고 사용하기 위해서는 많은 공부가 필요하다.

 

제약사항

제공하고 있는 기능들 외에, 원하는 옵션을 추가하는 것에 굉장히 보수적일 수 있다.

사용법이 정해져 있고, 기본적으로 설계된 구조를 바탕으로 코드를 작성하고 기능을 완성해야하기 때문에 코드를 유연하게 개발하는데 있어서 한계가 있을 수 있다.

 

크기

프레임워크는 많은 기능을 제공한다. 이는 개발하면서 필요하지 않은 기능도 포함된다는 것을 의미하고, 불필요한 기능이 메모리를 차지하기 때문에 리소스 낭비로 이어질 수 있다.

 

 

💡스프링(Spring)의 특징 -⭐ 결합도를 낮춰 유연할 개발 가능하게 해준다!

  • 제어의 역전(IOC : Inversion of Control)
    • 프로그램의 생명주기에 대한 제어권이 웹 애플리케이션 컨테이너에 있다. 
    • 사용자가 직접 new 연산자를 통해 인스턴스를 생성하고 메서드를 호출하는 일련의 생명주기에 대한 작업들을 스프링에 위임
    • 객체관리 주체가 프레임워크(Container)가 되기 때문에 개발자는 로직에 집중할 수 있다는 장점이 있다.

 

  • 의존성 주입(DI)
    • 객체 사이에 필요한 의존 관계에 대해서 스프링 컨테이너가 자동으로 연결해 주는 것
    • DI를 이용하여 빈(Bean) 객체 관리, 스프링 컨테이너에 클래스를 등록하여 스프링이 클래스의 인스턴스를 관리해 준다.
    👉🏻스프링 컨테이너에 빈(Bean)을 등록하고 설정하는 방법
    1. XML 설정을 통한 DI - applicationContext.xml에서 설정
    2. 어노테이션을 이용한 DI
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //DI가 없는 예제
    @RestController
    public class Controller{
        Service service = new Service(); //객체간의 결합도↑
     
    @RequestMapping("/hello")
    public String hello(){
            return service.helloMessage();
        }
    }
    		 cs

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //DI가 있는 예제
     
    //service
    @Component
    public class Service{
        public String helloMessage(){
            return "hello~"
        }
    }
     
    //controller
    @RestController
    public class Controller{
        @Autowired
        Service service;
     
        @RequestMappint("/hello")
        public String hello(){
            return service.helloMessage();
        }
     
    }
    		 cs
    → 어노테이션으로 Service 객체의 인스턴스를 쉽게 얻을 수 있다. = 결합도↓

 

  • 관점 지향 프로그래밍(AOP)
    • 주요 핵심 기능과 핵심 기능 구현을 위한 부가적인 기능(로깅 작업, 데이터베이스 연결 및 트랜잭션 처리, 파일 입출력 등) 구현을 분리하여 각각의 관점별로 묶어서 개발하는 방식

그럼 왜 스프링 부트가 필요할까❓

  • Spring MVC 프레임워크를 사용할 때 applicationContext.xml이외에 다양한 설정을 통해 의존성을 주입해야한다.
  • 기본 프로젝트를 셋팅하는데 많은 시간 소요

그럼 Spring Boot는 뭐가 다를까❓

  • Spring Boot는 따로 설정할 필요 없이 단지 실행만 하면 된다!
  • spring-boot-starter-web을 사용하면 종속된 모든 라이브러리를 알맞게 찾아서 가져오기 때문에 종속성이나 호환 버전에 대해 신경 쓸 필요가 없다!

공부하면서 작성한 글입니다. 틀린 내용이 있다면 알려주세요!🙏🏻

 

 

👀 참고

https://dzone.com/articles/spring-vs-spring-boot

https://msyu1207.tistory.com/entry/Spring-VS-Spring-Boot-차이점을-알아보자

'정리 > Spring' 카테고리의 다른 글

[Spring] DI & AOP  (0) 2021.09.24
[Spring] REST API  (0) 2021.09.09
[Spring] Spring MVC  (0) 2021.09.09
[Spring Boot + Vue.js] 구글로그인  (0) 2021.08.18
[Spring Boot] 이메일 인증 회원가입하기 구현  (2) 2021.07.23

다익스트라 알고리즘

  • 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘
  • 음의 가중치X
  • 시간 복잡도 O((V+E)logV) V=정점 개수, E=한 정점의 주변노드

 

예시

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
 
public class Main{
    
    public static class Node{
        int v,w;
 
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static List<Node> list[];
    static int [] distance;
    static boolean []visited;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        list =new ArrayList[N+1];
        distance = new int [N+1];
        visited = new boolean[N+1];
        
        for(int i=1;i<N+1;i++) list[i]= new ArrayList<>();
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int arrive = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            list[start].add(new Node(arrive,price));
        }
        
        st = new StringTokenizer(br.readLine()," ");
        int go = Integer.parseInt(st.nextToken()); //시작점
        int end = Integer.parseInt(st.nextToken()); //도착점
        
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[go] = 0; //시작점 0으로
        
        int min, current = 0;
        for(int i=0; i<N;i++) {
            min = Integer.MAX_VALUE;
            current = -1;
            for(int j=1;j<N+1;j++) { //거리가 가장짧은 정점찾기
                if(!visited[j] && distance[j]<min) {
                    min = distance[j];
                    current =j;
                }
            }
            if(current == end) break;
            
            for(Node next : list[current]) { //찾은 정점과 연결된 정점들의 거리 저장
                if(!visited[next.v] && distance[next.v]> distance[current]+next.w) {
                    distance[next.v] = distance[current] + next.w;
                }
            }
            visited[current] = true;
        }
        System.out.println(distance[end]);
    }
}
 cs

 

 

'정리 > 자료구조+알고리즘' 카테고리의 다른 글

투 포인터(Two Pointer)  (0) 2021.08.26
이진 탐색 (Binary Search) 알고리즘  (0) 2021.07.05
세그먼트 트리(Segment Tree)  (0) 2021.07.01
위상정렬  (0) 2021.06.18
비트마스크 (BitMask)  (0) 2021.04.21
 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이

www.acmicpc.net

 

풀이 방법

모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제였습니다.

 

저는 먼저 이렇게 크게 

1. 바이러스가 놓일 수 있는 연구소 위치를 list에 담기

2. 조합을 이용해 전체 바이러스 개수 중 M개 선택하기

3. 선택한 바이러스 퍼뜨리기

4. 바이러스가 퍼지는 최소 시간 구하기

이 순서로 구현했습니다.

 

조합을 이용해 M개의 바이러스 놓을 칸을 정했다면 spread() 메서드에서 상 하 좌 우로 이동하면서

바이러스를 퍼지게했습니다. 모든 바이러스가 퍼진 뒤에는, 최소 시간을 구해야 하기 때문에 time() 메서드를 통해서

모든 빈 칸에 바이러스가 퍼졌는지 확인과 함께 퍼뜨리는 최소 시간을 구해주었습니다.

이렇게 모든 바이러스가 놓일 수 있는 경우를 확인한 후 가장 최소 시간을 마지막에 출력해주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_17121_연구소2 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
    
    static int N,M, time = Integer.MAX_VALUE;
    static int [][] map, copy;
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    static ArrayList<info> list = new ArrayList<>();
    static ArrayList<info> select = new ArrayList<>();
    static Queue<info> queue = new LinkedList<>();
    static boolean [][] selected;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //연구소 크기
        M = Integer.parseInt(st.nextToken()); //바이러스 개수
        
        map = new int[N][N];
        selected = new boolean[N][N];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==1) map[i][j]= -1;
                else if(map[i][j]==2) {
                    list.add(new info(i,j));
                    map[i][j] =0;
                }
            }
        }
        comb(0,0);
        if(time==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(time);
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==M) {
            // 바이러스 퍼지기 & 최소 시간 확인
            spread();
            return;
        }
        
        for(int i=start;i<list.size();i++) {
            int x = list.get(i).x;
            int y = list.get(i).y;
            if(selected[x][y]) continue;
            
            select.add(new info(x,y));
            selected[x][y] = true;
            
            comb(cnt+1,i+1);
            selected[x][y] = false;
            select.remove(select.size()-1);
        }
        
    }
    
    public static void spread() {
        
        transfer();
        copy();
    
        while(!queue.isEmpty()) {
            info temp = queue.poll();
            
            for(int i=0;i<4;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny) && copy[nx][ny]==0 && !selected[nx][ny]) {
                    copy[nx][ny] = copy[temp.x][temp.y]+1;
                    queue.add(new info(nx,ny));
                }
            }
        }
        if(time()!=-1 && time>time()) time=time();
    }
    
    public static void copy() {
        copy = new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                copy[i][j]=map[i][j];
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
    
    public static void transfer() {
        for(int i=0;i<select.size();i++) {
            queue.add(new info(select.get(i).x, select.get(i).y));
        }
    }
    
    public static int time() {
        int min=0, count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(copy[i][j]>min) min = copy[i][j];
                if(copy[i][j]==0) count++;
            }
        }
        if(count!=M) return -1;
        
        return min;    
    }
 
}
 
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
백준 1520 내리막길 [JAVA]  (0) 2021.09.10
백준 16236번 아기 상어 [JAVA]  (0) 2021.08.29
백준 9081번 단어 맞추기 [JAVA]  (0) 2021.07.08
백준 1713번 후보 추천하기 [JAVA]  (1) 2021.07.04

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

 

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

예제

풀이 방법

이 문제는 저번에 도전했으나 해결하지 못해서 다시 풀어본 문제입니다.

 

이 문제에서 아기 상어가 어디로 이동해야 할지 결정하는 방법은

1. 가장 가까운 물고기를 잡아먹되

2. 가까운 물고기가 1마리 이상이라면 가장 위의 있는 물고기

3. 2번 조건을 만족하는 물고기가 1마리 이상이라면 가장 왼쪽의 있는 물고기를 먹기

위의 조건을 만족하는 물고기를 잡아먹어야 합니다.

 

여기서 주의해야 할 점은 아기 상어보다 크기가 큰 물고기는 지나갈 수 없고, 크기가 같은 물고기는 지나갈 수는 있으나 잡아먹을 순 없다. 즉, 아기 상어보다 크기가 작은 물고기만 잡아먹을 수 있다는 점.

또한 아기 상어의 크기만큼 물고기를 잡아먹었다면 아기 상어 크기가 1 증가한다는 점입니다.

 

제가 푼 방법은

1. 아기 상어 위치 shark 큐에 넣기

2. 아기 상어를 상 하 좌 우로 움직이면서 먹을 수 있는 먹이 정보 feed 큐에 넣기

3. feed 큐에 들어 있는 먹이들 중 거리가 가장 가까운 먹이 먹기 = (먹이 위치 0으로 변경)

4. 해당 먹이 위치로 아기 상어 이동, 잡아먹은 횟수 1 증가, 먹이 큐 초기화, 아기 상어가 먹은 물고기 수 확인하여 아기 상어 크기 1 증가

해당 먹이가 없을 때까지 1 ~ 4번 반복해주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_16236_아기상어 {
    
    static class info{
        int x,y,distance;
 
        public info(int x, int y, int distance) {
            super();
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
        
    }
    
    static int [] dx = {-1,1,0,0}; //상 하 좌 우
    static int [] dy = {0,0,-1,1};
    
    static int N, shark_age, size=0, count=0, time=0;
    static int [][] map;
    static PriorityQueue<info> feed = new PriorityQueue<>(new Comparator<info>() {
        //가장 가깝고, 가장 위, 가장 왼쪽
        @Override
        public int compare(info o1, info o2) {
            if(o1.distance==o2.distance) {
                if(o1.x==o2.x) return o1.y-o2.y;
                else return o1.x-o2.x;
            }
            return o1.distance-o2.distance;
        }
    });
    
    static Queue<info> shark = new LinkedList<>();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==9) {
                    shark.add(new info(i,j,0));
                    map[i][j] = 0;
                }
            }
        }
        shark_age=2;
        findFeed();
 
    }
    
    public static void findFeed() {
        
        while(true) {
            
            boolean [][] visited = new boolean[N][N];
            
            while(!shark.isEmpty()) {
                info temp = shark.poll();
                visited[temp.x][temp.y] = true;
                
                for(int i=0;i<4;i++) {
                    int nx = temp.x+dx[i];
                    int ny = temp.y+dy[i];
                    
                    if(range(nx,ny) && !visited[nx][ny]) {
                        if(0<map[nx][ny] && map[nx][ny]<7) {
                            if(map[nx][ny]<shark_age) {
                                feed.add(new info(nx,ny,temp.distance+1));
                                shark.add(new info(nx,ny,temp.distance+1));
                                visited[nx][ny]=true;
                            }
                            else if(map[nx][ny]==shark_age) {
                                shark.add(new info(nx,ny,temp.distance+1));
                                visited[nx][ny]=true;
                            }
                        }
                        else if(map[nx][ny]==0) {
                            shark.add(new info(nx,ny,temp.distance+1));
                            visited[nx][ny]=true;
                        }
                    }
                }
            }
            
            //가장 가까운 물고기 먹고
            if(!feed.isEmpty()) eat();
            else break;
        }
        System.out.println(time);
        
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
    
    public static void eat() {
        info eat = feed.poll();
        
        count++;
        if(count==shark_age) {
            shark_age++;
            count=0;
        }
        
        shark.add(new info(eat.x,eat.y,0));
        time+=eat.distance;
        map[eat.x][eat.y]=0;
        feed.clear();
    }
 
}
 
 cs

 

'문제 > 백준' 카테고리의 다른 글

백준 1520 내리막길 [JAVA]  (0) 2021.09.10
백준 17121 연구소2 [JAVA]  (0) 2021.09.02
백준 9081번 단어 맞추기 [JAVA]  (0) 2021.07.08
백준 1713번 후보 추천하기 [JAVA]  (1) 2021.07.04
백준 4358번 생태학 [JAVA]  (0) 2021.06.30

투 포인터 알고리즘

  • 1차원 배열에서 두 개의 포인터를 조작해가면서 원하는 결과를 얻는 알고리즘이다.
  • 투 포인터 알고리즘을 이용해 O(N^2)에서 O(NlogN)으로 개선할 수 있다.

 

예시

  • SUM =5 인 경우의 수 구하기

  • 위의 과정을 배열의 인덱스가 N일때 즉 모두 확인했을 때 반복문 종료!

 

코드

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
package twoPointer;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2003_수들의합2 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int [] arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start=0, end=0, sum=0, cnt=0;
        while(true) {
            if(sum>=M) sum -= arr[start++];
            else if(end==N) break;
            else sum += arr[end++];
            
            if(sum==M) cnt++;
        }
        System.out.println(cnt);
    }
 
}
 
 cs

 

 

 

'정리 > 자료구조+알고리즘' 카테고리의 다른 글

다익스트라(Dijkstra) 알고리즘  (0) 2021.09.04
이진 탐색 (Binary Search) 알고리즘  (0) 2021.07.05
세그먼트 트리(Segment Tree)  (0) 2021.07.01
위상정렬  (0) 2021.06.18
비트마스크 (BitMask)  (0) 2021.04.21

구글 로그인 

  • 구글 로그인 버튼 클릭
1
2
3
<a href="https://accounts.google.com/o/oauth2/v2/auth?scope=https://www.googleapis.com/auth/userinfo.email&response_type=code&client_id={client_id}&redirect_uri={redirect_uri}">
<img :src="require('@/assets/images/google-icon.png')"/>
</a>
 cs

 

  • 구글 로그인 진행 후, 리다이렉트 페이지로 이동하면 url에 Authorization code 확인!

 

  • Authorization code axios를 통해 백엔드에 전달
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let googleCode = new URL(window.location.href).searchParams.get("code");
    if(googleCode != null){
      console.log("구글로그인 시도");
      store.dispatch("auth/requestGoogleToken", googleCode)
      .then(function(result){
        console.log(result)
        if (result.data.idToken) {
          console.log("구글 result: ", result.data.idToken)
          console.log("구글 email : ",result.data.email )
          localStorage.setItem("jwt", result.data.idToken);
          store.commit("auth/setToken", result.data.idToken);
          store.commit("auth/setEmail", result.data.email);
          store.commit("auth/setProvider","google"); // 로그아웃할때 방식 다 달라서 구분용
        }
        router.push({
          path: "/"
        });
      }).catch(function(error){
        console.log(error)
      })
    }
 cs

 

  • Authorization code를 이용해 구글 access_token 및 id_token 발행
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 com.google.gson.JsonElement;
import com.google.gson.JsonParser;
import org.springframework.stereotype.Service;
import java.io.*;
import java.net.HttpURLConnection;
import java.net.URL;
 
@Service
public class GoogleService {
    public String getAccessToken (String authorize_code) {
        String access_Token = "";
        String id_Token = "";
        String reqURL = "https://oauth2.googleapis.com/token";
 
        try {
            URL url = new URL(reqURL);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("POST");
            conn.setDoOutput(true);
 
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(conn.getOutputStream()));
            StringBuilder sb = new StringBuilder();
            sb.append("grant_type=authorization_code");
            sb.append("&client_id="); //수정 할것
            sb.append("&redirect_uri="); //수정 할것
            sb.append("&client_secret="); //수정 할것
            sb.append("&code=" + authorize_code);
            bw.write(sb.toString());
            bw.flush();
            int responseCode = conn.getResponseCode();
            System.out.println("responseCode : " + responseCode);
 
            BufferedReader br = new BufferedReader(new InputStreamReader(conn.getInputStream()));
            String line = "";
            String result = "";
 
            while ((line = br.readLine()) != null) {
                result += line;
            }
            System.out.println("response body : " + result);
 
            JsonParser parser = new JsonParser();
            JsonElement element = parser.parse(result);
 
            access_Token = element.getAsJsonObject().get("access_token").getAsString();
            id_Token = element.getAsJsonObject().get("id_token").getAsString();
            System.out.println("access_token : " + access_Token);
            System.out.println(id_Token);
 
            br.close();
 
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
 
        return access_Token;
    }
  
}
 cs

 

  • 결과
1
2
3
4
responseCode : 200
response body : {  "access_token": "ya29.a0ARrdaM-w7dZpSKr4865j6fZ4SQcAbyHw9B2jG0Rd7vLpjf45gHlmbJ8YSEg6klSy8ElFFW-JanHQxd2u8zs7aUKTPZdLY9K28mx1k7a4J0JXGjX-k6MYqd0GaiNN9EV5wvXa_gpS7i6M3R36dGOkyvky9Wje",  
"expires_in": 3599,  "scope": "https://www.googleapis.com/auth/userinfo.email openid",  "token_type": "Bearer",  
"id_token": "eyJhbGciOiJSUzI1NiIsImtpZCI6IjZlZjRiZDkwODU5MWY2OTdhOGE5Yjg5M2IwM2U2YTc3ZWIwNGU1MWYiLCJ0eXAiOiJKV1QifQ.eyJpc3MiOiJodHRwczovL2FjY291bnRzLmdvb2dsZS5jb20iLCJhenAiOiIyMjk1MTExNDAxMTgtMzFkNHZwMTYwYzdkZDFsZDRnMjcxODBmbXExcWVzZzguYXBwcy5nb29nbGV1c2VyY29udGVudC5jb20iLCJhdWQiOiIyMjk1MTExNDAxMTgtMzFkNHZwMTYwYzdkZDFsZDRnMjcxODBmbXExcWVzZzguYXBwcy5nb29nbGV1c2VyY29udGVudC5jb20iLCJzdWIiOiIxMTE3MjkxNDg1Mzc4Mzg3NTY3NTUiLCJlbWFpbCI6InduZHVzeDFAZ21haWwuY29tIiwiZW1haWxfdmVyaWZpZWQiOnRydWUsImF0X2hhc2giOiJBOE94NFhPa2oyblV0aU1VUmhUeFBnIiwiaWF0IjoxNjI5Mjk1Njk3LCJleHAiOjE2MjkyOTkyOTd9.gsTWNfzCEZYniwwI9a_CoDmn5Kd7SUbyJLYxG9GbdBFpeXiS7yR_Zl3J2kDtqieDUgbt2EMZP4MlDEGbB0kglYWJXbE54kmbVKlmzMKK41GoLvohNnSEQUJHgj0bPFkBqJm8Z3DLhmWQJmqDczinUbHmYSbvcHgflRSJs1_0xAM7-xtmVE55rJoR0JzBkIjKhXGsGue9791lP0M0fM9y6SJxmkLJLv-1c1eoKIgY4cTbIYVOs29TwKRSQGSwTqsVBq63WinYFrt0ECc_e4RB21wcmDZx2aQe_SDEw4iqayWdFEnSYiyyit6XIpkLYXdaa_3F4RWpxL1biuJgMqSBWA"}
 cs

 

구글 id_token으로 로그인한 유저 정보 얻기

  • id_token을 이용해 구글 이메일, 프로필 사진 등 유저 정보 얻기
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
package com.babble.api.service;
 
import com.google.gson.JsonElement;
import com.google.gson.JsonParser;
import org.springframework.stereotype.Service;
import java.io.*;
import java.net.HttpURLConnection;
import java.net.URL;
 
@Service
public class GoogleService {
  
    public String getUserInfo (String id_token) {
        String reqURL = "https://oauth2.googleapis.com/tokeninfo?id_token="+id_token;
        String email="";
        try {
            URL url = new URL(reqURL);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("GET");
            conn.setDoOutput(true);
 
            int responseCode = conn.getResponseCode();
            System.out.println("responseCode : " + responseCode);
 
            BufferedReader br = new BufferedReader(new InputStreamReader(conn.getInputStream()));
            String line = "";
            String result = "";
 
            while ((line = br.readLine()) != null) {
                result += line;
            }
            System.out.println("response body : " + result);
 
            JsonParser parser = new JsonParser();
            JsonElement element = parser.parse(result);
            email = element.getAsJsonObject().get("email").getAsString();
 
 
            br.close();
 
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return email;
    }
 
}
 cs

 

  • 결과 - reqURL 에 따라 이메일, 프로필, 토큰 만료시간 등 여러 유저 정보 확인 가능!
1
2
responseCode : 200
response body : {  "iss": "https://accounts.google.com",  "azp": "229511140118-31d4vp160c7dd1ld4g27180fmq1qesg8.apps.googleusercontent.com",  "aud": "229511140118-31d4vp160c7dd1ld4g27180fmq1qesg8.apps.googleusercontent.com",  "sub": "111729148537838756755",  "email": "wndusx1@gmail.com",  "email_verified": "true",  "at_hash": "A8Ox4XOkj2nUtiMURhTxPg",  "iat": "1629295697",  "exp": "1629299297",  "alg": "RS256",  "kid": "6ef4bd908591f697a8a9b893b03e6a77eb04e51f",  "typ": "JWT"}
 cs

'정리 > Spring' 카테고리의 다른 글

[Spring] DI & AOP  (0) 2021.09.24
[Spring] REST API  (0) 2021.09.09
[Spring] Spring MVC  (0) 2021.09.09
[Spring] Spring이란?  (0) 2021.09.09
[Spring Boot] 이메일 인증 회원가입하기 구현  (2) 2021.07.23

현재 진행하고 있는 프로젝트에서 사용하고 있는 이메일을 이용해 회원가입을 진행할 수 있도록 구현했습니다.

네이버, 구글, 다음 등의 가입되어있는 이메일을 이용하여 해당 이메일로 인증번호를 보낸 뒤,

인증번호가 일치한 경우 회원가입이 될 수 있도록 했습니다.

 

저는 구글 메일을 이용해 구현했습니다.

 

 
 

구현 순서

1. dependency 추가

1. properties 추가

2. EmailConfig 추가

3. EmailService 추가

4. EmailServiceImpl 추가

5. Controller 추가

 

구현하기 전 간단한 설정이 필요합니다!!

 

https://www.google.com/settings/security/lesssecureapps에서 보안 수준이 낮은 앱의 액세스 활성화

활성화를 해줘야 메일을 받을 수 있어요!

 

dependency 추가

build.gradle

1
2
3
dependencies {
     implementation 'org.springframework.boot:spring-boot-starter-mail'
}
 cs

 

 

properties

email.properties

1
2
3
4
5
6
7
8
9
10
11
mail.smtp.auth=true
mail.smtp.starttls.required=true
mail.smtp.starttls.enable=true
mail.smtp.socketFactory.class=javax.net.ssl.SSLSocketFactory
mail.smtp.socketFactory.fallback=false
mail.smtp.port=465
mail.smtp.socketFactory.port=465
 
#admin 구글 계정
AdminMail.id = 
AdminMail.password =
 cs

 

 

EmailConfig

EmailConfig.java

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
import java.util.Properties;
 
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.context.annotation.PropertySource;
import org.springframework.mail.javamail.JavaMailSender;
import org.springframework.mail.javamail.JavaMailSenderImpl;
 
 
@Configuration
@PropertySource("classpath:email.properties")
public class EmailConfig {
 
    @Value("${mail.smtp.port}")
    private int port;
    @Value("${mail.smtp.socketFactory.port}")
    private int socketPort;
    @Value("${mail.smtp.auth}")
    private boolean auth;
    @Value("${mail.smtp.starttls.enable}")
    private boolean starttls;
    @Value("${mail.smtp.starttls.required}")
    private boolean startlls_required;
    @Value("${mail.smtp.socketFactory.fallback}")
    private boolean fallback;
    @Value("${AdminMail.id}")
    private String id;
    @Value("${AdminMail.password}")
    private String password;
 
    @Bean
    public JavaMailSender javaMailService() {
        JavaMailSenderImpl javaMailSender = new JavaMailSenderImpl();
        javaMailSender.setHost("smtp.gmail.com");
        javaMailSender.setUsername(id);
        javaMailSender.setPassword(password);
        javaMailSender.setPort(port);
        javaMailSender.setJavaMailProperties(getMailProperties());
        javaMailSender.setDefaultEncoding("UTF-8");
        return javaMailSender;
    }
    private Properties getMailProperties()
    {
        Properties pt = new Properties();
        pt.put("mail.smtp.socketFactory.port", socketPort);
        pt.put("mail.smtp.auth", auth);
        pt.put("mail.smtp.starttls.enable", starttls);
        pt.put("mail.smtp.starttls.required", startlls_required);
        pt.put("mail.smtp.socketFactory.fallback",fallback);
        pt.put("mail.smtp.socketFactory.class", "javax.net.ssl.SSLSocketFactory");
        return pt;
    }
}
 cs

 

 

EmailService

EmailService.java

1
2
3
public interface EmailService {
    String sendSimpleMessage(String to)throws Exception;
}
 cs

 

EmailServiceImpl

EmailServiceImpl.java

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
import java.util.Random;
 
import javax.mail.Message.RecipientType;
import javax.mail.internet.InternetAddress;
import javax.mail.internet.MimeMessage;
 
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.mail.MailException;
import org.springframework.mail.javamail.JavaMailSender;
import org.springframework.stereotype.Service;
 
@Service
public class EmailServiceImpl implements EmailService{
 
    @Autowired
    JavaMailSender emailSender;
 
    public static final String ePw = createKey();
 
    private MimeMessage createMessage(String to)throws Exception{
        System.out.println("보내는 대상 : "+ to);
        System.out.println("인증 번호 : "+ePw);
        MimeMessage  message = emailSender.createMimeMessage();
 
        message.addRecipients(RecipientType.TO, to);//보내는 대상
        message.setSubject("Babble회원가입 이메일 인증");//제목
 
        String msgg="";
        msgg+= "<div style='margin:100px;'>";
        msgg+= "<h1> 안녕하세요 Babble입니다. </h1>";
        msgg+= "<br>";
        msgg+= "<p>아래 코드를 회원가입 창으로 돌아가 입력해주세요<p>";
        msgg+= "<br>";
        msgg+= "<p>감사합니다!<p>";
        msgg+= "<br>";
        msgg+= "<div align='center' style='border:1px solid black; font-family:verdana';>";
        msgg+= "<h3 style='color:blue;'>회원가입 인증 코드입니다.</h3>";
        msgg+= "<div style='font-size:130%'>";
        msgg+= "CODE : <strong>";
        msgg+= ePw+"</strong><div><br/> ";
        msgg+= "</div>";
        message.setText(msgg, "utf-8", "html");//내용
        message.setFrom(new InternetAddress("properties email쓰세용!","Babble"));//보내는 사람
 
        return message;
    }
 
    public static String createKey() {
        StringBuffer key = new StringBuffer();
        Random rnd = new Random();
 
        for (int i = 0; i < 8; i++) { // 인증코드 8자리
            int index = rnd.nextInt(3); // 0~2 까지 랜덤
 
            switch (index) {
                case 0:
                    key.append((char) ((int) (rnd.nextInt(26)) + 97));
                    //  a~z  (ex. 1+97=98 => (char)98 = 'b')
                    break;
                case 1:
                    key.append((char) ((int) (rnd.nextInt(26)) + 65));
                    //  A~Z
                    break;
                case 2:
                    key.append((rnd.nextInt(10)));
                    // 0~9
                    break;
            }
        }
 
        return key.toString();
    }
    @Override
    public String sendSimpleMessage(String to)throws Exception {
        // TODO Auto-generated method stub
        MimeMessage message = createMessage(to);
        try{//예외처리
            emailSender.send(message);
        }catch(MailException es){
            es.printStackTrace();
            throw new IllegalArgumentException();
        }
        return ePw;
    }
 
}
 cs

★ 저는 인증코드 일치 여부를 비교해주기 위해서 sendSimpleMessage() 메서드를 void가 아닌 String으로 만들어주었습니다!

 

 

Controller 

Controller.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@PostMapping("/emailConfirm")
    @ApiOperation(value = "회원 가입시 이메인 인증", notes = "기존사용하고 있는 이메일을 통해 인증")
    @ApiResponses({
            @ApiResponse(code = 200, message = "성공"),
            @ApiResponse(code = 401, message = "인증 실패"),
            @ApiResponse(code = 404, message = "사용자 없음"),
            @ApiResponse(code = 500, message = "서버 오류")
    })
    public ResponseEntity<? extends BaseResponseBody> emailConfirm(
            @RequestBody @ApiParam(value="이메일정보 정보", required = true) String email) throws Exception {
 
        String confirm = emailService.sendSimpleMessage(email);
 
        return ResponseEntity.status(200).body(BaseResponseBody.of(200, confirm));
    }
 cs

★ 위에서 말했다시피, 인증코드 일치여부 확인을 위해 성공코드와 함께 인증코드 return

 

 

메일 확인

 

 

참고한 블로그

https://badstorage.tistory.com/38

'정리 > Spring' 카테고리의 다른 글

[Spring] DI & AOP  (0) 2021.09.24
[Spring] REST API  (0) 2021.09.09
[Spring] Spring MVC  (0) 2021.09.09
[Spring] Spring이란?  (0) 2021.09.09
[Spring Boot + Vue.js] 구글로그인  (0) 2021.08.18

Vuex

  • Vue.js 애플리케이션을 위한 상태 관리 패턴 + 라이브러리
  • 상태가 예측 가능한 방식으로만 변경될 수 있도록 하는 규칙 + 애플리케이션의 모든 구성 요소에 대한 중앙 집중식 저장소 역할

    ▶ 상태 관리란 ? 

    - 여러 컴포넌트 간의 데이터 전달과 이벤트 통신을 한 곳에서 관리하는 패턴을 의미

     

    ▶ 상태 관리의 필요성

    -  컴포넌트 기반 프레임워크에서는 작은 단위로 쪼개진 여러 개의 컴포넌트로 화면을 구성하는데, 규모가 커질수록

    1) 뷰의 컴포넌트 통신 방식인 props, event emit 이 거쳐야 할 컴포넌트 ↑

    2) Event Bus를 사용하여 컴포넌트 간 데이터 흐름을 파악하기 어려움

    이러한 문제점을 해결하기 위해 모든 데이터 통신을 한 곳에서 중앙 집중식으로 관리 = 상태 관리

     

    즉, 컴포넌트 간의 통신이나 데이터 전달을 좀 더 유기적으로 관리할 필요성이 생긴다.

     

    ▶ Store : 애플리케이션 상태를 보관하는 컨테이너

    특징

    - store의 상태가 변경되면 반응적이고 효율적으로 업데이트

    - store의 상태를 직접 변경할 수 없다.

vuex 데이터 흐름

Store

  • state
    • 컴포넌트 간에 공유할 data 속성
    • mutation을 통해서만 변경 가능
  • mutations
    • state를 변경할 수 있는 유일한 방법
    • commit를 통해서 호출가능
  • actions
    • 비동기 작업 가능
    • mutation를 호출하기 위한 commit 가능
    • dispatch를 통해 호출
    • axios를 통한 api호출과 그 결과를 리턴하거나 mutation으로 commit하는 용도로 사용
  • getter
    • state에 대해 연산을 하고 그 결과를 view에 바인딩
    • state의 변경 여부에 따라 view를 업데이트

 

'정리 > Web' 카테고리의 다른 글

React란?  (0) 2021.09.17
CSS  (2) 2021.03.19
HTML  (0) 2021.03.19
jQuery  (0) 2021.03.08
JavaScript  (2) 2021.03.05

문제

BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면

와 같이 된다. 이러한 순서에서 BEER 다음에 오는 단어는 BERE가 된다. 이와 같이 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하시오.

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다.

 

출력

각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다.

 

예제

풀이 방법

주어진 단어 다음에 나오는 단어를 찾는 문제였습니다.

 

처음에는 가능한 단어들을 다 만들어 놓고 정렬한 뒤, 주어진 단어의 다음 단어를 출력해주도록 구현했지만, 단어의 길이가 최대 99이므로 시간초과가 발생했습니다.

 

그래서 두번째로 구현한 방법이 

1 ) 단어 맨뒤에서부터 확인하면서 감소하는 부분 찾기

2 ) 다시 단어 맨뒤에서부터 확인하면서 감소하는 부분보다 큰 부분 찾기

3 ) 둘 위치 바꿔주기

4 ) 1)의 위치 뒷 부분 정렬

입니다.

 

예시)

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main_BJ_9081_단어맞추기 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0;i<T;i++) {
            char [] word = br.readLine().toCharArray();
            
            int index=-1, index2=0;
            char temp;
        
            for(int j=word.length-1;j>0;j--) {
                if(word[j-1]<word[j]) {
                    index=j-1; break;
                }
            }
            
            if(index==-1) {
                for(int j=0;j<word.length;j++) sb.append(word[j]);
                sb.append("\n");
            }
            else {
                for(int j=word.length-1;j>=0;j--) {
                    if(word[index]<word[j]) {
                        index2=j; break;
                    }
                }
                temp = word[index];
                word[index] = word[index2];
                word[index2] = temp;
                
                Arrays.sort(word,index+1, word.length);
                
                for(int j=0;j<word.length;j++) sb.append(word[j]);
                sb.append("\n");
            }
            
        }
        System.out.println(sb.toString());
    }
}
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 17121 연구소2 [JAVA]  (0) 2021.09.02
백준 16236번 아기 상어 [JAVA]  (0) 2021.08.29
백준 1713번 후보 추천하기 [JAVA]  (1) 2021.07.04
백준 4358번 생태학 [JAVA]  (0) 2021.06.30
백준 2242번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 [JAVA]  (0) 2021.06.30

이진탐색 알고리즘

  • 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘
  • 리스트의 중간 부분에 찾는 원소가 있는지 확인 후, 왼쪽에 있는지 오른쪽에 있는지 판단하여 검색
  • 즉, 자료를 반으로 나누어 탐색하는 방법
  • 시간복잡도 : O(logN)

예시

  • 찾고자 하는 값을 찾을 때까지 과정 반복!
  • 이진 탐색 알고리즘을 사용할때는 반드시 정렬된 자료에만 사용해야한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int binarySearch(int arr[], int left, int right, int key) { //반복문
        
        while(left<right) {            
            int mid = (left+right)/2;
            if(key==arr[mid]) //탐색 성공
                return mid;
            else if(key>arr[mid]) //중간 원소보다 크면
                left = mid+1;
            else //중간 원소보다 작으면
                right = mid-1;
        }
        return -1;
}
 cs

 

1
2
3
4
5
6
7
8
9
10
11
public static int binarySearch(int arr[], int left, int right, int key) { //재귀문
        
        if(left>right) return -1;
        int mid = (left+right)/2;
        if(arr[mid]==key) //탐색 성공
            return mid;
        else if(key>arr[mid]) // 중간 원소보다 크면
            return binarySearch(arr,mid+1,right,key);
        else // 중간 원소보다 작으면
            return binarySearch(arr,left,mid-1,key);
}
 cs

 

 

 

'정리 > 자료구조+알고리즘' 카테고리의 다른 글

다익스트라(Dijkstra) 알고리즘  (0) 2021.09.04
투 포인터(Two Pointer)  (0) 2021.08.26
세그먼트 트리(Segment Tree)  (0) 2021.07.01
위상정렬  (0) 2021.06.18
비트마스크 (BitMask)  (0) 2021.04.21

+ Recent posts

티스토리툴바