구글 로그인 

  • 구글 로그인 버튼 클릭
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 = trueString 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

이진탐색 알고리즘

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

세그먼트 트리(Segment Tree) 

  • 특정 구간 내 연산에 대해서 빠르게 응답하기 위해 만들어진 자료구조
    - 1,2,3,4,5라는 수들 중 2번째부터 5번째까지의 합을 구하고 싶다!
       = 배열로 구간합을 저장하고 sum[5] - sum[1]으로 구할 수 있다. -> 시간 복잡도 : O(1)

    - 만약 배열의 값이 바뀐다면?
      = 바뀔때마다 구간합을 더해서 다시 저장해야한다. -> 시간 복잡도 : O(N^2)

    - 세그먼트 트리를 사용했을 경우에는 시간 복잡도 O(NlogN)

 

  • 세그먼트 트리 만들기

 

 

 

 

구현

    • 트리 만들기
1
2
3
4
5
public static int init(int node_idx, int start, int end) {
        if(start==end) return tree[node_idx] = arr[start]; //start == end인 경우 : leaf노드

// 자식노드를 더한다 (왼쪽 노드 + 오른쪽 노드)
        return tree[node_idx] = init(node_idx*2, start, (start+end)/2+ 
init(node_idx*2+1, (start+end)/2+1, end);
}
cs

 

    • 배열 값 변경 (구간합 수정)
1
2
3
4
5
6
7
8
9
10
public static void update(int node_idx, int start, int end, int idx, long diff) {
        if(idx < start | idx> end) return;
 
        tree[node_idx]+=diff;
 
        if(start!=end) {
            update(node_idx*2,start,(start+end)/2,idx,diff);
            update(node_idx*2+1, (start+end)/2+1, end, idx, diff);
        }
}
cs

 

    • 구간합 구하기
1
2
3
4
5
6
7
8
9
public static int sum(int node_idx, int start, int end, int L, int R) {
        if(end<|| start>R) return 0;
        
        if(L<=start && end<=R) return tree[node_idx];
        
        return sum(node_idx*2, start, (start+end)/2,L,R) + 
sum(node_idx*2+1, (start+end)/2+1, end, L,R);
        
}
 
cs

 

세그먼트 트리 관련 문제

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

 

 

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

투 포인터(Two Pointer)  (0) 2021.08.26
이진 탐색 (Binary Search) 알고리즘  (0) 2021.07.05
위상정렬  (0) 2021.06.18
비트마스크 (BitMask)  (0) 2021.04.21
최소신장트리(MST) 알고리즘  (0) 2021.03.26

위상정렬이란?

  • 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것
    • 방향 그래프
    • 그래프의 순환 x

예시

 

 

 

코드

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
public class Main_ {
    
    
    static int N,M;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    static int [] indegree;
 
    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());
        
        indegree = new int[N+1];
        
        for(int i=0;i<=N;i++) list.add(new ArrayList<>());
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            list.get(a).add(b);
            indegree[b]++;
        }
        sort();
    }
    
    public static void sort() {
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> result = new LinkedList<>();
        
        for(int i=1;i<N+1;i++) {
            if(indegree[i]==0) {
                queue.add(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            result.add(temp);
            
            for(Integer item : list.get(temp)) {
                indegree[item]--;
                if(indegree[item]==0) {
                    queue.add(item);
                }
            }
        }
        while(!result.isEmpty()) {
            System.out.print(result.poll()+" ");
        }
    }
 
}
cs

 

 

비트마스크(BitMask)란?

  • 비트 필드에서 비트 연산에 사용되는 데이터로 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.
  • 이진수는 0과 1로 표현
  • 비트연산을 통해 삽입, 삭제, 조회 등이 간단해지며 더 빠른 연산이 가능해진다.

 

연산자

 

 

 

+ Recent posts