• NxM 크기의 체스 보드
• 나이트의 시작 위치: (N,1) 0이 아닌 1부터 시작한다고 가정
• 이동할 수 있는 칸의 최대 개수 구하기 이때, 최대 개수가 5이상인 경우, 모든 방법을 한 번 이상 사용해야함.

생각하기

만일, 모든 방법을 다 쓴다고 가정할 때, 최소 배열의 크기를 생각해 보자.

위 그림에서 보듯, 최소 세로(N)≥3, 가로(M)≥7 인 경우 4가지 방법을 모두 사용할 수 있다.

1. N =2

세로가 2인 경우, ①, ④ 방법은 쓸 수 없다. (왜 ??? 체스판을 벗어나니까.)

따라서 아무리 이동을 많이 할 수 있어도 문제 조건을 충족할 수 없기 때문에 이동 가능한 칸 수는 최대 4칸이다.

시작 칸을 제외하면 가로 길이는 M-1이 된다. ②, ③ 방법을 쓰면, 2칸씩 이동하므로 이동 가능한 칸 수 = (M-1)/2 시작 위치도 포함해야 하기 때문에 +1을 더한다.

** ∴ 최대 이동 칸 = Math.min(4, (M-1)/2 + 1)**

2. M < 7

나이트가 이동할 수 있는 방법은 모두 우측으로 +1칸 혹은 +2칸씩 이동한다. 그래서 시작 위치를 제외하고 최소 1+1+2+2 = 6칸이 있어야 4가지 방법을 모두 사용할 수 있다.

4칸 이하는 특정 방법만 사용해도 되므로, ①, ④ 방법만 취하면 된다. ** ∴ 최대 이동 칸 = Math.min(4, M)**

3. N≥3, M≥7

4가지 방법을 사용할 수 있는 체스판의 최소 크기를 충족한 경우에는 어떨까? 우측으로 +2 이동하는 방법은 1번 씩만 써서 2칸을 이동하고, 나머지를 우측으로 +1만 이동하면 된다.

1. ②, ③ 방법을 사용 시 남은 가로 길이: M-4(2+2)
2. ①, ④ 방법으로 나머지 M-4 길이 이동

** ∴ 최대 이동 칸 = 2+M-4 = M-2**

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N_1783 {
    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 count =0;
        if(N==1){
            count=1;
        }else if(N==2){      
            count = Math.min(4, (M-1)/2+1);
        }else if(M<7){
            count = Math.min(4,M);
        }else{
            count = M-2;
        }
        System.out.println(count);
    }
}

✨ 결과

문제도 이해 못해서 빠르게 답을 봤다. 답을 보니 머리가 똑똑해진 기분 세상엔 영리한 사람들이 참 많다! 나도 그렇게 될 거지롱

참고 jaewoo, [백준 No.1783 병든 나이트 - JAVA]

인증 과정에서 사용자가 성공적으로 자격 증명을 완료하면 JWT가 반환 됨 토큰 자체로 인증 수단이므로, 보안에 주의를 기울여야 함 ∴ 필요한 시간 보다 더 오래 보관하면 안 됨

사용자가 특정 경로나 리소스에 접근하려고 할 때, JWT를 같이 보내줘야함. 일반적으로 Authorization 헤더에 Bearer 스키마로 전달 Authorization: Bearer <token>

HTTP 헤더를 통해 JWT를 전달하는 경우, 토큰에 너무 많은 정보를 담으면 안 됨 일부 서버는 헤더의 크기가 8KB를 초과하는 걸 참지 않아..

1) Authorization 헤더

HTTP 프로토콜에서 클라이언트가 서버에 인가된 상태임을 전달하는 수단으로 사용됨 서버에서 사용자의 신원을 증명하기 위해 필수적 (HTTP/1.1 표준에서 처음 정의) Authorization: <스키마> <자격 증명>

2) Bearer 토큰

클라이언트가 특정 리소스에 접근할 수 있는 권한을 증명하기 위해 서버에 전달하는 토큰 HTTPS를 통해 전달되어야 하며, 이를 통해 토큰이 네트워크에서 탈취됨을 방지

OAuth 2.0의 등장

클라이언트가 리소스 소유자를 대신해 서버에 접근할 수 있는 인증과 권한 위임 방식을 표준화한 프레임워크 민감한 사용자 정보를 직접 전송하지 않고, 액세스 토큰을 사용해 인증 수행

이 과정에서 Authorization 헤더는 토큰 기반 인증의 전달 수단으로 채택, Bearer 스키마가 OAuth 2.0의 핵심 인증 방식으로 자리잡음

❓ 클라이언트랑 리소스 소유자 같은 말 아닌가여??

• 리소스 소유자
• 홍길동*이라는 사용자가 있습니다. 홍길동은 자신의 개인 정보를 포함한 데이터(예: 이메일, 프로필 사진 등)를 소셜 미디어 서비스(예: 구글, 페이스북)에 가지고 있습니다. 홍길동은 이 데이터에 대한 권한을 가지고 있는 리소스 소유자입니다.

  • 클라이언트 홍길동이 가입하고자 하는 앱 A가 있습니다. 이 앱은 사용자가 구글 계정을 통해 로그인을 하여 서비스를 이용할 수 있도록 제공합니다. 이때 앱 A는 리소스 소유자인 홍길동 대신 구글에 접근하여 홍길동의 인증 정보를 받아옵니다. 따라서 앱 A는 클라이언트 역할을 합니다.

2. Refresh Token

토큰을 주고 받는 환경이 보안에 취약해서, 토큰이 노출된다면? 토큰은 그 자체로 인증 수단이므로 서버는 누가 요청했는지 확인할 수가 없음.

토큰의 유효기간이 24시간이면, 도둑은 하루종일 토큰을 가지고 무엇이든 할 수 있음

❓ 그러면 토큰의 유효기간이 짧으면 되잖아요 사용자가 귀찮아 하잖아!!!!!!!!!!!!

이런 문제를 해결하기 위해 리프레시 토큰 등장

Refresh 토큰?

액세스 토큰이 만료되었을 때** 새로운 액세스 토큰** (ex. JWT)을** 발급**하기 위해 사용

토큰 도둑이 액세스 토큰 탈취해도 몇 분 뒤에는 쓸모 없어져서 안전하다.

리프레시 토큰 사용법

이전 글 - [Spring] 토큰 기반 인증, JWT

참고 자료 왜 Authorization "Bearer"인가요?

사용자가 서버에 접근할 떄 이 사용자가 괜춘한(인증된) 사용자인지 확인하는 방법은 대표적으로 서버 기반 인증 과 토큰 기반 인증이 있다.

스프링 시큐리티에서는 기본적으로 세션 기반 인증 제공한다. -> 사용자마다 사용자의 정보를 담은 세션 생성 & 저장하여 인증함

1. 토큰 기반 인증

토큰 기반 인증은 말 그대로 토큰 사용

❓ 토큰 서버에서 클라이언트를 구분하기 위한 유일한 값

• 서버가 토큰을 생성해 클라이언트에게 제공
• 클라이언트는 이 토큰을 갖고 있다가 여러 요청을 토큰이랑 같이 넘김
• 서버는 토큰만 보고 유효한 사용자인지 검증

1) 토큰을 전달하고 인증받는 과정

출처: 나 자신

2) 토큰 기반 인증의 특징

1. 무상태성

• 사용자 인증 정보가 담겨있는 토큰이 클라이언트에 있으므로 서버에 저장할 필요 없음 서버가 데이터를 유지하려면 그만큼 자원을 소비해야 함.

• 상태 관리를 할 필요가 없어서 완전한 무상태 (stateless) 로 효율적인 검증 가능

  ❓ 상태 관리 사용자의 인증 상태를 유지하면서 요청을 처리하는 것

2. 확장성

무상태성은 확장성에 영향을 줌 *오ㅐ❓ * > 서버를 확장할 때 상태 관리를 신경 안 쓰니까 서버 확장도 쉽게 함

IF. 주문 서버, 결제 서버 IN 물건 파는 서비스

3. 무결성

토큰 방식은 HMAC (Hash-based Message AuthentiCation) 기법이라고도 함 토큰을 발급한 이후, 토큰 정보 변경하는 행위는 할 수 없음

즉, 토큰의 무결성이 보장.. 하나라도 바꾸면 서버는 토큰이 유효하지 않다고 판단함

2. JWT란?

• JWT(JSON Web Token)은 정보를 JSON 객체로 안전하게 전송하는 방법을 정의하는 개방형 표준
• 크기가 작고, 독립적인 (self-contained) 형태를 가지며, 디지털 서명을 통해 검증할 수 있어 신뢰 가능
• 비밀키 (HMAC algorithm) 방식 또는 공개/개인키 (RSA, ECDSA) 방식으로 서명

❓ JSON (JavaScript Object Notation) 데이터를 키-값 (key-value) 쌍으로 구성하는 경량 데이터 형식

• 사람이 읽기 쉽고, 기계가 빠르게 파싱 가능
• 웹에서 데이터를 주고 받을 때 많이 사용됨

  >
  { 
  "name": "Alice",
  "age": 25,
  "isStudent": false,
  "skills": ["Java", "Spring Boot", "Vue.js"],
  "address": {
    "city": "Seoul",
    "country": "Korea"
  }
  }

JWT를 암호화 하면 기밀성을 포함 할 수 있음 = JWE (Json Web Encryption)

3. JWT 구조

. 을 기준으로 Header(헤더), Payload(내용), Signature(서명)으로 이루어짐 ex) xxxx.yyyy.zzzz

① Header

헤더는 일반적으로 '토큰 유형 & 사용되는 서명 알고리즘 ' 두 부분으로 구성됨.

{ // 예시
  "alg": "HS256",
  "typ": "JWT"
}

Header는 Base64Url로 인코딩 되어 JWT의 첫 번째 부분을 구성함

❓ Base64Url 인코딩

Base64 인코딩 의 변형된 형태

기존 Base64 인코딩은 URL에 사용 시 문제가 될 수 있는 문자를 포함 할 수 있어서 이른 URL에 적합하게 수정한 것

• 바이너리 데이터를 아스키 문자열로 변환하는 방법
• 주로 텍스트나 이미지 등의 데이터를 웹에서 안전하게 전송하기 위해 사용함
• 일반적으로 6비트씩 64개 문자 사용

② Payload

토큰과 관련된 정보(Claim)를 담음

❓ Claim 엔티티와 추가적인 데이터에 대한 설명 Registerd(등록된), public (공개), private (비공개) claim으로 나뉨

1. Registered Claim

토큰에 대한 정보를 담는 데 사용 JWT는 간결하게 작성 돼야 하므로 _클레임 이름은 3글자_로 제한

2. Public Claim

공개되어도 상관 없는 클레임 다른 시스템과의 상호운용성을 위해 사용될 수 있음 다른 시스템과의 충돌을 피하기 위해 유니크한 이름을 가져야 하며, 보통 URI로 작성

3. Private Claim

발급자와 수신자 간에만 의미 있는 클레임 다른 시스템과 공유되지 않으며, 해당 애플리케이션이나 서비스에서만 사용

JWT는 Header와 Payload를 Base64Url로 인코딩 하여 토큰 생성

디코딩이 정말 쉽기때문에, 민감한 정보는 넣지 말아야 함

