반응형

p21771 가희야 거기서 자는 거 아니야

처음 접근방법은 G의 각 꼭짓점 별로 좌표를 추적해서 좌우에 P가 있는지 탐색해보는 방식으로 접근했었는데, 정확한 이유는 모르겠지만 실패했다.

그래서 생각해 본 방법이 P의 넓이를 구하고 P의 갯수를 카운트했을 때 넓이가 안맞으면  가희가 베개를 사용하고 있는 것으로 판단하기로 해보고 문제를 풀어봤다.

hint

----

P의 갯수를 활용하는 것이 핵심

----

Solution

실행시간 - 124ms

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
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int gr = Integer.parseInt(st.nextToken());
        int gc = Integer.parseInt(st.nextToken());
        int pr = Integer.parseInt(st.nextToken());
        int pc = Integer.parseInt(st.nextToken());
        
        char[][] map = new char[r][c];
        
        for(int i = 0; i < r; i++){
            map[i] = br.readLine().toCharArray();
        }
        
        int n = pr * pc; // 60
        int count = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(map[i][j] == 'P'){
                    count++;
                }
            }
        }
        
        if(count == n){
            System.out.println(0);
        }else{
            System.out.println(1);
        }
        
        
        
    }
    
    
}
cs

 

다음에 기회가 된다면 각 꼭짓점 별로 판단하는 방식을 채용해보고 싶다... 정말 최고의 최적화일거같은데 반례가 어느걸까 궁금하다

반응형
반응형

13717번 포켓몬Go

내용은 구현이 익숙한 사람들은 효율을 생각 안하면 쉽게 구현할만한 문제같다.

위의 테스트케이스 기준으로 설명을 하자면.

4마리의 포켓몬을 입력받는데, 각 마리마다 입력받는 값은 Caterpie라는 문자열, 레벨업에 필요한 사탕갯수(12), Caterpie에게 투자할 수 있는 사탕의 갯수이다. 1레벨업을 할 때마다 2개의 사탕을 돌려받는다.

 ----

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
44
45
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //pokemon
        //levelupCandy
        //haveCandy
        String[] pokemon = new String[n];
        int[] levelupCandy = new int[n];
        int[] haveCandy = new int[n];
        
        for(int i = 0; i < n; i++){
            pokemon[i] = br.readLine();
            st = new StringTokenizer(br.readLine());
            levelupCandy[i] = Integer.parseInt(st.nextToken());
            haveCandy[i] = Integer.parseInt(st.nextToken());
        }
        //Caterpie
        //12
        //33
        
        int count = 0;
        int tempCount = 0;
        int index = 0;
        int maxCount = 0;
        for(int i = 0; i < n; i++){
            while(haveCandy[i] >= levelupCandy[i]){
                haveCandy[i] -= levelupCandy[i] - 2;
                tempCount++;
            }
            if(maxCount < tempCount){
                maxCount = tempCount;
                index = i;
            }
            count += tempCount;
            tempCount = 0;
        }
        System.out.println(count);
        System.out.println(pokemon[index]);
    }
}
cs

실행시간 - 124ms

반응형
반응형

1418번 K-세준수

N까지의 값을 입력받아서 각 수의 소인수분해를 통해 소인수를 받고 해당 소인수의 최댓값을 입력받은 K와 비교해 카운트한 수를 출력

-----

hint

각 소인수를 hashMap에 저장 이후 맥스값 출력

-----

Solution

실행시간 - 3496ms

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
import java.util.*;
import java.io.*;
// 1 2 3 4 5 6 7 8 9 10
// 1 2 3 2 5 3 7 2 3 5
class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); 
        int k = Integer.parseInt(br.readLine());
        int[] a = new int[n+1];
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>(n+1);
        
        for(int i = 0; i <= n; i++){
            a[i] = i;
            hs.put(i,0);//해시맵 초기화
        }
        
        //1은 되니까 배제
        for(int i = 2; i <= n; i++){//2부터 n까지의 소인수들을 저장
            int soinsu = a[i];
            for(int j = 2; j <= soinsu; j++){
                while(soinsu % j == 0){ 
                    soinsu /= j;
                    hs.put(i, j);
                }
                // 소인수분해 한 값들중에서 max값을 해당 hs에 집어넣는다.
            }
        }
        
        int count = 0;
        for(int i = 1; i < a.length; i++){
            if(hs.get(i) <= k){
                count++;
            }
        }
        System.out.println(count);
    }
}
cs

