fire_fly.log

두 코드의 시간 비교

Wed, 25 Oct 2023 01:06:55 GMT

 public int[] solution1(long n) {
        String str = n + "";
        int[] answer = new int[str.length()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = (int) (n % 10);
            if (n < 10) break;
            n /= 10;
        }

        return answer;
    }
public int[] solution2(long n) {
        return new StringBuilder().append(n).reverse().chars()
            .map(Character::getNumericValue).toArray();
}

solution2에서 더 빠른 시간으로 통과하는것을 볼 수 있는데, 막상 코드로 테스트를 해보면 solution1이 더 빠르다. 테스트를 잘못한것일까?

void solution1_solution2(){
      long number = 1234567890123456L;
      int iterations = 100000;
      long startTime1 = System.nanoTime();
      for (int i = 0; i < iterations; i++) {
          solution1(number);
      }
      long endTime1 = System.nanoTime();
      long startTime2 = System.nanoTime();
      for (int i = 0; i < iterations; i++) {
          solution2(number);
      }
      long endTime2 = System.nanoTime();

      System.out.println("Solution1 : " + (endTime1 - startTime1) + " nanoseconds");
      System.out.println("Solution2 : " + (endTime2 - startTime2) + " nanoseconds");

  }

코테 빠르게 준비하기 (실버 하위 수준)

Tue, 24 Oct 2023 05:40:07 GMT

각 자리의 숫자 빠르게 더하기

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;

        while(true){
            answer += (n%10);

            if(n<10) break;

            n /= 10;
        }

        return answer;
    }
}

숫자범위 조심

int 랑 long이 사칙연산 하게 되면 결과가 int로 되니, 조심하기

숫자 거꾸로 출력하기

자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 
예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다.
n은 10,000,000,000이하인 자연수입니다.