③ Signature

해당 토큰이 조작되었거나 변경되지 않았음을 확인하는 용도 Header 인코딩 값, Payload 인코딩 값 그리고 비밀키를 사용해 해시 값 생성

글이 길어지면 읽기 싫은 관계로 [Spring] 토큰 기반 인증, JWT 2편 에서 계속...

참고 Introduction to JSON Web Tokens

1. 인증 (Authentication): 사용자의 신원을 입증 하는 과정
2. 인가 (Authorization): 사이트의 특정 부분에 접근할 수 있는지 권한을 확인하는 과정

1. 스프링 시큐리티

스프링 기반 애플리케이션의 보안을 담당하는 스프링 하위 프레임워크

• 보안 관련 옵션 제공
• CSRF 공격, 세션 고정 공격 방어 및 요청 헤더 보안 처리
• 필터 기반 동작

❓ CSRF 공격 & 세션 고정 공격

• CSRF 공격: 사용자의 권한을 가지고 특정 동작을 수행하도록 유도하는 공격
• 세션 고정 공격: 사용자의 인증 정보를 탈취하거나 변조하는 공격

1) 필터 구조

1. Security Context Persistence Filter

Security Context Repository에서 Security Context를 가져오거나 저장하는 역할

2. Logout Filter

설정된 로그아웃 URL로 오는 요청을 확인해 해당 사용자 로그아웃 처리

3. Username Password Authentication Filter

인증관리자, 폼 기반 로그인 시 사용되는 필터로 아이디 & 패스워드 데이터를 파싱해 인증 요청을 위임한다.

4. Default Login Page Generating Filter

사용자가 로그인 페이지를 따로 지정하지 않았을 때 기본으로 설정하는 로그인 페이지 관련 필터

5. Basic Authentication Filter

요청 헤더에 있는 아이디와 패스워드를 파싱해서 인증 요청 위임

6. Request Cache Aware Filter

로그인 성공 후, 관련 캐시 요청이 있는지 확인 및 캐시 요청 처리 ex) 로그인 전 방문 페이지 기억 -> 로그인 후 해당 페이지로 이동

7. Security Context Holder Aware Request Filter

HttpServletRequest 정보를 감싼다. 필터 체인 상의 다음 필터들에게 부가 정보 제공

8. Anonymous Authentication Filter

필터가 호출되는 시점까지 인증되지 않은 경우, 익명 사용자 전용 객체인 Anonymous Authentication을 만들어 Security Context에 삽입

9. Session Management Filter

인증된 사용자와 관련된 세션 관련 작업 진행 세션 변조 방지 전략 설정, 유효하지 않은 세션에 대한 처리 및 세션 생성 전략 세움

10. Exception Translation Filter

요청을 처리하는 중에 발생할 수 있는 예외 위임 & 전달

11. Filter Security Interceptor

접근 결정 관리자 Access Decision Manager로 권한 부여 처리를 위임함으로써 접근 제어 결정 쉽게 함

위 과정에서 이미 사용자가 인증되어 있으므로 유효한 사용자인지 확인 가능 즉, 인가 관련 설정

2) 인증 처리 과정

아이디 & 패스워드 기반 폼 로그인 시도 시, 스프링 시큐리티에서 어떤 절차로 인증하는가?

1. 사용자가 폼에 아이디와 패스워드 입력 시 HttpServletRequest에 아이디와 비밀번호 정보가 전달됨

   ❓ Http Servlet Request

   Java Servlet API에서 제공하는 인터페이스 클라이언트로부터 들어온 HTTP 요청의 모든 정보를 캡슐화한 객체

   이 객체를 통해 클라이언트가 보낸 데이터(파라미터, 헤더, 쿠키 등)를 읽거나, 요청과 관련된 정보를 확인할 수 있음

2. Authentication Filter는 넘어온 정보 가지고 실제 구현체인 UsernamePasswordAuthenticationToken (이하 token) 만듦.

3. token을 Authentication Manager로 넘긴 후, 4. Authentication Provider에 보냄

   ❓ Manager ? Provider ?

   Authentication Manager는 인터페이스, 기본 구현체가 Provider Manager. Provider Manager 내부에 있는 Authentication Provider(s)를 사용하는 거임

5. 사용자 아이디를 UserDetailService에 보낸 후, 6. 아이디로 찾은 사용자 정보를 UserDetails 객체로 만듦

7. 입력 정보와 UserDetails의 정보를 비교해 실제 인증 처리

❓ 인증 처리

인증 성공	Authentication 객체 반환
인증 실패	AuthenticationException 발생

8. 9. 10. 인증이 성공한 경우 SecurityContextHolder에 Authentication 저장

3) Security Context Holder

- Security Context Holder

• Spring Security가 현재 인증된 사용자의 세부 사항을 저장하는 공간 Spring Security는 Holder에 뭐가 어떻게 저장되는지 신경 안 씀.

• 걍 여기 있으면 인증된 친구들인갑다 생각함

• 기본값으로 ThreadLocal을 사용함

  각 스레드마다 독립적인 변수를 저장할 수 있게 해주는 클래스 즉, 여러 스레드가 동시 실행될 때 각 스레드가 자신만의 값을 가짐. 서로 터치 X

• Security Context Holder는 Security Context를 보관 & 제공하는 공간

- Security Context

• 현재 인증된 사용자의 보안 정보를 담고 있는 객체 주로 Authentication 객체를 포함하며 이 객체는 사용자가 로그인 후 인증된 상태에서 어떤 역할(권한)을 가지고 있는지 등의 정보를 제공함

출처: Servlet Authentication Architecture

• 숫자가 저장된 배열 (nums)와 목표값 (target)이 주어진다.
• 배열 내의 모든 숫자를 더하거나 빼서 target을 만들 수 있는 경우의 수 반환

생각하기

처음 문제를 읽고 "내가 이거 풀 수 있나?" 라는 생각이 먼저 듦. 그래서 그냥 배열 끝까지 탐색하고 target 값이 0이 되면 경우의 수 count 올리는 방식으로 접근했다.

🍳 전체 소스 코드 1

class Solution {
        static int count;
    public int findTargetSumWays(int[] nums, int target) {
        count=0;
        dfs(nums, target, 0, 0);
        return count;
    }
      public static void dfs(int [] nums, int target, int idx, int total){
        if(idx == nums.length){
            if(target == total){
                count++;
            }
            return;
        }

        dfs(nums, target, idx+1, total+nums[idx]);
        dfs(nums, target, idx+1, total-nums[idx]);
    }
}

• count: 경우의 수
• dfs(): 현재 값을 누적값에 더하거나 빼기

이렇게 배열의 끝까지 도달했을 때 target과 누적값(total)이 같으면 count 1증가

풀리긴 풀리는데 시간복잡도가 외딴섬 로맨틱 -> 넘 오래 걸려유

그렇다면.. 중복탐색을 안하게끔 만들어 주면 되겠다~

🍳 전체 소스 코드 2

class Solution {
    static Map<String,Integer> memo;
    public int findTargetSumWays(int[] nums, int target) {
         memo = new HashMap<>();
        int res =dfs(nums, target, 0,0);
        return res;
    }
      public static int dfs(int [] nums, int target, int idx,int total){
        if(idx == nums.length){
            return target == total?1:0;
        }
        if(memo.containsKey(idx+","+total)){
            return memo.get(idx+","+total);
        }

        int res = dfs(nums, target, idx+1,total+nums[idx])
                + dfs(nums, target, idx+1,total-nums[idx]);

        memo.put(idx+","+total, res);
        return res;
    }
}

• memo: key: 현재idx, 누적값 value: target 도달 여부

이번에는 memo라는 Map을 사용해서 현재 인덱스의 누적값이 memo에 존재하는 경우, 탐색을 진행하지 않고 저장된 value를 반환 하는 코드를 추가했다.

이게 되나? 어차피 우리는 순차적으로 배열을 탐색하기 때문에.. 뒤는 안 봐도 비디오임 못 믿을 수도 있으니 해볼게유

이 2)에서 인덱스가 3이고 누적값이 1인 경우는 이미 위에서 확인했잖아요? 그래서 4)에서 해당 값을 고대로 사용해가지고 탐색하지 않는 겁니다..

✨ 결과

어려워도.. 냅다 박치기 하면 풀린다.. 리팩토링은 일단 풀고 나서 생각하자

이미지를 받아서 저장하는 로직을 구현하는 중 Maximum upload size exceeded 에러가 발생했다.

에러메시지 그대로 사진이 넘 커서 저장하기 싫다는 말이다. 나는 따로 사이즈를 지정을 안 해줘서 최대 크기인 1MB만 받을 수 있는데, 나는 그 용량을 초과했다.

✨ 해결

위처럼 최대 사이즈를 수동으로 저장해조야한다.

참고: [오류해결] resolved [org.springframework.web.multipart.maxuploadsizeexceededexception: maximum upload size exceeded]

• 각 칸의 높이를 저장한 NxM 배열, 현재 갖고 있는 블럭 수(b)가 주어짐
• 최단시간에 모든 칸의 높이가 같도록 해야함. ⓛ 블럭 쌓기 = 1초 ② 블럭 제거 & inventory 저장 = 2초
• 답이 여러 개인 경우, 높이가 가장 큰 값을 반환

생각하기

현재 배열 내에서 최소 높이(이하 min), 최대 높이(이하 max)를 알면, 답으로 나올 수 있는 높이의 범위는 min<= height <= max 임. 그러면 위 범위에서 반복문을 돌려서 가장 적은 시간 & 높이를 구하면 됨.

예제에 보면 같은 높이를 가진 칸이 여러 개일 수 있으니까, map을 이용해서 풀면 어떨까? map: key: 높이, value: 해당 key 높이를 가진 칸의 개수

특정 높이 (height)를 기준으로, count = map.get(h) : 배열 내 h 높이를 가진 칸의 개수

** 1. 높이(h) > height인 경우** 높이 차이(diff) 만큼 블럭 제거 time += diff x count x 2 && b += count

** 2. 높이(h) < height인 경우**

높이 차이 (diff) 만큼 블럭 쌓기 time += diff x count && b -= count

계산이 끝나고 난 후 현재 가지고 있는 블럭(b)가 음수인 경우, 사용할 수 있는 블럭을 초과했으므로 해당 높이는 답이 될 수 없음.

따라서 b >= 0인 경우만, 나올 수 있는 경우로 간주하고 진행해야한다.

🍳 전체 소스 코드

import java.io.*;
import java.util.*;

public class Main{
    static Map<Integer, Integer> ground;
    static int b;
    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());
        b = Integer.parseInt(st.nextToken());

        int cMax = -1;
        int cMin = 256;
        ground = new HashMap<>();
        while(n-- > 0){
            st= new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                int k = Integer.parseInt(st.nextToken());
                ground.put(k,ground.getOrDefault(k, 0)+1);
                cMax = Math.max(cMax, k);
                cMin = Math.min(cMin, k);
            }
        }
        if(ground.keySet().size()==1){
            System.out.println(0+" "+cMax);
            return;
        }

        int res= Integer.MAX_VALUE;
        int height =0;
        for(int h =cMin;h<=cMax;h++){
            int time = getHeight(h);
            if(time > -1){
                if(time <= res){
                    res =time;
                    height = Math.max(height, h);
                }
            }
        }
        System.out.println(res+" "+height);
    }

    public static int getHeight(int height){
        int blocks = b;
        int  time =0;
        for(int h : ground.keySet()){
            int count =ground.get(h);
            int diff = Math.abs(height-h); // 높이차
            if(h>height){   // 제거
                time +=count*diff*2;
                blocks+=count*diff;
            }
            else if(h < height){    // 추가
                time +=count*diff;
                blocks-=count*diff;
            }
        }
        if(blocks<0){
            return -1;
        }
        return time;
    }
}