직접 무식하게 푼거라 효율이 매우 좋지 않음...

반응형
반응형

24444번 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net

 

이번엔 BFS... DFS 보다 습득하는데 더 오래 걸린 듯 하다

그나마 이번 문제 풀면서 범위설정이나 조건이나 여러가지로 감을 좀 잡은듯

 

------

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
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    static boolean[] isVisit;
    static ArrayList<Integer>[] a;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
 
        int u, v;
 
        isVisit = new boolean[n+1];
        a = new ArrayList[n+1];
 
        for(int i = 1; i < n + 1; i++){
            a[i] = new ArrayList<Integer>();
        }
 
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            a[u].add(v);
            a[v].add(u);
        }
 
        for(int i = 1; i < n + 1; i++){
            if(!a[i].isEmpty()) {
                Collections.sort(a[i]);
            }
        }
 
        BFS(r, n, m);
 
    }
 
    static void BFS(int r, int n, int m){ // r이 1이라고 가정했을 때
        Queue<Integer> queue = new LinkedList<>();
 
        int temp;
        int[] count = new int[n+1];
        int countNum = 1;
 
        isVisit[r] = true;
        count[r] = countNum++;
        queue.offer(r);
 
        while(!queue.isEmpty()){
            temp = queue.poll();
            for(int i = 0; i < a[temp].size(); i++) {
                if (!isVisit[a[temp].get(i)]) {//방문하지 않았을 때 실행
                    isVisit[a[temp].get(i)] = true;
                    count[a[temp].get(i)] = countNum++;
                    queue.offer(a[temp].get(i));
                }
            }
        }
 
        for(int i = 1; i < n + 1; i++){
            System.out.println(count[i]);
        }
    }
}
 
cs

 

실행시간 - 1996ms

너무 길어서 최적화좀 해주고싶은데.... BufferedReader말고는 상상이 안됨

반응형
반응형

movie

얄코님 유튜브영상

  • 익스플로러는 한동안 독과점을 한 채로 있었기에 국제 웹 표준을 지키지 않았다
  • 때문에 호환이 잘 안된다
반응형
반응형

우리가 스프링을 왜 사용하는지 장점이 무엇인지 공부를 해 보았습니다.

또 사용하면서 계속 염두에 두고 있어야 할 CLEAN CODE의 원칙중 SOLID에 대해서 간단하게 공부했습니다.

목차


  1. 스프링의 개념
  2. SOLID

스프링의 개념


스프링은 다양한 라이브러리를 지원한다

그 중에 필수 기술과 선택 기술이 있는데

대표적으로 필수로 사용하는 라이브러리는

스프링 프레임워크, 스프링 부트 가 있고,

선택적으로 사용하는 라이브러리는

스프링 데이터, 스프링 세션, 스프링 시큐리티, 스프링 RestDocs, 스프링 배치, 스프링 클라우드 등이 있다.

그림으로 나타낸 스프링 기술 라이브러리

그림으로 나타낸 스프링 기술 라이브러리

위에서 설명한 각 라이브러리들에 대해 간단하게 정리해보고자 한다.

스프링 프레임워크


기술 특징

  • 핵심 기술
  • 스프링 DI컨테이너(의존성 주입), AOP, 이벤트, 데이터 바인딩
  • 테스트
  • 스프링 기반 테스트 지원 - 기존 자바에서 사용하는 JUnit 테스팅을 스프링 기반으로 테스트도 가능하게 해준다
  • 데이터 접근 기술
  • 트랜잭션, JDBC, ORM지원, XML지원
  • 스프링 MVC, 스프링 WebFlux
  • 기술 통합
  • 캐시, 이메일, 원격접근 등등