class Solution {
    public int[] solution(long n) {
        String str = n+"";
        int[] answer = new int[str.length()];
        for(int i=0;i


변환
    // Integer List -> int[]
    answer.stream().mapToInt(Integer::intValue).toArray();

    // 문자열 -> 정수
    Integer.parseInt(str)

    //모두 소문자로
    String toLower(String id){
        return id.toLowerCase();
    }

    //a~z, 0~9, . _ - 삭제
    String removeChar(String id){
         return id.replaceAll("[^a-z0-9\\._-]", "");
    }

    // 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
    String dotsToDot(String id){
        return id.replaceAll("\\.{2,}", ".");
    }

    //마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
    String removeDotsAtStartOrEnd(String input) {
        input = input.replaceAll("^\\.", "");
        return input.replaceAll("\\.$", "");
    }

    // 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
    // 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
    String only15Length(String input){
        if (input.length() >= 16) {
            input = input.substring(0, 15);
        }
        if (input.endsWith(".")) {
            input = input.substring(0, input.length() - 1);
        }
        return input;
    }

    // new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
    String addLast(String id){
        if(id.length()<=2){
            while(id.length()<3){
                id+=id.charAt(id.length() - 1);
            }
        }
        return id;
    }
정수주면 거꾸로된 정수출력하기 🍟
       String[] list = String.valueOf(n).split("");
        Arrays.sort(list);

        StringBuilder sb = new StringBuilder();
        for (String aList : list) sb.append(aList);

        return Long.parseLong(sb.reverse().toString());
map에 있는 value를 업데이트

map의 쌍의 value를 업데이트 하고 싶을때 이전것을 remove하지 않고 put(key, newValue) 만으로 가능하다

다시 풀어볼 문제
https://school.programmers.co.kr/learn/courses/30/lessons/133502



fetch join 에서 alias가 필요한 이유
Tue, 22 Aug 2023 05:25:42 GMT
서론
fetch join 시 alias를 사용해서 필터링하는게 왜 안되는걸까요?
보통 이에 대한 답변으로 디비상태와 객체상태의 일관성이 깨지게 됨을 보통 얘기합니다.
alias를 사용해서 필터링해버리면 실제 디비에 있는 데이터보다 적은 개수가 나오게 되니까요.
근데 어차피 그 필터링된 결과만을 결과로 리턴해주어야한다면
사용해도 괜찮을 것 같은데
디비상태와 객체상태의 일관성이 깨지는게 왜 문제가될까요?

유지관리 문제?
캐싱?

2차 캐시관련 버그
사실은 유지관리/캐싱 문제보단 2차 캐시와 관련되어 버그가 생길 수 있기 때문에 지양해야합니다.
예를들어서
team과 member가 일대다 연관이고
team을 select해온다는 sql이 있다고 가정합니다.
1. select * from team fetch join member where member.name = 'member1' //디비에 있는 일부 데이터 불러옴
2. select * from team fetch join member //디비에있는 모든 데이터 불러옴

하나의 트랜잭션에서 1의 sql을 호출한 뒤에 2를 호출하면
디비에 쿼리를 날려서 내용을 얻어오긴 하지만, 이미 team_id에 해당하는 객체가 영속성 컨텍스트에 존재해서 가져온 내용을 버립니다.
그래서 추후에 문제가생길 수 있습니다.
개발자는 모든 데이터를 불러올것이라고 생각했는데 필터링된 member를 가진 객체가 불러와지기 때문입니다.



백준 2146 다리만들기 자바
Fri, 18 Aug 2023 04:11:36 GMT

처음 이 문제를 그냥 BFS로 풀려고 하니 답이 안나왔다. 왜냐하면 대륙1, 대륙2, 대륙3은 서로 다른 대륙이기에 동시에 진행해버리면 서로 서로에게 가까워지면서 실제 시간보다 빠르게 나오기때문이다. 독립적인 실행이 가능하게 해야했다. 즉, 대륙1에서만 BFS를 진행하고 그다음엔 대륙2에서 BFS를 진행하는.. 식으로 해야했다
그런데.. 한대륙에서만 bfs를 진행한다고 하더라도 다른 좌표(r,c)에서의 bfs 진행 결과가 현재 좌표 (x,y)에 영향을 미치면 제대로 된 결과가 안나올 것 같았다.

문제상황
static int bfs(int r, int c,int cnt){
        int result=0;
        Queue q = new LinkedList<>();
        q.add(new Point(r,c));
        while(!q.isEmpty()){
            int size = q.size();
            while(size>0){
                Point cur = q.poll();
                visited[cur.r][cur.c] = true;

                for(int i=0;i<4;i++){
                    int rr = cur.r + dx[i];
                    int cc = cur.c + dy[i];
                    if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                    if(map[rr][cc]==0){
                        visited[rr][cc] = true;
                        q.add(new Point(rr,cc));
                    }else if(map[rr][cc] == cnt){
                        visited[rr][cc] = true;
                    }else{
                        return result;
                    }

                }

                size--;
            }
            result++;
        }
        return -1;

    }
  //main함수
   for(int i =0; i


메인함수내에서의 이중 포문은 내가 걱정했던 문제를 해결해준다
하나의 좌표에 대해 bfs를 수행하면서 다른 좌표에서 수행한 bfs 좌표랑 격리해주는것같다
bfs함수에서는 탐색이 다끝나면 -1을 return하는데 이 값을 처음에 return하도록 한 이유는 제대로 값을 못찾으면 값을 구분하기 위해서였다. 하지만 bfs가 여러번 실행되고, 하나의 케이스에서는 좌표가 내륙에 위치해서 더이상 탐색을 안할수도있다. 그럼 -1 이 return될거고 그럼 제대로 된 min값이 안나온다

정답코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int n;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int map[][];
    static boolean visited[][];
    static int bfs(int r, int c,int cnt){
        int result=0;
        visited = new boolean[n][n];
        Queue q = new LinkedList<>();
        q.add(new Point(r,c));
        while(!q.isEmpty()){
            int size = q.size();
            while(size>0){
                Point cur = q.poll();
                visited[cur.r][cur.c] = true;

                for(int i=0;i<4;i++){
                    int rr = cur.r + dx[i];
                    int cc = cur.c + dy[i];
                    if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                    if(map[rr][cc]==0){
                        visited[rr][cc] = true;
                        q.add(new Point(rr,cc));
                    }else if(map[rr][cc] == cnt){
                        visited[rr][cc] = true;
                    }else{
                        return result;
                    }

                }

                size--;
            }
            result++;
        }
        return Integer.MAX_VALUE;

    }
    //map에 있는 대륙의 개수를 count한다
    static int count(){
        temp = new boolean[n][n];
        int result = 0;
        for(int i=0;i=n||cc>=n||rr<0||cc<0||temp[rr][cc] ||map[rr][cc]==0) continue;
            dfs(rr,cc, k);
        }
    }
    static class Point{
        int r;
        int c;
        Point(int r, int c){
            this.r=r;
            this.c=c;
        }
    }
    static boolean temp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for(int i=0;i

메모리를 많이 사용하는 문제

정답으로 처리가 되긴했지만 다른 풀이에 비해 메모리를 많이 사용하고 있었다
추가적으로 방문배열을 하나 더 선언해서 내가 탐색한 대륙1에 대해 모두 방문처리를 해주는 식으로 코드를 짜면 메모리를 반절정도 덜 사용하게 된다

//main
 temp = new boolean[n][n];
        for(int i =0; i

static int bfs(int r, int c,int cnt){
        //한점에서만 bfs를 진행할거기때문에 visited배열을 매번 초기화 해주어야한다
        temp[r][c] = true;
        visited = new boolean[n][n];
        Queue q = new LinkedList<>();
        q.add(new Point(r,c,0));
        while(!q.isEmpty()){
            //size 만큼 반복해주는 행위 = class에 len이라는 필드추가하는것과 같음
            Point cur = q.poll();
            //1x1의 예외상황을 처리하기 위함
            visited[cur.r][cur.c] = true;

            for(int i=0;i<4;i++){
                int rr = cur.r + dx[i];
                int cc = cur.c + dy[i];
                if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                //방문안한 점인데 0이면 그쪽으로 탐색을 진행한다. 그러다가 다른 지역을 만나면 result(time) 을 반환한다
                if(map[rr][cc]==0){
                    visited[rr][cc] = true;
                    q.add(new Point(rr,cc,cur.t+1));
                    //map[rr][cc]가 0 도 아니고 cnt도 아니라면 다른 대륙이다
                    //time의 최소시간을 return해주자
                }else if(map[rr][cc] != cnt){
                    return cur.t;
                }else{
                   //추가 이거때문에 ..
                   temp[rr][cc] = true;
                }

            }
        }
        return Integer.MAX_VALUE;

    }



hash table 중간 value 삭제
Sun, 13 Aug 2023 03:13:41 GMT

hash table은 배열로 구현되어있을텐데 특정 중간 value를 어떻게 삭제하나요?
각각의 요소는 linkedlist로 연결되어있지않은데 어떻게 중간값을 삭제하는게 가능한지 궁금합니다


위와 같은 질문을 해결하기 위해 hash table의 삭제 코드를 들여다 봤다
public synchronized V remove(Object key) { // 키를 사용하여 값을 제거하는 함수
  Hashtable.Entry[] tab = this.table; // 테이블의 배열을 가져옴
  int hash = key.hashCode(); // 키의 해시 값을 계산함
  int index = (hash & 2147483647) % tab.length; // 계산한 해시 값을 사용하여 배열에서 위치(인덱스)를 찾음
  Hashtable.Entry e = tab[index]; // 찾은 인덱스에서 연결 리스트(링크드 리스트)를 가져옴

  for (Hashtable.Entry prev = null; e != null; e = e.next) { // 해당 연결 리스트를 순회함
      if (e.hash == hash && e.key.equals(key)) { // 만약 현재 요소의 키가 찾는 키와 같다면
          if (prev != null) { // 이전 요소가 있다면 (첫 번째 요소가 아닌 경우)
              prev.next = e.next; // 이전 요소가 현재 요소를 건너뛰고 다음 요소를 가리키게 함 (현재 요소를 리스트에서 제거)
          } else {
              tab[index] = e.next; // 첫 번째 요소를 제거하는 경우, 배열의 해당 인덱스를 다음 요소로 업데이트 함
          }

          // 값을 성공적으로 제거하였으므로, 변경 카운트와 요소 수를 업데이트하고, 제거된 값을 반환함
          ++this.modCount; 
          --this.count;
          V oldValue = e.value;
          e.value = null;
          return oldValue;
      }

      prev = e; // 다음 반복을 위해 이전 요소를 현재 요소로 업데이트함
  }

  return null; // 찾는 키가 없는 경우 null을 반환함
}




```

shift연산을 하는 과정이 없다
그리고 지금 삭제 연산을 하고 있는것은 같은 index에 해당하는 연결리스트를 순회해서 key와 일치하는 value를 찾고 있는 과정이다.
내가 궁금한것은 연결리스트에서의 값 삭제가 궁금한것이 아니라 table내의 각각의 요소는 배열로 처리되어있을것인데 그 각각의 요소를 삭제하는 과정이 궁금했다
코드를 살펴 본 결과 각각의 요소 자체를 삭제하는게 로직이 있는게 아니라 
각각의 요소는 연결 리스트를 참조하고 있고 해당 연결리스트에서 key와 일치하는 값을 delete하는 과정을 거치는 것 같다.




리플렉션이 언제 필요할까?
Tue, 08 Aug 2023 01:59:38 GMT
리플렉션이란?

힙 영역에 로드된 Class 타입의 객체를 통해, 원하는 클래스의 인스턴스를 생성할 수 있도록 지원하고, 인스턴스의 필드와 메소드를 접근 제어자와 상관 없이 사용할 수 있도록 지원하는 API
여기서 로드된 클래스라고 함은, JVM의 클래스 로더에서 클래스 파일에 대한 로딩을 완료한 후, 해당 클래스의 정보를 담은 Class 타입의 객체를 생성하여 메모리의 힙 영역에 저장해 둔 것을 의미한다.리플렉션 장단점

런타임 시점에서 클래스의 인스턴스를 생성한다
접근 제어자와 관계 없이 필드와 메소드에 접근하여 필요한 작업을 수행할 수 있는 유연성을 가지고 있다.
캡슐화 저해리플렉션을 언제 사용하는가?

가령 사용자가 덧셈을 입력하고 싶다고 하면 덧셈에 관한 class를 사용해야하고, 뺄셈이라고 명령어를 입력하면 뺄셈에 대한 class를 사용해야한다고 가정하자. 이를 일반적으로 구현하려면 if-else문을 사용해야한다. 하지만 리플렉션을 사용하면 다음과 같은 일이 가능하다String className = getUserInput(); 
Class clazz = Class.forName(className);
Object operation = clazz.newInstance();

즉, 리플렉션을 사용하면 사용자 입력이나 설정파일과 같이 런타임에야만 알 수 있는 정보를 가지고 인스턴스를 생성할 수 있습니다




코테 급하기 준비하기
Wed, 19 Jul 2023 09:39:48 GMT
bfs

목적: 큐사용해서 구현해보기
public static void BFS(int start){
      Queue q = new LinkedList<>();

      q.add(start);
      isVisited[start] = true;
      while(!q.isEmpty()){
          int x = q.poll();//이위치
          start = x;//이위치
          for(int i=1;i

dfs

stack사용해서 구현해보기
public static void dfs(int v){
      // 현재 노드 방문 처리
      visited[v] = true;
      // 방문 노드 출력
      System.out.print(v + "");

      // 인접 노드 탐색
      for (int i : graph[v]){
          // 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
          if (visited[i]==false){
              dfs(i);
          }
      }
  }
정렬

퀵정렬, 계수정렬 구현법 알아와오기

퀵정렬
private static void quickSort(int[] arr, int start, int end) {
  // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
  if (start >= end)
    return;

  // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
  int pivot = start;
  int lo = start + 1;
  int hi = end;

  // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
  // 서로 엇갈리게 될 경우 while문 종료
  while (lo <= hi) {
    while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
      lo++;
    while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
      hi--;
    if (lo > hi)                 // 엇갈리면 피벗과 교체
      swap(arr, hi, pivot);
    else
      swap(arr, lo, hi);             // 엇갈리지 않으면 lo, hi 값 교체 
    }

  // 엇갈렸을 경우, 
  // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
  quickSort(arr, start, hi - 1);
  quickSort(arr, hi + 1, end);

}


이진탐색

내가 구해야하는 최소값을 mid의 기준값으로 잡는다

대략 이런느낌의 코드가 나온다
      int l=1;
      int r=sum;
      int min = Integer.MAX_VALUE;
      while(l<=r){
          int mid = 500;
          int my = 0;
          int count = m;

          for(int i=0;i= mid){
                  count--;
                  my -= cost[i];
              }
              else my+=cost[i];
          }
          if(count>m){
              l = mid-1;
          }
          else r = mid+1;
      }
다익스트라

한노드~다른 모든 노드까지의 최소비용을 결정하는 알고리즘

전체적인 코드 흐름



node의 idx와 cost를 Node라는 class로 표현한다 그래서 graph라는 중첩 list에 저장을 해둔다

dist라는 배열을 만든다. 이때 출발지점만 0으로 setting하고 나머지는 inf로 설정

반복은 전체노드의 개수만큼 진행한다

현재 모든 거리 비용중 방문안한 노드고 가장최소 dist를 찾아서 idx를 찾는다.

해당 node를 방문처리한다

방문한 node의 인접노드들에 대해서 node dist값, 현재노드~인접노드값을 비교해서 더 작은 값으로 갱신한다
//1,2번처리되었다고 가정
for (int i = 0; i < V; i++) {
         //  현재 거리 비용 중 최소인 지점을 선택한다.
         // 해당 노드가 가지고 있는 현재 비용.
         int nodeValue = Integer.MAX_VALUE;
         // 해당 노드의 인덱스(번호).
         int nodeIdx = 0;
         // 인덱스 0은 생각하지 않기 때문에 0부터 반복을 진행한다.
         for (int j = 1; j < V + 1; j++) {
             // 해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다.
             if (!visited[j] && dist[j] < nodeValue) {
                 nodeValue = dist[j];
                 nodeIdx = j;
             }
         }
         // 최종 선택된 노드를 방문처리 한다.
         visited[nodeIdx] = true;

         // 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신한다.
         for (int j = 0; j < graph.get(nodeIdx).size(); j++) {
             // 인접 노드를 선택한다.
             Node adjNode = graph.get(nodeIdx).get(j);
             // 인접 노드가 현재 가지는 최소 비용과
             // 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신한다.
             if (dist[adjNode.idx] > dist[nodeIdx] + adjNode.cost) {
                 dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
             }
         }
     }



우선순위 큐 이용


node의 idx와 cost를 Node라는 class로 표현한다 그래서 graph라는 중첩 list에 저장을 해둔다

dist라는 배열을 만든다. 이때 출발지점만 0으로 setting하고 나머지는 inf로 설정

우선순위 큐를 사용하는데 시작점에 대한 노드를 추가하고 dist값도 0으로 초기화한다

큐에서 최소비용을 갖는 노드를 꺼낸다 근데 이때 해당 노드의 비용이 dist배열보다 크다면 고려할 필요가 없다(더작아져야 갱신할건데..그럴일이 발생하지않을테니 고려할 필요 없음)

큐에서 꺼낸 노드의 인접노드들을 방문해서 이웃노드의 거리가 현재 노드를 거쳐간게 더 빠르면 갱신된 내요을 큐에 넣는다
//1,2번 처리되었다고 가정
PriorityQueue q = new PriorityQueue((o1, o2) -> Integer.compare(o1.cost, o2.cost));
     // 시작 노드에서, 시작 노드로 가는 값이 초기에 가장 짧은 비용을 갖는 노드이다.
     // 즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것이다.
     q.offer(new Node(start, 0));
     // 해당 노드를 선택한 것이나 마찬가지 이므로, dist[start] = 0으로 갱신.
     dist[start] = 0;
     while (!q.isEmpty()) {
         Node curNode = q.poll();

         // 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
         // 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
         // 주의점 2 : 중복노드 방지1 : 만일, 이 코드를 생략한다면, 언급한 내용대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
         // 만일 그렇다면, 큐에 있는 모든 다음 노드에대하여 인접노드에 대한 탐색을 다시 진행하게 된다.
         // 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것 만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다.
         if (dist[curNode.idx] < curNode.cost) {
             continue;
         }
         for (int i = 0; i < graph.get(curNode.idx).size(); i++) {
             Node nxtNode = graph.get(curNode.idx).get(i);
             if (dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
                 dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
                 // 갱신된 경우에만 큐에 넣는다.
                 q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
             }
         }
벨만포드



다익스트라 음수가중치 버전

음수가중치로 인한 사이클이 발생시 알려줄 수 있음
// 정점의 수만큼 반복
      for (int i = 1; i <= N; ++i) {
          // 모든 간선을 돌면서
          for (int j = 0; j < edgeList.size(); ++j) {
              int from = edgeList.get(j).from;
              int to = edgeList.get(j).to;
              int cost = edgeList.get(j).cost;

              // from까지 갈수 없다면 갱신 x 
              if (dist[from] == INF) continue;

              // to까지 가는 비용보다 from까지 가는 비용 + from에서 to까지 가는 비용이 더 저렴하다면 갱신
              if (dist[to] > dist[from] + cost) {
                  // v번째 횟수에 갱신이 된다면 음의 사이클이 존재하기 때문에 최단 경로를 구할 수 없음.
                  if (i == N) {
                      System.out.println("음의 사이클 존재");
                      return;
                  }
                  dist[to] = dist[from] + cost;
              }
          }
      }
크루스칼
크루스칼 기본 문제

최소신장트리(MST)

그래프의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프로 사이클X
정점의 개수 n개면 간선의 개수 n-1개 가짐
하나의 그래프에 많은 신장 트리 존재


초기 상태로 정점은 서로 연결되어 있지 않다. 간선을 하나씩 추가하면서 MST를 만든다. 크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.

구현방법

간선은 가중치를 기준으로 오름차순 정렬한다.

간선을 하나씩 살핀다. 간선을 MST에 추가했을 때 MST에 사이클이 생기지 않으면 추가한다. 사이클이 생긴다면 다음 간선으로 넘어간다.
// 유니온 
public static void union(int[] parent, int x, int y) {
   x = find(parent, x);
   y = find(parent, y);

   if(x < y) parent[y] = x;
   else parent[x] = y;
}
// 파인드
public static int find(int[] parent, int x) {
   if(parent[x] == x) return x;
   else return find(parent, parent[x]);
}





public static void kruskal(int[][] graph, int[] parent) {
    int cost = 0;
    for(int i = 0; i < graph.length;i++) {
        if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
            cost += graph[i][2];
            union(parent, graph[i][0], graph[i][1]);
        }
    }
    System.out.println(cost);
}
### unionfind(디스조인트 셋)
- Union Find: 공통 원소가 없는 부분 집합을 효과적으로 표현하기 위한 자료구조를 표현할때 사용하는 알고리즘
- Disjoint Set: 위의 알고리즘으로 표현된 자료구조
- Union(a, b)
  - 합치기 ( a와 b가 속한 집합을 합친다 )
- Find ( a )
  - a가 속한 집합 번호를 찾는다
- parent[i]는 '부모 노드 번호'를 의미한다 ( 자신이 어떠한 부모에 포함되어있는지를 나타냄)
```java
    private void union(int a, int b, int[] parents) {
        int aParent = find(a, parents);
        int bParent = find(b, parents);

        if (aParent == bParent) return;
        parents[aParent] = bParent;
    }

    public static int find(int parent[], int node){
        if(node != parent[node]){
            parent[node]= find(parent, parent[node]);
        }
        return parent[node];
    }
플로이드워셜

모든 정점간의 최소비용을 계산하고 싶을때 사용for (int k = 0; k < N; k++) {
          for (int i = 0; i < N; i++) {
              for (int j = 0; j < N; j++) {
                  dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
              }
          }
      }
위상정렬

순서를 일부를 정해줬을때 전체순서를 정하는 알고리즘
가령 A->B라고 하자.
알고리즘순서


edgeCount라는 자기에게 화살표하는 (A)의 경우 COUNT값이 1이고 B는 아무도 화살표가 출발하지 않으니 0이다. 이점을 참고하여EdgeCount를 setting

edgeCount가 0인값을 q에 넣고 

큐에서 하나씩 빼서 인접노드들 검사한다. 그리고 그 인접노드의 edgecount를 제거하고 이때 edgecount가 0이됐으면 큐에 넣는다
     int[] edgeCount =new int[n+1];
     ArrayList> graph = new ArrayList<>();
     for(int i=0;i<=n;i++){
         graph.add(new ArrayList<>());
     }
     for(int i=0;i queue = new LinkedList<>();
     for(int i=1;i




참고
https://sskl660.tistory.com/59 (자세한 다익스트라)
https://sorjfkrh5078.tistory.com/30 (자세한 벨만포드)
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BCKruskal-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 (자세한 크루스칼)
https://st-lab.tistory.com/250 (자세한 퀵정렬)



LCS
Wed, 19 Jul 2023 07:09:10 GMT
LCS을 풀때 다음 점화식을 사용하는 이유
x[m]==y[n]
-> LCS[m][n] = LCS[m-1][n-1]+1
x[m]!=y[n]
-> Math.max(LCS[m-1][n], LCS[m][n-1])

x[m] == y[n]
X[m] 위치와 Y[n] 위치의 문자가 동일하면 두 시퀀스에서 공통 문자를 찾았다는 의미입니다.LCS[i-1][j-1] 테이블의 "이전 대각선 값"은 (m-1)번째 및 (n-1)번째 문자까지 두 시퀀스의 LCS 길이를 나타냅니다. m번째 및 n번째 위치에서 일치 항목을 찾았으므로 이 일치 항목을 (m-1)번째 및 (n-1)번째 위치까지 시퀀스의 LCS에 추가할 수 있습니다. 이것이 이전 대각선 값에 1을 더하는 이유입니다.


x[m] != y[n]
이경우 LCS[m][n]가 LCS에 포함될 수 없다. 그렇기때문에 왼쪽이나 오른쪽 문자열중 하나의 문자를 제거함으로써 얻는 LCS 길이 수중 가장 큰 값을 가져가서 자신의 값으로 삼는다. 



내식대로 설명해보기..
1) 둘이 같을땐 대각선 왼쪽에 있는애에다가 1을 더해
대각선왼쪽이 무엇을 의미하냐면 각 문자열에서 문자하나씩 제거한거야 지금 현재 위치에서 둘이 같으니까 이전문자열에서 하나를더하는거임 (나도먼말인지모르겠음 )
2. 둘이 같지않을땐 위아니면 왼족옆에있는 값중에서 큰값을 선택함
왜냐면 현재값은 lcs가 아니기때문에 이전값을 그대로 가져와야하는데 이전값은 문자열a에서 문자하나제거한거 or 문자열 b에서 문자하나제거한거
이기때문!



완전탐색
Wed, 15 Feb 2023 02:23:33 GMT
14620 꽃길
시도1
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    static int min = Integer.MAX_VALUE;
    static Point p;
    static int arr[][];
    static int n;
    static boolean isVisited[][];
    public static void solve(int i, int j){
        //들어온인자의 상하좌우에 대해서
        if(i+1 < n && j+1 < n && i-1 >=0 && j-1 >= 0){
            //꽃을 심을 수 있는곳이면 상,하,좌,우 탐색을 한다
            if(!isVisited[i][j] && !isVisited[i+1][j] && !isVisited[i][j+1] &&
                    !isVisited[i][j-1] && !isVisited[i-1][j]){
                //꽃을 심는다
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i-1][j] + arr[i][j-1];
                if(min >= temp){
                    min = temp;
                    p = new Point(i,j);
                }
            }

        }
    }
    public static void visit(){
        int r = p.x;
        int c = p.y;
        //방문했던곳의 상하좌우만 방문처리
        isVisited[r][c] = true;
        isVisited[r+1][c] = true;
        isVisited[r][c+1] = true;
        isVisited[r][c-1] = true;
        isVisited[r-1][c] = true;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        isVisited = new boolean[n][n];
        for(int i=0;i

가장최소값만을 찾는데.. 가장최솟값만을 찾는게 합이 최소인것을 보장해주지않을때도있을것같다
왜냐하면 가장최솟값을 visited처리해줌으로써 그다음 최솟값을 처리못할수도있기때문에 합이 최소인것을 찾기위해선 저코드말고 다르게 짜야할것같다.
15661
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static int arr[][];
    static int min = Integer.MAX_VALUE;
    static boolean isTeamA[];
    public static void solve(int depth, int idx){
        if(depth>=arr.length){
            //능력치 차이의 최소를 구한다
            int teamA=0;
            int teamB=0;
            boolean allTeamA = true;
            boolean allTeamB = true;
            for(int i=0;i


이코드는 if문 내부가 한번만 호출된다

2961
 public static void solve(int depth, int idx){
        if(idx ==n){
            if(!list.isEmpty()){
                int sSum=1;
                int dSum=0;
                for(Integer i: list){
                    sSum *= flavors[i].s;
                    dSum += flavors[i].d;
                }
                min = Math.min(min, Math.abs(sSum-dSum));
            }
            return;
        }
        //뒤에있는것을 무조건 선택하게함
        //중간에있는것만 선택하는것이 안됨
        //오름차순 + 뒤에 더 큰수가있으면 무조건출력 이런 로직임
        for(int i=idx;i




최단거리(2)
Sun, 05 Feb 2023 02:53:53 GMT
11657

distance범위주의

distance는 최대 몇인지를 잘 모르겠다.

최대가아니라 최솟값을 주의해야한다

음의사이클을 돌면서 distance가 계속해서 감소한다

간선이 최대 6000개 있을 경우에 한 노드는 그 간선6000개 때문에 6000번의 업데이트를 가지게 될 수있다. 그런데 -10000만큼 작아진다면
6000*-10000만큼 작아질것이고 이것을 매라운드(n-1)마다 반복하니까 
6000 * -10000 * (500-1)만큼 작아질수있기때문에 int가 아니라 long으로 선언해주어야한다
public static boolean Bellmanford(int start){
      distance[start] = 0;
      //v-1번만 반복을 한다. i번의 반복을 할때마다 1번의 간선만 거친경우, 2번의 간선만거친경우.. (가장먼거리의노드에겐)v-1번의 간선만 거친 경우에 대해서
      //distance를 도출해낸다 그렇기때문에 v-1번반복을 해야한다
      for(int i=0;i distance[node.s] +  node.cost){
                  distance[node.e] = distance[node.s] + node.cost;
              }
          }
      }

      //만약에 위의과정을 거쳐서 최단경로를 확정지었는데도 계쏙갱신이 되는곳이있다면
      //그 그래프는 음의 사이클을 가진다고볼수있다. 그렇기에 최단경로를 구할수없음을 표시해준다
      for (Node node:list){
          if(distance[node.s]!=INF && distance[node.e] > distance[node.s] +  node.cost){
              distance[node.e] = distance[node.s] + node.cost;
              return true;
          }
      }
      return false;
  }


22865


위사진에 있는 코드를 아래사진과같이 바꿔도 정답이 뜨는데 그 이유를 모르겠다

distance[p.to] -> p.cost  로바꿨다의문1

p.cost < distance[p.to]라면 distance[p.to]를 p.cost로 갱신해야하는거아닌가? 생각해보니 왜 갱신하는코드가 없을까?의문2

왜 코드를 바꿔도 정답이 뜨는걸까? 둘은 일치하지않을때도있는데말이다.
예를들면 큐에 집어너호 나서 distance가 업데이트된다면 cost와 distance의 값은 달라지게된다.

1719

https://lotuslee.tistory.com/99
a->b->c->d면
distance[a][b]=b;
distance[a][c] = distance[a][b],
distance[a][d] = distance[a][c]
이런식으로가면 결국 a-d, a-c, a-b에 모두 b가 저장됨




최단거리(1)
Wed, 01 Feb 2023 06:18:53 GMT
18352

한노드 -> 다른노드로 가는 최단경로 + 가중치 양수 -> 다익스트라11404

왜 숫자범위 적당히 크게 하면되는거지. 어느정도인지 내가 어떻게 알지?
어느정도까지 크게해야하는지 어떻게알지?
nm까지 max의 값은 커질 수 있다. 왜냐하면 a->b가 일렬로 나열되어있고, 100개이며 각각의 가중치가 1000000이면 nm만큼의 가중치가 될것이기때문이다.

11403

임의의 한 노드 -> 다른 노드에 대한 모든 경로니까 플로이드 워샬적용

13549 숨박꼭질

이 노드를 백트래킹으로 풀면 왜안되는건지 모르겠다 stackoverflow가 터지는군public static int solve(int t, int current){
      if(current<0 || current> 100000) return Integer.MAX_VALUE;
      if(current==k){
          return t;
      }
      int a = solve(t+1, current-1);
      int b = solve(t-1, current+1);
      int c = solve(t, current *2);
      return Math.min(Math.min(a,b),c);
  }


시도1

아래 코드가 무슨 문제가 있는지 찾아봐라import org.w3c.dom.Node;



import javax.management.ObjectName;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main{
    static int n;
    static int k;
    static boolean visited[];
    public static class Node implements Comparable{
        int t;
        int x;
        Node(int t, int x){
            this.t=t;
            this.x=x;
        }
    @Override
    public int compareTo(Node o) {
        return this.t-o.t;
    }
}
public static int solve(int s){
    PriorityQueue q = new PriorityQueue<>();
    q.add(new Node(0, s));
    visited[s]= true;
    while(!q.isEmpty()){
        Node node = q.poll();
        if(node.x == k) {
            return node.t;
        }
        add(q,node.x*2, node.t);
        add(q,node.x+1, node.t+1);
        add(q,node.x-1, node.t+1);

    }
    return -1;
}
public static void add(PriorityQueue q, int x, int t){
    if(x<0 || x>100000||visited[x]) return;
    visited[x] = true;
    q.add(new Node(t, x));
}
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String input[] = br.readLine().split(" ");
    n = Integer.parseInt(input[0]);
    visited = new boolean[100001];
    k = Integer.parseInt(input[1]);
    bw.write(solve(n)+"\n");
    bw.flush();
    bw.close();

}
}

## 문제1
- 구현의도는 이랬다. time을 기준으로 우선순위큐를 생성한다
- 그러면 time이 적은것부터 먼저 꺼내게 될것이고, 그러다보면 시간이 가장 적게 든 x의 좌표를 바로 꺼낼 수 있을것이다.
- 하지만 이 풀이법은 문제가 존재한다
1. q에 넣는 순간 q는 정렬되기때문에 visited코드를 add할때 넣어주면 안되고 poll할때 넣어주어야한다 < 이 부분이 이해가 안간다. 왜 add할때 넣어주는 점이 문제가 되는것이며, 그 문제를 poll할때 visited를 true로 지정해줌으로써 해결할 수 있는것인가?
- 하지만 visited의 위치를 바꿈으로서 정답이 떴다.
- 내가 add할때 방문처리를 했던이유는 poll할때방문처리를 하게 되면 poll하기전까지는 그 지점을 계속 중복해서 방문하게되기때문이다. 
어쨋든 큐에 넣게되는순간이라는 것은 그 좌표까지 왔다는얘기다. 방문처리를 해주는 이유도 계속 그 좌표에 중복방문하는것을 막기위한 것이다. 어차피 그 좌표까지 오면 그 뒤의 일은 똑같다 +1, -1, `*2` 세가지 경우를 q에 또 삽입할 것이다.

## 해결
-  5-10-9-18-17 을 생각해보자
반복이 1회 진행될때마가 5,6,7,...visited칸들은 모두 true가 될것이다.
방문처리 된 이후에 더적은 t를 가지는 node가 나타나서 해당 지점을 방문하려고했다
근데 이미 다른 경로에의해(더오래걸리는경로)방문처리가 되었다면?
-> 내가 큐에 넣는다. 그러면 우선순위큐에 의해 정렬이될것이다. 정렬이 되고 나서. 그 순서에 의해서 뽑힌 대로 방문처리를 해주어야지 오래걸리는 경로에 의해 방문처리가 되지않는다
- 큐에넣고 바로 visited를 하라는얘기가 아니다. 큐에 넣고 해당노드가 poll되는 시점이여야한다. 그래야 그 노드가 적절하게 호출되는 시점인거고. 그떄 방문처리를 해주어야한다
- (그 노드는 가장 t가 빠른 노드임 그래서 그 노드를 먼저 방문처리해줘도됨. 왜냐면 우리가 걱정하는것은 다른 더 오래걸리는경로에 의해 노드가 먼저 방문처리되는것을 걱정하는거기때문)
## 문제2
- visited의 위치를 바꾸고싶지않다면 어떻게 해야할까?
- 그 경우엔 우선순위 큐말고 그냥 큐를 쓰면된다!
- 그리고 add하는 순서에 신경을쓴다(t가 변하지 않는 `x*2`부터 add)
- `x*2`부분을 먼저 add한다고 하더라도, 다음 반복때 시간이 더 적게 드는 Node가 Queue의뒤쪽에 배치될것이다. 그러니까 이 풀이법은 min을 찾는다고 바로 return하면 안된다. 큐에 있는 내용을 다 뒤져보고, node.x == k인 node중. 가장 적은 t를 가지는 node를뽑아내는 코드가 필요하다.
```java
public static int solve(int s){
        PriorityQueue q = new PriorityQueue<>();
        q.add(new Node(0, s));
        visited[s]= true;
        int min = Integer.MAX_VALUE;
        while(!q.isEmpty()){
            Node node = q.poll();
            if(node.x == k) {
                min = Math.min(min, node.t);//Queue를쓰기때문에 가장먼저나오는애가 최솟값이라는보장이 없다.
            }
            add(q,node.x*2, node.t);//순서신경쓰기:얘부터
            add(q,node.x+1, node.t+1);
            add(q,node.x-1, node.t+1);

        }
        return min;
    }
    public static void add(PriorityQueue q, int x, int t){
        if(x<0 || x>100000||visited[x]) return;
        q.add(new Node(t, x));
        visited[x] = true;
    }
가중치가 존재하는 간선?

이문제가 왜 가중치가 존재하는 간선인거지?결론
import org.w3c.dom.Node;



import javax.management.ObjectName;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main{
    static int n;
    static int k;
    //방문여부 처리하는 변수 - 이 변수 없으면 같은 x(위치)가 몇백개가 q에 들어가서 메모리 초과남
    static boolean visited[];
    public static class Node implements Comparable{
        int t;
        int x;
        Node(int t, int x){
            this.t=t;
            this.x=x;
        }
    @Override
    public int compareTo(Node o) {
        return this.t-o.t;
    }
}
public static int solve(int s){
    //우선순위 큐 사용 - time기준으로 정렬을해서 poll해서 얻은 node의 위치가 k랑 같은경우, node.t를 반환해서
    //최단시간을 구할 수 있음
    PriorityQueue q = new PriorityQueue<>();
    q.add(new Node(0, s));
    visited[s]= true;
    while(!q.isEmpty()){
        Node node = q.poll();
        //꺼낸것을 방문처리해야한다. add함수에서 큐에 넣고 방문처리하면 안된다
        //그이유: 처음엔 add하자마자 방문처리를해야. 그 위치에 절대 다시 방문하는일없게할 수 있기때문이었음
        //근데. 그렇게하면안됨. 왜냐하면. 방문처리는 최단경로에 대해서만 방문처리를 해주어야하기때문임
        //최단경로가 아닌 경로상에서 방문처리가 되어버린다면. 최단경로를 구할 수 없게됨
        //그래서 일단 q에서 꺼낸다음에 방문처리를 하는것임
        //q에서 꺼낸값이라는건 지금. 현재 가장 t가 작은값인 노드라는 뜻이고. 그런 경우에 그 값은 최단경로상에 있을것이기때문에 방문처리를 해주어도된다
        //그냥 막 모든 인접값들에 대해 방문처리를 해버리면 그 노드가 최단경로상에도, 최단경로가 아닌경로상에도 존재해서 최단경로를 만들지못하게 막아버릴수도있기때문이이다
        visited[node.x] = true;
        if(node.x == k) {
            return node.t;
        }
        add(q,node.x*2, node.t);
        add(q,node.x+1, node.t+1);
        add(q,node.x-1, node.t+1);

    }
    return -1;
}
public static void add(PriorityQueue q, int x, int t){
    if(x<0 || x>100000||visited[x]) return;
    q.add(new Node(t, x));
}
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String input[] = br.readLine().split(" ");
    n = Integer.parseInt(input[0]);
    visited = new boolean[100001];
    k = Integer.parseInt(input[1]);
    bw.write(solve(n)+"\n");
    bw.flush();
    bw.close();

}
}
# 11265
- 모든 노드간의 최단경로를 구함 -> 플로이드 워샬
# 1753
## 시도1
- 다음 코드는 왜 안되는것일까?
```java
   public static void solve(){
        PriorityQueue q = new PriorityQueue<>();
        q.add(new Node(s, 0));
        distance[s] = 0;
        while(!q.isEmpty()){
            Node node = q.poll();
            isVisited[node.n] = true;
            for (Node neighbor:list[node.n]) {
                if(distance[neighbor.n]> distance[node.n] + neighbor.cost && !isVisited[node.n]){
                    distance[neighbor.n] = Math.min(distance[neighbor.n], distance[node.n] + neighbor.cost);
                    q.add(new Node(neighbor.n, distance[neighbor.n]));
                }

            }
        }
    }

방문처리를 poll을 하고 나서 해줘야하는것은 알겠다. (인접노드에 대해서 방문처리를 해버리고, 인접노드를 큐에 추가하는 if문에서 방문된건 건너뛰는 코드를 작성하면 인접노드에 대한 인접노드는 파악할 수 없어지기때문)

근데 그럼. 방문된것은 건너뛰는코드를 어디에다 작성해야하나? < 이걸 잘 모르겠음

나는 예제를 들어서 생각을 해봤음


일단 1을 방문함. 그럼 큐에 2,3,5가쌓임. 그리고 1을 방문처리함
그리고 235를 큐에 넣음. 그리고 2에 들어감. 2의 인접노드 1 3 4 을 모두 큐에 추가하기전, 방문 했던 1은 제외함 -> 즉, 인접노드를 추가하는 코드에서 방문한노드면 제외시키는 코드를 넣으면되겠다고 생각을하게됨. 근데 그게 오답이 떠서 왜그런가했더니 이웃노드.n이 아니라 node.n을 넣어서그런거였음
!isVisited[node.n] < 이부분

근데 그래도 궁금한점이있음. 내가 코드를 짠것은 이해감. 근데 


이렇게 구현해도 될수있다는게 막 와닿진 않음. 이 처리로 인해서 한번 방문한것은 다시 처리안되겠구나 정도만 알겠음 !
궁금증2

왜 distance[neighbor.n]> distance[node.n] + neighbor.cost 이 경우에 대해서만 큐에 이웃을 집어넣는것인지?

아래코드에 답을 적어놨다.
해결
public static void solve(){
      PriorityQueue q = new PriorityQueue<>();
      q.add(new Node(s, 0));
      distance[s] = 0;
      while(!q.isEmpty()){
          Node node = q.poll();
          //방문처리를 여기서 하는 이유: 인접노드에서 방문처리를 해버리면 인접노드의 인접노드를 방문할 수 없어짐
          isVisited[node.n] = true;
          for (Node neighbor:list[node.n]) {
              //distance[neighbor.n]> distance[node.n] + neighbor.cost  이 경우에만 큐에 집어넣는 이유는.
              //만약에 그 반대 상황이면 기존 노드관계에 대해 update할 사항이 전혀없다 하지만 이 경우엔
              // 1->2로가는 최단경로가 1로갱신됐기때문에 2를 거치는, 즉 2의 인접노드들에 대한 경로 업데이트도 필요하게 됐다는 애기다
              //만약 저조건없으면 메모리초과뜸
              if(distance[neighbor.n]> distance[node.n] + neighbor.cost && !isVisited[neighbor.n]){
                  distance[neighbor.n] = Math.min(distance[neighbor.n], distance[node.n] + neighbor.cost);
                  q.add(new Node(neighbor.n, distance[neighbor.n]));
              }

          }
      }
  }
다익스트라구현에 대한 의문



시작노드를 큐에 넣는다
큐에서 뺀 노드의 인접노드에 대해 조사한다.
그리고 거리를 최소로 갱신한다(자신의 이전 distance값, 시작노드의 distance+시작노드~해당노드의 거리) 둘중에 작은걸로 갱신한다
그리고 만약 갱신이 된다면 큐에 다시 넣는다 <- 왜 갱신이 된애들에대해서만 큐에 넣지? - 위에 적음

14938

한노드 - 다른모든노드들에 대한 최단경로를 구하면 될것같다import java.io.*;
import java.util.*;



public class Main{
    static int n;//발전소 수
    static int w;// 전선 수
    static float m;// 제한 길이
    static int item[];
    static final int MAX = 1000000000;
    static double arr[][];
    static Point plant[];
    static double distance[];
    static boolean isVisited[];
// 이 노드는 왜 필요한것인가?
// 시작노드~ i번노드사이의 최단경로에 대해 우선순위큐를 구현해야한다.
public static class Node implements Comparable{
    int n;//i번 발전소
    double distance;//s발전소에서 i번 발전소까지 걸리는 거리(일직선상의 거리가 아닌, 발전소를 거쳐서 나온 거리를 의미함)
    Node(int n, double distance){
        this.n=n;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        return (int)(this.distance - o.distance);
    }
}
//발전소의 위치를 기록하는 클래스
public static class Point{
    int x;
    int y;
    Point(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public static int solve(int s){
    PriorityQueue q = new PriorityQueue<>();
    q.add(new Node(s, 0));
    //시작노드->시작노드로 가는 최단경로는 0이다
    distance[s] = 0;
    while(!q.isEmpty()){
        Node node = q.poll();
        for(int i=1;i<=n;i++){
            //arr[i][node.n]!=MAX라는것은 이동가능하다는얘기. i번발전소-> node.n 발전소로 이동가능하다는 얘기
            //i의 기존최단경로 vs node.n을 거친 최단경로 중. node.n을 거친 최단경로가 더 작다면. 즉 distance에 대한 업데이트가 필요하담녀
            if(arr[i][node.n]!=MAX && distance[i] > distance[node.n]+arr[i][node.n]){
                distance[i] = distance[node.n]+arr[i][node.n];
                q.add(new Node(i, distance[i]));

            }
        }
    }
    return print(distance[n]);
}
public static int print(double a){
    return (int)(a*1000);
}
public static double getDistance(int s, int e){
    double a = Math.pow(plant[s].x - plant[e].x, 2);
    double b = Math.pow(plant[s].y - plant[e].y, 2);
    return Math.sqrt(a+b);
}
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String input[] = br.readLine().split(" ");
    n = Integer.parseInt(input[0]);//노드개수
    w = Integer.parseInt(input[1]);//전선수
    m = Float.parseFloat(br.readLine());//제한 길이
    arr = new double[n+1][n+1];
    plant = new Point[n+1];
    distance = new double[n+1];
    isVisited = new boolean[n+1];
    //1~n번까지의 발전소의 위치가 정해짐
    for(int i=1;i<=n;i++){
        String input2[] = br.readLine().split(" ");
        int x = Integer.parseInt(input2[0]);
        int y = Integer.parseInt(input2[1]);
        plant[i] = new Point(x,y);
        //distance: 출발지~i번째 발전소까지의 거리(이떄의 거리는 일직선상의 거리가 아닌, 발전소를 거친 최단거리를 의미한다)
        distance[i] = MAX;
    }
    //arr배열을 초기화시킨다
    //arr배열엔 이제 거리가 m이하인 간선에 대해서만 값을 표시하고 나머지는 INF로 표시한다
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            double temp = getDistance(i, j);
            if(temp N으로 가는 최단거리를 찾아야한다
    bw.write(solve(1)+"");
    bw.flush();
    bw.close();

}
}

# 2224
## 시도1
- 일단 map을 사용해보려고했다. 그 이유는 보통은 노드를 번호로 매기고, 번호는 int형으로 표현할 수있어서 인덱스 대신 사용이 가능하다. 근데이건 알파벳이여서 int대신사용하기가 좀 그렇다..
- 일단 이 문제는 정렬이 되어있는상태에서 dfs로 방문할때마다 출력을 해주면될것같다.
## 시도2
![](https://velog.velcdn.com/images/flre_fly/post/0cc0196c-21bc-4f26-9d53-94bd92f6de29/image.png)
- 명제를 담을 start(명제시작점)라는 변수를 가지는 Node라는 변수를 만들었다
하지만 이렇게하면 인덱스로 노드를 찾는게 너무 어렵다. 인덱스는 start인데말이다
그래서 그냥 조금 큰 배열을 만들고 char->int화해보기로했다
![](https://velog.velcdn.com/images/flre_fly/post/730fe679-b18e-41bf-8408-2309f37370e9/image.png)
- 그렇게 생각하니 코드가 많이 줄었다. 코드의 복잡성도 줄인것같다.하지만 char을 인덱스로 사용한다는게 딱히 쉽게이해할수있는 코드는 아닌것같다고생각했다
## 시도3
- stackoverflow가 떴다.. 만약에 a->b->a인 경우 stackoverflow가 터질것같은데 이걸 어떻게 막아야하는지모르겠다
```java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static Map> map;
    static Node[] nodeArr;
    static Set result = new HashSet<>();
    public static class Node{
        PriorityQueue neighbor = new PriorityQueue<>();
        Node(char c){
            neighbor.add(c);
        }
    }
    public static void solve(Node node, char start){
        if(node==null || node.neighbor==null) return;
        for(char c : node.neighbor){
            result.add(start + " => "+ c);
            solve(nodeArr[c],c);
            solve(nodeArr[c],start);
        }
    }
    public static void print(ArrayList result){
        for (int i=0;i ");
        }
        System.out.println(result.get(result.size()-1));

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        map = new HashMap<>();
        nodeArr = new Node[150];
        for(int i=0;i ");
            for(int j=0;j
시도4


위의 코드를 chatgpt의 도움을 받아 stackoverflow를 없애봤다
하지만 오류가 뜬다. 순서가 잘못되었다.import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;



public class Main{
    static Map> map;
    static Node[] nodeArr;
    static Set result = new HashSet<>();
    static boolean[] visited;
    public static class Node{
        PriorityQueue neighbor = new PriorityQueue<>();
        Node(char c){
            neighbor.add(c);
        }
    }
    public static void solve(Node node, char start){
        if(node==null || node.neighbor==null) return;
        for(char c : node.neighbor){
            if (!visited[c]){
                result.add(start + " => "+ c);
                visited[c] = true;
                solve(nodeArr[c],c);
                solve(nodeArr[c],start);
                visited[c] = false;
            }
        }
    }
    public static void print(ArrayList result){
        for (int i=0;i ");
        }
        System.out.println(result.get(result.size()-1));
}
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());
    map = new HashMap<>();
    nodeArr = new Node[300];
    visited = new boolean[300];
    for(int i=0;i ");
        for(int j=0;j
}

## 시도5
- 그래서 이번엔 정렬을 하기 위해서 Result라는 class를 도입하고, 이 class에 값을 넣고 정렬하여 마지막에 출력하도록 할려고했다 근데 오답이 뜬다. 이유를 모르겠다
```java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static Map> map;
    static Node[] nodeArr;
    static Set result = new HashSet<>();
    static boolean[] visited;
    static List resultList = new ArrayList<>();
    public static class Node{
        PriorityQueue neighbor = new PriorityQueue<>();
        Node(char c){
            neighbor.add(c);
        }
    }
    public static class Result implements Comparable{
        char start;
        char end;
        Result(char start, char end){
            this.start=start;
            this.end=end;
        }

        @Override
        public int compareTo(Result o) {
            if(this.start==o.start){
                return this.end - o.end;
            }else return this.start-o.start;
        }
    }
    public static void solve(Node node, char start){
        if(node==null || node.neighbor==null) return;
        for(char c : node.neighbor){
            if (!visited[c]){
                result.add(start + " " + c);
                visited[c] = true;
                solve(nodeArr[c],c);
                solve(nodeArr[c],start);
                visited[c] = false;
            }
        }
    }
    public static void print(ArrayList result){
        for (int i=0;i ");
        }
        System.out.println(result.get(result.size()-1));

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        map = new HashMap<>();
        nodeArr = new Node[300];
        visited = new boolean[300];

        for(int i=0;i ");
            for(int j=0;j "+result.end+"\n");
        }
        bw.close();

    }
}
시도6

생각해보니 a=>a 일경우에 출력하지 않는것을 빼먹었다. 그래서 다시작성했다import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;



public class Main{
    static Map> map;
    static Node[] nodeArr;
    static Set result = new HashSet<>();
    static boolean[] visited;
    static List resultList = new ArrayList<>();
    public static class Node{
        PriorityQueue neighbor = new PriorityQueue<>();
        Node(char c){
            neighbor.add(c);
        }
    }
    public static class Result implements Comparable{
        char start;
        char end;
        Result(char start, char end){
            this.start=start;
            this.end=end;
        }
    @Override
    public int compareTo(Result o) {
        if(this.start==o.start){
            return this.end - o.end;
        }else return this.start-o.start;
    }
}
public static void solve(Node node, char start){
    if(node==null || node.neighbor==null) return;
    for(char c : node.neighbor){
        if (!visited[c]){
            result.add(start + " " + c);
            visited[c] = true;
            solve(nodeArr[c],c);
            solve(nodeArr[c],start);
            visited[c] = false;
        }
    }
}
public static void print(ArrayList result){
    for (int i=0;i ");
    }
    System.out.println(result.get(result.size()-1));

}
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());
    map = new HashMap<>();
    nodeArr = new Node[300];
    visited = new boolean[300];

    for(int i=0;i ");
        for(int j=0;j "+result.end+"\n");
    }
    bw.close();

}
}
- 하지만 그래도 오답이 뜬다
- 그래서 chatgpt를 통해 자문을 구했다.
![](https://velog.velcdn.com/images/flre_fly/post/63147410-2c53-450d-bc28-2e2ce7a5dd86/image.png)
- 그래서 이것저것 고쳐봤지만 계속 오답을 내고 chatgpt는 내말을 못알아듣길래 일단여기까지 하고 답안지를 보기로했다.

## 답지
```java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static boolean arr[][];
    static final int MAX = 150;
    public static void solve(){ 
        //플로이드워샬은 모든 정점사이의 최단경로를 구해준다
        //그과정에서 모든 정점사이의 가능한 경우의수를 모두 탐색하기때문에 이 문제에서도 적합하다
        //두 노드의 관계만 보면 되기에, 두노드가 결국 이어질수있냐?를 보는것이다
        for(int k=0;kk로도 이어지고 k->j로도 이어진다면 i->j로도 이어질 수 있음을 의미한다
                    if(arr[i][k] && arr[k][j]) arr[i][j] = true;
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        //150정도는 설정해주어야지 알파벳의 아스키코드값중 가장 큰 숫자를 넘는다
        arr = new boolean[MAX][MAX];
        for(int i=0;i ");
            char c1 = input[0].charAt(0);
            char c2 = input[1].charAt(0);
            arr[c1][c2] = true;
        }
        solve();
        StringBuilder sb = new StringBuilder();
        int count=0;
        for(int k=0;k "+ (char)i+"\n");
                    }
                }
            }
        }
        bw.write(count+"\n");
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}


세션-쿠키 헷갈렷던점
Thu, 26 Jan 2023 07:52:30 GMT
질문1


쿠키랑 세션이랑 다른거잖아요
둘다 인증에 사용되는 작은 저장소같은거예요
저는 둘이 다르다고해서
어떤로그인에는 전과정에 쿠키만 쓰이고 어떤과정에는 전과정에 세션만쓰이고
이런건줄알았는데 이 그림을 보니
로그인이라는건 세션+쿠키가 둘다쓰이는 작업인거네요..?
로그인을 하면 항상 sessionid를 발급해줘야하니까 세션이 쓰이고
클라이언트 측에서는 그정보를 저장하고있어야하니 sessionid를 담은
쿠키가 생성되는거구요.

질문2
세션과 쿠키는 다른것이며 둘다 인증방식에 쓰입니다.
둘의 차이점은 관리되는곳(세션은 서버에서, 쿠키는 클라이언트측에서)과 만료기간정도의 차이가 있는데요
저는 로그인이 세션버전의 로그인이있고 쿠키버전의 로그인이 따로있는줄알았습니다. 그러니까 쿠키랑 비슷한데 좀더 보안이 강화된게 세션버전의 로그인이라고 생각했어요
그런데 로그인이라는과정안에 세션과 쿠키가모두사용되는거같아서요
로그인요청시 서버가 sessionid생성해서 클라이언트에게 돌려주면 클라이언트는 일단 그 정보를 저장해야하잖아요. 요청해야하니깐..
그래서 이떄 쿠키에 session id를 저장합니다. 그리고 신규요청을 보내면 그 요청에 쿠키가 들어가있습니다. 그리고 서버는 그 쿠키정보를 까봐서 sessionid가 유효한지 검증을 하는 과정을 거지구요... 그리고 그 과정이 완료되면 클라이언트가 요청한 작업을 수행해줘요..
제가 설명한게 맞나요?
질문3
쿠키정보는 항상 서버에 전송되기때문에 네트워크 트래픽이 유발돼요
근데 쿠키는 웹브라우저에 있는 작은저장소예요 이말은 곧 서버의 자원을 활용하지 않는다는얘기죠
근데 서버에 항상 전송돼서 네트워크 트래픽을 유발하는게 서버의 자원을 쓰는것과 다른얘기인가요?
자꾸 요청이 오면 그거 처리하느라 자원을 써야하는거아닌가요?

출처
https://sjparkk-dev1og.tistory.com/1



DFS BFS(1)
Thu, 26 Jan 2023 01:10:34 GMT
1260: DFS BFS
 public static void BFS(int start){
        Queue q = new LinkedList<>();

        q.add(start);
        isVisited[start] = true;
        while(!q.isEmpty()){
            for(int i=1;i

저코드가 있으면 안되는 이유는 일단 q에 넣은 값을 start로 잡아야하는데 start에 대해서 두번 검색을 하기때문이다. 일단 생각한것이랑 다르게 동작하고 있으므로 오답이 나올 수 있다.
 public static void BFS(int start){
        Queue q = new LinkedList<>();

        q.add(start);
        isVisited[start] = true;
        while(!q.isEmpty()){
            int x = q.poll();//이위치
            start = x;//이위치
            for(int i=1;i

11725

입력받을당시에는 뭐가 parent고 뭐가 child인지를 모른다.
a랑 인접한 node가 어떤녀석들인지만 알 수있다. 그리고 우리는
일단 루트노드부터시작해서 bfs 탐색을 해가면서. 큐에 넣어보면서
큐에서 노드를 넣을시점에 큐에 넣을 data의 부모를 알 수 있다.
왜냐하면. 큐에넣을 노드의 인접노드를 기준으로 for문을 돌려서 인접노드들을 찾아낼것이기때문에.
그리고 또한 계속반복하는것을 막으려면 한번 방문한곳은 false처리를하든 해서 더이상 방문하면 안된다. 이를 위해 isVisited변수를 넣어주었고, parent를 idx별로 구하기위해 parents배열을 정의하였다import com.sun.jdi.request.BreakpointRequest;



import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.OptionalInt;
import java.util.Queue;
public class Main{
    //1~n까지의 노드리스트를 담을 변수
    //이 노드를 1부터 시작해서 1의 이웃탐색 후 -> 큐에 쌓인 이웃노드 기준으로 계속탐색을 진행해나갈것임
    static Node[] nodeList;
    //i번째 애의 부모는 parents[i] = a 의 a값이다.
    static int[] parents;
    //방문했는데 계속방문하면안된다. 한번방문한곳은 q에 다시넣어지면안된다. 이 변수가 없으면 무한루프를 돌게된다
    static boolean[] isVisited;
    //node의 정의가 중요하다 left right parent같은 변수는 어차피 입력이 들어올떄 무엇이 parent인지 무엇이 left인지 모르기때문애
    //그냥 이웃한 노드들을 담는 리스트를 정의하였다
    public static class Node{
        int data;
        ArrayList neighborList;
        //처음에 노드를 추가하는것을 생각해보자. 이웃노드는 여러번에 걸쳐들어올수있기때문에 일단 생성자로는 이웃노드까지 받는 코드대신
        //node가 가지고있는 값. data만 받도록하고 리스트를 초기화시켜준다
        public Node(int data){
            neighborList = new ArrayList<>();
            this.data = data;
        }
        //이웃노드 추가하는 코드
        public void addNeighbor(int data){
            neighborList.add(data);
        }
    }
    public static void solve(){
        //큐를 사용해서 bfs를돌린다. 그러면 이웃노드에 대해서만 계속 탐색을 할 수 있다
        Queue q = new LinkedList();
        //일단 1이 루트 노드이기때문에 큐에 nodelist[1]=1의 값을 가지는 노드 를 집어넣어주었다
        q.add(nodeList[1]);
        //q는 모든 노드를 방문하면 비어지게 될것이고, 그에 따라 반복문이 끝날것이다
        while(!q.isEmpty()){
            Node node = q.poll();
            int idx = node.data;
            //큐에서 빼낸 노드에 대해 반복문을 돌린다
            for (Integer item: node.neighborList) {
                //방문하지 않은 노드여야만 한다. 이전에 방문한 노드는 이미 부모가 밝혀졌거나. 내가 큐에 넣은 노드일 수 있다
                if(!isVisited[item]){
                    //예를들어 첫 노드 즉 data=1인 노드의 데이터는 idx값일것이다.
                    //item의 부모는 idx라고 설정해주는 코드이다
                    parents[item] = idx;
                    //방문처리
                    isVisited[item] = true;
                    //이웃노드에 대해 똑같은 행위를 반복할 수 있게 설정
                    q.add(nodeList[item]);
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        nodeList = new Node[n+1];
        parents = new int[n+1];
        isVisited = new boolean[n+1];
        for(int i=1;i<=n;i++){
            nodeList[i] = new Node(i);
        }
        for(int i=0;i
}
}
# 2589
- 주석달아놓은거 이유 찾아야함
```java
import com.sun.jdi.request.BreakpointRequest;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static boolean isLand[][];
    static boolean isVisited[][];
    static int count;
    static int max;
    static class Point{
        int x;
        int y;
        int depth;
        Point(int x,int y, int depth){
            this.x=x;
            this.y=y;
            this.depth = depth;
        }
    }
    public static int bfs(int x, int y, int depth){
        Queue q = new LinkedList<>();
        q.add(new Point(x,y,depth));
        isVisited[y][x] = true;
        while(!q.isEmpty()){
            Point p = q.poll();
            if(max < p.depth) {
                System.out.println(p.depth);
            }
            max = Math.max(p.depth, max);
            //max의 위치가 여기면안된다 이유를 모르겠다
            add(q, p.x+1,p.y, p.depth);
            add(q, p.x-1,p.y, p.depth);
            add(q, p.x,p.y+1, p.depth);
            add(q, p.x,p.y-1, p.depth);
        }
        return max;
    }
    public static void add(Queue q, int x, int y, int depth){
        if(x>=0&&y>=0&&y



n과m
Mon, 23 Jan 2023 00:46:22 GMT
시도1
  public static void solve(int idx){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            list.remove(list.size()-1);
        }

        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve(i+1);
            }
        }
    }

idx=1일때를 생각해보면
idx=1일때 결과가 1 하나만 출력이돼야한다. 근데 1일떄 1,2,3모두 출력된다.
이런식이면 idx=2일때도 결과가 출력된다는얘기다. 그러므로 이 코드는 틀렸다.
그리고 remove의 위치도 문제가된다.
size=m일때만 제거를 하는것이니 1로출발해서 두개를 출력해야하면 1로시작하는것만나온다

시도2
 public static void solve(int idx){
        //1이추가된다
        list.add(idx);
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();

        }
        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                solve(i+1);
                list.remove(list.size()-1);
            }
        }
    }

1 2 출력을 하고 나와서 2 제거한다
그다음 반복에서 1 3 출렫하고 3제거한다
반복끝
재귀함수 첫번째에 넣게되면. 재귀함수 호출되는 순간만 add하겠다는것이다.
함수내부의 재귀함수를 호출하는 부분은 for문 하나니까 그갯수만 나오기때문에
오답이 나올것이다. 이럴땐 for문안에 add문을 넣어주면 여러개를 출력하게될수있다

시도3
public static void solve(int idx){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            return;

        }
        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve(i);
                list.remove(list.size()-1);
            }
        }
    }

for문의계속증가하고있는 인덱스인 i를넘겨줘서 계속그거부터 시작하게하고있다.
이렇게된다면 list에 담기는수는 매번 증가하는 수만 추가될것이다.

최종
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static int m;
    static ArrayList list;
    public static void solve(){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            return;

        }
        for(int i=1;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve();
                list.remove(list.size()-1);
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        list = new ArrayList<>();
        solve();

        bw.flush();
        bw.close();
    }
}

매번 1부터 검사를해서 내가 리스트에 추가시킨것만 제외시킨다.
시간복잡도는 m^n일라나?

5568 카드놓기 (비슷한문제)
https://www.acmicpc.net/problem/5568
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static int n;
    static int k;
    static String arr[];
    static ArrayListlist = new ArrayList<>();
    static boolean visited[];
    public static void dfs(int idx, String num, int count){

        if(idx > n) return;
        if(count ==k){
            if(!list.contains(num)) list.add(num);
            return;
        }
        for(int i=1;i

dfs(idx+1, num + arr[i], count+1);
dfs(idx+1, num, count);//이줄이 없어도된다
왜냐하면 반복문을 통해 그다음 반복에선 arr[i]을 미포함시키고 진행할것이니깐.



ch 09 java.lang + 유용한 클래스
Thu, 19 Jan 2023 12:26:08 GMT
java.lang

기본적인 클래스 포함하고있음. 그래서 import문 없이도 사용하도록 해줌
toString이나 equal, getClass

clone

기본적으로 얕은복사이기때문에 깊은 복사를 진행하려면 
Cloneable을 상속받고, 오버라이딩 해주어야한다

공변반환타입

오버라이딩 시 조상메서드의 반환타입을 자손클래스의 타입으로 변경가능public Point clone(){
  ...
  return (Point)obj;
}
문자열의 비교
String x1 = "a";
String x2 = "a";//문자열리터럴, 기존것 재사용
String x3 = new String("a");//매번 새로운 인스턴스 생성
System.out.println(x1==x2);//true
System.out.println(x3==x2);//false


빈 문자열

길이가 0인 배열을 생성할 수 있다 String은 내부적으로 char[]로 구현되어있고, 빈문자열의 경우 배열의 길이가 0이다String str = null;
//char c = '\u0000'
String str2 = "";
//char c = ' ';


StringBuffer

String클래스는 인스턴스를 생성할때 지정된 문자열을 변경할 수 없다
StringBuffer클래스는 변경이 가능하다
문자열 편집을 위한 버퍼를 가지고 있다.
String클래스와 다르게 equal을 오버라이딩해놓지 않아서 equal메서들를 써도 ==을쓴것과 같이 주솟값만을 비교한다

StringBuilder

멀티스레드에 안전하도록 동기화되어있다
동기화는 StringBuffer의 성능을 떨어뜨린다
StringBuilder: StringBuffer에서 스레드 동기화를 뺀 것

StrictMath

Math 클래스는 최대한의 성능을 얻기위해 JVM이 설치된 OS의 메서들를 호출해서 사용한다 -> OS에 의존적인 계산
어떤 os에서 실행돼도 항상 같은 결과를 얻도록 Math클래스를 새로작성한것. 
성능은 다소 떨어짐

Wrapper class

모두 equal을 오버라이딩 하고 있음Integer x1 = 2;
Integer x2 = 2;
System.out.println(x1==x2);

==연산시 주솟값을 비교함. 하지만 이것은 리터럴이기때문에 값을 비교함
리터럴을 넣어줬을땐 x1에 진짜 값이 저장되고, 만약 객체를 넣어줬을땐 주솟값을 넣어준다는 얘기




ch8 예외처리
Thu, 19 Jan 2023 11:41:00 GMT
Exception, RuntimeExeption


Exception class: 사용자의 실수와 같은 외적인 요인에 의해 발생하는 예외-> Checked 예외-> 반드시 예외처리를 해주어야함
RuntimeException class: 프로그래머의 실수로 발생하는 예외

unchecked 예외 -> 예외처리를 반드시 해주지 않아도됨



try-catch의 목적

프로그램 실행시 발생할 수 있는 예외가 일어나면 이러한 처리를 통해 프로그램이 비정상적으로 종료되는것을 막기위하여 작성하는 코드

try-catch의 흐름

try블럭내에서 예외가 발생한경우 catch문을 찾아서 catch문을 수행하고 try-catch문 이후의 문장을 수행한다
예외가 발생하지 않은경우 catch문은 영원히 수행되지 않는다 public static void main(String[] args) throws IOException {
      System.out.println("1");
      try{
          System.out.println("2");
          System.out.println(0/0);
          System.out.println("3");
      }catch(ArithmeticException ae){
          System.out.println("4");
      }
      System.out.println("5");
      //1 2 4 5출력, 예외발생이후의 문장은 수행하지 않음
  }

예외가 발생한경우, 예외발생이후의 문장들은 수행하지 않고 바로 catch문으로 이동한다
catch문의 예외클래스에 대해 인스턴스가 만들어지고 instanceof연산자로 인스턴스임이 확인이 되면 해당 블록안으로 들어가게된다. 그래서 가장 최상위 예외 클래스인 Exception을 ArithmeticException대신 넣어도 잘 돌아간다

자바는 메서드에 이러한 예외가발생할수있음을 코드로 작성해놔야한다
그래서 프로그래머가 이러한 예외가 발생할 수 있음을 코드만 보고도 짐작할 수 있다
두가지 예외처리 방식
1

public class Main{
    static File createFile(String fileName) throws Exception {
        try{
            if(fileName.isEmpty()) throw new Exception("파일이름이 유효하지 않습니다");
        }catch(Exception e){
            fileName = "제목없음.txt";
        }
        File f = new File(fileName);
        return f;
    }
    public static void main(String[] args) throws Exception {
        System.out.println(createFile(null).getName());

    }
}
2

import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InvalidPropertiesFormatException;
import java.util.Scanner;

public class Main{
    public static File createFile(String str){
        if(str.isEmpty()) new Exception("파일이름이 유효하지 않습니다");
        return new File(str);
    }
    public static void main(String[] args) throws Exception {
        String str = null;
        try{
            File f = createFile(str);
            System.out.println(f.getName() + " 파일이 성공적으로 생성되었습니다");
        }catch(Exception e){
            System.out.println(e.getMessage() + "\n 다시 입력해 주세요");
        }
    }
}
finally는 언제 사용?

예외가 발생하든 안하든 두 경우 모두 이후에 실행되어야하는 코드는 finally에 적어준다

try-catch의 문제

입출력을 한다고 생각해보자. 입출력도중에 예외가 발생할 수 있으므로 try-catch로 감쌀것이다. 그런데 입출력이끝난후에는 꼭 사용한 자원을 반환하기위해 close를 해주어야하는것들이 있다.
그렇게 되면 try문이 중첩되어 가독성측면에서 좋지 않다.
그리고 만약 예외가 두군데서 발생하면 앞의 예외가 무시된다는 점에 있다.

try-with-resource

try문이 끝나면 자원을 자동으로 반납해준다public static void main(String[] args) throws Exception {
      int sum = 0;
      int score =0;
      //try괄호에 객체를 생성한다
      //fis와 dis는 AutoCloseable을 구현한 class여야 try가 끝나고 자동으로 close된다
      try(FileInputStream fis = new FileInputStream("score.txt");
          DataInputStream dis = new DataInputStream(fis)){
           while(true){
                  score = dis.readInt();
                  System.out.println(score);
                  sum += score;
           }
           //try문이 끝나면 위에서 생성한 fis와 dis는 닫히게된다
      }catch(EOFException e){
              System.out.println("점수의 총합: " + sum);
      }catch(IOException e){
              e.printStackTrace();
      }




}

## 중간에 예외가 발생해도 둘다 출력해준다
![](https://velog.velcdn.com/images/flre_fly/post/906dd460-4c54-44cd-8075-35308d009fd7/image.png)

# 예외되던지기
- 예를들어 a라는 예외가발생했을때 해당 메서드를 호출한곳, 그리고 해당 메서드 이렇게 두부분에서 에러처리가 필요할땐 다음과같이 해당 메서드에서 에러에 대한 처리를 한 후에 인위적으로 다시 error를 던져준다
```java
public static void func2(){
        try{
            func();//발생한 예외를
        }catch(Exception e){//여기서 받고 아래에서 예외처리2
            System.out.println("예외처리2");
        }
    }
    public static void func() throws Exception {
        try{
            throw new Exception();//예외가 발생했음!
        }catch(Exception e){
            System.out.println("예외처리1");
            throw e;//예외를 다시 던짐
        }
    }
연결된예외

예외A가 예외B를 발생시켰다면 A를B의 원인예외라고 한다
여러예외를 하나의 큰 분류의 예외로 다루고싶을때 원인예외를 쓴다
아래글을 참고하자
A가 원인이라고 말해주는것보다 D->C->B->A.. 이렇게 A가 원인이 된 경로를 말해주면 훨씬 원인을 파악하는게 수월하기때문이다.
그렇기때문에 예외의 원인을 같이 감싸서 다시 던져주는 것이다.
또한 예외처리를 선택적으로 할 수 있도록 변경하는것도 가능하기 때문이다
https://inpa.tistory.com/entry/JAVA-%E2%98%95-%EC%98%88%EC%99%B8-%EB%8D%98%EC%A7%80%EA%B8%B0throw-%EC%98%88%EC%99%B8-%EC%97%B0%EA%B2%B0Chained-Exception#%EC%98%88%EC%99%B8%EB%A5%BC_%EB%8B%A4%EB%A5%B8_%EC%98%88%EC%99%B8%EB%A1%9C_%EA%B0%90%EC%8B%B8_%EB%8D%98%EC%A7%80%EA%B8%B0




bw.close, bw.write(숫자)
Thu, 19 Jan 2023 05:16:25 GMT
  BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("111");
        bw.flush();
        bw.close();
  BufferedWriter bw2 = new BufferedWriter(new OutputStreamWriter(System.out));
        bw2.write("222");
        bw2.flush();
        bw2.close();
실행결과에 111만 출력된다. 디버깅 해보면 둘은 다른객체같은데도 close시에 아예 출력자체가 안된다.
그 이유가 뭘까?
스트림을 닫고난 뒤에 다시 여는게 안되는것일까?

어떤사람은 이게 111,222가 모두 출력이된다고 해서 잘 모르겠다
만약에 111만 출력이 된다면 다음상황이 아닐까 생각중이다
객체가 여러개 생성이 되더라도 스트림은 Printstream 하나를 공유하고, 스트림을 닫아버리면 객체를 생성해서 다시여는게 안된다. <- 가아닐까? 그런데 왜 어떤사람은 둘다 출력이되는것일까? 코드가 똑같은데
테스트코드에서랑 psvm(public static void main)에서 writer 객체가 다르다.
테스트코드에서는 해당 객체가 close되더라도, 새로 생성하면 해당 객체를 다시 재활용이 가능한데,
psvm에서는 close하면 System.out 전역객체에 Null로 되어 writer가 없는거같습니다

bw.write(숫자)

이상한게 출력이 되는이유는.. 이넘겨지는 숫자를 그대로 출력해주는게 아니라 이숫자에 대응하는 아스키코드값을 출력해주기때문이다
https://docs.oracle.com/javase/7/docs/api/java/io/BufferedWriter.html#write%28int%29


스트림

자바에서는 파일이나 콘솔의 입출력을 직접 다루지 않고, 스트림(stream)이라는 흐름을 통해 다룹니다.
스트림(stream)이란 실제의 입력이나 출력이 표현된 데이터의 이상화된 흐름을 의미합니다.
즉, 스트림은 운영체제에 의해 생성되는 가상의 연결 고리를 의미하며, 중간 매개자 역할을 합니다.
그리고 스트림을 닫아줘야 다른곳에서 여기에 접근이 가능함


http://www.tcpschool.com/java/java_io_stream



BufferedReader vs Scanner
Thu, 19 Jan 2023 04:55:50 GMT
InputStreamReader

문자열을 한글자 단위로 읽는다
매번 문자열 읽는것? 매우 비효율적BufferedReader

InputStreamReader+버퍼링기능

데이터 추가 요청시마다 데이터 읽는게 아닌, 일정한 크기의 데이터를 한번에 읽어서 버퍼에 보관하고
사용자의 요청이 있을때 읽어오는 방식으로 동작 -> 빨라진 속도



Scanner

-> 공백, 줄바꿈 단위로 입력을 받음 -> 좀더 쉽게 데이터를 입력받음

데이터타입이 받는 시점에 결정됨. -> 별도의 캐스팅 필요없음



결론
Scanner가 별도의 파싱과정 + 버퍼사이즈도 작아서 잦게 입력요청을 보낼경우 잦게 요청이 들어옴 -> scanner가 더 느림



DP(2)
Wed, 18 Jan 2023 03:18:15 GMT
10844: 쉬운계단수
아이디어

(A+B+C+D)%E = A%E + B%E + C%E + D%E
즉, 다 더한다음에 E로 나누면 overflow나니까 계산결과가 나올때마다
E로 나눠준다
숫자를 하나씩 만들어간다고 생각하자. 가장중요한 수는 맨뒷자리수다. 맨뒷자리수가 무엇이냐에 따라 다음에 올 수가 결정된다.
예시를 통해 규칙을 찾는것이 중요하다.
예시를 통해 규칙을 찾으려했지만 찾기 힘들었다. 잘나누는 것도 필요하다
우리가 규칙을 잘 찾기 위해서는 잘 나누어 놓는것이 중요하다.
맨뒷자리수가 가장 중요하고, 이에따라 다음수가 결정된다면
맨뒷자리수가 무엇이냐에 따라 숫자들을 다 나눠보자코드
import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;



public class Main{
    //dp[n][k]: 맨뒷자리수가 k이면서 자릿수는 n개인 수들의 개수를 의미
    //dp[1][2]: 은 숫자 2를 의미한다. 자릿수는 1개이면서 맨뒷수는 k즉 2다
    static long dp[][];
    //입력받는 수 n을 의미한다.
    static int n;
    //문제를 재귀적으로 해결하는 함수를 만들었다.
    //기록이 되기때문에 매우짧은시간내에 해결이 가능하다
    public static long solve(int n, int k){
        //아래 조건이 없으면 stackoverflow난다
        //k에 대한 조건은 없어도된다 아래의 코드에서 알아서 잡아주기때문
        //k가 너무커질려하는순간 = 9 에서 알아서 컷해줌
        //k가 너무작아지려고하는순간 = 0에서 알아서 컷해줌
        //그래서 우리는 n을 계속 감소시키다보면 n==1인곳에 도달할거고
        //그곳은 기본값으로 지정해줬기때문에 무조건그 값을 return하고 재귀를끝내도록해준다
        if(n == 1) return dp[n][k];
        //dp에 값이 저장되어있는경우 그 값을 return해준다 대신 나눠서 리턴해준다
        // 모두 더한다음에 나누는거나 각값을 나눈다음에 더하는것이나 같기떄문에 이같은연산이 가능하다
        if(n==1&&k==9||dp[n][k]!=0) return dp[n][k]% 1000000000;
        //k==0인 경우에는 규칙에서 보인 특성에 따라 자릿수를 낮추고 k번쨰의 개수를 리턴한다
        //자릿수가하나작고, 9로끝나는 숫자들로 dp[n][k]에 해당하는 숫자를만들수있기대문이다
        if(k==0) {
            dp[n][k] = solve(n-1, 9);
            return dp[n][k];
        }
        //1인 경우에 규칙을 살펴보면 자신보다 하나큰수로 자기자신을 만들수있다.
        //이들은 모두 자기보다 작은수에 대해서 값을가져와서 채우는데
        //n==1인 기본값이 채워져있어서 재귀적으로 이런작업이가능한것이다
        else if(k==1){
            dp[n][k] = solve(n-1, k+1);
            return dp[n][k];
        }
        //9인 경우도 예외적으로 k+1, k-1로 처리할수없기때문에 아래와같이 직접숫자를넣어주었다
        else if(k==9) {
            dp[n][k] = solve(n-1, 8)+ solve(n-1, 0) ;
            return dp[n][k];
        }
        //그외의 숫자들은 모두 아래와같은 규칙으로 적용이 가능하다
        //값을 기록해야하기때문에 기록하는과정을빼먹지말자
        else{
            dp[n][k] = solve(n-1, k+1) + solve(n-1, k-1);
            return dp[n][k];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        dp = new long[n+1][10];
        //초기화하는 작업
        for(int i=0;i<10;i++){
            dp[1][i] = 1;
        }
        //자릿수가 1개이면서 0으로끝나는 숫자는 없다
        //0은 해당되지않는다
        dp[1][0] = 0;
        //solve(n,1)만 하면 숫자 1에 대해서만 조사하기때문에..
        //모든숫자를 채워서 재귀탐색을하기위해선 0~9까지를 조사해야한다
        for(int i=0;i<=9;i++){
            solve(n,i);
        }
        //조사를 마친 후 배열에 저장된 값들을 모두 더해준다
        long sum = 0l;
        for(int i=0;i<10;i++){
            sum += dp[n][i];
        }
        //너무커질수도있으니 나눠준다
        bw.write(sum % 1000000000 +"");
        bw.flush();
        bw.close();
    }
}

# 11726: 2xn 타일링
## 아이디어
- N번쨰의 요소가 이전값들과 어떤관계가있는지를 생각해보았다.
N번째요소는 N-2번쨰요소에 세로로긴 막대기 하나붙인결과 + N-1요소에 가로로 긴 막대기 하나를 붙인 결과에 해당했다

# 11057: 오르막수

## 아이디어
![](https://velog.velcdn.com/images/flre_fly/post/9e801e4e-8e0c-4eb5-8973-fb3bf2b9860d/image.png)
n은 자릿수
0~9는 0~9로끝나는 수
즉, 220은 4자리수이면서 0으로끝나는 수의 갯수를 의미한다
220은 n=4-1인 n=3의 모든값을 더한 결과와 같다.
n=2쪽이 좀더 이해하기 쉽다
(n=2,k=0)인 수는
(n=1,k=0)~(n=1,k=9)의 합과 같다.

```java
import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
    // 
    //
    static long arr[][];
    public static long solve(int n, int k){
        //계속 n-1만하다보면 n이 음수가 돼버린다. 그에 대응하는 배열값은 없다
        //멈춰주어야한다. 종료조건이 있어야한다
        if(n<=0) return 0l;
        //memorization을 통해 여기서 함수의 재귀를 멈춰준다
        if(arr[n][k]!=0) return arr[n][k];
        long sum = 0l;
        //i는 k부터 9까지여야한다
        //그러니까 가장 마지막수가 i라면 그 뒤의 수는 무조건 i보다 크거나 같아야한다는얘기다
        for(int i=k;i<=9;i++){
            long x = solve(n-1,i);
            sum= (sum + x) % 10007;
        }
        arr[n][k] = sum;
        //다 더한뒤에 나누는거나 중간중간 더하는과정에서 매번나누는거나 똑같다
        return arr[n][k] % 10007;
    }
    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());
        //n+1인이유는 n=0인칸은 안쓸것이기때문이고
        //10으로 써준이유는 0부터9까지수를 써줄것이기때문이다
        arr = new long[n+1][10];
        //가장 아랫단에 있을 수들을 초기화해주어야한다
        //이값이 없으면 함수가 stackoverflow날것이다.
        //함수가 더이상 호출못하게 끝맺음해주는부분이있어야한다
        for(int i=0;i<=9;i++){
            arr[1][i] = 1;
        }
        long sum =0l;
        //solve를할때마다 n번쨰자릿수에서 i번째로 끝나는 수의 갯수가 출력된다
        //해당 갯수를 모두 더하면 n번째자릿수의 오르막수를 구할 수 있다
        for(int i=0;i<=9;i++){
            sum = (sum + solve(n,i)) % 10007;
        }

        bw.write(sum%10007+"");

        bw.flush();
        bw.close();
    }


}
2193: 이친수

이친수가 되기위해선 
이친수 + 0 이거나
이친수 + 01 이여야한다
n자리 이친수를 구하기위해서 
n-2자리이친수 + 0 과
-1자리 이친수 + 01을 가져오면된다
즉, dp[n]=dp[n-2]+dp[n-1]이 성립한다.
11053: 가장긴증가하는수열
public static void solve(){
        dp[0] = 1;
        //원소 하나하나를 보고. 이 원소를 이전원소들과 비교하여 얼마나 큰지를 따져봐야한다
        for(int i=1;i=dp[k]에 등호를 넣었다
                //값은 내가 더 큰데 dp의 값, 즉 이전원소들이 만들어놓은 수열이 더 긴경우
                //기존것에 합세한다
                if(dp[i]<= dp[k] && arr[i] > arr[k]){
                    //기존것에 합세하는거기때문에 기존값+1을해준다
                    dp[i] = dp[k]+1;
                }
            }
        }
11055: 가장 큰 증가 부분 수열
 public static int solve(){
        //이런 이런 식의 부분 증가수열은 기준점을 잡은 후 기준점 이전까지의 수들과 비교하여 자신이 큰 경우만 dp 배열을 갱신해주면된다
        // 증가 부분 수열 중에서 합이 가장 큰 것을 나타내는 변수 result
        //수열의 합은 0보다는 클테니까 0을 초기화한다
        int result =0;
        //입력받은 수열의 갯수만큼 for문을 돌린다
        for(int i=0;i

1932: 정수삼각형
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Objects;
import java.util.StringTokenizer;

import static java.util.Objects.*;

public class Main{
    static int arr[][];
    static int sum[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        //삼각형에 대한 정보를 담을 arr배열
        arr = new int[n][n];
        //삼각형가장꼭대기에서 아래로부터 합을 저장할 sum배열
        sum = new int[n][n];
        //입력받는 부분
        for(int i=0;i

9465: 스티커

오해했던 점
스티커가 모두 찢어진다는게아니라 하나씩만 떼어지는 건 줄 알았다.

풀이1

일단 Node라는 class를 따로만들어서 위치와 value를 저장한다
그리고 Node를 정렬한다
가장큰값부터 꺼내서 그 인근값들은 못가게 false로 바꾼다
근데 이런식으로하면
0 80 100 80
0 0   80 0 
이런 배열이 있을때 최댓값을 찾지 못한다.
무조건 가장큰 값부터 찾는다고 해서 최대를 보장해주지 않는다.

풀이2
스티커가 모두 찢어지는것이라면. 내가 i번째 배열요소를 봤을때 그 요소는 이전 요소들과 어떤 관계가 있을지 생각한다.

화살표에 해당하는 두 지점에만 갈 수 있다.
A와 B는 갈 수 없는것이 아니지만, 문제조건상 최댓값을 찾고, 요소들엔 모두 양수가있을것이기때문에 그 이전 요소들을 무조건 들러주는것이 최댓값을 찾을 수 있게 해준다.=



화살표가 다음아래칸을 가리키는지 다다음아래칸을 가리키는지에 따라 최댓값이 변한다. 무조건 다음아래칸을 가리킨다고 해서 더 많은 값을 가져올 수 있는게 아니라. 보여드린 예시처럼 세번째 아래에 있는 50의 경우, 매우 큰 숫자일 경우에 다다음 아래칸이 더 합이 클 수 있다.왜 4번째 아래의 0과 5번째 아래의 0은 선택하면 안되는것일까?

두번째아래10을 선택해도, 네번째 0을 선택할 수 있다.
세번째아래 50을 선택하면 5번째 아래의 0을 선택할 수 있다.
그러니까 결국 두번쨰아래와 세번째 아래만 고려하면 나머지를 다 고려할 수 있게 되는 것이다.코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;



import static java.util.Objects.*;
public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i
        }
        //계속 더해나가다보면 배열의 가장 끝 두 값 중 가장 큰 값으로 출력해주면된다
        //가장 마지막은 어쨋든 가장 마지막끝에서 발생될것이기 때문
        bw.write(Math.max(dp[0][x-1], dp[1][x-1])+"\n");

    }

    bw.flush();
    bw.close();
}
}
# 2156: 포도주 시식
처음에는 xooxoo와 ooxoox의경우의수만 세주면된다고 생각했다.
일단 한번선택할때 두개를 선택하는게 무조건 이득이라고생각했기떄문이다
oxooxoo이런선택지가 있다는것을 몰랐따.
```java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static int wine[];
    static int dp[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        wine = new int[n+1];
        dp = new int[n+1];
        for(int i=0;i
11052: 카드구매하기

public class Main{
    static int n;
    static int card[];
    static int dp[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        card = new int[n+1];
        dp = new int[n+1];
        String input[] = br.readLine().split(" ");
        //card에 대한 정보를 입력받는다
        //idx를 card갯수로 조회하고 싶어서 n+1만큼 선언
        for(int i=1;i<=n;i++){
            card[i] = Integer.parseInt(input[i-1]);
        }
        //기본 전략은 다음과 같다
        //구하려는것: 개수 x를 가지는 카드가격의 최댓값
        //개수가 예를들어 x라면. 1~x까지의 여러 조합을 통해
        //1 x-1
        //2 x-2 이런조합을 통해 합이 x인 것들중 최댓값을 dp에 저장한다
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] = Math.max(dp[i-j] + card[j], dp[i]);
            }
        }


        bw.write(dp[n]+"\n");

        bw.flush();
        bw.close();
    }
}
15486 퇴사2
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static int[] dp;
    public static void solve(){
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        //dp[x]: x일 이전까지 일을 했다고 가정했을떄 x날에 받을 돈의 최댓값
        //n일까지 일할테니까 dp[n+1]의값을 구하면된다
        //문제를 쪼개서 생각해보면
        //x일이전까지일을했고 + 지금 이일을했을때 그떄가서 받을 돈, 이일을 하지 않는다고 가정했을때 내가 받을 최댓값
        //중에 최댃값을 매번 갱신해준다
        //그리고 dp의 값은 이전의 최댓값을 그대로 끌고와야 계속 누적이 된다
        dp = new int[n+2];
        for(int i=1;i<=n;i++){
            String input[] = br.readLine().split(" ");
            int period = Integer.parseInt(input[0]);
            int pay = Integer.parseInt(input[1]);
            //값을 끌고오는 것
            dp[i] = Math.max(dp[i-1], dp[i]);
            //대상의 원래값(지난 idx에서 누군가가 더큰값으로 업데이트했을수도있으니) vs i번째날기준 i-1까지 일을했고, i번째날에 받을돈 + 이번에 내가 일을 하며 받을돈,
            int target = period+i;
            if(target

11058 크리보드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static long dp[];
    static long solve(int idx){
        if(idx<=0) return 0;
        if(dp[idx]!=0) return dp[idx];
        //큰수부터 시작하기때문에 dp[idx-1]+1을넣으면 0에다 +1을 한 값을 넣게된다
        //일단 여기서 부터 재귀호출을 하여서 값을 구해놓은 다음에 for문을 돌려야한다
        //1. A만 추가하는경우
        dp[idx] = solve(idx-1)+1;
        //idx의 위치보다 3칸 왼쪽에 있는애부터 계속왼쪽으로 한칸씩 간다
        //그래서 왼쪽으로 한칸 갈때마다 곱하는 수를 늘려준다
        //아래의 식은 예제를 만들어서 식을 세웠다.
        //2. Ctrl(복붙)하는 경우: 이경우는 세세하게 나눠보면
        //세종류의 버튼을 누르는것과 세종류의 버튼을 이미 눌렀다면 버튼 하나만 눌러도되는경우가있다
        //근데 이경우를 아래 for문으로 합칠 수 있다.

        //solve(i):i번 버튼을 눌렀을때의 A의 최댓값
        //세종류의 버튼을 이미 눌렀다고 가정하고 시작을해야한다. 그래야 두번쨰 복붙의 경우도 진행이 가능하니까
        //그래서 3을빼주는것이다. 이미 버튼이 눌려졌다고 가정한다
        //그리고 A의 갯수는 하나 줄이고 곱하는수(곱하는버튼)은 늘리면서 가장 큰 조합을 찾아서
        //dp에 저장한다
        for(int i=idx-3;i>=1;i--){
            dp[idx] = Math.max(solve(i) * (idx-i-1), dp[idx]);
        }
        return dp[idx];
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        //예외처리
        if(n==1) {
            bw.write("1\n");
            bw.flush();
            bw.close();
            return;
        }
        if(n==2){
            bw.write("2\n");
            bw.flush();
            bw.close();
            return;
        }
        dp = new long[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        bw.write(solve(n)+"\n");
        bw.flush();
        bw.close();
    }
}
12865: 평범한 배낭
시도1

아래의 직사각형이 물건이라고 가정할떄 다음과 같이 하면 최댓값을 구할 수 있을것이라고 생각했다. 근데 아래와 같이 로직을 짜게 되면 
다음 예시에서 잘못된 답을 도출할 것이다.
3 5
3 4
2 1
1 100
104를 도출해야하는데 101을 도출한다.
그이유는 일단 감당할수있는 weight보다 합이 작으면 추가해주기때문이다.
추가해주는 값이 최대의 value를 보장한다고 말할수있는가?
없다.




import com.sun.jdi.request.BreakpointRequest;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static long dp[];
    //가방안에 넣는 물건을 정의한 class
    public static class Thing{
        //무게
        int weight;
        //가치
        int value;
        Thing(int w, int v){
            this.weight = w;
            this.value = v;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input[] = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int weight = Integer.parseInt(input[1]);
        Thing[] things = new Thing[n];
        for(int i=0;i resultList = new ArrayList();
        for(int i=0;i

시도2
아이템이 주르륵 나열되어있다고 생각하자. 그리고 아이템을 선택하거나 안할수있다.
그리고 선택을 하거나 안할때의 값을 생각해서 둘중에 더 큰것으로 매번 갱신한다면 최종결과를 얻을 수 있다. 하지만 이것을 재귀로한다면 시간초과가 날것이다. 일단 두개를 선택하는 경우에서도 2^n이나옴
dp[i] = dp[i-1]에 관한 식?
i만으로는 부족하다. 하나의 변수가 더있어야한다. 왜냐하면 idx가 -1이되면서 기준값이 되는 weight변수또한 변하기때문이다.
무게k에 들어갈수있는가치 v의 최댓값을 구해야한다.
v를 결과값이라고 생각해보고, 무게를 변수로 생각해보자.
또한 아이디어의 첫 시작이 i번째 물건을 챙길수도있고, 아닐수도있고니까
i와 k의 이차원배열로 만들고 그 결과값이 value여야한다

dp[i][w] = dp[i-1][w-wi]이런식으로 변수 두개를 받는 배열이 필요하다
dp[i][w]: i까지 물건을봤을때의 value의 최댓값.weight는 현재 w

이해안가는점
o(nW)의 시간복잡도를 가지는것은 이해하겠으나 이게 다항함수가 아니라고한다.
왜냐하면 w는 값자체의 범위를 표현하는것이기때문에 값하나를표현하려면 
값의개수가 n개라고 했을때 2^n = w이다 (왜지?)
w라는숫자가 들어올때 입력사이즈는 logW이다 (왜지?)
그러니까 o(n*2^n)인것이다
코드

public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input[] = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int weight = Integer.parseInt(input[1]);
        int dp[][] = new int[n+1][weight+1];
        int value[][] = new int[n+1][2];
        for(int i=1;i<=n;i++){
            String input2[] = br.readLine().split(" ");
            int w = Integer.parseInt(input2[0]);
            int v = Integer.parseInt(input2[1]);
            value[i][0] = w;
            value[i][1] = v;
        }
        //0부터 시작하면 dp[i-1][w]에 접근할떄 예외처리를 해주어야해서
        //1부터 시작하게끔 만들음

        for(int i=1;i<=n;i++){
            for(int w=1;w<=weight;w++){
                int valueW = value[i][0];
                if(w < valueW) dp[i][w] = dp[i-1][w];
                else{
                    dp[i][w] = Math.max(dp[i-1][w], value[i][1]+dp[i-1][w-valueW]);
                }
            }
        }
        bw.write(dp[n][weight]+"");
        bw.flush();
        bw.close();
    }
}
9251: LCS
int형으로 배열을 선언하게 되면 값이 0인것들은 모두 무시하게된다. 0일수도있는데..
그럼 재귀호출이 계속쌓이는것이다. 이게 그렇게 문제가 되는줄은 모르겠는데 문제가 되나보다.. 이해가 잘 안가긴한다.
점화식을 보고 그대로 식을 세웠다. 하지만 왜 점화식을 저렇게 세울 수 있는지 잘모르겠다
 다시꼭 풀어봐야겠다

https://minhamina.tistory.com/147



ch07
Mon, 16 Jan 2023 12:57:45 GMT
객체지향프로그래밍
상속

기존클래스들의 멤버변수, 메서드 모든정보를 다 알고있는 클래스를 또 하나 정의하여 추가적인 변수/메서들르 정의하는것포함

a를 가지고 있는 관계면 a를 포함관계에 집어넣는다. 즉, 멤버변수에 정의한다. 그런데 a가 A이다. 이런 is a 관계이면 a를 상속관계에 집어넣는다. extends를 사용함을 의미한다

오버라이딩

부모메서드를 자식에서 재정의하는것

부모 static메서드 오버라이딩

불가능하다. 만약 된다고 해도 이건 오버라이딩이 아니라 각 클래스에 별개의 static메서드를 정의한것이다

오버로딩

매개변수로 구분되는, 이름이 같은 메서드를 중복정의하는것

다중상속

예를들어 A클래스에도 a라는 멤버변수가 있고 B클래스에도 a라는 멤버변수가있을때 이 둘을 상속받는 C에서 a두개를 구분할 수 없다
관계들이 복잡해진다
복합적인 기능을 가지는 클래스 쉽게 작성가능
단일상속일 경우 다중상속보다 클래스의 관계가 명확해진다
다중상속을 사용할경우 상속말고 포함개념을 사용하여 멤버변수로 등록후 사용하자

object

A라는 클래스를 만들었다고하자. 모든 클래스의 조상은 object이기때문에 extends object라는 코드를 컴파일러가 자동으로 추가해준다

super

super()는 부모클래스 생성자를 뜻하며 자식생성자의 첫줄에서 실행되어야한다
왜냐하면 자식에서 부모의 변수/메서드 무언가를 사용할수도있기때문
모든클래스는 object로부터상속받는다. 이때문에 일단 생성자의첫줄은 부모를 호출하는거일수밖에없다
만약에 생성자를호출하는 코드가 아니더라도 컴파일러가 자동으로 인자가 없는 생성자를 삽입해준다

패키지

클래스들의 묶음

클래스의 실제이름은 패키지까지 포함한다

클래스는 물리적으로 하나의 .class 즉 클래스파일인것과 같이 패키지는 물리적으로는 하나의 디렉터리를 의미한다

하나의 소스파일에는 첫번째 문장으로 단 한번의 패키지 선언만 허용 package 패키지명;

모든 클래스는 반드시 하나의 패키지에 속해야한다

만약 패키지를 지정하지 않으면 이름없는 패키지에 속하게된다


import

다른패키지의 클래스를 사용하려면 아주 긴 패키지명.클래스명을 사용하여 매번 클래스를 사용할때 긴 이름을 사용해야한다.
import 를사용하면 컴파일러에게 패키지명을 알려주는거와 다름없어서
알아서 클래스명앞에 패키지명을 붙여준다import java.util.*;
import java.text.*;
//import java.*; 

마지막 문장이 1+2 번쨰 문장을 대신해주진않는다.
즉, 하위패키지의 클래스까지 포함해주는게 아니라 하나의 패키지내에있는 클래스들만 가능하다

static import

static멤버를 호출할때 클래스 이름을 생략할 수 있다import static java.lang.Math.random;
//System.out.println(Math.random());
System.out.println(random());//Math 생략


제어자

부가적인 의미를 부여하는 것
public, protected, static, final ..

접근제어자를 사용하는 이유

외부로부터 데이터의 접근을 적절히 제어해서 내부구현을 감추기 위해서
내부구현이 다드러나는 코드는 외부와 내부의 결합도가 커져서 유지보수가 어렵다
또한 사용하면안될곳에서도 사용이 일어날 수 있다final

클래스 final: 자식클래스 정의못함
메서드 final: 오버라이딩 못함
일반적으로 선언과 초기화를 동시에 해야하지만 인스턴스의 경우 생성자에서 초기화가 가능

abstract

클래스 abstract: 추상메서드를 가지고있음을 의미
메서드 abstract: 선언부만 작성하고 구현부는 작성하지 않았다라는것을 알림
추상클래스는 아직 미완성된 클래스임으로 인스턴스를 생성할수없다
다른클래스가 이 클래스를 상속받아서 원하는 일부의 메서드만 오버라이딩해도된다는 장점이있다. 만약 abstract이 없다면 구현내용을 비워도되는것을 매번 빈 구현을 다 정의해야한다는 번거로움이 있다.


왜 추상메서드를 정의?

추상메서드 선언 (abstract선언) 대신에 빈몸통을주고 그것을 구현하라고하면? -> 컴파일에러안나기때문에 개발자가깜빡하고 넘어갈수있음
구현을 강제하기 위해서 abstract선언이 포함된 추상메서드 선언을 해야함추상클래스 vs 인터페이스

추상 클래스는 그 추상 클래스를 상속받아서 기능을 이용하고, 확장시키는 데 있습니다. 반면에 인터페이스는 함수의 껍데기만 있는데, 그 이유는 그 함수의 구현을 강제하기 위해서 입니다
추상클래스란? 상속을 통해서 자손 클래스에서 완성하도록 유도하는 클래스
추상클래스는 IS - A "이다".
인터페이스는 HAS - A "을 할 수 있는".
이런식으로 추상클래스와 인터페이스를 구분하여 사용하게 되면 장점이 있다.
A라는 개념에 속해서 만들어지는 기능과 A'라는 포괄적인 기능을 사용하기때문에 할 수 있는 기능을 분리해주기때문에 서로다른 개념에 속하고 같은 기능을 사용한다고할때 유지보수가 수월하게 코드로 구현할수있게된다.
아래의 예제에서는 kevin과 tertile이 사람/동물로 다른 추상클래스를 가지지만 같은 인터페이스를 상속받으므로써 같은 동작을 수행할 수 있다


무엇을 언제 사용?

일반메서드 + 추상메서드를 쓴다면 추상클래스를, 추상메서드만 사용한다면 인터페이스를 사용하자

정리

추상클래스는 추상메서드를 가지고있는 클래스를 의미한다
추상메서드란무엇일까? 추상메서드란 구현부가 비어잇고 abstact라는 키워드가 붙은 메서드를 의미한다
추상클래스도 인터페이스의 역할을 할 수 있는데 둘을 구분하였다
이이유는 둘의 역할이 애초에 다르기때문이다.
추상클래스는 ~이다 의 관계일때 사용하고
인터페이스는 ~라는것을 할 수잇다 라는 관계일때 사용한다
이렇게 개념에 대한 구현과 기능에 대한 구현을 분리함으로써
다른 개념에 속하더라도 같은 기능을 할 수 있도록 코드를짜는게 가능해진다

생성자의 접근제어자

생성자에 접근제어자를 두면 싱글톤같은 패턴을 만들 수 있게 된다

싱글톤 패턴

왜 static class여야할까?

지금 new Singletone으로 쓰고있지만 사실은 


Main 클래스 인스턴스 생성
Main 클래스 인스턴스를 활용하여 싱글톤 인스턴스 만들기
과정을 거쳐야한다
그런데 바로 new를 통하여 생성하였으니 안되는것이다. 이를 해결하려면
s변수의 static선언해제
Singleton 클래스를 static선언하고 Main.singleton();사용
main클래스 인스턴스를 만든 뒤에 해당 인스턴스로 싱글톤 인스턴스 만들기정리



싱글톤클래스가 inner 클래스예요
이너클래스는 외부 클래스의 인스턴스가 생성된 이후에 생성돼요
그래서 저렇게 static변수에 자기 인스턴스를 할당할수없어요
왜냐하면 static 변수는 인스턴스 생성 이전에 할당돼야하니깐요
만약 그러고 싶다면 main인스턴스를 static으로 하나만든다음에 그 인스턴스로 싱글톤 인스턴스를 만들거나
class를 static으로 정의해서 main클래스 인스턴스 생성없이도 싱글톤클래스를 만들수있도록 해야해요

public class Main{
  //final 클래스-> 자식 클래스 정의못함
  //final을 붙여야 컴파일시점에 오류를 잡을 수 있음
  public final  class Singleton{
      //싱글톤 클래스가 내부클래스이기때문에 외부클래스 인스턴스를 생성해주든지
      //static으로 class를 선언하든지 해줘야함
      private static Main main = new Main();
      //static으로 변수를 선언해줘서 클래스의 인스턴스 생성없이도
      //그러니까 인스턴스 생성전에 클래스를 만드는것만으로도 인스턴스하나를 생성해서 가지고있어야함
      private static Singleton s = main.new Singleton();
      //외부로의 접근을 막는다 위코드에서 만든 인스턴스를 제외하고는 추가 인스턴스를 만들 수 없다
      private Singleton(){

      }
      //해당 메서드로만 인스턴스로의 접근이 가능하게하고 하나의 인스턴스를 매번 재활용해서 사용한다
      public static Singleton getInstance(){
          return s;
      }
  }
}


추가 알아둘 사항

static 메서드에 abstract붙일 수 없다. 
static메서드는 몸통이 있는 메서드에만 사용할 수 있기때문
오버라이딩 시 부모메서드보다 더 넓은 범위의 접근제어자를 사용해야한다
ㅈ다형성

여러가지 형태를 가질 수 있는 능력
부모타입의 참조변수로 자식인스턴스를 참조가능

참조변수타입vs 인스턴스타입
참조변수타입만큼 참조를 할 수 있고
인스턴스 타입만큼의 메모리가 확보된다
인스턴스타입을 자식만큼해도 참조변수를 부모로하면 부모만큼밖에 참조를 못한다
Parent p = new Child();//error 작은것 <- 큰것일때 error발생
Child c = new Parent();
Child c2 = (Child) p;//자식 참조변수가 자식 인스턴스가리킴
Parent p2 = (Parent) c;//부모 참조변수가 부모 인스턴스가리킴

상속에서의 형변환

자식->부모: 형변환생략가능
부모->자식: 형변환생략불가능 (더커질것이기때문에)
형변환은 참조변수의 타입을 변환하는것이지 인스턴스를 변환하는것이 아니다
형변환을 시킨다는것은 곧 내가 참조할 수있는 멤버의 개수를 조절하게 되는것이다
참조변수가 인스턴스를 가리킬때를 주의해야한다 작은것으로 큰것을 가리킬수없다. 어차피 참조를 못할거기때문에 컴파일에러가 발생한다

멤버변수와 멤버메서드

다음 코드에서(중복정의된 경우) 참조변수에 따라 멤버변수가 달라지는 반면 멤버메서드는 인스턴스에 따라 호출되는 메서드가 달라진다

보통은 캡슐화를 통해 getter, setter를 사용하는데 이렇게 멤버변수에 직접접근하게되면 참조변수의 타입에다라 사용되는 멤버변수가 달라질 수 있어서 조심해야한다
public static vodi main(){
  Parent p = new Child();
  Child c = new Child();

  System.out.println(p.x);//100
  p.print();//"자식"
  System.out.println(c.x);//200
  c.print();//"자식"
}
class Parent{
  int x = 100;
  void print(){
      System.out.println("부모");
  }
}
class Child{
  int x = 200;
  void print(){
      System.out.println("자식");
  }
}
매개변수의 다형성
public class Item{
      int price;
}
  public class Tv extends Item{}
  public class Computer extends Item{}
  public class Person{
      int money = 1000;
      public int buyTv(Tv tv){
          return money-tv.price;
      }
      public int buyComputer(Computer computer){
          return money-computer.price;
      }
      //앞의 두 메서드를 하나의 메서드로 처리가능
      public int buy(Item item){
          return money-item.price;
      }
  }

참조변수 하나로 자식인스턴스를 가리킬수있으니 자식인스턴스의 공통적인부분(부모클래스에 정의된 부분)은 다음과같이 공통코드로 대체가 가능하다

이때문에 부모참조변수를 통해 서로다른인스턴스타입의 배열을 만드는것도 가능


인터페이스

모든 멤버변수는 public static final 이다
모든 메서드는 public abstract이다
그리고 위의 제어자는 생략가능하다
인터페이스 끼리의 상속은 implements가 아니라 extends를 사용한다
인터페이스는 static상수만 정의할 수 있어서 부모의 멤버변수와 충돌할일이 거의없고 충돌해도 킄ㄹ래스이름붙여서 구분이 가능하다

다중상속을하고싶을때

비중이높은쪽을 상속받고 나머지 한쪽은 인터페이스로도 정의한다 
그리고 멤버변수로 나머지한쪽에 대한 인스턴스를 만들어서
인터페이스를 구현하는 메서드 내부에서 인스턴스로 내부 메서드들을 호출한다

인터페이스를 이용한 다형성
fightable을 구현한 fighter class가 있다고 가정하다
Fightable f = new Fighter();//가능
public void attach(Fightable f){...}//매개변수로도 사용가능
public Fightable method(){...}//리턴타입으로 정의하는것도 가능
//Fightable 을 구현한 구현체의 인스턴스를 넘겨주어야함
return타입이 인터페이스라는것은?

해당 인터페이스를 구현한 클래스의 인스턴스를 반환한다는 의미

인터페이스의장점

개발시간단축
ㄴ 설계도를 바탕으로 각자 설계도에 맞는 코드를 짜면되니까 나눠서 업무를 하기에 좋다
서로관계없는 클래스들에게 관계를 맺어줄 수 있다
ㄴ 서로 상속관계도 아닌 클래스들에게 하나의 인터페이스를 구현하여 공통의 기능을 구현시킬 수 있다
직접적인 관계를 간접적으로 만들 수 있다class A{
  public void print(B b){
      b.print();
  }
}
class B{
  public void print(){
      System.out.println("BB");
  }
}
class A{
  //B와의 직접적인 연관이 끊어졌다
  public void print(I i){
      i.print();
  }
}
class B implements I{
  public void(){
      System.out.println("BB");
  }
}
//추가적인 클래스
class C implements I{
  public void(){
      System.out.println("CC");
  }
}

B의 내용이 변경되어도 A에게 영향이 가지 않는 간접적인 관계가 되었다

디폴트 메서드

인터페이스에 메서드를 추가하게 되면 해당 인터페이스를 구현한 모든 클래스에 대해 선언을 또 해주어야한다

인터페이스에 추가메서드가 생길경우 디폴트 메서드로 정의해준다
그러면 이를 모든 클래스에서 사용할 수 있다

여러 인터페이스에서 디폴트 메서드 간의 충돌이 일어나면 구현클래스에서 해당 메서드를 오버라이딩해주어야한다(컴파일에러남)

디폴트 메서드와 디폴트메서드가 포함된 인터페이스를 구현하는 클래스의 메서드간 충돌이 일어난다면 디폴트 메서드는 무시된다
interface C {
      default void print(){
          System.out.println("C");
      }
}
  interface B extends C{
      default void print(){
          System.out.println("B");
      }
  }
  static class Fighter implements B{

  }
  public static void main(String[] args) throws IOException {

      Fighter ff = new Fighter();
      ff.print();//"B"
  }





```java
 interface C {
        default void print(){
            System.out.println("C");
        }
 }
    interface B extends C{
        default void print(){
            System.out.println("B");
        }
    }
    static class Fighter implements B{
        //추가된 코드
         public void print(){
            System.out.println("Fighter");
        }
    }
    public static void main(String[] args) throws IOException {

        Fighter ff = new Fighter();
        ff.print();//"Fighter"
    }
내부메서드

두 클래스가 긴밀한 관계일때 사용
내부클래스에서 외부클래스의 멤버에 쉽게 접근가능
외부로부터 불필요한 클래스(내부클래스)를 감출 수 있다(캡슐화)

내부클래스의 종류

선언된 위치에 따라 구분할 수 있다


인스턴스 클래스: 멤버변수 위치
스태틱 클래스: static 멤버변수 위치
지역 클래스
익명클래스

static클래스의 내부클래스로 인스턴스 non-static이 가능할까?

가능하다import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;



public class Main{
     static class outerClass{
        class innerClass{
            int x1;
            static int x2 = 2;
        }
        static class staticInnerClass{
            int x1 = 1;
            static int x2 = 2;
        }
        public static void print(){
            System.out.println(innerClass.x2);
        }
}
public static void main(String[] args) throws IOException {
    outerClass class1 = new outerClass();
    outerClass.innerClass class2 = class1.new innerClass();
    class2.x1 = 2;
    outerClass.innerClass class4 = class1.new innerClass();
    class4.x1 = 4;
    System.out.println(class2.x1);
    System.out.println(class4.x1);
}
}
출력결과 2 와 4 가 나온다.
```java
import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
     static class outerClass{
         int x;
        class innerClass{
            int x1;
            static int x2 = 2;
        }
        static class staticInnerClass{
            int x1 = 1;
            static int x2 = 2;
        }
        public static void print(){
            System.out.println(innerClass.x2);
        }

    }
    public static void main(String[] args) throws IOException {
        outerClass class1 = new outerClass();
        class1.x = 2;
        outerClass class2 = new outerClass();
        class2.x = 3;
        System.out.println(class1.x);
        System.out.println(class2.x);
    }
}
출력결과 2와 3이나온다
static의 내부에 있다고 무조건 다 static이 되는것이 아니다.
class단위에 static이 붙는다는것은 외부클래스 참조없이 만들수있다! 만을 의미하는것가탇
Main없이 new로 바로 outerClass를 생성할 수 있는 그정도의 의미를 갖고있는것같다
그래서 다음코드도 false가 나온다.
static class는 인스턴스가 생성되는영역인 heap에 생긴다
static영역에 생기지않는다
익명클래스

이름이 없는 클래스로 이름이 없어서 생성자도 가질 수 없고, 상속받는 인터페이스 혹은 클래스 하나만 사용해서 만들 수 있다. 익명클래스는 이름이 없기때문에 컴파일을 하면 외부클래스명$숫자.class라는 이름으로 클래스파일이름이 결정된다


https://brunch.co.kr/@kd4/6
https://myjamong.tistory.com/150