✍ 부분 코드 설명

변수 선언 & 초기화

public class Main{
    static Map<Integer, Integer> ground;
    static int b;
    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());
        b = Integer.parseInt(st.nextToken());

        int cMax = -1;
        int cMin = 256;
        ground = new HashMap<>();
        while(n-- > 0){
            st= new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                int k = Integer.parseInt(st.nextToken());
                ground.put(k,ground.getOrDefault(k, 0)+1);
                cMax = Math.max(cMax, k);
                cMin = Math.min(cMin, k);
            }
        }
    ...   

• ground: 높이 별로 땅의 개수 저장
• b: 현재 갖고 있는 블럭 개수
• cMax: 배열 내 최대 높이
• cMin: 배열 내 최소 높이

높이에 따른 땅의 개수를 groud에 저장하고, 최대 높이, 최소 높이를 구한다.

높이 계산하기

        ...

  if(ground.keySet().size()==1){
            System.out.println(0+" "+cMax);
            return;
        }

        int res= Integer.MAX_VALUE;
        int height =0;
        for(int h =cMin;h<=cMax;h++){
            int time = getHeight(h);
            if(time > -1){
                if(time <= res){
                    res =time;
                    height = Math.max(height, h);
                }
            }
        }
        System.out.println(res+" "+height);
    }
            ...

- res : 최소 시간 - height: 최대 높이

• key가 1개인 경우, 배열 내 모든 땅의 높이가 같다는 의미

• 땅을 고를 필요가 없으므로 0, cMax 반환 및 종료

cMin ~ cMax 범위 내에서 각 값을 기준 높이(h)로, getHeight() 함수 호출

함수 반환 값이 -1이 아니면, 땅을 고를 수 있는 경우임 -> 현재 저장된 최소 시간(res) 보다 작거나 같은 경우, res값 갱신, 최대 높이(height) 갱신.

getHeight 함수

        ...

   public static int getHeight(int height){
        int blocks = b;
        int  time =0;
        for(int h : ground.keySet()){
            int count =ground.get(h);
            int diff = Math.abs(height-h); // 높이차
            if(h>height){   // 제거
                time +=count*diff*2;
                blocks+=count*diff;
            }
            else if(h < height){    // 추가
                time +=count*diff;
                blocks-=count*diff;
            }
        }
        if(blocks<0){
            return -1;
        }
        return time;
    }
}

- blocks : 현재 사용 가능한 블럭 수 - time : 총 소요시간

ground에 저장된 모든 높이를 순회하면서, time과 blocks를 계산한다.

*1. blocks가 음수인 경우 * 사용할 수 있는 블럭을 초과해서 땅을 고른 경우이기 때문에 해당 높이는 답이될 수 없음 ∴ -1반환

2. blocks가 0이상인 경우 사용가능한 블럭 내에서 땅을 골랐으므로 소요시간을 반환한다.

✨ 결과

처음에 높이로 삼을 수 있는 건 블럭 내의 높이만 가능하다고 생각해서 풀었더니 틀렸다. 최소 높이~최대 높이 사이의 모든 값을 기준으로 삼고 브루트 포스로 풀어야 한다...

나처럼 바보 상자가 되지 말기를

• 선영이(1번)가 캠프파이어에 참여하는 날에는 새로운 노래 등장
• 선영이 없으면, 참가자들끼리 아는 모든 노래 공유

MT가 끝난 이후, 모든 노래를 아는 친구들 오름차순 출력

생각하기

선영이는 모든 노래를 알고 있다... 왜냐하면 선영이가 대장이라 선영이 있을 때만 새로운 노래를 부르기때문이다. 그럼 매일 두 가지 경우로 나누어서 처리해야한다.

1) 선영이가 있는 경우 현재 참가자들끼리 *새로운 노래 *추가

2) 선영이가 없는 경우 자기들이 알고 있는 노래를 공유하므로, 공유한 모든 노래들을 당일 참가자에게 추가.

처음에는 Set만 사용해서 현재 모든 노래를 알고 있는 참가자만 저장했지, 참가자별로 알고 있는 노래들은 저장하지 않았다.

선영이가 있는 날, 아래 친구들을 set에서 제외한다.

1. 이전 노래를 모르는 친구
2. 현재 모든 노래를 알고 있는 친구들 중 오늘 참가하지 않은 친구
   선영이가 없는 날이면, 현재 참가자 중에 set에 포함된 친구가 있으면 참가자 모두를 set에 넣어줬다.

그런데, 이렇게 풀면 아래 반례에서 걸린다.

내 접근대로 풀면 모든 노래를 아는 친구는 1번만 있다고 나온다.

하지만, 4일째에 2, 3, 4번이 서로 알고 있는 노래를 공유하게 되므로 결과적으로 1, 2, 3 ,4 번이 모든 노래를 알 수 있다.

위 반례를 통해** 친구들 별로 자신들이 알고 있는 노래를 저장** 해야 함을 알게 돼서 다 갈아엎었음. ㅎ

🍳 전체 소스 코드

import java.io.*;
import java.util.*;

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

        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int days = Integer.parseInt(br.readLine());
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int d=0;d<days;d++){
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            List<Integer> participants = new ArrayList<>();
            while (st.hasMoreTokens()){
                participants.add(Integer.parseInt(st.nextToken()));
            }
            if(participants.contains(1)){
                for(int p: participants){
                    Set<Integer> know = map.getOrDefault(p, new HashSet<>());
                    know.add(d);
                    map.put(p, know);
                }
            }else{
                Set<Integer> shares =new HashSet<>();
                for(int p : participants){
                    if(map.get(p)!=null)
                        shares.addAll(map.get(p));
                }
                for(int p: participants){
                    map.put(p, new HashSet<>(shares));
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        int goal = map.get(1).size();
        for(int p: map.keySet()){
            if(map.get(p).size() ==goal){
                result.add(p);
            }
        }
        Collections.sort(result);
        for(int v: result){
            bw.write(v+"\n");
        }
        bw.flush();
        bw.close();
    }
}

✍ 부분 코드 설명

변수 선언 & 초기화

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

        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int days = Integer.parseInt(br.readLine());
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int d=0;d<days;d++){
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            List<Integer> participants = new ArrayList<>();
            while (st.hasMoreTokens()){
                participants.add(Integer.parseInt(st.nextToken()));
            }
    ...   

• n: MT 참가자 수
• days: MT 날짜
• map: key: 참가자 번호, value: 해당 참가자가 아는 노래
• participants: 당일 참가자 목록

participants 리스트에 당일 참가자들을 저장한다.

선영이 유무에 따른 처리

        ...

    if(participants.contains(1)){
                for(int p: participants){
                    Set<Integer> know = map.getOrDefault(p, new HashSet<>());
                    know.add(d);
                    map.put(p, know);
                }
            }else{
                Set<Integer> shares =new HashSet<>();
                for(int p : participants){
                    if(map.get(p)!=null)
                        shares.addAll(map.get(p));
                }
                for(int p: participants){
                    map.put(p, new HashSet<>(shares));
                }
            }
        }
            ...

1. 선영이 있는 경우 참가자 전원 오늘 날짜 추가 (= 새로운 노래는 하나만 부르니까 걍 오늘 날짜 저장해도 됨)

2. 선영이 없는 경우 잡도리하는 선영이 없어서 자기들이 아는 노래 공유하는 시간 갖는다. 그래서 shares 집합을 만들어서 참가자들이 알고 있는 노래들을 다 저장함. 그리고 참가자들 노래 목록을 shares로 업데이트

모든 노래 알고 있는 친구 찾기

        ...

   List<Integer> result = new ArrayList<>();
        int goal = map.get(1).size();
        for(int p: map.keySet()){
            if(map.get(p).size() ==goal){
                result.add(p);
            }
        }
        Collections.sort(result);
        for(int v: result){
            bw.write(v+"\n");
        }
        bw.flush();
        bw.close();
    }
}

위에 문제 설명에서 말했듯, 선영이는 모든 노래를 알고 있잖아요? 그러면, 선영이가 아는 노래 개수 = 참가자가 아는 노래 개수 인 경우 해당 친구는 모든 노래를 알고 있다고 간주해도 되겠죠?

그리고 오름차순으로 출력하라고 했으니 Collections.sort 로 오름차순으로 만들어주고 출력!

✨ 결과

개오래걸림 그래두 풀었으니 뭐.. 네..

• 0 ~ numCourse-1까지 모든 과목을 수강할 수 있는지 여부 반환
• 선수 과목이 있는 경우, 선수 과목을 먼저 수강해야 함.

생각하기

처음 고민했을 땐 위상정렬이라고는 생각을 못했다. [0,1], [1,0] 선이수 과목끼리 _싸이클이 생기게 되면 모든 과목을 들을 수가 없음_을 깨닫고, 싸이클이 생기면 false를 반환하면 되겠다고 생각해서 코드를 쳤다. 근데 걍 틀림

싸이클 여부를 찾은 건 잘했는데, 위상 정렬이랑 안 친해서.. 몰랐어유 그래서 오늘 위상정렬 공부했음

❓ 위상정렬

위상 정렬(Topology Sort)이란?

방향이 있는 비순환 그래프 (DAG, Directed Acyclic Graph)에서 사용

• 작업 i와 작업 j 사이에 간선(i, j)가 존재한다면 작업 i는 반드시 작업 j보다 먼저 수행되고, 그래프의 모든 간선이 이런 성질을 만족하는 정렬을 의미한다.

• 위상 정렬은 사이클이 없는 유향 그래프G=(V, E)에서 V의 모든 정점을 정렬하되 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야한다.

만일 그래프에 사이클이 존재한다면, 해당 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다.

넘 이론적인 얘기라서 이해가 어려울 수 있다. 간단히 대학교 전공 수업처럼 선이수 과목 먼저 수강해야 다음 거 들을 수 있음. 그런데 a의 선이수 과목이 b고 b의 선이수 과목이 a면 말도 안 된다는 의미

위상 정렬 방법

• Kahn's Algorithm: 진입차수와 큐를 이용
• DFS: 그래프를 DFS로 탐색하면서 작업을 스택에 쌓음

문제 풀 때 칸 알고리즘 사용했으니 먼저 소개하겠다. dfs 풀이는 210. Course Schedule II 문제도 같이 풀어서 아래에 설명

1. Kahn's Algorithm

 public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] list =new List[numCourses];
        List<Integer> res = new ArrayList<>();
        int [] indegree = new int[numCourses];
        for(int [] pair : prerequisites){
            int after  =pair[0];
            int before = pair[1];
            if(list[before]==null){
                list[before] = new ArrayList<>();
            }
            list[before].add(after);
            indegree[after]++;
        }
        Queue<Integer> que = new ArrayDeque<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                que.offer(i);
            }
        }

        while(!que.isEmpty()){
            int cur = que.poll();
            res.add(cur);

            if(list[cur]!=null){
                for(int v: list[cur]){
                    indegree[v]--;
                    if(indegree[v]==0){
                        que.offer(v);
                    }
                }
            }
        }
        System.out.println( res.size() == numCourses);
        return res.size() == numCourses;
    }