스프링 프레임워크 기능들을 설명한 참조페이지

최근에는 스프링 부트를 통해 프레임워크의 기술들을 편리하게 사용 가능하게 되었다.

스프링 부트


현 시점에서는 스프링을 사용한다면 기본으로 사용한다고 보면 된다고 한다

단독으로 실행할 수 있는 스프링 애플리케이션을 쉽게 생성해준다

Tomcat같은 웹 서버가 내장돼서 별도의 웹 서버가 필요하지 않게 되었다

빌드 구성을 단순화 하기 위한 starter 종속성을 제공한다 - 이로인해 타임리프, oauth2 등등을 빌드할 때 아래의 형식으로 선언할 수 있음

spring-boot-starter-xxx 빌드 예시
dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
    implementation 'org.springframework.boot:spring-boot-starter-security'
    implementation 'org.springframework.boot:spring-boot-starter-oauth2-client'
		implementation 'org.springframework.boot:spring-boot-starter-thymeleaf'
}

스프링과 3rd parth(외부)라이브러리가 자동으로 구성된다.(버전업되거나 이러한 부분들 관련해서 자동으로 구성된다.)

참조 페이지

그 외의 스프링 라이브러리


  • 스프링 데이터
  • CRUD기능 사용을 돕는다 - 대표적으로 스프링 데이터JPA가 있다
  • 스프링 세션
  • 세션기능 편리하게 사용가능
  • Security
  • 로그인 인증 및 권한 부여, 해킹(세션변조, 클릭재킹, 교차 사이트 요청 위조)으로부터 보호
  • Rest Docs Api
  • 데이터 구축 편리화(Restful서비스 문서화)
  • 스프링 배치
  • 트랜잭션 관리, 리소스 관리, 대용량 레코드 처리에 필수적인 재사용 가능한 기능을 제공
  • 클라우드
  • 클라우드 기술

등등이 있다 더 많은 라이브러리를 보고싶다면 여기를 참조

스프링이라는 단어는 문맥에 따라 다르게 사용된다.

스프링 DI 컨테이너 기술

스프링 프레임워크

스프링 부트, 프레임워크 등을 모두 포함한 스프링 생태계

말하는 상황에 따라 뜻이 다르게 사용될 수 있다.

스프링은 좋은 객체지향 애플리케이션을 개발할 수 있게 도와주는 프레임워크

스프링에서 객체지향 특성중 다형성을 극대화해서 이용할 수 있게 도와주는 프레임워크 이다.

스프링을 들어가기 전 알아두면 좋은 개념

SOLID


클린코드로 유명한 로버트 마틴이 좋은 객체 지향 설계의 5가지 원칙을 SOLID라고 한다.

  • SRP 단일 책임 원칙단 하나의 책임이라는 것은 모호하다.문맥과 상황에 따라 다르다.
  • 클 수 있고, 작을 수 있다.
  • 한 클래스는 하나의 책임만 가져야 한다.

중요한 기준은 변경이다. 변경이 있을 때 파급 효과가 적으면 단일 책임 원칙을 잘 따른 것

ex) UI변경, 객체의 생성과 사용을 분리

OCP : 개방-폐쇄 원칙

중요!

소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다

이 방식은 다형성을 활용해서 인터페이스를 구현한 새로운 클래스에 새로운 기능을 구현하면 도움이 될 것이다.

이는 지키기 상당히 힘든데 우리는 Spring 컨테이너가 이 부분을 해결하는데 도움을 준다

LSP : 리스코프 치환 원칙

인터페이스의 기능적 신뢰성을 보장해줘야한다.

ex) 자동차는 가속과 감속을 할 수 있지만 0 미만의 속력이 나오면 안된다.

이를 인터페이스로 구현했을 때 0 미만의 속력이 나온다면 LSP를 지키지 못한것

ISP : 인터페이스 분리 원칙