✍ 부분 코드 설명

** 변수 선언 및 초기화 **

 public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] list =new List[numCourses];
        List<Integer> res = new ArrayList<>();
        int [] indegree = new int[numCourses];
        for(int [] pair : prerequisites){
            int after  =pair[0];
            int before = pair[1];
            if(list[before]==null){
                list[before] = new ArrayList<>();
            }
            list[before].add(after);
            indegree[after]++;                      
        }
            ...

• list: 정점 별 진출 정점 저장
• indegree: 정점 별 진입 차수 저장
• res: 진입 차수가 0인 (방문 가능한) 정점 저장

위상 정렬

    ...

 Queue<Integer> que = new ArrayDeque<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                que.offer(i);
            }
        }
        while(!que.isEmpty()){
            int cur = que.poll();
            res.add(cur);

            if(list[cur]!=null){
                for(int v: list[cur]){
                    indegree[v]--;
                    if(indegree[v]==0){
                        que.offer(v);
                    }
                }
            }
        }
        System.out.println( res.size() == numCourses);
        return res.size() == numCourses;
    }

1. 진입 차수가 0인 정점 que에 삽입
2. 순차적으로 que에서 정점 제거 및 res에 해당 정점 삽입
3. 현재 정점 (cur)의 진출 정점이 존재하는 경우, 해당 진출 정점들의 진입 차수 감소.
4. 1 ~ 3과정을 que가 빌 때까지 반복

백문이 불여일견

2. DFS & Stack

package Arrays_Hashing;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class N_210 {
    static List<List<Integer>> list;
    static Stack<Integer> stack;
    static boolean [] visited;
    static boolean [] finish;
    static boolean cycle;
    public static int[]canFinish(int numCourses, int[][] prerequisites) {
        list =new ArrayList<>();
        stack = new Stack<>();
        visited = new boolean[numCourses];
        finish = new boolean[numCourses];
        cycle =false;

        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }

        for(int [] pair: prerequisites){
            int after= pair[0];
            int before= pair[1];
            list.get(before).add(after);
        }

        for(int i=0;i<numCourses;i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        int [] res = new int[numCourses];
        if(!cycle){
            int idx =0;
            while(!stack.isEmpty()){
                res[idx++] = stack.pop();
            }
        }
        else{
            return res;
        }
        System.out.println(true);
        return res;
    }
    public static void dfs(int cur){
        if(cycle){
            return;
        }
        visited[cur] = true;
        for(int next : list.get(cur)){
            if(!visited[next]) {
                dfs(next);
            }
            else if(!finish[next]){
                cycle = true;
                return;
            }
        }
        finish[cur]=true;
        stack.push(cur);
    }

    public static void main(String[] args) {
        int numCourses = 2;
        int [][] prerequisites = new int[][]{
                {1,0},
                {0,1}
        };

        canFinish(numCourses, prerequisites);
    }
}

✍ 부분 코드 설명

** 변수 선언 및 초기화 **

public class N_210 {
    static List<List<Integer>> list;
    static Stack<Integer> stack;
    static boolean [] visited;
    static boolean [] finish;
    static boolean cycle;
    public static int[]canFinish(int numCourses, int[][] prerequisites) {
        list =new ArrayList<>();
        stack = new Stack<>();
        visited = new boolean[numCourses];
        finish = new boolean[numCourses];
        cycle =false;

        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }

        for(int [] pair: prerequisites){
            int after= pair[0];
            int before= pair[1];
            list.get(before).add(after);
        }

            ...

• list: 정점 별 진출 정점 저장
• visited: 정점 별 방문 여부
• finish: 정점 별 방문 완료 여부
• cycle: cycle 존재 여부

위상 정렬

    ...

     for(int i=0;i<numCourses;i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        int [] res = new int[numCourses];
        if(!cycle){
            int idx =0;
            while(!stack.isEmpty()){
                res[idx++] = stack.pop();
            }
        }
        else{
            return res;
        }
        System.out.println(true);
        return res;
    }
    public static void dfs(int cur){
        if(cycle){
            return;
        }
        visited[cur] = true;
        for(int next : list.get(cur)){
            if(!visited[next]) {
                dfs(next);
            }
            else if(!finish[next]){
                cycle = true;
                return;
            }
        }
        finish[cur]=true;
        stack.push(cur);
    }

1. 현재 방문하지 않은 정점 기준, dfs 호출
2. 현재 정점 방문 처리 & 진출 정점 확인 2-1) 진출 정점에 방문하지 않은 경우 해당 정점 기준 재귀 호출 2-2) 진출 정점에 이미 방문 했지만, 완료된 정점이 아닌 경우, 그래프 내에 싸이클이 존재하므로 탐색 하지 않고 RETURN
3. 더이상 진출 정점이 없는 경우, 방문 완료 처리 및 stack 삽입

이렇게 하면, 방문해야 하는 순서대로 stack에 저장되므로 순서도 파악할 수 있다.

✨ 결과

학부생때 위상 정렬 배웠는데,, 아예 안써서 기억의 저편으로 넘어가버렸다. 그래도 오늘 다시 공부했으니 다행~

내가 접근한 풀이를 보여주자면

 static boolean [] visited;
    static Map<Integer, List<Integer>> map;
    static boolean res;
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        res = true;
        map =new HashMap<>();
        for(int [] pre: prerequisites){
            List<Integer> tmp = map.getOrDefault(pre[0], new ArrayList<>());
            tmp.add(pre[1]);
            map.put(pre[0],tmp);
        }
        for(int i=0;i<numCourses;i++){
            visited = new boolean[numCourses];
            if(!visited[i] && map.containsKey(i)){
                for(int v : map.get(i)){
                    dfs(v);
                    visited[i]=true;
                }
            }
            if(!res){
                System.out.println(res);
                return false;
            }
        }
        System.out.println(res);
        return res;
    }
    public static void dfs(int cur){
        if(map.get(cur)==null){
            return;
        }
        if(!visited[cur]){
            visited[cur]=true;
            for(int v: map.get(cur)){
                dfs(v);
            }
            if(!res){
                return;
            }
        }else{
            res = false;
        }
    }

dfs로 접근헀는데,, 싸이클 체크를 괴상하게 구현해서 틀림 ㅎㅎ

• 퇴사 전까지 돈을 땡기고 싶은 백준이에게.. 최대 이익 선물해 주기

예전에 풀다가 대차게 틀렸던 문제였다. 분명 그때 풀이 보고 다음에 만나면 짓밟아 주겠다고 생각했는데 오늘 보니 또 새롭네요

생각하기

dp 냄새가 납니다. 백준이가 벌 수 있는 최대의 돈.. 뭔가 이전 최댓값과 비교해서 현재값이 더 크면 그게 정답이 될 것 같은 느낌이 들었어요.

i번째 날 작업이 걸리는 시간이 n인 경우, i+n날 이후 모든 날의 이익은 최소 i번째 날의 이익이라는 것을 깨닫는 게 중요하다.

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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 [][] dp =new int[n+1][2];
        int [] total = new int[n+2];
        dp[0][0] = 0;
        dp[0][1] = 0;
        for(int i=1;i<=n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            dp[i][0] = Integer.parseInt(st.nextToken());
            dp[i][1] = Integer.parseInt(st.nextToken());
        }
        int max =0;
        for(int i=1;i<=n;i++){
            int time = dp[i][0]+i;
            if(time <= n+1){
                for(int t = time;t<=n+1;t++){
                   total[t] =  Math.max(total[t], dp[i][1]+total[i]);
                }
            }
        }

        System.out.println(total[n+1]);
    }
}

백문이 불여일견

• dp: 날짜별 작업 시간 & 이익 저장
• total 날짜별 누적 최대 이익 저장

현재 날짜에서 작업시간을 더한 날을 next라고 칭했을 때, next 값이 퇴사날 이전인 경우 계산을 시작한다.

• 현재 날짜까지 최대 이익 (total[i]) + 현재 날짜를 선택함으로써 얻을 수 있는 이익 (dp[i][1])

• next에 누적된 이익 (total[next])

위 두 개의 값 중 더 큰 값을 total[next]에 저장한다.

숫자에 빨간 표시한 부분이 최대 이익이 갱신된 경우 다. 위와 같은 로직으로 계산이 이루어진다고 생각하면 된다.

우리는 배열을 만들 때, 퇴사날인 8일의 공간을 만들어 줘서 total[8]에 최대이익을 저장하면 된다. 나는 이 방법을 반복문 내에, i+n일 이후부터 퇴사날까지 반복문을 하나 더 두어서 최대 이익을 저장할 수 있게 했다.

이중 반복문이기에 내 풀이는 효율적이진 않다. 반복문을 돌리지 않고 풀 수 있는 방법이 있지만, 문제를 풀고 나서 깨달았다.

for(int i=1;i<=n;i++){
    int time = dp[i][0]+i;
    if(time <= n+1){
        total[time] =  Math.max(total[time], dp[i][1]+total[i]);
    }
    total[i+1]=Math.max(total[i],total[i+1]);
}

이중 반복문이 아닌, 현재 날짜의 다음 날짜의 최대 이익을 비교해서 다음 날짜의 최대이익을 갱신하면 된다.

그렇게 되면, 우리는 퇴사날까지 우리가 구한 최대 이익을 들고 갈 수가 있다.

✨ 결과

음. 혼자 푼 거 꽤괜 시간 단축만 하면 될 거 같다

• 남학생: 받은 숫자 배수 스위치 상태 변경
• 여학생: 받은 숫자 기준, 대칭이 되는 모든 스위치 상태 변경
• 스위치 상태는 20개 씩 출력 후 줄바꿈

그렇게 어려운 문제는 아닌데, 오래걸렸다.. 처음에 문제를 제대로 안 읽어서 배수인 줄 몰랐고,, 20개 줄바꿈도 안 했고 무엇보다 인덱스를 잘 못 다뤘다.

생각하기

풀이 방법은 간단하다. 그냥 위 조건대로 구현을 하면 되는 문제긴 한데, 인덱스 조절하는 게 좀 번거로웠다.

배열의 경우 0부터 시작을 하는데, 문제에서는 스위치 번호가 1부터 시작을 해서 배열의 크기를 주어진 수+1 만큼 해주고 구현하면 된다.

🍳 전체 소스 코드

import java.io.*;
import java.util.StringTokenizer;

public class N_1244 { 
    static int[] switches;

    public static void printSwitches(){
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<switches.length;i++){
            sb.append(switches[i]+" ");
            if(i%20==0){
                sb.append("\n");
            }
        }
        System.out.println(sb.toString());
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st =new StringTokenizer(br.readLine());

        switches = new int[n+1];
        for(int i=1;i<=n;i++){
            switches[i] = Integer.parseInt(st.nextToken());
        }
        int student = Integer.parseInt(br.readLine());
        while(student -- > 0){
            st = new StringTokenizer(br.readLine());
            int sex = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());

            calc(sex, pos);
        }
        printSwitches();
    }
    public static void calc(int sex, int pos){
        if(sex == 1){
            for(int i=1;pos*i<switches.length;i++){
                switches[pos*i] =
                        (switches[pos*i]==0)?1:0;
            }
        }else{
            int start, end;
            start = end=pos;
            while(start >=2 && end<switches.length-1){
                start--;
                end++;
                if(switches[start]!=switches[end]){
                    start ++;
                    end--;
                    break;
                }
            }
            for(int i=start;i<=end;i++){
                switches[i] =
                        (switches[i]==0)?1:0;
            }
        }
    }

}

• main : 입력 및 초기화
• calc : 남&여 학생에 따른 스위치 변화
• printSwitches: 스위치 상태 출력

✍ 부분 코드 설명

Main 함수 - 입력 & 변수 초기화

     static int[] switches;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st =new StringTokenizer(br.readLine());

        switches = new int[n+1];
        for(int i=1;i<=n;i++){
            switches[i] = Integer.parseInt(st.nextToken());
        }
        int student = Integer.parseInt(br.readLine());
        while(student -- > 0){
            st = new StringTokenizer(br.readLine());
            int sex = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());

            calc(sex, pos);
        }
        printSwitches();
    }

    ...   

• switches: 스위치 상태 저장 배열
• n: 스위치 개수
• student: 학생 수
• sex: 학생 성별
• pos: 스위치 변경 기준 위치

들어온 입력대로 스위치 상태를 저장해 주고, 학생 수 만큼 calc 함수를 호출해서 스위치 상태를 변경한다.

calc 함수

    public static void calc(int sex, int pos){
        if(sex == 1){
            for(int i=1;pos*i<switches.length;i++){
                switches[pos*i] =
                        (switches[pos*i]==0)?1:0;
            }
        }else{
            int start, end;
            start = end=pos;
            while(start >=2 && end<switches.length-1){
                start--;
                end++;
                if(switches[start]!=switches[end]){
                    start ++;
                    end--;
                    break;
                }
            }
            for(int i=start;i<=end;i++){
                switches[i] =
                        (switches[i]==0)?1:0;
            }
        }
    }

sex 매개변수에 남학생은 1로, 여학생은 2로 들어온다.

1. 남학생

남학생은 스위치 번호가 자신이 받은 수의 배수이면 상태를 바꾼다. 예를 들어 3이 들어온 경우, 우리는 3번,6번, 9번 .. 스위치를 바꾼다. i 값을 증가해 가면서 배수를 찾으면 돼서 여학생보다 쉽다.

2. 여학생

여학생은 자신이 받은 수의 스위치 번호를 기준으로 양 옆이 대칭인 모든 스위치의 상태를 바꾼다.

예를 들어 스위치의 초기상태가 1 1 0 0 0 1 0 이고, 여학생이 4번을 받은 경우, [3번, 5번] 스위치가 0으로 대칭이고, [2번, 6번] 스위치가 1로 대칭이다. 하지만, [1번, 7번] 스위치는 각각 1과 0이므로 대칭이 아니다.

결국, 2번~6번까지의 스위치의 상태를 변화시키므로 1 0 1 1 1 0 0 이 된다.

start와 end 변수를 이용해서 pos기준 왼쪽과 오른쪽을 탐색한다.

걍 보여주면서 설명

여학생인 경우 위와 같은 순서로 스위치 상태가 변경 된다.

*Q. * start가 2이하면 종료라 했는데, 3)과정에서 에서 start가 1인데 왜 안 끝나고 실행 돼?

A. 어 왜냐면 3) 과정은 조건문에서 start가 2일 때 실행이 됐는데, 실행문에서 start--로 줄여준 거니까 while은 start가 1인줄 아직 몰랑 그 담에 검사할 때 1인거 앎

보통 배열 탐색 반복문의 종료 조건은 0이상, 마지막 수 미만으로 설정한다. 그래서 처음에 while의 조건을 1이상, 9 (switches.lengthh) 미만으로 설정했더니 틀렸음

왜냐하면, 만약에 모든 스위치가 좌우 대칭인 경우에 end = 9가 되고, start는 0으로 종료가 될 건데, 그렇게 하면 우리는 배열의 범위를 넘어서기 때문에.. _인덱스 초과 에러_가 나요~

그래서 while문의 종료조건이 start가 2이상, end가 마지막에서 두 번째 번호 미만으로 설정했다.

어차피 실행문 내에서 증감을 하기에 모든 원소를 살펴볼 수 있음

대충 요런 식으로 흘러감

printSwitches 함수

  public static void printSwitches(){
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<switches.length;i++){
            sb.append(switches[i]+" ");
            if(i%20==0){
                sb.append("\n");
            }
        }
        System.out.println(sb.toString());
    }

20개 마다 줄바꿈 하라고 했으니 20으로 나누어 떨어지면 줄바꿈 문자 삽입 그대로 배열 출력하면 됨

✨ 결과

내가 젤 싫어하는 인덱스 초과 ;;; 보다시피 실버 4인데 오래걸렸다. 왜 구현에 이렇게 오래 걸렸지 ??? 왜냐면 처음부터 문제 제대로 안 읽고 쉬워 보인다고 빠져가지고 생각 덜 해서 그래

구현 문제 좀 풀어봐야겠다.

• 문제 이름에 어그로 끌려서 압축을 어떻게 했길래 입출력이 이모양이지 생각했지만, _*모든 원소 중 현재 원소보다 작은 친구들 개수 *_구하는 문제.

생각하기

난 인덱스 초과 에러 다음으로 시간 초과에 걸리면 기분이 나쁘기에 시간 제한과 N의 최댓값을 보고 시간 복잡도를 먼저 생각합니다. (최근에 들인 좋은 습관)

1초당 보통 1억 번의 연산이라고 생각하면 돼서, 2초니까 우린 2억 번 연산 내로 풀어야 해요. O(N²)= 1조니까 중첩 반복문 돌리는 순간 시간 초과 엔딩남

그렇다면, O(NlogN)은 어떨까? N=1,000,000일 때,Log(1,000,000) ≒ 20. 즉, 2천만번이라서 다행히 시간초과 안 납니다.

그런데 처음에 귀신 씌어서 Log(1,000,000)을 1,000으로 계산해가지고 O(NlogN)도 시간초과 나는줄 알고 좀 고민 많이 했다...

왜 고민했냐면, 배열을 정렬하는 Arrays.sort 함수가 O(NlogN) 걸려서 이거 쓰면 안 되는 줄 알았음..

그래놓고 우선순위 큐 썼는데, 알고보니 PQ 풀이도 같은 시간복잡도라서 멍청 시간만 썼다.

그래서 두 가지 풀이가 있다. 우선순위 큐, 그리고 배열 정렬 둘 다 설명할 건데,** 배열 정렬이 더 효율적임**

✍ 풀이 방법

1. Priority Queue & HashMap

   public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int [] arr = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i=0;
        while(st.hasMoreTokens()){
            int val = Integer.parseInt(st.nextToken());
            pq.add(val);
            arr[i++]=val;
        }

        int count = 0;
        while(!pq.isEmpty()){
            int prev = pq.poll();
            map.put(prev, count);
            if(!pq.isEmpty() && prev!=pq.peek()){
                count++;
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int key: arr){
            bw.write(map.get(key)+" ");
        }
        bw.flush();
        bw.close();
    }

• arr : 주어진 순서대로 숫자 저장
• map : (key: 숫자, value: key보다 작은 원소 개수)
• pq : 오름차순 정렬에 사용

1. 입력 받은 원소들을 pq와 arr 배열에 삽입 pq는 나중에 뽑아낼 때 작은 친구들 부터 뽑아낼 거고, arr은 출력에 쓰려고 함.

2. map의 key는 pq에서 뽑아낸 값, value는 count 값 저장. 중복값이 존재할 수도 있으니, 현재 원소와 그 다음으로 작은 원소가 같으면 count를 증가시키지 않습니다.

3. 입력 받은 순서대로 값을 출력해야 하니 arr 배열에 저장된 원소를 key값으로 map에서 value를 취해 출력

Q. arr배열 안 만들고 대신 순서 보장해 주는 LinkedHashMap 써서, map.values() 하면 안 됨?

A. ㅇㅇ 해봤는데 중복 원소 허용이라 안 됨 ex) 2, 4, -10, 4, -9 들어오면 1, 3, 0, 1 나와서 4가 씹힙니다.

암튼 이렇게 풀면 배열 두 개 놓고 정렬 원소 쓰는 것보다 메모리, 시간 면에서 비효율적입니다.

그냥 굳이 이렇게 풀 수도 있구나.. 라고 생각하면 됨

2. Arrays.sort & HashMap

 public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        int [] arr  =new int[n];
        int [] sorted  =new int[n];

        for(int i=0;i<n;i++){
            int v =  Integer.parseInt(st.nextToken());
            arr[i] =v;
            sorted[i] =v;
        }
        Arrays.sort(sorted);
        int count =0;
        for(int v: sorted){
            if(map.containsKey(v)){
                continue;
            }
            map.put(v, count++);
        }

        for(int v: arr){
            bw.write(map.get(v)+" ");
        }
        bw.flush();
        bw.close();
    }

• arr, map : PQ 풀이와 역할 같음
• sorted: 원소 정렬 후 배열

1. arr, sorted 배열에 원소 저장
2. Arrays.sort 함수를 이용해 sorted 배열 오름차순 정렬
3. 오름차순대로 map에 해당 원소 value 저장 (원리는 pq 풀이와 동일)
4. arr 배열 원소 순서대로 출력

✨ 결과

확실히 차이 나죠? 결론: 계산을 잘 하자, 그래두 시간 복잡도 생각해서 푼 건 잘했어

• 문제 이름에서 알 수 있듯이 양방향 그래프가 주어지면 DFS, BFS 각각의 방법으로 방문하는 정점을 출력하면 된다.
• 단, 정점 방문 시 작은 숫자부터 방문

생각하기

솔직히 컴공 졸업했으면 이거 고민하면 안 된다~ 난 컴공 탈락

몇 개월 전만 해도 BFS, DFS 로직 바로 구현이 가능했는데, 오래 안 만졌다고 그새 까먹는 건 반성 많이 해야 합니다. 오늘 제대로 공부했으니 그래두 ㄱㅊ아 다음에 까먹으면 걍 죽으면 됨

개념을 알면 풀 수 있기에 생각할 게 따로 있는 건 아니고, DFS, BFS를 설명하려 한다.

1. DFS

DFS는 Depth-First Search의 약어로 깊이 우선 탐색이라고 한다. 이름에서 어떤 친구인지 대충 유추가 가능하지만, 백문이불여일견

1. 1번 부터 시작한다고 가정했을 때, 1번 정점과 연결 된 친구들 탐색 (1번 방문 처리)
2. 2번, 3번, 4번이 연결 됐지만, 가장 작은 숫자를 탐색한다고 하면, 2번으로 이동
3. 2번 정점과 연결된 친구들 탐색 (방문 처리가 되지 않은 정점만 탐색)
4. 이미 방문한 1번을 제하고, 4번으로 이동 (2번 방문 처리)
5. 4번 정점과 연결된 친구들 탐색
6. 마찬가지로 이미 방문한 1번, 2번을 제하고 3번으로 이동 (4번 방문처리)
7. 3번 정점과 연결된 다른 모든 정점이 모두 방문 됐으므로 종료.