특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다

DIP : 의존관계 역전 원칙

중요!

프로그래머는 추상화에 의존해야지 구체화에 의존하면 안된다. 의존성 주입은 이 원칙을 따르는 방법 중 하나다.

멤버서비스는 멤버리파지토리만 바라보는 역할에만 의존해야한다는 뜻

우리가 그램그램을 사용하면서 mvc 관련해서 멤버리퍼지토리 등등 각 역할에 맞게만 구현하게 하는 걸 말한다.

쉽게 말해서 구현 클래스에 의존하지 말고 인터페이스에 의존하라는 뜻이다.

해당 개념을 간단하게라도 배운 이유는

스프링이 객체지향의 핵심인 다형성과 SOLID 원칙중 OCP, DIP를 가능하게 할 수 있게 지원을 해준다.

자바만을 통해서 CLEAN CODE를 만들기 위해 해당 OCP, DIP원칙들을 지키며 개발을 한다면 스프링 프레임워크에 있는 DI컨테이너의 필요성을 느끼게 될 수밖에 없다고 한다.

이러한 DI컨테이너의 활용이 스프링 프레임워크(boot x)의 핵심!

이상적으로는 모든 설계에 인터페이스를 부여하는 것이 가장 CLEAN CODE에 가깝다고 한다

하지만 인터페이스를 도입하면 추상화라는 비용이 발생한다.

반응형

'공부 > 노션정리본' 카테고리의 다른 글

깃 배시 명령어 정리 및 간단이론  (0) 2023.02.23
반응형

13023번 ABCDE

https://www.acmicpc.net/problem/13023

 

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

 

 

DFS공부하다가 만난 문제 그냥 열심히 구현 하다가

문득 궁금해져서 일반 for문으로 바꾸고 싶어졌었다가 상당히 오랜 시간 잡아먹은 문제

for each에서 for문 가는거 그렇게 어려운 것도 아닌데 중첩이 되어있으니까 좀 헷갈렸던거 같음

 

-------

hint

그냥 dfs구현하고 depth 1에서 5까지 쌓인다면 1을 출력하게 구현하면 됨

-------

Solution

일반 for문

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
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5 || isDepthFive == 1) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i = 0; i < A[n].size(); i++) {
            if (!visited[A[n].get(i)]) {
                DFS(A[n].get(i), depth + 1);
            }
        }
 
        visited[n] = false;
 
    }
}
 
cs

 

for each문

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
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i : A[n]) {
            if (!visited[i]) {
                DFS(i, depth + 1);
            }
        }
        visited[n] = false;
    }
}
 
cs

 

처음엔 구현을 못해서 for each로 했는데

일반 for문 구현하고 백준보니까 속도랑 메모리 측면에서 for문이 더 좋았다

그 이유는 chat GPT씨가 설명해줌 ㅎㅎ

 

반응형
반응형

movie

얄코님 유튜브영상

  • 웹 프로그래밍 필수 html, css, js
반응형
반응형

movie

뇌과학자님 유튜브영상

  • 이해안되면 외워라
  • 외우는게 때로는 정답
반응형

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

왜 웹 개발자들은 익스플로러를 싫어하나요?  (0) 2023.04.29
HTML, CSS, JavaScript가 뭔가요?  (0) 2023.04.12
비동기 프로그래밍이 뭔가요?  (0) 2023.04.09
REST API가 뭔가요?  (0) 2023.04.09
객체지향 디자인패턴 2  (0) 2023.04.09
반응형

movie

얄코님 유튜브영상

  • 비 동기 좀 웃기네 ㅋㅋㅋㅋ
  • 동기 : 순서대로 실행되는 경우 앞의 코드가 끝나야 다음 코드가 실행됨
  • 비동기 : 꼭 순서대로 실행되는게 아님 여러스레드를 통해서 일을 함
  • 특징으로는 콜백함수가 있다.
  • 콜백지옥을 해결하기 위해 promise를 도입 (많이 직관적이다)
반응형

+ Recent posts