따라서 1, 2, 4, 3 순서로 DFS가 구현된다. 만일, 4번 정점과 연결된 5번이 있다면, 방문 순서는 1, 2, 4, 3, 5가 된다.

즉, 현재 정점에서 이동할 수 있는 여러 정점이 있더라도, 다른 정점으로 계속 이동하고 난 후 다시 돌아와서 방문하는 개념이다.

BFS와 같이 보면 더 쉬울 거다.

2. BFS

BFS는 Breadth-First Search의 약어로** 너비 우선 탐색**이라고 한다. 마찬가지로.. 같은 그림을 보여주고 설명해조야지

비슷하게 생겼지만, 설명을 보면 다르다.

1. 1번 부터 시작한다고 가정했을 때, 1번 정점과 연결 된 친구들 탐색 (1번 방문 처리)
2. 작은 숫자부터 2번, 3번, 4번 방문할 예정 (모두 방문 처리)
3. 2번 정점과 연결된 미방문 친구들 탐색
4. 3번 정점과 연결된 미방문 친구들 탐색
5. 4번 정점과 연결된 미방문 친구들 탐색
6. 연결된 모든 정점을 방문했으므로 종료.

따라서 1, 2, 3, 4 순서대로 BFS가 구현된다. 만일, 2번에 5번 정점이 연결된 경우, 1, 2, 3, 4, 5 순서가 된다.

즉, 현재 정점과 연결된 정점들을 우선으로 탐색하는 개념이다.

조금 이해가 되려나ㅎ.. 중요한 건 위 로직을 코드로 구현하는 방법이니까 함 설명해 보겠다.

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static boolean[] visited;
    static StringBuilder sb;
    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 e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        visited = new boolean[n+1];
        sb  = new StringBuilder();

        while (e -- >0){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            PriorityQueue<Integer> list = map.getOrDefault(a, new PriorityQueue<>());
            list.add(b);
            map.put(a,list);

            list = map.getOrDefault(b, new PriorityQueue<>());
            list.add(a);
            map.put(b,list);
        }

        dfs(map, start);
        sb.append("\n");
        visited = new boolean[n+1];
        bfs(map,start);

        System.out.println(sb.toString());
    }

    public static void dfs(Map<Integer, PriorityQueue<Integer>> map, int current){
        visited[current]=true;
        sb.append(current+" ");
        if(map.get(current) == null){
            return;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(map.get(current));
        while(!pq.isEmpty()){
            int v = pq.poll();
            if(!visited[v]){
                dfs(map, v);
            }
        }
        return;
    }

    public static void bfs(Map<Integer, PriorityQueue<Integer>> map, int start){
        Queue<Integer> que = new ArrayDeque<>();
        que.add(start);
        visited[start]=true;
        while (!que.isEmpty()){
            int cur = que.poll();
            sb.append(cur+" ");
            if(map.get(cur)==null){
                continue;
            }
            PriorityQueue<Integer> pq = map.get(cur);
            while(!pq.isEmpty()){
                int v = pq.poll();
                if(!visited[v]){
                    visited[v]=true;
                    que.add(v);
                }
            }
        }
    }
}

함수별로 살펴보자

✍ 부분 코드 설명

Main 함수 - 입력 & 변수 초기화

public class Main{
    static boolean[] visited;
    static StringBuilder sb;
    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 e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        visited = new boolean[n+1];
        sb  = new StringBuilder();

        while (e -- >0){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            PriorityQueue<Integer> list = map.getOrDefault(a, new PriorityQueue<>());
            list.add(b);
            map.put(a,list);

            list = map.getOrDefault(b, new PriorityQueue<>());
            list.add(a);
            map.put(b,list);
        }

        dfs(map, start);
        sb.append("\n");
        visited = new boolean[n+1];
        bfs(map,start);

        System.out.println(sb.toString());
    }

...

• n: 정점 개수
• e: 간선 개수
• start: 탐색 시작 위치
• map: 정점간 연결을 담는 map (key: 정점 value: 정점과 연결된 다른 정점 list)
• visited: 정점의 방문 여부 확인

그 간선 수만큼 연결 관계를 입력 받잖아요? 그런데 양방향 연결이니까, 들어오는 두 개의 정점이 서로의 key, value 둘 다 해조야 합니다.

value 리스트로 우선순위 큐를 쓴 이유는 문제에서 정점 번호가 작은 순서대로 방문하라고 했기에 써줬구요. ArrayList로 했다가, 하나 하나 다시 정렬하자니 머리 아프더라구요

그렇게 입력을 받고난 후 dfs, bfs 함수를 호출합니다.

dfs 함수

  public static void dfs(Map<Integer, PriorityQueue<Integer>> map, int current){
        visited[current]=true;
        sb.append(current+" ");
        if(map.get(current) == null){
            return;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(map.get(current));
        while(!pq.isEmpty()){
            int v = pq.poll();
            if(!visited[v]){
                dfs(map, v);
            }
        }
        return;
    }

bfs와 다른 점이 있다면, 재귀 호출 로 이루어진다는 점? 왜냐 우린 깊이 깊이 들어가야 하니까..

1. 우선 current로 들어온 현재 정점을 방문 처리 하고 시작한다.
2. 만일, current 정점과 연결된 다른 정점이 없는 경우 return
3. 현재 정점과 연결된 다른 정점들을 pq에 저장
4. pq에서 하나씩 빼서 방문하지 않은 노드가 있다면, 해당 노드를 current 로 dfs 호출
5. 위 과정 반복

bfs 함수

    public static void bfs(Map<Integer, PriorityQueue<Integer>> map, int start){
        Queue<Integer> que = new ArrayDeque<>();
        que.add(start);
        visited[start]=true;
        while (!que.isEmpty()){
            int cur = que.poll();
            sb.append(cur+" ");
            if(map.get(cur)==null){
                continue;
            }
            PriorityQueue<Integer> pq = map.get(cur);
            while(!pq.isEmpty()){
                int v = pq.poll();
                if(!visited[v]){
                    visited[v]=true;
                    que.add(v);
                }
            }
        }
    }

bfs는 선입선출 의 특징을 가진 큐를 가지고 구현합니다.

1. que 선언 및, start 정점 삽입
2. start 정점을 방문 처리
3. que에서 앞에 있는 정점 빼내어 cur 변수에 저장
4. 만일 cur 정점과 연결된 다른 정점이 없는 경우, que에서 다른 정점 빼내기
5. 연결된 정점이 있는 경우, 연결된 모든 정점을 que에 삽입 및 방문 처리
6. que가 빌 때까지 위 과정 반복

기억해야 할 점은 que에 넣으면서 방문 처리까지 해주는 거? 중복 삽입이 될 수 있기에..

ex) 1 - 2 ,4 2 - 3, 4

이렇게 연결 돼 있다고 하면 1번 정점에서 4번 정점이 이미 연결돼 방문할 예정이므로 2번 정점에선 4번 정점을 무시해야합니다~

✨ 결과

까먹어서 나에게 실망했지만,, 그만큼 중요한 개념이기때문에, 또 공부해서 리마인드 했으니 오히려 좋다. 그 나중에 응용 문제 많이 나오니까 또 까먹지 말자~

모든 자연수는 4개 이하의 제곱수의 합으로 표현 가능. 어떤 자연수는 해당 제곱수의 합이 여러개일 수도 있다.

• 어떤 자연수가 주어질 때, 표현되는 제곱수가 가장 적은 개수 찾아라.

  ex) N = 26 5²+1² : 2개 4²+3²+1²: 3개 답: 2개

생각하기

틀렸어요. 답 봤구요..

처음엔 그리디인줄 알고 풀었는데 그리디가 아니었다. 내가 접근한 방식을 잠깐 설명하자면,

1. 처음 주어지는 자연수(이하 n)의 제곱근(이하 sqrt) 찾기 (소수점 내림).
2. n에서 sqrt² 뺀 값을 n에 저장. (n = n-sqrt²)

n이 0이 될 때까지 위 과정을 반복.

이렇게 풀고 제출했는데, 46%에서 틀렸다. 반례는 27532 자연수가 들어왔을 때 나왔다.

답은 27532 = 26²+ 66² + 150²로 3개가 나와야 한다. 나의 로직은 아래와 같은 계산 과정으로 제곱수 개수를 구한다.

|계산 과정|계산 결과|| |---|---| |√27532| = 165.92...| |27532 - 165²| = 307| |√307| = 17.52..| |307 -17²| = 18| |√18| = 4.24...| |18 - 4²| = 2| |2| = 1²+1²| 27532 = 1²+1²+4²+17²+165² 로 가장 작은 개수도 아닐 뿐더러 4개를 초과한다. ㅋㅋ 그래서 가장 큰 값만 취하는 그리디 방식이 답이 아님을 알게 됐다...

그리디만 철썩 같이 믿었는데.. ㅜ 아무튼 다른 분들의 풀이를 봤다.

접근 방식

브루트 포스로 풀 수도 있고, dp로 풀 수 있다고 한다. dp가 훨씬 효율적이기에 dp 풀이를 참고했다.

앞서 말했듯 n은 √n 이하의 제곱수들의 합으로 구성이 된다.

n이 4인 경우를 예로들자.

• 1²+1²+1²+1²
• 2²

위 처럼 표현이 가능한데, 우리는 2²을 취해야 한다. 그런데,1²+1²+1²+1²은 3의 제곱수합에서 1²을 더한 값이다.

그러면 1부터 x²<=n일 때까지 x를 증가해 나가면서 가장 적은 개수를 저장하면 되나? 라고 생각할 수 있는데, 처음 보면 뭔 소리인지 싶다.

dp 배열에 해당 자연수에 대한 최소 값들이 저장돼 있다고 가정해 보자. n=4, idx = 4-1² => dp[3] idx = 4-2² => dp[0]

dp[3]과 dp[0]중 가장 적은 친구를 취해서 +1 하면, 그게 4를 만들 수 있는 가장 적은 개수라는 말이다.

3을 만들 수 있는 최소 제곱수 개수는 3개이고(1²+1²+1²), 0을 만들 수 있는 최소 제곱수는 0개이므로 우리는 0을 택한다. 그렇게 하면 dp[4]=1이므로 옳게 나온다.

16을 예로 들면, 아래 경우 중 최소 값을 취하여 저장한다.

16-1² = 15. (dp[15])+1개 16-2² = 12 (dp[12])+1개 16-3² = 7 (dp[7])+1개 16-4² = 0 (dp[0])+1개

이해가 됐으면 좋겠다ㅠ

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public 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[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                min = Math.min(min,dp[i-j*j]);
            }
            dp[i] = min+1;
        }
        System.out.println(dp[n]);
    }
}

1. 최소 개수를 저장하는 dp 배열을 선언 & 초기화
2. dp[0]과 dp[1]에는 값 미리 저장
3. 최소 개수 저장
   • i는 2부터 n까지
   • j는 1부터 j*j <= i 까지 반복.
   • 제일 적은 개수를 min에 저장
   • 최종적으로 찾은 min에 1을 더한 값을 dp[i]에 저장
4. dp[n] 출력

✨ 결과

진짜 알다가도 모를.. 아니 그냥 모르는 dp... 해당 문제 북마크 해두고 한 달 뒤에나 한 번 더 풀어봐야겠다. 이번 문제 설명하기 넘 어려웠다. 하지만 최선은 다했다 ㅎ

• 문제는 위에서 자세히 설명했으므로 설명은 패스
• 그 정사각형인데, 숫자가 같아야 해요.

생각하기

예전에 풀었던 문제~ 그래두 확실히 하기 위해서 끄적거렸음

물구나무 서서도 재귀 문제라 쉽게 풀리겠지 생각했지만 내가 물구나무에 소질이 없어서 1시간 걸렸다.

접근 방식

먼저, 순회를 시작하기 전에 맨 처음 원소를 flag 변수로 잡고 시작 순회 하다가 flag랑 다른 애 나오면, 4분할을 해야 하잖아요?

위 처럼 길이가 4인 정사각형이 주어져있다고 했을 때, 현재 flag (1)과 다른 0을 만나면 우측 그림처럼 4분할해서 4번의 재탐색이 필요함.

4분할의 기점인 위치를 살펴보면,

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N_2630 {
    private static int res[];
    public static void recur(int [][] map,  int row, int col, int len){
        int flag =  map[row][col];
        if(len == 1){
            res[flag]++;
            return;
        }
        for(int i=row; i<row+len;i++){
            for(int j=col;j<col+len;j++){
                if(flag != map[i][j]){
                    int half = len/2;
                    recur(map, row,col, half);
                    recur(map, row,col+half, half);
                    recur(map, row+half,col, half);
                    recur(map, row+half,col+half, half);
                    return;
                }
            }
        }
        res[flag]++;
        return;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [][] map  = new int[n][n];
        res = new int[2];
        for(int i=0;i<map.length;i++){
            StringTokenizer st  = new StringTokenizer(br.readLine());
            for(int j=0;j<map[0].length;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(map, 0,0,n);
        System.out.println(res[0]+" "+res[1]);
    }
}

하나씩 살펴봅시다.

✍ 부분 코드 설명

입력

public class N_2630 {
    private static int res[];

    ...

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [][] map  = new int[n][n];
        res = new int[2];
        for(int i=0;i<map.length;i++){
            StringTokenizer st  = new StringTokenizer(br.readLine());
            for(int j=0;j<map[0].length;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(map, 0,0,n);
        System.out.println(res[0]+" "+res[1]);
    }
}

• n: 초기에 주어지는 종이 크기
• map: 배열 저장
• res: 색종이 개수 저장

2차원 배열인 map에 입력으로 주어지는 초기 색종이 값 저장 recur 함수를 호출하여 탐색

recur 함수

 public class N_2630 {
    private static int res[];
    public static void recur(int [][] map,  int row, int col, int len){
        int flag =  map[row][col];
        if(len == 1){
            res[flag]++;
            return;
        }
        for(int i=row; i<row+len;i++){
            for(int j=col;j<col+len;j++){
                if(flag != map[i][j]){
                    int half = len/2;
                    recur(map, row,col, half);
                    recur(map, row,col+half, half);
                    recur(map, row+half,col, half);
                    recur(map, row+half,col+half, half);
                    return;
                }
            }
        }
        res[flag]++;
        return;
    }

    ...

recur 함수는 row, col 매개변수에 현재 종이의 flag가 될 시작점을 받고, len에는 현재 종이의 길이를 받음

만일 len이 1인 경우에는 한 칸만 탐색하면 되기때문에, res 배열의 flag 위치의 값을 1을 증가.

그 외의 경우 배열을 순회하며 flag와 다른 값을 마추진 경우 4분할을 다시 시작합니다.

여기서 row, col 값을 넘겨줄 때, 현재 인덱스 (i,j) 를 넘겨주는 실수를 했는데, 그렇게 넘겨주면 내가 원하는 곳이 아닌 엉뚱한 곳을 시작점으로 4분할 하게 되므로.. 꼭 row, col을 넘겨줘야한다.

넘 당연한 소리 같지만, 나는 이게 발목을 좀 잡았다.

나는 이 코드의 핵심이 return이라고 생각한다.

왜냐하면 처음에 return이 아닌 break를 썼다가 색종이 개수가 280개인가 웃기지도 않은 숫자가 나왔다.

이중반복문이기 때문에, break를 써도 상위 반복문(현재 i)은 그대로 진행이 돼서 우리가 앞전에 4분할해서 탐색한 부분을 중복 탐색 하기 때문이다.

우리는 한 번 안 맞으면 더 안 볼 거잖아요? 그러려면 함수를 탈출하는 return을 작성해줘야 원하는 로직으로 프로그램이 동작합니다.

궁금하면, 디버깅 해보면 됨

✨ 결과

해빈이 문제에서 조합이 나의 약점이라고 했는데 조합은 재귀를 활용한 문제라서 정확히는 재귀가 나의 약점이다.

이번 문제와 비슷한 문제를 3~4번 정도 풀었었는데, 1시간이나 걸리면 안됐다. 조금 더 생각하고 풀어서 돌아가는 일이 없도록 해야겠다.

그래도 풀었죠? ㅎ

• 세로 길이가 2로 고정된 타일에 가로 길이 n이 주어지면, 2x1 (이하 세로 타일), 1x2 (이하 가로 타일) 타일로 채우는 방법의 수 구하기.

예전에 얘랑 씨름하다가 결국 답 봤던 것 같은데 마법처럼 어떻게 풀었는지 기억이 안 나서 새마음 새출발했다.

생각하기

규칙을 찾기 위해 끄적인 노트를 가져왔다..

파블로프의 개처럼 경우의수 = dp 라고 떠올리게 돼서 냅다 규칙을 찾았다. 규칙이 보일랑 말랑하지만 딱 떨어지지 않아서 예제를 쳐다봤는데 익숙한 숫자 55가 보였다. 맞다. 이 숫자는 _피보나치 수열에서 10번째로 오는 수_다.

그래서 피보나치로 풀었음.

그치만, 예제를 보고 힌트를 얻어서 풀었기에 이렇게 넘어가면 안 된다.

접근 방식

n이 3인 경우, (2x3)타일링을 하는 경우의 수는 위 그림에 나와있다. 자세히 보니 2x2 타일링에서 세로타일을 오른쪽에 붙이고, 2x1 타일링에서 가로 타일을 갖다 붙인 모양새다.

그렇다면, 가로 길이가 n인 타일링의 방법의 수 = n-1 타일링 방법 + n-2 타일링 방법임을 알 수 있겠다.

나는 처음 규칙을 찾을 때 n-2 타일링 방법을 이용하는 게 어려웠다. 왜냐하면 n-2타일링에서 세로타일 2개를 붙여서 n 타일링을 만들 수 있는데, 그렇게 하면 n-1 타일링에서 세로타일을 붙인 경우와 중복되는 부분이 있었기 때문이다.

다시 생각해 보니, n-2에서 세로타일을 붙인 경우는 n-1에서 세로타일을 붙인 경우에 모두 존재하기 때문에 신경쓸 필요가 없겠다.

세로 지옥에서 빨리 벗어났다면 피보나치 힌트를 보지 않고 풀 수 있지 않았을까 싶다.

🍳 전체 소스 코드

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class N_11726 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int [] dp = new int[n+2];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-2]%10007+dp[i-1]%10007;
        }
        System.out.println(dp[n]);
    }
}

장황한 설명에 비해 코드는 간결하다. 피보나치 수열을 n번째까지 dp 배열에 저장하고, n번째 수를 반환하면 된다.

문제에서 10,007로 나눈 나머지 값을 반환하라 했으므로 계산을 하면서 적용한다.

✨ 결과

생각보다 빨리, 생각보다 쉽게 풀었다. 성장했나부다.. 항상 dp에게 떨면서 눈물만 흘리던 내가 아니야 흥

• 해빈이가 옷 하나만 걸쳐도 되니까 나체만 아닌 모든 경우의 수
• 종류별로 한 개만 입을 수 있음 ex) 모자 두 개 안 됨

생각하기

내가 제일 약한 분류인 조합 문제이다. 그런데 걸치는 옷의 조합을 나열하는 게 아닌 단지 경우의 수만 구하는 거라서 수학으로 풀 수 있지 않을까 싶었다. (재귀 짜다가 번뜩 생각남) 하지만, 기껏 짜놓은 재귀가 아깝기도 했고.. 시간도 많이 지나서 그냥 제출하고 25%에서 실패해서 답 봤다.

풀이 방법은 결국 수학이지롱

접근 방식

headgear - hat, turban eyewear - sunglasses

위와 같이 예제가 주어졌지만, 문제에서는 해빈이가 나체만 아니면 된다고 했다. 즉, 우리는 아래와 같이 _아무것도 안 입는 선택지_도 분류에 넣어주고 경우의 수를 구해야 한다.

headgear - hat, turban,NONE eyewear - sunglasses, NONE

그러면, 우리가 구할 수 있는 경우의 수는 headgear 종류에서 1개 * eyewear 종류에서 1개 = ₃C₁X ₂C₁ = 3 X 2 = 6

이때, 두 종류 모두 NONE을 고르는 경우가 포함돼 있으므로 결과값에서 1을 빼주면 답이 된다.

🍳 전체 소스 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());

        while(tc-- >0){
            Map<String, Integer> map = new HashMap<>();
            int count  = Integer.parseInt(br.readLine());
            while(count -- >0){
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                String sort = st.nextToken();
                map.put(sort, map.getOrDefault(sort,1)+1);
            }
            long result = 1;
            for(String key: map.keySet()){
                result*=map.get(key);
            }
            result-=1;
            bw.write(result+"\n");
        }
        bw.flush();
        bw.close();
    }
}

✍ 부분 코드 설명

입력

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());

        while(tc-- >0){
            Map<String, Integer> map = new HashMap<>();
            int count  = Integer.parseInt(br.readLine());
             while(count -- >0){
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                String sort = st.nextToken();
                map.put(sort, map.getOrDefault(sort,1)+1);
            }
        ...

• Map: key에는 옷의 종류, value에는 해당 종류의 옷 개수를 넣어준다.

경우의 수 구하기

     long result = 1;
            for(String key: map.keySet()){
                result*=map.get(key);
            }
            result-=1;
            bw.write(result+"\n");
        }
        bw.flush();
        bw.close();
    }
}

• map을 순회 하면서 구한 경우의 수를 result 변수에 삽입한다.
• 나체인 경우의 수가 포함돼 있으니 result에서 1을 제한다.

✨ 결과

조합만 나오면 벌벌 떤다. 이번 문제는 나열하는 게 아니기 때문에 수학적으로 접근하여 푸는 거였지만 나열하라는 문제가 나오는 걸 대비해서 외우든가 알아도야겠다.

📖 참고

Stranger's LAB - [백준] 9375번 : 패션왕 신해빈

• 양방향 연결된 네트워크 쌍이 주어짐
• 1번 컴퓨터를 시작으로 바이러스에 감염된 컴퓨터 개수 찾기

생각하기

Map을 이용해서 풀면 되겠다고 문제 보고 생각이 들었다. key에는 컴퓨터 번호, value 값으로 연결된 컴퓨터 list를 넣으면 되고.. key값에 있는 친구들 빼면서 개수 세면 되겠지? 했지만 5%에서 걍 틀리기

양방향인 거 알면서 양방향으로 구현하지 않은 내 잘못이다. 1 2 이렇게 들어오면, 1->2, 2->1 모두 구현해 주고 풀어야한다.

🍳 전체 소스 코드

package DFS_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class N_2606 {
    public static void insert(Map<Integer, List<Integer>> map, int s, int e){
        if(!map.containsKey(s)){
            map.put(s, new ArrayList<>());
        }
        if(!map.containsKey(e)) {
            map.put(e, new ArrayList<>());
        }
            map.get(s).add(e);
            map.get(e).add(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int con = Integer.parseInt(br.readLine());
        boolean [] visited = new boolean[n+1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        while (con > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            insert(map,s,e);
            con--;
        }
        int virus = 0;
        Queue<Integer> que = new ArrayDeque<>();
        que.add(1);
        visited[1]=true;
        while(!que.isEmpty()){
            int key = que.poll();
            if(!map.containsKey(key)){continue;}
            for(int i: map.get(key)){
                if(visited[i]){
                    continue;
                }
                visited[i] = true;
                que.add(i);
                virus++;
            }
        }
        System.out.println(virus);
    }
}

✍ 부분 코드 설명

입력

 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int con = Integer.parseInt(br.readLine());
        boolean [] visited = new boolean[n+1];
        Map<Integer, List<Integer>> map = new HashMap<>();

        while (con > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            insert(map,s,e);
            con--;
        }
        ...

• n : 전체 컴퓨터 수
• con: 네트워크 쌍
• visited: 컴퓨터 방문 처리 배열
• Map: 네트워크 쌍 저장

insert 함수

public static void insert(Map<Integer, List<Integer>> map, int s, int e){
        if(!map.containsKey(s)){
            map.put(s, new ArrayList<>());
        }
        if(!map.containsKey(e)) {
            map.put(e, new ArrayList<>());
        }
            map.get(s).add(e);
            map.get(e).add(s);
    }

• 매개변수 s 와 e로 들어온 컴퓨터 둘 다 key, value 값으로 하여 map에 저장한다.

** virus 카운트**

    ...    
     int virus = 0;
    Queue<Integer> que = new ArrayDeque<>();
    que.add(1);
    visited[1]=true;
    while(!que.isEmpty()){
        int key = que.poll();
        if(!map.containsKey(key)){
            continue;
        }
        for(int i: map.get(key)){
               if(visited[i]){
                continue;
            }
            visited[i] = true;
            que.add(i);
            virus++;
        }
    }
    System.out.println(virus);
}

• que: 다음 key 값이 될 컴퓨터 (바이러스 감염됨)

문제에서 1번 컴퓨터가 숙주 컴퓨터라고 했으니, que에 1을 넣고 방문처리를 해주면서 시작한다.

map에 현재 1번에 들어있는 list를 순회한다. 해당 컴퓨터를 이미 방문한 경우는 건너뛰고, 그렇지 않은 경우 que에 삽입 & 방문처리 한다. virus 변수를 1씩 증가한다.

que에 남아 있는 원소가 없을 때까지 반복하고, virus를 반환하며 종료한다.

✨ 결과

양방향인 걸 알았는데 양방향으로 구현을 안 해서 오래 걸렸다. 그냥 쉽게 갈걸... .. 그래도 풀어서 기분 조타

배열 내의 3개의 원소를 더한 값이 0이 되는 모든 경우의 수 찾기 -> 중복 경우의 수는 제외~

생각하기

배열을 정렬하고, 양수와 음수를 나눠서 풀어야 한다고 생각했다. 그래서 이진탐색으로 양수와 음수 경계의 인덱스를 먼저 찾고, List<Integer> plus List<Integer> minus에 양수, 음수 원소들을 저장했다.

합이 0이 되는 경우

• 양수 2개+음수 1개 = 0
• 음수 2개 + 양수 1개 = 0
• 양수 1개 + 음수 1개 + 0 = 0 (배열에 0이 존재 하는 경우,)

같이 3가지 경우 중 하나라도 만족하면 답이 된다.

막상 나누고 보니, 위 세 조건을 구현하는 게 막막했다. 30분 동안 씨름 후 답을 봤다.

결론부터 말하자면,

숫자 1개를 고정하고, 남은 원소들을 투 포인터를 사용해 접근하는 방식이었다.

🍳 전체 소스 코드

class Solution {

   public static int findIdx(int[] nums){
        int start = 0;
        int end = nums.length-1;
        while(start<=end){
            int half = (start+end)/2;
            if(nums[half]==0){ return half;}
            else if(nums[half]<0){
                start =  half+1;
            }
            else{
                end = half-1;
            }
        }
        return start;
    }
    public List<List<Integer>> threeSum(int[] nums) {

           Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        if(nums[0]>0 || nums[nums.length-1]<0){
            return res;
        } 

        int lastIdx = findIdx(nums);
        if(lastIdx <0) lastIdx++;
        for(int i=0;i<=lastIdx;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int j = i+1;
            int k = nums.length-1;
            while(j<k){
                int total  = nums[i]+nums[j]+nums[k];
                if(total<0){
                    j++;
                }else if( total>0){
                    k--;
                }else{
                    res.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    while(nums[j]==nums[j-1] && j<k){
                        j++;
                    }
                }
            }
        }
        return res;
    }
}

✍ 부분 코드 설명

1. 변수 선언

   public List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        if(nums[0]>0 || nums[nums.length-1]<0){
            return res;
        } 

        int lastIdx = findIdx(nums);
        if(lastIdx <0) lastIdx++;

        ...

• res: 경우의 수를 저장하는 리스트
• lastIdx: 첫 양수 인덱스 저장 변수

1. nums 배열 정렬
2. 반환할 res 변수 선언
3. 만일 배열 내에 음수 혹은 양수가 없다면 답이 존재할 수 없으므로 종료
4. findIdx 함수를 호출 하여, 첫 양수 인덱스를 구한다.

2. findIdx 함수

  public static int findIdx(int[] nums){
        int start = 0;
        int end = nums.length-1;
        while(start<=end){
            int half = (start+end)/2;
            if(nums[half]==0){ return half;}
            else if(nums[half]<0){
                start =  half+1;
            }
            else{
                end = half-1;
            }
        }
        return start;
    }

이진 탐색을 이용하여 양수 시작점 찾기. (0인 경우 0 인덱스 반환)

3. 변수 선언

    ...
for(int i=0;i<=lastIdx;i++){
    if(i>0 && nums[i]==nums[i-1]){
        continue;
    }
    int j = i+1;
    int k = nums.length-1;
    while(j<k){
        int total  = nums[i]+nums[j]+nums[k];
        if(total<0){
            j++;
        }
        else if(total>0){
            k--;
        }
        else{
            res.add(Arrays.asList(nums[i],nums[j],nums[k]));
            j++;
            while(nums[j]==nums[j-1] && j<k){
                j++;
            }    // while
        }    // else
    }    // while
}    // for
    return res;
} // threeSum

• i: 고정수의 인덱스.
• j: i+1 ~ k까지
• k: 배열의 끝 ~ j까지

중복된 경우를 허용하지 않았으므로, 중복값이 있다면 진행하지 않고 다음 원소로 넘어간다.

끗!

✨ 결과

세 원소를 가지고 풀어야 하는 문제를 또 마주치게 된다면 이 접근법을 사용해야겠다. 넘 어려워 보였지만,, 풀고 정리까지 하니 좀 친해졌다.

에러 1

The last packet sent successfully to the server was 0 milliseconds ago. The driver has not received any packets from the server.

패킷 보냈는데 driver가 서버로 부터 아무 패킷도 못 받았다고 함. 있었는데 없어졌어요

구글링 해서 mysql 설정을 바꿔주면 된다고 해서 바꿔줬지만 그래도 여전. mysqld.conf 설정 참고 게시글

에러 2

Failed to initialize JPA EntityManagerFactory: [PersistenceUnit: default] Unable to build Hibernate SessionFactory; nested exception is org.hibernate.exception.JDBCConnectionException: Unable to open JDBC Connection for DDL execution

그런데 이런 에러 로그도 있길래 바로 구글링 때려벌임

변경 전 spring.jpa.hibernate.ddl-auto=create 변경 후 spring.jpa.hibernate.hbm2ddl.auto=create

이래 변경하고 실행하면, 실행이 됨

에러 3

RDS와 제대로 연동이 됐는지 봐야하니까 정보 입력하고 회원가입 버튼 눌렀더니 하단의 에러 폭발

java.net.ConnectException: Connection timed out: no further information at java.base/sun.nio.ch.Net.pollConnect(Native Method) ~[na:na] at java.base/sun.nio.ch.Net.pollConnectNow(Net.java:672) ~[na:na] at java.base/sun.nio.ch.NioSocketImpl.timedFinishConnect(NioSocketImpl.java:549) ~[na:na]

스프링에서 데이터베이스 접근하여 접속을 기다리다가 뱉는 타임아웃 에러라고 한다.

에러 원인으로 spring.datasource.url이 RDS 엔드포인트로 되어있어서 그런가? 라는 생각이 들었다. 돈 내기 싫어서 퍼블릭 액세스 허용을 안 해뒀거든요..

저번 게시글에 ec2 -> rds 접속까지 했는데 springboot -> ec2 -> rds는 도당체 멀까.. 라고 생각하면서 오랜 친구인 gpt를 찾아갔다.

나: springboot에서 ec2를 통해 rds로 터널링 하고싶음, 근데 나 putty 써. gpt: [내가 전에 만든 putty ssh 터널 설정] (https://velog.io/@0woy_/EC2-%EC%83%9D%EC%84%B1-%EB%B0%8F-RDS-%EC%97%B0%EB%8F%99#3-putty%EB%A1%9C-ec2-%EC%84%9C%EB%B2%84-%EC%A0%91%EC%86%8D) 하고 나서 properties 설정 ㄱㄱ

datasource.url에서 rds 엔드포인트가 아닌 localhost라는 점!

에러 4

Access denied for user 'groot'@'localhost' (using password: YES) at com.mysql.cj.jdbc.exceptions.SQLError.createSQLException(SQLError.java:130) ~[mysql-connector-j-8.3.0.jar:8.3.0]

새로운 에러 발생.. 오히려 좋아. groot 사용자가 localhost 접근 권한이 없는듯

내 db 사용자에 groot는 있지만 host가 localhost는 아니라서 새로 맹글어줌

CREATE USER 'groot'@'localhost' IDENTIFIED BY 'password';
GRANT ALL PRIVILEGES ON *.* TO 'groot'@'localhost';
FLUSH PRIVILEGES;

비밀번호는 알아서..

그런데 문제가 생겼다. 이미 3306 포트로 로컬 db가 있는데, rds에 저장되는 게 아니라 이 로컬에 저장이 돼버리는 사태;;

그래서 putty 수정했어요.

기존에 있던 forwarded ports 지워주고, Source port를 3307로 바꿔서 다시 저장했다. 그리고 .properties 파일에 localhost:3306 -> localhost:3307로 포트 번호 같이 변경해 주었다.

실행했더니 이제 저장도 잘 된다. 더이상 에러가 발생하지도 않고.. 정말 행복하다.

이렇게 local 스프링에서 ec2이용해 rds로 접속까지 끗.. 이틀동안 삽질했다. 많은 일이 었었어..