[필수1]백준 풀이 알고리즘 템플릿 - java

사용할 알고리즘들의 템플릿들을 정리하겠다.

물론 약간의 알고리즘 해석만을 동반하며, 자세한 해석은 아래 링크를 달아두겠다.

• 참고 링크 : 구글링 등등

시간복잡도

• 컴퓨터가 대략 1억 번의 계산이 1초 내에 가능하다고 기억(실제론 좀 더 계산)

  복잡도 표

  
  

공간복잡도

• 512MB = 1.2억개의 int

본인이 생각하는 알고리즘 풀이 과정

• 무조건 알고리즘 분석할 때 “종이, 펜 활용” 하여 “복잡도” 분석
  • 완.탐 복잡도는?? -> 가능하다면 “순.조.부 + 상태트리(BFS,DFS)” 생각 -> “순.조.부 파트“
    -> 완.탐이 가능하다면 완.탐을 우선 해답 도출 후 성능 개선을 추천
    -> 순.조.부로 문제해석 힘들때 “상태트리” 그려보면 풀이 떠오를 수 있음
  • 불가능하다면, 혹시 적절한 자료구조는?? => 아래 자료구조 정리 참고
  • 또는 완.탐 생각할 필요없이 “단순구현” 인지?? => 아래 시뮬레이션 정리 참고
  • 복잡도 너무큰데 해결안되면 “DP(for, memoi)” 고려 -> “DP 여러가지 유형“
    • DP, 그리디를 함께 고려하면 좋은데 그리디는 “반례가없다”를 증명하는것이 어려워서 “확신”이 없으면 PASS 하는것을 추천
    • 참고로 그리디 유형에 우리가 아는 알고리즘이 많다.
      • 프림, 크루스칼, 다익스트라, 플로이드, 힙 등 -> “코드 암기“
  • 최단거리 같으면 “BFS와 다익스트라, 플로이드” 고려 (각각 상황에 맞게 사용하게 됨)
    • 최단 경로 트리, 보는김에 이것도 확인 -> 최소 신장 트리
  • “그래프”, 트리 종류 같다면?? 아래 필수 고려(+BFS, DFS)
    • 정점 중심 : 인접행렬(밀집행렬) or 인접리스트(희소행렬)
      • 최소신장트리 : 프림(우선순위 큐)
      • 최단경로 : 다익스트라(우선순위 큐+new dist배열), 플로이드(3중 for문+new 인접행렬)
    • 간선 중심 : 간선리스트
      • 최소신장트리 : 크루스칼(Union find)
      • 최단경로 : 벨만포드
  • 완.탐, 순.조.부, 최단경로 . . . -> 다양한 예시 참고
    • BFS, DFS -> 최단거리는 꼭 “BFS”!!
    • 백트래킹(Backtracking) -> DFS(재귀) 사용중
    • Branch-and-Bound(분기한정법)
• 문제를 꼭 “자세히” 읽고, “조건 잘 확인”
  • 타입 애매하다? long 사용
  • 입력좌표는 (1,1) 또는 (0,0) 인가?? + (x,y) 형태가 (행,열) 또는 (열,행) 인가??
• 필수 코드 암기 : 알고리즘 필수 코드암기

아래 자료구조 정도는 기억

• 스택&큐&덱, 해시맵, 우선순위 큐(+정렬), 무한대 자료형
  • 큐 ArrayDeque 상용할것 -> LinkedList 보다 빠름
    Stack<Integer> st = new ArrayDeque<>();
Queue<Integer> qu = new ArrayDeque<>();
Deque<Integer> qu = new ArrayDeque<>();
    • 스택은 push, pop, peek
    • 큐는 offer, poll, peek
    • 덱은 큐에 First, Last만 추가 -> ex: offerFirst, pollFirst, peekFirst …
    • 아래 정리된 코드들은 “옛날코드” 많아서 햇갈리지 말것(스택, 큐)
  • 해시맵 : 배열 시간초과.. 정렬.. 필요없고 키,값 형태?? HashMap 사용 이런느낌!
    • get, put, keySet().iterator() 와 .next() 정돈 알고 있자
    • 해시 잘 활용한 문제 -> 백준1620
  • 우선순위 큐 -> 백준 나무 재테크, 이차원 배열과 연산 참고 -> 정렬 커스텀 중요
    • compareTo 오버라이딩 직접 하는게 빠름 -> 예로 implements Comparable<>
    • !qu.isEmpty() 보다 size 미리 구해서 사용이 빠름
    • 우선순위 큐 최대한 낭비없이 사용 권장 -> 그냥 큐도 마찬가지
    • 정리 참고 -> “우선순위 큐“
  • 무한대 자료형: BigInteger 사용 dp[0]=BigInteger.valueOf(0) 이나 dp[i-1].add(dp[i-2]) 처럼 특정 메소드를 사용!
    • 예시 문제: 피보나치수4
• 트리, 그래프 -> “트리“
  • 탐색부분 체크(트리탐색-BFS,DFS,이진트리순회)
  • 간선의 수에 따라 인접행렬, 인접리스트를 선택한다. 보통 인접리스트 많이 사용
    • V^2 보다 E가 많이 작을수록(희소행렬) 인접리스트!! 반대는 인접행렬
  • 트리 -> “중복방문(visited) 걱정없음” -> 사이클 구조가 될 수 없기 때문!
    • 힙 - “완전이진트리” + “위 아래 관계” / 힙 응용 - 우선순위 큐
    • 이진검색트리(=BST) - “좌 우 관계”(정렬유지) / + RBT(정렬유지)
    • 이진트리 - 자식2개씩 / 포화이진트리 - 꽉찬것 / 완전이진트리 - “왼쪽”부터 이진트리
  • 그래프 -> “중복방문(visited) 주의” -> 사이클 탐색(찾기) : visited[], finished[] 사용 -> 백준9466_텀 프로젝트
    • dfs(1) 실행 : dfs(1)->dfs(2)->dfs(3)->dfs(1) 사이클때 dfs(1) 시점에 finished[]가 false라서 사이클 확인이 가능
      dfs(3)->dfs(2)->dfs(1) 순서로 탐색 종료 처리됨(=finished[]가 true되는 순서)
  • 최단경로트리 vs 최소신장트리
    • 비슷한 것 같지만 “서로를 보장(관계)하지 않음”
      -> 최단경로라면 꼭 최소신장이고 이런 관계까지 보장하지는 않는다는 것
    • 최단경로트리 -> 멀리 돌아가더라도 거리(가중치)가 가장 짧은것
      • 최단 경로 트리
      • 다익스트라(코드기억) : 하나의 정점에서 다른 모든 정점으로의 최단경로 -> 우선순위 큐 + 최소거리 배열
        • TIP1) X->N 경로 입력 주어지고, 역방향으로 일부러 입력받고아서 N->X였던것을 X-N으로 최단경로구하면 결국 N->X로 최단경로 구해진 값과 동일하다는 개념 (X로 가는 최단경로)
        • TIP2) N->X 최단경로를 구할 때 차라리 다익스트라를 N번 하는것도 방법 -> N*ElgE 복잡도
      • 플로이드(코드기억) : 모든 정점에서 다른 모든 정점으로의 최단경로 -> 3중 for문 + 인접행렬
      • 벨만포드 : 다익스트라는 양수만, 벨만포드는 음수도 최단경로 사용 가능
        • 근데, 벨만포드까지는 코테 잘 안나올것 같아서 나중에 시간나면 보는걸로..
    • 최소신장트리 -> 돌아가는것을 고려하지 않고 인접 정점들 중 거리(가중치)가 가장 짧은것
      사이클X로 모든노드 연결된 상태 -> 루트노드는 모든노드에 연결 되므로 루트노드 갈 수 있으면 “신장트리”가 될 수 있다.
      최소신장트리는 모든 정점을 “연결”하는데 의의가 있다.
      • 최소 신장 트리
      • 프림(코드기억) -> 우선순위 큐
      • 크루스칼(코드기억) -> Union find
        • TIP1) 모든 노드를 조회하는데 최악이나 최선의 비용일 때 MST 활용
          백준13418 의 경우 “오르막길(최악)”, “내리막길(최선)”을 각각 1, 0으로 임의로 입력받고,
          임의로 입력받은 간선을 “오름차순, 내림차순”으로 따로 정렬후 MST를 각각 진행해서 최선, 최악 비용을 구해낼 수 있다.
• 위상정렬(코드기억) -> 간단하니 이것도 기억해두자..! -> 위상정렬
  • outArr배열을 dp배열처럼 사용 : bottom-top 방식DP의 “for문” 이 “위상정렬” 로 치환으로 이해하자
  • 이분탐색 : binarySearch, lower_bound, upper_bound 직접 구현 방법 기억
• 정리해둔 이분탐색 목차 참고 -> “자바의 binarySearch“
  • 응용 문제 (LIS) -> “가장 긴 증가하는 부분 수열 5“
• +개념참고) 최장 증가 부분 수열(LIS) + 최장 공통 부분 수열(LCS) -> increasing, common

자주 나오는 로직은 그냥 외우자 -> "시뮬레이션(구현)"

• EX0) “정렬 암기” -> Long.compare(a.x, b.x) 는 a.x < b.x ? -1 : (a.x==b.x?0:1) 와 동일
  String은 A.compareTo(B) 활용! (이미 구현된 메소드임)
  • 정렬은 “객체” 사용시 객체 class에 오버라이딩 추천,
    “기본타입” 사용시 바로 오버라이딩 추천 -> 익명 클래스 사용보단 간편한 람다 추천
  • 참고) Arrays.sort(Quick), Collections.sort(Merge)
  • 참고) lambda 는 @FunctionalInterface 인 경우에만 사용가능 -> ex : Comparator
    • @FunctionalInterface는 추상 메소드가 1개만 있는것을 보장
  • 정렬 코드 예시

  • // lambda -> 추천!! -> start, end 처럼 "구간 설정"도 가능!!(중요)
    Arrays.sort(inArr, start, end, (n1, n2) -> n1-n2);
    PriorityQueue<integer> qu = new PriorityQueue<>((n1,n2)->n1-n2);
    // 익명함수(클래스) -> 비추
    PriorityQueue<Node> qu = new PriorityQueue<>( new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) { return o1.x - o2.x; }
    }
    // 객체 class에 바로 오버라이딩 -> 추천!!
    static class Node implements Comparable<Node> { 
    	// 정렬 TIP -> 메소드 사용할지 말지는 자유
        // Long.compare(a.x, b.x) 는 a.x < b.x ? -1 : (a.x==b.x?0:1) 와 동일
    	@Override
        public int compareTo(Node o) { return this.y - o.y; }
    }
    

  • 문자열 비교 equals, hasCode 오버라이딩 예시 -> 이것도 객체 만들었다면 필수 필수!! -> Set같은 중복제거 자료구조 사용 시 무조건 오버라이딩 필요
    • 첫번째 코드는 좀 더 유연하긴 하다. (instanceof 는 Item 클래스의 서브 클래스도 포함해줌)
    • 두번째 코드는 좀 더 엄격해서 권장! (동일 클래스만 포함) -> 이걸 기억!

    • @Override
      public int hasCode() {
          return Objects.hash(itemId, itemNm);
      }
      @Override
      public boolean equals(Object obj) {
          if (obj instanceof Item) {
              Item item = (Item) obj;
              if(this.itemId == Item.itemId && this.itemNm.equals(item.itemNm)) {
                  return true;
              }
              return false;
          }
          return false;
      }
      

    • static class Pair{
          char a; char b;
          public Pair(char a, char b) {
              this.a=a; this.b=b;
          }
          @Override
          public boolean equals(Object obj){
              if (this==obj) return true;
              if (obj == null || this.getClass() != obj.getClass()) return false;
              Pair p = (Pair) obj;
              return this.a==p.a && this.b==p.b;
          }
          @Override
          public int hashCode() {
              return Objects.hash(a, b); //hashCode 도 필수
          }
      }
      

• EX1) 2차원 배열 회전 로직?? 반시계: B[x][y]=A[N-1-y][x], 시계: B[x][y]=A[y][M-1-x]
  • 단 x,y가 0부터 시작 -> N-1, M-1은 끝자리 인덱스 의미
  • 실제로 좌표 그려보면서 구하면 공식을 금방 도출할 수 있다.
  • 추가1) 배열돌리기1 같은 회전 로직은 rotate(x, y, N, M) 로 회전로직 구현해놓고,
    • 여러 시작점(x,y), 끝점(N,M) 을 줘서 함수를 재사용!
  • 추가2) “범위체크+visited”로 구현 가능하다.
    • 좌표 원복하고 방향 전환하는 형식이 될 것이다.
  • 추가3) 분할정복 Z, 곱셈(똑같은 크기로 분할 때) -> 좌표이동 ( + 크기 활용 )
    • x+=N 이나 y+=N 같이 좌표 이동을 하되 특정한 크기(N) 을 사용한 이동
    • 최적화 : 원하는값 있는 부분으로만 분할정복
• EX2) dx, dy로 1칸씩 같던 것을 끝까지 이동(while)하는것 -> dx, dy를 좌표에 더할수록 해당 방향으로 계속 이동 가능하단 점을 알아두자
  • 추가1) 2048 or 모노미노도미노2 처럼 끝까지 이동(while) + 범위 넘으면 원복(–) 방식 괜찮음
  • 이것을 “하나의 함수” 로 구성하여 “각각의 좌표나 행,열”로 각각 재사용 추천
  • “오른쪽 방향일때 오른쪽부터 접근해야하는가” 이런것도 꼭 고려!
• EX3) 투포인터의 개념을 잘 생각 -> 두개의 배열을 인덱스 따로 하여 따로 동작하고 싶을때도 있기에 이 개념을 기억해두자
  • 용액_2467 백준
• EX4) 배열의 인덱스를 실제 숫자로 치환하여 생각하는 방식 -> 숫자 빈도수 구하거나 등등…
• EX5) “빈도수” 구할때 List[] 도 있지만, HashMap 에 담으려 노력해보자 (자료구조 활용)
  • Map<Integer, Integer> map = new HashMap<>(); // <number, count>
  • hm.put("java", hm.getOrDefault("java", 0)+1); -> put, get 함수 기억

  • Map<Character, Set<Character>> neighborMap = new HashMap<>();
    Set<Character> neighbors = bfs(i, j);
    char country = grid[i][j];
    if(neighborMap.get(country) == null) {
        neighborMap.put(country, neighbors);
    }
    else {
        for (Character c : neighbors) {
            neighborMap.get(country).add(c);
        }
    }
    //위 코드를 한줄로 만들어주는 computeIfAbsent 메소드도 기억
    neighborMap.computeIfAbsent(country, k -> new HashSet<>()).addAll(neighbors);
    

  • HashSet은 중복제거에 활용하기 좋다!! -> 객체는 equals, hashCode 필수!

    • Set<Pair> uniquePairs = new HashSet<>();
      for (char neighbor : neighbors) {
          if (country < neighbor) { //asc
              uniquePairs.add(new Pair(country, neighbor));
          } else {
              uniquePairs.add(new Pair(neighbor, country));
          }
      }//A-B, B-A 구분은 사전 순 정렬로 해결하여 중복을 방지 (오버라이딩 필수)
      

    • 사용자 클래스의 경우 오버라이딩 안하면 중복 검증에 실패한다. 일반 타입은 당연히 성공하고!
• EX6) 보통 “시뮬레이션”은 복잡도가 높지않아 배열 상태를 매번 새로 복제 잘 고려 -> 한번씩 이런 사소한 할당에서 문제가 발생
  • int[][] backup = new int[10][10];
  • 이후에 backtracking 에 사용할 수도 있으니 이런 복제도 잘 고려
• EX7) 2차원 좌표 구간합 방식 -> sum[i-1][j] 와 현재 가로방향(->) 누적값 과 inArr[i][j] 현재값 이 필요
  • 즉, sum[i][j] = sum[i-1][j](바로위) + 해당 i행의 가로방향(->) 누적값 + inArr[i][j]
  • 아래 그림처럼 노랑,파랑,분홍 네모 영역 확장처럼 2차원 좌표 구간합 생성
  • 
• EX8) 반시계는 시계방향 3번과 동일하다 -> 단, 90도일때!! 90도 아니면 해당아님!!
• EX9) 슬라이딩 윈도우 알고리즘 (Sliding Window)
  • DNA 비밀번호 -> 참고로 “부분문자열” 은 연속이다.
  • 맨 앞 문자는 제거, 새문자가 맨 뒤에 추가 -> 핵심

  • // "AAACGCTT" 문자열 주어진다 가정
    // S:전체 문자열 길이 (ex: AAACGCTT->8)
    // P:전체 문자열에서 뽑을 부분 문자열 길이
    // dna[]는 "AAACGCTT" 같은 문자열 배열 (ex: dna[0]='A', dna[4]='G')
    // cnt[]는 빈도수 배열 -> A,C,G,T 외 나머지 문자위치는 Dummy
    static void solve() { 
        // 맨 앞 P개 처리 
        for(int i=0; i<P; i++) cnt[ dna[i]-'A' ]++;
        check();
        // P 이후 한 개씩 처리
        // 이전 P개 중 "맨 앞 문자는 제거, 새문자가 맨 뒤에 추가" -> Sliding Window
        for(int i=P; i<S; i++) {
            // 맨 앞 (제거)
            cnt[ dna[i-P]-'A' ]--;
            // 맨 뒤 (새로운) (추가)
            cnt[ dna[i]-'A' ]++;
            check();
        }
    }
    //
    //Sliding Window 시각화
    // - 전체 문자열: "AAACGCTT"
    // - 부분 문자열 길이 3가정
    //알고리즘 적용: AAA -> AAC -> ACG -> CGC -> GCT -> CTT
    //
    

• EX10) 테스트케이스(입력)가 몇개인지 모를 때

• BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  //테케가 몇개인지 모를 때
  while(true) {
      String t = br.readLine();
      if ( t==null || t.length()==0 ) break;
      //풀이...
  }
  

• EX11) 2차원 배열에서 동일한 행,열 뿐만아니라 “대각선” 유무 알아낼 때
  • Math.abs(p.x - nx) == Math.abs(p.y - ny) : 행차이와 열차이가 같다면 “같은 대각선 상에 존재”
  • 대표로 N-Queen 문제 참고!!
• EX12) 참고 : “중위 표기식 -> 후위 표기식 변환법”과 “후위 표기식 계산” 방법
  • A+B*C-D/E 를 ABC*+DE/- 로 변환법??
    • “연산자 스택”에 top이 자신보다 우선순위 낮은 연산자일때까지 pop(+아웃풋) 후 push - 후위표기식
      • ”(“ 연산자는 코드보면 젤 낮은 우선순위로 보고 있음.
    • “피연산자”는 스택 없이 바로 아웃풋임!
  • ABC*+DE/- 계산법 ??
    • “스택”에 ‘A’,’B’,’C’ 넣다가 연산자(‘*’) 만나는순간 B*C로 연산후 다시 스택에 push

디버깅에 활용 추천 메소드! + 간단한 FileInput

• 1차원 : System.out.println(Arrays.toString(inArr));
• 2차원 : for문과 System.out.println(Arrays.toString(inArr[i]));
• System.setIn(new FileInputStream("input.txt"));
• 객체 출력에는 toString 오버라이딩 추천 -> 범위지정?? Arrays.copyOfRange 활용
• 실제 디버깅 팁
  • 이클립스 : F8 브레이크포인트 이동, F6 함수단위 이동, F5 한줄씩 이동
  • if문 넣어서 원하는 곳에 한번에 이동(브레이크포인트 함께사용)
  • 보고싶은 변수 드래그하면 한번에 볼 수 있음

// 실제로 아래 4줄이 1줄로 줄어듬!
//for(int j=1; j<=N; j++) {
//System.out.print(inArr[j]+" ");
//}
//System.out.println();
System.out.println(Arrays.toString(inArr)); // 1차원
System.out.println(Arrays.toString(Arrays.copyOfRange(dp[i], 0, K+1))); // 2차원(범위 지정)

// 파입 입출력을 System.in 으로 사용 가능하게 설정
System.setIn(new FileInputStream("input.txt"));

// toString 오버라이딩으로 객체 내용 보기 간편
@Override
public String toString() { return "Node [y=" + y + ", x=" + x + "]"; }

Template

반드시 백준에 제출할 때는 클래스명 : Main

package는 꼭 주석 or 제거

// 포괄적인 라이브러리 선언
import java.util.*;
import java.io.*;

순.조.부 + 비트 연산

비트연산 총 3가지 -> 바이너리카운팅과 비트마스킹과 Next Permutation을 소개 (참고정도만!)

무엇보다 순열.조합.부분집합의 이해가 굉장히 중요 + BFS,DFS와 함께 상태공간트리 까지

생각의흐름 - 순.조.부(+BFS,DFS) + 상태공간트리

Intro에서도 언급했지만, 본인의 경우 완.탐 복잡도라면 “순.조.부 + 상태트리(+BFS,DFS)” 생각

-> 꼭 완.탐이 가능하다면 완.탐을 우선 해답 도출 후 성능 개선을 추천

-> 모든 경우의 수를 생성하기 때문에 느리지만, 해답을 못찾을 확률이 작기 때문

“암기”

• 순열 → visited 활용(backtracking) -> 반복문은 for i,j,k ... if(i != j) if(i != k && j != k) ...
• 중복 순열 → visited 뺄 수 있음 (구현 더 간단)
• 조합 → idx+1 (visited 없이 가능) -> 반복문은 for i=1, j=i+1, k=j+1 ...
• 중복조합 → idx (조합과 한끗차이)
• 부분집합 → visited의 T/F 에 재귀 2개 사용
• for문으로 되는지부터 판단 -> for문으로 간단히 해결 문제 많음
  • 순열 조차도 for문으로 표현 가능 -> {1,2,3} 정도 크기라면 3중 for문으로 가능
  • 단, 가변인가 고정인가도 중요 -> 만약 nPr 에서 r에 따라
    • r이 2~3개 내외 고정된 경우 → 반복문 중첩구현 간단
    • r이 크거나 가변된 경우 → 재귀 가 더 간단
• 참고) 시간복잡도
  • 순열은 n의 수가 10보다 클 경우 순열 문제가 아닐 가능성이 높음
    • 순열의 시간복잡도 n!
  • 조합은 n=30, r=15일 경우 약 1억 5천 → ₃₀C₁₅ = 155117520
  • 부분 집합은 n이 30일 경우
    • 2^20은 약 100만, 2^30은 약 10억

순열(=permutation), 중복순열(개념중요)

“순서”가 의미 있는지, 뽑힌 애들의 각 “자리”가 의미 있는지 ⇒ 순열
사전: n개 중 r개를 뽑아서 일렬로 나열하는 것

기호 : nPr, _nπ_r

• “중복순열, 중복조합은?” -> 중복이 존재하는것 (EX : 112)

  • 중복순열, 중복조합 의 경우 r이 n보다 클 수 있다. 참고문헌
  • 아래의 “주사위 윷놀이” 문제를 보면 게임의 모든 경우의수는,
    • “말4마리” 와 “10개자리” 로써 {1,1,1,1}, {1,1,1,2} … 로써 “중복순열”
    • 이때 n을 4, r을 10으로 볼 수 있겠다. -> ₄π₁₀
    • 또한 4*4*4*4*4... 니까 4^n

• 예시 문제

  • 순열 : N과 M (1), SWEA_6808. 규영이와 인영이의 카드게임
  • 중복순열 : 주사위 윷놀이

• 예시 코드 -> 반복문은 노션에서 참고

  • // 순열 nPm
    perm(int depth) {
        if(depth == M) {
            // 순열 생성 완료
        }
        for(int i=1; i<=N; i++) {
            if(visited[i]) continue;
            visited[i]=true;
            outArr[depth] = i;
            perm(depth+1);
            visited[i]=false; //backtracking
        }
    }
    // 중복순열
    perm(int depth) {
        if(depth == M) {
            // 중복순열 생성 완료
        }
        for(int i=1; i<=N; i++) {
            outArr[depth] = i;
            perm(depth+1);
        }
    }
    

  • // i와 depth 구분 -> 무엇이 고정이고, 무엇이 가변인지(순열)
    // 참고 : inArr(규영) "고정", inArr2(인영) "순열"
    public static int[] inArr = new int[9]; // 규영
    public static int[] inArr2 = new int[9]; // 인영
    public static boolean[] visited = new boolean[9];
    public static int win, lose;
        
    public static void dfs(int depth, int gu, int in) {
        //base condition
        if(depth == 9) {
            if(gu > in) win++;
            if(in > gu) lose++;
            return;
        }
        //recursion
        for(int i=0; i<9; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            if(inArr[depth] < inArr2[i]) { // depth, i 확실하게 이해할 것!
                dfs(depth+1, gu, in+inArr[depth]+inArr2[i]);
            } else {
                dfs(depth+1, gu+inArr[depth]+inArr2[i], in);
            }
            visited[i] = false;
        }
    }
    

• 예시 트리

  • 순열 -> “순서(자리)”
    • 
  • 중복순열 -> “순서 + 중복까지”
    • 

조합(=combination), 중복조합(개념중요) -> 부분집합에 포함되는 특징

“순서”가 의미 없는지, 뽑힌 애들의 각 “자리”가 의미 없는지 ⇒ 조합 사전: n개 중 순서를 생각하지 않고 r개를 택하는 것

기호 : nCr, nHr

• 즉, “ABC” 와 “BAC” 가 (순서)의미있냐? 없으면 조합

• “중복순열, 중복조합은?” -> 중복이 존재하는것 (EX : 112)

  • 중복순열, 중복조합 의 경우 r이 n보다 클 수 있다. 참고문헌

• 예시 문제

  • 조합 : N과 M (2), 백설 공주와 일곱 난쟁이, 스타트와 링크
    • 주사위를 3번 던져서 모두 다른 수가 나올 수 있는 모든 경우
      (단, 123, 132, 321 와 같은 경우는 중복되는 경우로 봄)
    • 구성 : 동일, 순서 : 다름 -> ₆C₃
  • 중복조합 : N과 M (4)
    • 주사위를 3번 던진 결과가 다음과 같이 중복 되는 경우를 제외하고 나올 수 있는 모든 경우
      (112, 121, 211 -> 중복되는 경우)
    • 구성 : 동일, 순서 : 다름 + 중복(112) -> ₆H₃

• 예시 코드 -> 반복문은 노션에서 참고
  아래 코드엔 없지만 당연히 visited 써서 풀어도 됨 -> 참고: 재귀파트 바로 앞 DFS코드

  • // 조합 nCm
    comb(int depth, int idx) {
        if(depth == M) {
            // 조합 생성 완료
        }
        for(int i=idx; i<=N; i++) {
            outArr[depth] = i;
            comb(depth+1, i+1);
        }
    }
    // 중복조합
    comb(int depth, int idx) {
        if(depth == M) {
            // 중복조합 생성 완료
        }
        for(int i=idx; i<=N; i++) {
            outArr[depth] = i;
            comb(depth+1, i); // 이 차이밖에 없음. 한끗차이
        }
    }
    // 참고) 조합 또다른 방식
    comb(depth+1, idx+1); // 현재 선택 OK 다음 자리 이동
    comb(depth, idx+1); // 현재 선택 X
    

• 예시 트리

  • 조합 -> “순서(자리) 의미X”
    • 
  • 중복조합 -> “순서 없으며 + 중복까지”
    • 

부분집합(=subset)-> 조합과 유사

“있다 or 없다” 로 경우의 수를 구하면 -> 부분집합
사전: 어떠한 집합이 다른 집합의 부분

기호 : ⊂ 또는 ⊃

• 집합에 포함된 원소들을 “선택”하는 것

• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.

• power set(=멱집합) : 집합론에서 멱집합은 주어진 집합의 모든 부분 집합들로 구성된 집합

• 예시 문제

  • 냅색 -> “선택/비선택” 표현 가능하니까
  • 도영이가… -> 문제 지문 중에 “적절히 섞어서” 이런 지문도 부분집합으로 해석 가능.
    • _NC₁, _NC₂, _NC₃, …, _NC_n 이런식으로 탐색하라고 해석 되니까!
  • 만약 공집합도 포함이면??
    • _NC₀ 까지 포함하는 것

• 예시 코드 -> for문은 노션에서 참고

  • subset(int depth) {
        if(depth == N) {
            // 부분집합 완성
        }
        visited[depth] = true;
        dfs(depth+1);
        visited[depth] = false;
        dfs(depth+1);    
    }
    

• 예시 트리 -> 선택, 비선택이니까 이진트리를 생각하면 된다. 2ⁿ

  • 

하나의 문제를 풀때 무조건 한가지 방식인게 아니다. 예로 “햄버거 다이어트” 라는 SWEA 문제를 보면,

“조합” 으로 해결 -> 무게를 기저조건으로

“부분집합” 으로 해결 -> N(재료개수)를 기저조건으로

심지어 냅색 유형의 DP로도 충분히 풀이가 될 수 있다.

비트연산

참고 정도로 알아두자 -> 비트마스킹+메모이제이션(DP) 로 방문배열 대신 비트마스킹을 써야하는 경우가 있다

• 예를들어 dp[i | 1<<k] 같이 메모이제이션의 매개변수로 사용하는경우 일반 방문배열(visited[])로는 할 수 없다.
• 아마 가능하다 해도 메모리나 시간초과가 뜨게 로직을 구현해야 할것이다.
• 따라서 “dp의 매개변수로 비트마스킹을 사용하는 경우” 로 기억하자. -> 백준-외판원 순회

기본 비트연산 방법은 구글에 검색해서 확인.

비트 시프트 연산의 출력값을 간단하게 계산하는법 : 2^k 로 생각

• 2 << 3 이면 2*2^3
• 2 >> 3 이면 2/2^3
  • 1<<3 이면 k=2^3 => 1*2^3 = 8
  • 2<<3 이면 k=2^3 => 2*2^3 = 16
  • 3<<3 이면 k=2^3 => 3*2^3 = 24

& : 특정 자리가 0인지 1인지 확인하고 싶을 때 사용

| : 특정 자리를 1로 변경

<< : 자리(크기) 역할

바이너리 카운팅(Binary Counting), 비트 마스킹(bit mask), 다음순열(Next Permutation) 소개

바이너리 카운팅(Binary Counting)

2진수로 경우의수를 표현 가능 -> bit의 표현이 원소의 선택/비선택 표현

• 예로 {1, 3, 5, 6, 9} 가 있을때 이것의 모든 부분집합을 2진수로 표현이 가능

• 00000 ~ 11111 : 총 2^5로 32개(공집합 포함) 가지수
• (i & (1<<j)) != 0
  • 1«j 는 인덱스 역할이며, i비트의 1«j 번째를 & 연산으로 1인지 확인하는 것
  • 예로 1«3 이라면, 1 -> 1000 로써 {1,2,3,4,5} 자리 중 2가 있는 자리를 의미한다.

비트 마스킹(bit mask)

부분집합 로직에 visited 대신 비트 마스킹 적용 예시

• visited = true -> mask | 1 << depth
  • 예로 mask는 00010, depth는 3 가정하면
  • 1«3 은 1->1000 이니까 00010 | 1000 을 비트연산하면 01010 이 된다.
  • 즉, 해당자리에 1 로 방문처리 한 효과
• if(visited) -> if((mask & 1 << i) != 0)
  • i번째 자리의 비트가 0이 아니면 1로써 방문을 의미하므로 true

다음순열(Next Permutation)

현재의 순열에서 “사전 순으로 다음 순열 생성”

구현 로직

• 배열을 오름차순 정렬한 후 시작 -> 가장 작은 순열 한번 처리!

• 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.)

  1. 뒤쪽부터 탐색하며 교환위치(i-1) 찾기 (i:꼭대기)

  2. 뒤쪽부터 탐색하며 교환위치(i-1) 와 교환할 큰 값 위치(j) 찾기

  3. 두 위치 값(i-1, j) 교환

  4. 꼭대기위치(i) 부터 맨 뒤까지 오름차순 정렬

     오른차순 방식을 나타내는 그림

일반적인 NP 코드
한번 더 수도 코드로 설명하자면?

1. 뒤에서부터 첫 번째로 감소하는 인덱스 찾기

2. 뒤에서부터 src[i-1]보다 큰 값 찾기

3. 두 값을 교환

4. i-1위치 뒤쪽을 reverse swap

   꼭대기위치(=i) 부터 맨 마지막 위치(=k)까지 오름차순 정렬이 되는 것
   그림의 코드와 동일하며, 3 2 5 4 1 -> 3 2 1 4 5 로 “오름차순 정렬” 됨을 확인!

예시) 조합 - NP활용

• 아래 생략된 np메소드 코드는 위의 “일반적인 NP 코드”와 동일
• 따라서 아래 코드의 index배열은 NP메소드를 거쳐서 00111에서 01011… 이런식으로 변함

BFS, DFS -> 최단거리는 꼭 “BFS”!!

BFS(넢이우선검색), DFS(깊이우선검색)은 정말 단골 문제들이다.

BFS는 최단거리에 자주 사용하고, DFS는 그래프나 트리에서 주로 사용한다.

• BFS는 큐 를 활용하고, DFS는 스택 또는 재귀(필자는 주로 재귀)를 활용한다.
  • 재귀자체가 스택과 동일한 구조이기 때문이다.
  • 주의할점은 BFS는 방문기록을 큐에 집어넣는 시점에 남겨야 한다.
• DFS는 “재귀+백트래킹” 부분에서 많이 언급하겠다.

BFS 방문기록 -> 큐에 집어넣는 시점에 하자 (바킹독님의 글에서 본 기억)

• 방문기록은 방문 안한곳만 큐에 넣어 탐색하기 위한 목적
  • ex : 좌표라면? visited[nx][ny]=true
  • 이때 for문 4방향은 좌표(nx,ny)를 구할때 사용하는것이므로 꼭 구분!
• 일반적인 트리와 코드 모양??
  • “트리의 가지” 는 “좌표”로 생각
    • “방향”은 가지치는 조건으로 활용한 것일 뿐
  • 큐Size는 “해당 level의 가지의 총 개수”
  • “레벨” -> 최단거리로 볼 수 있다. -> “가중치 일정할 때”
  • for(큐 Size 만큼) 코드 이전이나 이후 코드 자리에 “해당 레벨에서 처리할 로직” 작성
    • 이후 코드 자리는 “큐가 비었을때도 놓치지 않는다”

너무 중요한 “최단거리” -> BFS, 0-1BFS, 다익스트라(O^2), 벨만포드(음수), 플로이드(O^3)

• BFS, 0-1BFS 만 소개 -> 나머지는 아래에 따로 정리한 부분에서 찾아볼 것

• BFS 최단거리 구하는 다양한 방식들

  • “배열(ex: dist[][])”에 거리저장 -> 모든 거리 필요시 좋음
  • “구조체(큐에 들어갈)”에 거리저장 -> 각각이 거리를 기억 -> 자주 사용중
  • “레벨”로 구해질 때 -> 간단한건 이걸로도 금방 구할 수 있음

• (개념) 가중치의 유무에 BFS 방식??

  • 가중치가 존재O : 두 정점을 잇는 간선들의 가장 작은 가중치 합 -> 가중치 다를때로 보자
  • 가중치가 존재X : 두 점점을 잇는 간선들의 가장 작은 개수(=레벨) -> 가중치 동일로 보자

• (중요!) 가중치에 따른 BFS 방식??

  • 가중치 동일(“거리일정”) -> 중복방문이 필요없다.

    • dist배열, 구조체, 레벨로 다 구할 수 있다.
    • dist배열 활용시 이전노드들도 기록할 수 있는 장점이 있다.
    • “큐” 를 통해 “레벨(높이)순” 으로 접근하므로 “최적의거리만 기록”하므로 DP개념포함
      • DP배열이 1차원, 2차원 연습하기 좋은 문제 : 숨바꼭질4_BOJ13913, 이모티콘_BOJ14226

  • 가중치 다름(“거리다를수있을경우”) -> 중복방문이 필요하다.

    • 참고 : 거리가 다르면 BFS로 최단거리 구하기가 어려운 이유??

      • BFS는 같은 depth(레벨)에 존재하는 다른 노드들은 고려하지 않기 때문이다.

      • 아래 그림처럼 가중치가 있을때, A에서 C로가는 최소비용을 구하라 한다면?

      • BFS가 가능한 경로는 A->B, A->C 가 끝이다.

      • 그러나 A->C->B 로써 가중치 2가 정답이다.

        

    • 따라서 보통 다익스트라(or 벨만포드)를 권장한다. -> 그러나 BFS 방안도 존재하긴 한다.(뇌피셜)

    • 큐에 들어갈 구조체를 활용하라 (1)

      • 확산시 중복방문을 허용해야한다. 단 무조건 중복방문을 허용할 수는 없으며 visit배열에,
      • 방문 표시가 아닌 누적치를 저장한다. 또한 visit에 저장된 누적치보다 확산할 경로의 누적치가 더 이로울 경우에만 확산한다.
      • 아래쪽에 코드 정리한게 있는데 그부분을 확인!!
        • 제목 : p.dist 같이 좌표 말고도 거리까지 기록하는 BFS

    • 가중치를 동일하게 바꿀수 있다면 바꿔라 (2)

      • 예시로 SWEA 1493. 수영대회 결승전 문제로 들 수 있다.
        • 문제를 보면 거리 1초 일정해서 동일한 가중치로 볼 수 있지만,
        • 대기했다가 지나갈 수 있는 경우가 있어서 그런 부분은 가중치가 2, 3이 될 수 있다.
        • 따라서 해당 가중치가 동일할 수 있게끔 구현한 방식이다.
        • 이를 위해 “조건에 걸린 좌표는 다시 큐에 삽입” 을 했다.
      • 예시 한가지 더있는데 백준.벽 부수고 이동하기_2206 이 있다.
        • 이 문제는 NXM 좌표의 칸수를 거리로 보아서 동일한 가중치로 볼 수 있지만,
        • 벽을 1번까지 통과할 수 있어서 벽O, 벽X 의 가중치가 다를 수 있다.
          • 물론 실제로 1칸은 거리1로 가중치는 여전히 동일하지만,
          • 벽을 통과했을때 경로와 벽을 통과하지 않았을때 경로가 좌표가 동일한데 거리(가중치)가 다를 수 있다는 의미이다.
        • 무엇이든 처음 방문이 최단경로(BFS특성)니까 visited를 벽O,벽X 2개 사용해서 해결했다.
      • 아래에 코드 정리한게 있는데 그부분을 확인!!
        • 제목 : 너비가 아닌 “레벨(높이)” 구하는 BFS
        • 제목 : 벽 부수고 이동하기 - visited 2개 + 트리레벨 사용

    • 0과 1로 이루어진 가중치라면 0-1BFS를 사용하라 (3)

      • 가중치가 0과 1로 이루어진 특수 환경에서 사용
      • deque 사용
      • 참고 -> 숨바꼭질 3 풀이

BFS 기본형태 4방향 좌표이동

// BOJ 1926번 : 그림
public class test { 
    static int[] dx = {0,1,0,-1}; // 행 : 우,하,좌,상
    static int[] dy = {1,0,-1,0}; // 열 : 우,하,좌,상
    static boolean[][] visited = new boolean[505][505];
    static int N;
    static int M;
    static int[][] inArr = new int[505][505];
    static int resultTemp;

    public static void bfs(int x, int y) {
        Queue<Pair> qu = new LinkedList<>();
        visited[x][y] = true; // 방문 표시
        qu.add(new Pair(x,y)); // push

        while(!qu.isEmpty()) {
            int cx = qu.peek().first; // front
            int cy = qu.peek().second;
            resultTemp++; // 너비 구함 -> 높이(레벨) 자리가 아님
            qu.remove(); // pop

            for (int i=0; i<4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx<0 || ny<0 || nx>N-1 || ny>M-1) continue; // 범위 내 체크
                if(visited[nx][ny]) continue; // 방문 여부 체크
                if(inArr[nx][ny] == 1) {
                    // 땅이 있는 경우(=1) 큐에 추가
                    visited[nx][ny] = true; // 방문 표시
                    qu.add(new Pair(nx,ny));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        for (int i = 0 ; i< N ; i++){
            stk = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j< M; j++){
                inArr[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        // run
        int resultMax = 0;
        int resultCount = 0;
        for(int i = 0; i<N;i++){
            for(int j = 0 ; j<M;j++){
                if(visited[i][j] || inArr[i][j] == 0) continue;
                resultTemp = 0; // 넓이 변수
                bfs(i, j); // 0,0 시작
                resultMax = Math.max(resultMax, resultTemp);
                resultCount++;
            }
        }
        System.out.println(resultCount);
        System.out.println(resultMax);
    }

    static class Pair {
        int first;
        int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}

BFS 시작점이 여러 개

• BFS를 동시에 동작하듯이 해야하는 경우에 해당된다.
• 같이 시작할 시작점들을 while문 돌리기전 큐에 전부 삽입후 평소처럼 BFS를 진행한다.
• 큐의 특성상 들어온 순서대로 진행할거기 때문에 가능한 것이다.

BFS 거리측정 + 시작점이 두 종류

• BOJ 4179번 : 불! 문제를 예시로 들겠다.
  • 두개의 큐를 사용해서 따로 BFS를 돌리는 형태이다.

public class Main {
    static int R, C; // Row, Column
    static char[][] inArr = new char[1005][1005];
    static int[][] dist1 = new int[1005][1005]; // J
    static int[][] dist2 = new int[1005][1005]; // F
    static int[] dx = {0,1, 0, -1};
    static int[] dy = {1,0, -1, 0};

    public static void bfs() {
        // init dist1, dist2
        for(int i=0;i<1005;i++){
            Arrays.fill(dist1[i], -1);
            Arrays.fill(dist2[i], -1);
        }
        // J(지훈), F(불) 위치 찾아서 각각 큐에 push
        Queue<Pair> qu1 = new LinkedList<>(); // LinkedList 로 선언해야함(J)
        Queue<Pair> qu2 = new LinkedList<>(); // LinkedList 로 선언해야함(F)
        for(int i = 0; i<R;i++){
            for(int j = 0 ;j<C;j++){
                if(inArr[i][j] == 'J') {
                    dist1[i][j] = 0; // 지훈이 거리 기록(분)
                    qu1.add(new Pair(i,j));
                }
                if(inArr[i][j] == 'F') {
                    dist2[i][j] = 0; // 불 거리 기록(분)
                    qu2.add(new Pair(i,j));
                }
            }
        }
        // F(불) BFS
        while(!qu2.isEmpty()) {
            int cx = qu2.peek().first;
            int cy = qu2.peek().second;
            qu2.remove();

            for(int i = 0 ; i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if (nx<0 || ny<0 || nx> R - 1 || ny > C - 1) continue; // 범위 내 체크
                if (inArr[nx][ny] == '#') continue; // 벽 체크
                if (dist2[nx][ny] == -1) {
                    dist2[nx][ny] = dist2[cx][cy] + 1; // 거리(분) 기록
                    qu2.add(new Pair(nx, ny));
                }
            }
        }
        // J(지훈) BFS
        // 불이 언제 어디서 퍼지는지 다 알고난 후 J(지훈)를 BFS 한다.
        // J가 범위를 벗어난 경우 탈출 성공이라 했으므로, 
        // 이때 불이 퍼지기 전에 탈출인지만 추가로 체크하면 된다.
        while(!qu1.isEmpty()){
            int cx = qu1.peek().first;
            int cy = qu1.peek().second;
            qu1.remove();

            for(int i = 0 ; i<4;i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                // 범위 내 체크
                if (nx<0 || ny<0 || nx>R-1 || ny>C-1){
                    // 이곳은 범위 밖(즉, 탈출)
                    // 따라서 이때 불 보다 먼저인지 체크(dist1[cx][cy] < dist2[cx][cy])
                    // dist2[cx][cy] == -1 의 의미는 F(불)이 사방에 갇혀서 못나온 경우다.
                    if (dist1[cx][cy] < dist2[cx][cy] || dist2[cx][cy] == -1) {
                        System.out.println(dist1[cx][cy]+1);
                        return;
                    }
                    continue;
                }
                if (inArr[nx][ny] == '#') continue; // 벽 체크
                if (dist1[nx][ny] == -1) {
                    dist1[nx][ny] = dist1[cx][cy] + 1; // 거리(분) 기록
                    qu1.add(new Pair(nx,ny));
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());
        for(int i = 0 ; i<R;i++){
            stk = new StringTokenizer(br.readLine(), "");
            String inStr = stk.nextToken(); // string
            for(int j = 0 ; j<C;j++){
                inArr[i][j] = inStr.charAt(j); // char
            }
        }
        // run & output
        bfs();
    }
    static class Pair {
        int first, second;
        public Pair(int first, int second) {
            this.first = first; this.second = second;
        }
    }
}

1차원에서의 BFS (즉, 4방향이 아니라)

• dx,dy 배열을 통해서 for(int i=0; i<4; i++)에서 nx, ny 를 구하는 것만 존재하는게 아니라,
• 필요에따라 for (auto nx : inArr[cx]) 형태로 다른 요소들의 접근방식도 존재한다.

너비가 아닌 “레벨(높이)” 구하는 BFS

// bfs 종료하게 되면 level의 값은 반드시 최단 경로의 길이가 되는 것! (단, 가중치 일정때)
// 이동에 제약이 생기면 자기자신을 "큐에 추가" -> 이 또한 핵심! (스스로 길이를 키우는것)
level = 0;
while(!qu.isEmpty()) {
    int size = qu.size();
    for(int s = 0; s < size; s++) { // "이게 핵심"
        int cx = qu.peek().x;
        int cy = qu.peek().y;
        qu.remove();
        // 종료 시점
        if (cx==tX && cy==tY) return; // 반드시 최단 경로 (bfs 특성)

        for(int i=0; i<4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            // 범위 & 방문 체크
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (visited[nx][ny]) continue;
            // 이동 가능여부 체크(섬, 소용돌이 등)
            int move = moveCheck(nx, ny, result);
            // => 0: 섬, 1: 이동, 2: 소용돌이
            if(move == 0) continue;
            else if(move == 1) {
                qu.add(new Pair(nx, ny));
                visited[nx][ny] = true;
            }
            else if(move == 2) {
                qu.add(new Pair(cx, cy)); // 자기자신을 추가 (대기하는 경로로 빠지는 것)
            }
            else {
                System.out.println("예상치 못한 error");
            }
        }
    }
    level++; // level
}
level = -1; // 도착지 이동 실패시 -1 출력

그림(트리)을 그려보았다.

• 자기자신을 넣는 “큐에 삽입 시점”도 중요
• 소용돌이를 만나면 “대기”하기 때문에 “다시 큐에 삽입”을 했고,
• 이 효과는 “가중치가 동일”하게 적용한 것으로 볼 수 있게 되었다.
• 따라서 “중복방문”도 해당안되는 것이다.

p.dist 같이 좌표 말고도 거리까지 기록하는 BFS

public static void bfs(int cx, int cy, int N) {
    Queue<Pair> qu = new LinkedList<>();
    qu.add(new Pair(cx,cy,0)); // dist : 0
    dpArr[cx][cy] = inArr[cx][cy]; //init

    while(!qu.isEmpty()) {
        Pair p = qu.peek();
        qu.remove();
        //if(cx==N-1 && cy==N-1) return; // 종료시점 필요X

        for(int i=0; i<4; i++) {
            int nx = dx[i] + p.x;
            int ny = dy[i] + p.y;
            if(nx<0||ny<0||nx>=N||ny>=N) continue;
            if(dpArr[nx][ny]==-1 || dpArr[nx][ny]>p.dist+inArr[nx][ny]) {
                //visited true // 필요X -> 중복방문 해야할거라서
                qu.add(new Pair(nx, ny, p.dist+inArr[nx][ny]));
                dpArr[nx][ny] = p.dist+inArr[nx][ny]; // update
            }
        }
    }
}

트리를 그려보았다.

• 거리를 비용으로 보면 된다 -> 실제 문제에서는 각기 다른 비용을 제공
• 또한, 화살표 그려져있긴 한데 정확히는 “좌표”를 의미한다고 봐주면 되겠다.
• “큐 삽입 시점” 이 제일 핵심

벽 부수고 이동하기 - visited 2개 + 트리레벨 사용

public static void bfs() {
    Queue<Pair> qu = new ArrayDeque<>();
    qu.offer(new Pair(0,0,0)); // {x, y, wall}
    visitedNoWall[0][0] = true;
    int level = 1; // (0,0) 부터시작
    if(N==1&&M==1) level=0; // 아래에서 어차피 ++하기 때문에 예외처리
    while(!qu.isEmpty()) {
        int size = qu.size();
        level++;
        for(int s=0; s<size; s++){
            Pair p=qu.poll();
            for(int i=0; i<4; i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx<0||ny<0||nx>=N||ny>=M) continue;
                if(p.wall==0) { // 아직 벽 안부순경우
                    if(inArr[nx][ny] == 0) { // 0은 빈벽
                        if(visitedNoWall[nx][ny]) continue; // 벽 안부순 visited를 체크
                        qu.offer(new Pair(nx, ny, 0)); // 큐 삽입시점
                        visitedNoWall[nx][ny]=true;
                    }else { // 1은 벽
                        if(visitedYesWall[nx][ny]) continue; // 벽 부순 visited를 체크
                        qu.offer(new Pair(nx, ny, 1)); // 큐 삽입시점
                        visitedYesWall[nx][ny]=true;
                    }
                }else { // 이미 벽 부순경우
                    if(inArr[nx][ny] == 0) {
                        if(visitedYesWall[nx][ny]) continue;
                        qu.offer(new Pair(nx, ny, 1)); // 큐 삽입시점
                        visitedYesWall[nx][ny]=true;
                    }else {
                        continue; // 이미 벽도 부쉈고(wall=1), 맵에 벽을 만난경우(inArr[nx][ny]=1)
                    }
                }
            }
        }
        // 기록 -> 종료시점
        if(visitedNoWall[N-1][M-1]) {
            result1 = level; break;
        }
        if(visitedYesWall[N-1][M-1]) {
            result2 = level; break;
        }
    }

    //최종 출력
    if(visitedNoWall[N-1][M-1] || visitedYesWall[N-1][M-1]){
        System.out.println(Math.min(result1,result2));
    }else{
        System.out.println(-1);
    }

}

DFS의 visited 로직이 어디 있느냐에 따라 약간 구조가 다르다. -> 2가지 모습 아래 제시

// 첫번째 방식
static List<Integer>[] inArr = new ArrayList[10];
static boolean[] visited = new boolean[10];
static void dfs(int cur) {
    visited[cur] = true; // 이곳에 로직 작성방식(1)
    System.out.println(cur);
    for (int nxt : inArr[cur]) {
        if(visited[nxt]) continue;
        dfs(nxt);
    }
}
main -> dfs(0);

// 두번째 방식
static List<Integer>[] inArr = new ArrayList[10];
static void dfs(int depth, List<Integer> val) {
	if (depth == 4) { // base condition
		result = 1;
		return;
	}
	
	for (int nxt : val) {
		if (visited[nxt]) continue;
        visited[nxt] = true; // 이곳에 로직 작성방식(2)
        outArr[depth] = nxt; // 출력할 값 기록
        dfs(depth + 1, inArr[nxt]);
        // visited[nxt] = false; // backtracking
	}
}
main -> visited[0]=true; dfs(0); // 이방식은 외부에서도 로직작성이 필요해짐

재귀(Recursion)

절차지향적 사고 -> 귀납적 사고 가 반드시 필요!!!

절차적으로 이해하지 마라!! 귀납적으로 그냥 이렇게 되겠구나라고 생각만 하라!! 도미노를 생각!!

• 수학적 귀납법
  • 1번 도미노가 쓰러진다.
    k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.
    • 참(true) : 1번 도미노가 쓰러진다, k번 도미노가 쓰러지면(가정)
    • 두 문장이 참이므로 k+1번 도미노.. 또한 귀납적으로 참
  • 예시1) 아래 코드의 예시
    • func1(1)이 1을 출력한다.
      func1(k)가 k,k-1,k-2…1을 출력하면 func1(k+1)은 k+1,k,k-1,k-2…1을 출력한다.
  • 예시2) 하노이 탑 이동 순서(n개 원판을 기둥 1 -> 기둥 3 으로 이동)

    • n-1개의 원판을 1->2 이동
      n번 원판을 1->3 이동
      n-1개의 원판을 2->3 이동
      => 규칙이 큰 원판 위에 작은 원판을 두는것이기 때문에 반드시 n-1개 원판이 기둥 2에 있고,
      n번 원판이 기둥 1-> 기둥 3 으로 이동하는 경우의 존재는 생각해보면 자명하다.

    • 원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.
      원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.

    • 코드 구현 방식

      • n-1가 S→E(임시기둥)
      • n가 S→T(도착기둥) : 이때 result.add로 기록 또는 “출력”
      • n-1가 E→T(도착기둥)

      

• 재귀 함수의 조건
  • Base condition : 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함
  • 모든 입력은 Base condition으로 수렴

• 재귀에 대한 정보

  • 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함
    • 모든 재귀 함수는 for문으로 만들 수 있음
    • 재귀는 for문 보다 메모리/시간에서 손해를 봄(함수 호출량 때문)
  • 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음(계산 중복 때문)
    • 예 : 피보나치 수열 => 해결법(DP로 중복 계산 재사용을 통해서 해결)
  • 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨
    • 100000 정도 호출했을 때 정상동작 하지 않으면 구글 검색을 통해 스택 메모리 제한을 해제할 것

재귀로 로직 작성 순서 -> 반드시 “Flat”한 관점으로 구현할 것

​ 1. 함수의 정의

​ 2. base condition

​ 3. 재귀 식

static StringBuilder sb = new StringBuilder(); // 문자열 기록
public static void func(int n){
    if(n==0) return; // base condition
    sb.append(n+" ");
    func(n-1); // 재귀(recursion)
} 
public static void main(String[] args) throws IOException {
    func(5);
    System.out.println(sb); // 출력
}

ex) 백준 Z -> while, 재귀 둘다 (재귀와 for문은 서로 구현 가능한 관계라는것을 기억)

• 문제 특성상 N은 2^N 에 사용됩니다.
• 그리고 “분할정복” 관점입니다. -> 2^N x 2^N -> 2^N-1 x 2^N-1 로 정확히 4개 만들어서 4등분하는 문제!
  • 똑같은 크기로써 분할정복이 가능한 문제 -> while, 재귀 둘다 구현 제시
  • 분할할 때 “좌표이동 + N(크기)”

//while(for문)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
r = Integer.parseInt(stk.nextToken());
c = Integer.parseInt(stk.nextToken());

// N계산
N = (int) Math.pow(2, N); // 2^N

// 최초 탐색 시작점
int y=0;
int x=0;

while(true) {
    if(N==1) break; // N -> N/2 -> N/2 ... 2x2(마지막) 까지는 진행

    N /= 2; // N>>1 

    // 4가지 영역 중 r, c 가 어디에 있는지에 따라 미리 계산할 수 있는 부분 이득을 취한다.
    if( r < y+N && c < x+N ) { // top-left <= 이득 X, 이 부분을 다시 더 나눠야 한다.
        ;
    }else if( r < y + N && c >= x + N) { // top-right <= 왼쪽 미리 계산 이득, 시작점 오른쪽 이동
        ans+=N*N*1;
        x+=N; // 좌표이동
    }else if( r >= y + N && c < x + N) { // bottom-left <= 위쪽 2개 미리 계산 이득, 시작점 밑으로 이동
        ans+=N*N*2;
        y+=N; // 좌표이동
    }else { // bottom-right <= 위쪽 2개 오른쪽 1개 3개 미리 계산 이득, 시작점 오른쪽 밑으로 이동
        ans+=N*N*3;
        x+=N; // 좌표이동
        y+=N;
    }
}

System.out.println(ans);
}

//재귀(recursion)
static void z(int y, int x) {
    // 기저조건
    if (N==1) return;

    N /= 2; // N>>1 

    // 4가지 영역 중 r, c 가 어디에 있는지에 따라 미리 계산할 수 있는 부분 이득을 취한다.
    if( r < y+N && c < x+N ) { // top-left <= 이득 X, 이 부분을 다시 더 나눠야 한다.
        z(y,x);
    }else if( r < y + N && c >= x + N) { // top-right <= 왼쪽 미리 계산 이득, 시작점 오른쪽 이동
        ans+=N*N*1; // 부분이득
        z(y,x+N);
    }else if( r >= y + N && c < x + N) { // bottom-left <= 위쪽 2개 미리 계산 이득, 시작점 밑으로 이동
        ans+=N*N*2;
        z(y+N,x);
    }else { // bottom-right <= 위쪽 2개 오른쪽 1개 3개 미리 계산 이득, 시작점 오른쪽 밑으로 이동
        ans+=N*N*3;
        z(y+N,x+N);
    }

}

백트래킹(Backtracking) -> DFS(재귀) 사용중

“백트래킹” 은 다음과 같은 절차로 진행된다.

1. 상태 공간 트리의 깊이 우선 검색을 실시한다.
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다른 노드로의 검색을 계속한다.

상태 공간트리 를 그려가면서 문제를 이해하고, 재귀 형태로 풀어나가자.

• 백트래킹은 재귀에서 자주 볼 수 있으며 본인은 보통 DFS(재귀방식)+visited[]로 자주 구현한다.
  • 사실 “순열”을 구할 때 사용한 방식도 백트래킹으로 볼 수 있고, visited 사용해서 false로 되돌아간다면 모두 백트래킹의 개념이라고 이해하면 된다.
• 물론, 재귀 방식에서 func(cur+1, tot); func(cur+1, tot+arr[cur]); 이런식으로 2개의 가지를 뻗고 visited[] 없이도 충분히 백트래킹이 구현이 되기 때문에 “재귀를 제대로 이해해두자”
  • 왜냐하면 위 코드의 의미는 “visited=true”재귀와 “visited=false”재귀로 볼 수 있기때문에 사실상 앞에서 언급한 방식과 “동일한” 백트래킹 방식으로 해석할 수 있다. -> “부분집합 의미”
  • 참고 : 백트래킹 을 DFS+재귀로 자주 사용하지만, 분기한정법 은 여러 검색 방법(DFS 말고도…!)들을 지원하는 차이가 있다.

유명한 N-Queen 의 예시 -> 주석 위주로 확인

static int N;
static int[] col;

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    col = new int[N + 1]; // 0번 행을 제외하고 작업하기 위해 1을 더한다.각 행에 하나씩만 배치할 수 있기 때문에 1차원, col[i]번째방에 여왕을 배치할 열값을
    // 저장한다.

    setQueens(1); // 1행부터 시도
    System.out.println(answer);
    in.close();
}

// 유도파트 : 현재 행의 첫열부터 무조건 퀸을 놓고 그 위치가 가능한지 체크하고 가능하다면 다음 행으로 퀸을 놓으러 재귀호출한다.
// 가능하지 않다면 다음 열로 시도 한다.
// 기본파트 : 마지막행까지 다 놓았다면 경우의 수 증가후 리턴
public static void setQueens(int rowNo) {

    if (rowNo > N) { // 시도하려는 rowNo행번호가 N보다 크면 말판끝까지 다 놓은 경우
        answer++;
        return;
    }
    for (int j = 1; j <= N; j++) { // 해당 행의 1열부터 n열까지 퀸 놓는 시도
        col[rowNo] = j;
        if (checking(rowNo)) { // rowNo행의 j열의 상황으로 가능한지 체크하여 가능하다면 다음행 시도
            setQueens(rowNo + 1); // rowNo+1번째 행 시도
        }
    }
}

// rowNo행에 퀸을 놓을수 있는지 1행부터 기존 rowNo-1행까지 rowNo행와 비교하며 체크
public static boolean checking(int rowNo) {
    for (int k = 1; k < rowNo; k++) {
        // 같은 행에 배치할수 없으므로 행은 비교할 필요 없고 열값에 대해서만 비교하면 됨
        // col[rowNo]:현재 퀸의 위치 , col[k] :이전 퀸들의 위치(k: 1~(rowNo-1))
        if (col[rowNo] == col[k] || Math.abs(col[rowNo] - col[k]) == rowNo - k) {// col[rowNo] == col[k] 열이 같은지 체크
            // (한행에 하나씩 구하기 때문에 행체크 불필요)
            return false; // Math.abs(col[rowNo]-col[k]) == rowNo-k 대각선 체크 (열값차이와 행값차이가 같다면 대각선)
        }
    }
    return true;
}

N과 M(1) - 대표적인 템플릿 : BOJ15649

// BOJ 15649
// N과 M(1) : 1부터 N까지 자연수 중에서 `중복 없이(=visited 활용)` M개를 고른 수열
// 즉, (1 2) (1 3) 은 가능하지만 (1 1)은 불가 + "순서(자리) 존재"
static int N, M;
static int[] outArr = new int[10];
static boolean[] visited = new boolean[10];
static StringBuilder sb = new StringBuilder();

public static void dfs(int depth) {
    // base condition
    if(depth == M) {
        for(int i = 0 ; i<M; i++){
            sb.append(outArr[i]+" ");
        }
        sb.append('\n');
        return;
    }
    // recursion
    for(int i = 1 ; i<=N; i++){
        if(visited[i]) continue;
        visited[i] = true;
        outArr[depth] = i;
        dfs(depth+1); // recursion
        visited[i] = false; // backtracking
    }
}

트리를 그려보았다.

N과 M 시리즈 - dfs 방식 백트래킹 사고력 확장

• BOJ15650, BOJ15651 ,BOJ15663, BOJ15686
• 문제 특성상 for문으로 i가 출력값(가지에 적힌)이 된건데,
• 4방향(dx,dy)에서의 for문 i도 출력값이라 착각하면 안된다.
  • 얘는 “좌표”가 출력값으로 봐야한다. -> 자꾸 착각해서 기록했다

// 참고 : 1~N 순서대로 접근했기 때문에 수열을 구하면 사전순(오름차순)으로 출력
// 그러나, 랜덤 값이 들어온 경우에 사전순 출력을 위해선 수열 구하기전에 `sort`작업이 필요

// (1) `i > preValue`로 구하는 값 오름차순 (즉, 현재값 > 이전값)
// (추가) 이 문제를 "조합", "중복조합(비내림차순)" 으로도 해결 가능!
// (추가) 현재 코드는 "순열"로 구한 코드
for (int i = 1; i <= N; i++) {
    if (!visited[i] && i > preValue) { // 만약 비내림차순은? `i>=preValue`
        visited[i] = true;
        outArr[depth] = i;
        dfs(depth + 1, i);
        visited[i] = false; // backtracking
    }
}

// (2) 1부터 N까지 자연수 중에서 `중복 허용(=visited 활용X)` M개를 고른 수열
// 그림에 중복불가로 잘못 적혀있으니 무시할것
// (추가) 이 문제의 의미는 "중복순열"을 구하는 것
for (int i = 1; i <= N; i++) {
        //visited[i] = true;
        outArr[depth] = i;
        dfs(depth + 1);
        //visited[i] = false; // backtracking
    }
}

// (3) 애초에 입력이 1 2 3 4 가 아닌 1 1 2 3 이런식으로 중복으로 들어올 경우 처리방법 소개
// `tempNum != inArr[i]` 이 핵심
// (추가) 입력 자체가 중복으로 들어온것이라 잘 생각해야함.
int tempNum = 0; // 이전값 기록해둬서 중복 수열 생성되지 않도록 하기 위함
for (int i = 1; i <= N; i++) {
    if (!visited[i] && tempNum != inArr[i]) {
        tempNum = inArr[i];
        visited[i] = true;
        outArr[depth] = inArr[i];
        dfs(depth + 1, inArr[i]);
        visited[i] = false;
    }
}

// (4) 마지막으로 시간초과를 해결하는 TIP => 아래 동작만 필요한 경우들에 사용!!
// => 이 경우 사실 2중, 3중... for문으로 전체 접근(완.탐)하는것과 동일하다.
// => 그런데 M이 10이다?? 그럼 10중 for문을 해야하는데 그건 별로다.
// 따라서 아래 방식을 잘 기억해두고 써먹자!
// (추가) 이는 "조합"방식과 유사하다. visited 없이 "조합"으로 충분히 구현 될 것이다.
for (int i = index; i < chicken.size(); i++) { // 반드시 index부터 시작해야 시간초과 안전
    p = chicken[i];
    if (visited[p.first][p.second]) continue;
    visited[p.first][p.second] = true;
    outArr[depth] = i; // 선택된 치킨집 index 기록
    dfs(depth + 1, i); 
    visited[p.first][p.second] = false; // backtracking
}

(1 ~ 3) 트리를 그려보았다.

• visited 를 사용하면 말그대로 가지마다 적혀있는 숫자들이 중복하지 않게 가지를 뻗어나가는 것이다.
• 2번을 보면 visited를 사용하지 않은 모습이다. -> 전형적인 “중복순열” 모습

(4) “마지막으로 시간초과를 해결하는 TIP => 아래 동작만 필요한 경우들에 사용!! “ 이부분의 의미를 트리로 나타내보겠다.

• 생각보다 중요한 개념이다.

• (추가 정보) 이 내용은 “조합”이라고 보면 된다. -> “순열”로 풀려고하니까 시간초과 문제가 있던건데 이제부터 이 트리의 구조는 “조합”으로 생각하자

• 가정 : 치킨집 최대 M(=3)개 택, 총 치킨집 개수는 5개(네이밍=1,2,3,4,5)

• 이를 for문으로 모두 접근한다면??

  for(int i=0; i<N-2; i++) {
      for(int j=i+1; j<N-1; j++) {
          for(int k=j+1; k<N; k++) {
              // M(=3)개씩 선택가능한 쌍 모두 접근
          }
      }
  }
  

• 그런데, M이 10이라면 10중 for문 해야한다… 따라서 “백트래킹”을 사용

• (추가 정보) 물론, 순열로직에 조합로직을 짬뽕한 코드인데, 그냥 “조합”로직 사용하면 됨!

• 아래는 해당 그림

부분수열의 합 - 응용(사고력 확장)

• 이것도 “백트래킹”으로 볼 수 있다.
• (추가정보) 이 내용은 “부분집합” 이다.

// 이 문제도 위 코드와 같은 형태로 해결할 수 있지만, 좀 더 간단하게 해결할 수도 있다.
// 위 코드의 경우 하나의 형태로만 재귀를 한것이다.
// 하지만, 이 문제를 상태 트리 그려보면 값을 더한경우 안더한경우로 나눠 볼 수 있다.
// 즉, 2개 형태로 재귀를 할 수 있고 훨씬 코드도 간결해진다.
public static void func(int depth, int sum) {
	if (depth == N) { // base condition
		if (sum == S) result++;
		return;
	}
	func(depth + 1, sum); // 안더함
	func(depth + 1, sum + inArr[depth]); // 더함
}

트리를 그려보았다.

트리의 지름 - 응용(사고력 확장) : BOJ1167

// 생각해보면, DFS에서 반드시 탈출하는 base condition 을 꼭 depth로 구현할 필요는 없다.
// 즉, visited를 통해 방문 체크할 경우 당연히 모두 방문하게 되면 재귀 종료는 자명하기 때문이다.
// 아래 예시는 임의로 입력들어온 노드를 DFS를 통해서 제일 거리가 먼 노드를 구하는 코드이다.
static void dfs(int val, int node) {
    // base condition -> visited
    if(maxVal < val) {
        maxVal = val; // 가중치 합 => 최대 거리
        maxNode = node; // 이때의 해당 노드
    }
    // recursion
    for(Node nxt : inArr[node]) {
        if(visited[nxt.nxt]) continue;
        visited[nxt.nxt] = true;
        dfs(val+nxt.w, nxt.nxt);
        visited[nxt.nxt] = false; // backtracking
    }
}
// 아래는 main 함수 내에서 dfs 호출
visited[1] = true;
dfs(0, 1); // 임의의 노드 1 -> maxNode를 구함 (제일 먼 거리의 노드 1개 구한것)
visited[1] = false; // backtracking

// maxNode로 maxNode와 제일 먼 거리 노드 1개를 또 구하면?? 트리의 지름
// 트리의 지름 : 노드와 노드사이 거리가 제일 긴 한쌍의 길이
visited[maxNode] = true;
dfs(0, maxNode); // 임의의 노드 maxNode
visited[maxNode] = false; // backtracking

트리를 그려보았다.

창용 마을 무리의 개수 - SWEA 7465(사고력 확장)

• 백트래킹 개념이 들어간 문제는 아니다.
• 그냥 for문으로도 바로 풀렸겠다.

/*
dfs를 보면 매우 간단한 로직이며, 위 문제처럼 기저조건은 visited로 해결이다.
단, 여기서 포인트는 "방문체크와 result++" 부분이다.
*/
public static void dfs(int idx, boolean[] visited, List<Integer>[] inArr) {
    // base condition -> visited
    List<Integer> inNum = inArr[idx];
    for(int num : inNum) {
        if(visited[num]) continue; // 방문체크(1)
        visited[num] = true;
        dfs(num, visited, inArr);
    }
}
// 아래는 main 함수 내부
//run
for(int i=1; i<=N; i++) {
    if(visited[i]) continue; // 방문체크(2)
    dfs(i, visited, inArr);
    result++; // 이곳까지 오면 무리 1개 추가된 것(가지1개 추가)
}

트리를 그려보았다.

(재귀 사고력 확장) 감시_15683 -> 백준

• cal 함수는 dfs가 너무 길어질거같아서 빼낸 함수일 뿐이지 dfs 내부로직으로 보면 된다.
• 백트래킹이 “2차원 배열”인 점이 인상깊다.

static void cal(Point p, int depth, int[][] backup) {
    for(int i = 0; i<4; i++) {
        // dArr1[i] 는 dir(방향)이며, calOut은 주어진 방향에 직진으로 이동하는 함수
        // cctv 1,3,4 는 4번 회전(방향) 필요하며, cctv2는 2번, cctv1은 1번이다.
        if(p.cctv == 1) { // 4번 회전
            calOut(p, dArr1[i]); 
        }else if(p.cctv == 2) { // 2번 회전
            if(i>1) continue; 
            calOut(p, dArr2[i][0]);
            calOut(p, dArr2[i][1]);
        }else if(p.cctv == 3) { // 4번 회전
            calOut(p, dArr3[i][0]);
            calOut(p, dArr3[i][1]);
        }else if(p.cctv == 4) { // 4번 회전
            calOut(p, dArr4[i][0]);
            calOut(p, dArr4[i][1]);
            calOut(p, dArr4[i][2]);
        }else if(p.cctv == 5) { // 1번 회전 (=회전 안함)
            if(i>0) continue; 
            calOut(p, dArr5[i][0]);
            calOut(p, dArr5[i][1]);
            calOut(p, dArr5[i][2]);
            calOut(p, dArr5[i][3]);
        }
        dfs(depth+1); // 다음 cctv 이동
        // backtracking
        for (int k = 0; k < N; k++) {
            for (int l = 0; l < M; l++) {
                outArr[k][l] = backup[k][l];
            }
        }
    }
}

static void dfs(int depth) {
    // base condition
    if(depth == inCCTV.size()) {
        int num = 0;
        for(int i = 0; i<N; i++) {
            for(int j = 0 ;j<M; j++) {
                if(outArr[i][j] == 0) num++; // 사각지대 구하기;
            }
        }
        result = Math.min(result, num);
        return;
    }

    // 현재 depth(cctv개수)에서 배열 상태 매번 새로 복제
    Point p = inCCTV.get(depth);
    int[][] backup = new int[10][10];
    for(int i = 0 ; i<N; i++){
        for(int j = 0 ; j<M; j++) {
            backup[i][j] = outArr[i][j];
        }
    }
    // recursion
    cal(p, depth, backup);
}

트리를 참고해보자

Branch-and-Bound(분기한정법)

개념 이해해두자. 실제로 백트래킹과 DFS 조합으로 많이 사용했다. 분기한정법-개념

• 분기한정법 : Backtracking + 다른 탐색들(DFS,BFS,우선순위큐 등)

  • Bound : 마디가 유망한지 여부를 결정하기 위해서 한계치(bound) 계산

  • So far the best : 현재까지 찾은 최적의 답

• 최적화 문제의 SST 비교

  • 최적화 문제의 SST 비교 최소화 문제(예: TSP(=외판원 문제))

    • 트리 깊어질수록 BOUND값이 절대 작아질 수 없음(Low Bound를 구함)

    • 최적화 문제의 SST 비교 최대화 문제(예: 0-1냅색)

      • 트리 깊어질수록 BOUND값이 절대 커질 수 없음(Upper Bound를 구함)

햄버거 다이어트 SWEA 문제 -> 아마도 이런 문제풀이 방식을 의미하는듯 한다(뇌피셜)

• result = Math.max(result, benefit); 이 So far the best 가 되고,
• inArr[i][1]+weight 이 Bound 가 되고,
• if(weight>L) return; 이 Low Bound or Upper Bound 가 될 것 같다.
• 물론, 접근은 백트래킹까지는 아니고 “조합” 경우의수로 접근했다.

다이나믹 프로그래밍(DP)

동적 프로그래밍(=DP)는 재귀(메모이제이션) 방식과 반복문 방식이 있다.

top-bottom, bottom-top 방식으로 보면 된다.

• 두 방식의 공통점은 “값을 재사용” 하여 성능을 끌어올린다는 것이다.

• 즉, 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결한다.

• 대표적인 다양한 DP 유형들이 있어서 기억해두자.

bottom-top 방식 - 반복문

DP를 푸는 과정 - 테이블 잡고 식 찾는 연습이 매우매우 중요

​ 1. 테이블 정의하기

​ 2. 점화식 찾기

​ 3. 초기값 정하기

EX) 1로 만들기 BOJ : 1463번

• 테이블 정의하기
  • D[i]는 i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
• 점화식 찾기
  • D[12]는 ??
    3로 나누면 (D[12] = D[4] + 1)
    2로 나누면 (D[12] = D[6] + 1)
    1을 빼면 (D[12] = D[11] + 1)
    => D[12] = min(D[4]+1, D[6]+1, D[11]+1)
  • D[k] = ?
    => D[k] = min(D[k/3]+1, D[k/2]+1, D[k-1]+1)
• 초기값 정의하기
  • D[1] = 0

// input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
// init - dp
d[1] = 0;
// run
for(int i = 2 ; i<=N; i++){
    d[i] = d[i-1]+1;
    if(i%2==0) d[i] = Math.min(d[i], d[i/2]+1);
    if(i%3==0) d[i] = Math.min(d[i], d[i/3]+1);
}
// output
System.out.println(d[N]);

top-bottom - 재귀(메모이제이션)

재귀를 사용해 전체를 탐색하되 “메모이제이션 배열”을 선언해 “재사용” -> 더이상의 재귀를 방지

EX) [SWEA] 정사각형 방(1861)

문제해석

• NxN 형태의 맵에 방들이 존재하며, 해당 방의 숫자들은 “모두 다르다”
• 상하좌우로 이동 가능하며 현재 방보다 “정확히 숫자 1 커야한다”
• 어느 방에서 시작해야 가장 많은 방을 조회할 수 있나??

static int dfs(int x, int y){
    // 이미 다른 dfs 에 의해 memoi 각 계산되어 있으면 그걸 재사용
    if(memoi[x][y] != 0) return memoi[x][y]; // 이것이 DP핵심!!

    // 이후 조건에 맞는 더 갈 수 있는 곳 방문
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0||ny<0||nx>=N||ny>=N) continue;
        if(map[nx][ny]==map[x][y]+1) {
            return memoi[x][y] = dfs(nx,ny) +1; // +1 : 방한칸 이동했기에 추가
        }
    }
    // 더이상 x,y에서 갈 곳이 없다.
    return memoi[x][y] = 1; // 자기자신 1칸
}

DP 다양한 유형

참고 : DP 정리

• 피보나치

  • f[n] = fib[n-1] + fib[n-2]
• 이항계수
  • B[i][j] = B[i-1][j-1] + B[i-1][j]
B[i][i]=1, B[i][0]=1 ,if(j==i || j==0)
• 격자경로
  • P[i][j] = P[i-1,j] + P[i,j-1]
P[1,j] = P[i,1] = 1
  • 심화 : 표시된 곳을 2회 지나야 하는 경우? 3차원으로 DP 선언
    EX : (표시없는길 개수)/(표시1번 지난길 개수)/(표시2번 지난길 개수)

• 거스름돈

  • C[i][j] = min( C[i, j–D[i]] + 1, C[i-1, j] ) ,if D[i]<=j
C[i][j] = C[i-1][j] ,if D[i]>j
C[i][j] = 0 ,if j==0
  • 참고 : D는 Denom 으로써 액면가(화폐 단위 : 1원 10원 등등)을 의미
• 연쇄 행렬곱셈(BOJ11049)
  • M[i][j] = ,if i<j
  • M[i][j] = 0 ,if i==j
  • 추천(응용) 문제 : 파일 합치기_BOJ11066
    • 연쇄 행렬곱셈처럼 로직은 동일하다.
    • 차이점은 BOJ11066 문제의 점화식에 “결합비용” 부분은 행렬이 아니다보니 다른 값을 사용해야 한다.
• LCS(BOJ6251)
  • C[i][j] = max( C[i-1][j], C[i][j-1] ) ,if A[i]!=B[j]
C[i][j] = C[i-1][j-1] + 1 ,if A[i]==B[j]
C[i][j] = 0 ,if i==0 || j==0
  • Find a Longest Common Subsequence 제일 긴 공통된 부분 문자열을 의미하며,
    A문자열과 B문자열이 주어졌을때 이들의 LCS를 구한다는 의미이다.

• LIS(BOJ2565)

  • 핵심 : i번째 인덱스에서 끝나는 최장 증가 부분 수열 마지막에 arr[k] 추가했을 때 LIS 길이와 기존 length[k] 값을 비교

  • // length[]의 각 요소값은 최장 증가 부분 수열의 개수
    for (int k = 0; k < n; k++) {
        length[k] = 1;
        for (int i = 0; i < k; i++) {
            if(arr[i] < arr[k]) {
                length[k] = max(length[k], length[i] + 1);
            }
        }
    }
    

  • Longest Increasing Subsequence 각 원소가 이전 원소보다 큰 최장 증가 부분 수열을 의미

• OBST(Optimal Binary Search Tree)

  • 
  • '’키’‘의 검색 빈도수(즉, 확률)를 받아서 BST의 최적인 트리를 구하는 것
    • WHY? 빈도수 높은 키값이 루트와 가까울수록 더욱 효율적이기 때문에 사용!
    • 자세한 개념은 이곳에서

• 0-1 Knapsack(BOJ12865)

  • max( P[i-1][w], pi + P[i-1][w-wi] ) ,if wi<=w
P[i][w] = P[i-1][w] ,if wi>w
  • 단, top-bottom 으로 넘어가면 “연산량”을 줄일 수 있지 근본적인 “메모리 문제”가 있을경우 이를 해결한다는게 아님. 착각X
    • 따라서 냅색 문제 메모리 초과일 것 같을때 해당 문제 조건만 보지말고 다른 방향의 풀이 생각!
    • 참고(심화) 문제 -> 앱_7579
• 프리랜서의 일정 정하기(SWEA4052)
  • OPT[j] = max ( OPT[j-1], w[j] + OPT[p(j)] )
    • OPT[j-1] : 일정 j 선택X
    • OPT[p(j)]+w(j) : OPT[p(j)]는 p(j)<j인 일정들 중 젤 큰 index의 최적해(OPT) 값
      • p(j) : 일정 j와 겹치지 않고, j와 가장가까운(큰) 일정을 의미
      • w(j) : 일정 j의 비용
    • BOJ는 없고 SWEA 에 4052 문제로 존재
      • 참고로 문제에 그림 조금 잘못 그려져 있음.
• 완전정보 게임(coin move game)
  • Nim 게임을 의미 - 바둑돌 가져가기, coin move game, coin game, card game
  • “바둑돌 가져가기, coin move game” 는 확실히 이해하는것을 권장

• 제한된 비트 스트링의 개수

  • S[k] = S[k-1] + S[k-2]
  • 이건 너무 쉬운 풀이인데, 비트 스트링 개수 세는 아이디어는 기록하면 좋을듯 해서
  • 참고 : 제한된 비트 스트링의 개수
• 최대 공백 정사각형(SWEA4062)
  • LES[x][y] = min( LES[x-1][y-1], LES[x][y-1], LES[x-1][y] ) + 1
LES[x][y] = 1 if 첫번째 행or열이 비었을때
LES[x][y] = 0 if 비어있지 않다면
  • LES[x][y] 는 공백 정사각형 크기이며, [x,y]는 해당 정사각형의 우측하단 좌표를 의미
• 위상정렬 + DP(BOJ2056)
  • 위상정렬과 DP는 밀접한 관계가 있는데, 해당 문제를 풀어서 느껴볼 것
  • 참고 : 위상정렬과 DP관계

• TSP(외판원 순회)

  • 2가지 방법(=분기한정법, DP) 해결가능하며 아래에서 “비트마스크+dp” 방식을 소개한다.

  • dp[i][j] 의미

    • i : 내가 지금까지 방문한 마을을 수로 표현
    • j : 현재 내가 있는 마을
    • dp[i][j]-> 이런 상태가 완성되었을 때의 최솟값 (=total_cost)

  • //dp init
    int dp[][] = new int[(1 << N)][N];
    /* fill dp to Integer.INT_MAX; */
    dp[1][0] = 0; //0번 마을을 방문했고(1), 현재 0번 마을에 있음(0)
        
    //dp
    for(int i = 1; i < (1 << N); i++){ //현재 내가 방문한 마을의 비트 값, visited_array
    	for(int j = 0; j < N; j++){ //현재 내가 서 있는 마을, now_pos
    		if(dp[i][j] == Integer.INT_MAX) continue; //불가능한 상태를 보려고 함
    		for(int k = 0; k < N; k++){ //내가 다음으로 방문하려는 마을, next_pos
    			if((i & (1 << k)) > 0) continue;
    			//i는 방문했던 마을의 비트 값이었음. 그런데 지금 가려는
    			//k번 마을이 이미 이 비트에 있으면 갈 수 없으므로 continue 처리
    			dp[i | (1 << k)][k] = Math.min(dp[i | (1 << k)][k], dp[i][j] + cost[j][k]);
    			//k번 마을의 비트를 채우면서 k번으로 이동해야 하므로 [i | (1 << k)][k]
    			//현재 나의 최소값 (dp[i][j]) + 이동 비용(cost[j][k])을 다음 상태로 전달
    		}
    	}
    }
    int result = Integer.INT_MAX;
    for(int i = 1; i < N; i++){
    	result = Math.min(result, dp[(1 << N) - 1][i] + cost[i][0]);
    } //N개의 비트를 모두 채운 상태 = (1 << N) - 1 로 표현 가능.
    

그리디(Greedy)

그리디란 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘

구현자체는 굉장히 간단해서 따로 정해진 코드 탬플릿은 X

단, 코테에서 추천 전략은 문제가 100% 그리디 풀이란게 확신하면 짜서 제출 및 틀리면 빠르게 손절
100% 확신이 없으면, 일단 넘어가고 마지막에 남은 시간에 코딩 시작

수학(Math)

자세한 개념은 반드시 알고리즘 기초 - 수학, 바킹독 - 수학 게시물을 함께 참고

1. 소수

개선시킨 소수판정과 소인수분해는 모두 O(√n)

1부터 n까지의 수 중에서 소수 목록을 구하는건 에라토스테네스의 체를 사용

• 소수 판정법(소수 1개!!) - O(√n)
  • 합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다.
    • EX) N=18 : 2<=√18, N=25 : 5<=√25, N=21 : 3<=√21

// √N 이하까지만 확인해도 소수 판별이 가능하므로 복잡도 N -> √N 개선
public static boolean isPrime(int n) {
	if(n == 1) return false; // 주석가능
    for(int i = 2; i*i<=n; i++) { // √N 이하까지 돈다.
        if(n%i == 0) return false;
    }
    return true;
}
// 또는 아래로 암기
public static boolean isPrime(int n) {
    for(int i = 2; i<=(int)Math.sqrt(n); i++) // √N 이하
        if(n%i == 0) return false;
    return true;
}

• 소수 목록(소수 여러개!!) - 에라토스테네스의 체
  • 소수는 자신보다 작은 수들의 배수값과 동일한게 있으면 안되는 특징을 이용
  • 예로 2의 경우??
    • 처음 prime[2]는 소수로 그대로 있고, prime[4, 6, 8...] 배수들은 소수가 아닌것으로 걸러지는 형태이다.

// 에라토스테네스의 체
// prime배열 의미 : false면 소수, true면 소수아님 => 초기값 false로 초기화(전역배열)
int p = 2;
while(p*p <= N) {
    if(prime[p] == false) {
        for(int i = p*p; i<=N; i+=p) { // i+=p 는 p의 배수들 걸러내려고
            prime[i] = true;
        }
    }
    p++;
}

• 소인수분해
  • 소인수분해 : 자연수를 소인수(약수들 중 소수)들의 곱으로 표현하는 것
    • EX) 60 = 2 x 2 x 3 x 5
  • 방법1) N 이하의 모든 소수를 에라토스테네스의 체로 다 찾은 다음에 그 소수들로 N을 나누어보는 방법
  • 방법2) 하지만, 이보다 더 괜찮은 방법이 존재(루트N 복잡도)
    • i를 2,3,4,5… 올라가면서 N을 나누어 떨어질때마다 소인수 목록에 기록하는 방법

// 소인수분해
for(int i = 2; i*i<=N; i++) { // √N 이하까지 돈다.
    while(N%i == 0) { // while문 (약수는 나누어 떨어져야 함)
        System.out.println(i); // 구한 소인수
        N/=i; // n이 1이 될때까지 갱신
    }
}
if(N!=1) System.out.println(N); // 마지막에 n이 1이 안될경우도 있는데, 그땐 n으로 나누면 1이 됨

• 참고) 팩토리얼 수에서 특정 수의 개수 구할때 유용한 특징 존재 : 10!의 경우 5의 개수를 구하기 위해 5를 10으로 나누면, 1~10 곱한 값 사이의 5가 나온 개수가 출력된다.

2. 최대공약수, 최소공배수(GCD, LCM)

• 최대 공약수(GCD), 최소 공배수(LCM) - 유클리드 호제법
  • 유클리드 호제법 : 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a> b), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
    • (a, b) = (b, r)
    • EX) 10 20 : (10, 20) = (20, 10) = (10, 0) = 10

// 최대공약수 -> (a, b) = (b, r)
// (1) 재귀 방식
public static int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
// (2) 반복문 방식 - 정수론의 정리 이용
// 정리 : 두 정수 a(≥0)와 b(>0) 가 있을 때, a = b∙q+r (0 ≤r<b) 이면  gcd(a,b) = gcd(b,r) 이다.
public static int gcd(int a, int b) {
    int r1 = a; int r2 = b; // init
    while(r2>0) {
        int q = r1/r2; // 몫
        int r = r1-r2*q; // 나머지 r = a-b*q
        r1 = r2; r2 = r;
    }
    return r1;
}

// 최소공배수 -> A X B = GCD(A,B) X LCM(A,B)
public static int lcm(int a, int b) {
    return a / gcd(a,b) * b; // overflow 방지 위해 나누기 먼저(곱셈이라 가능)
}

3. 연립합동방정식

아래 그림에서 조건에 만족한 학생 수를 구하기 위해 0~29 학생 수 때의 상황을 테이블로 나타냈고,
정답은 27명임을 알 수 있으며 이런 문제를 연립합동방정식 이다.

다만, 이렇게 0~29 명 때를 전부 찾아보는게 아닌 5개만 확인하면 되는 효율적인 방법을 소개한다.

• N%6==3 인 수들이 필요하고, 이는 처음 3부터 시작해서 +6인 3,9,15,21,27이다.
• 이 5개의 수들 중에서 N%5==2 를 찾기만 하면 된다.

public static int chk() {
    for(int i = 3; i<30; i+=6) { // N%6==3 인 경우들만 접근
        if(i % 5 == 2) return i;
    }
    return -1;
}

4. 이항계수(조합)

방법1) 조합의 공식 : nCr = n!/[(n-r)!r!] 을 이용하는 방법

방법2) 조합 성질 : nCk = (n-1)C(k-1) + (n-1)Ck 를 이용해서 DP로 구하는 방법(추천!!)

• 점화식 : d[i][j] = d[i-1][j-1] + d[i-1][j]

5. A진법 to B진법의 변환(관계)

필자는 이것을 A진법 -> 10진법 -> B진법 의 변화로 해결하고 있다.

백준11576 풀이 게시글 참고!!

• A진법 -> 10진법
  • 예로 2진법이라면??
    • 먼저, 10진수 값이 10 이였다면 이를 2진법으로 표현 했을때는 1010이다.
      • 1010 의 일의 자리 수를 10진수로 표현하면 0*2^0 = 0 이다.
      • 1010 의 십의 자리 수를 10진수로 표현하면 1*2^1 = 2 이다.
      • 1010 의 백의 자리 수를 10진수로 표현하면 0*2^2 = 0 이다.
      • 1010 의 천의 자리 수를 10진수로 표현하면 1*2^3 = 8 이다.
    • 마지막으로 1010 을 10진수로 표현한다면??
      • 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3 = 0 + 2 + 0 + 8 = 10
• 10진법 -> B진법
  • 10진수를 기수 B로 계속 나누어서 나머지 값을 거꾸로 출력하는 방식이다.
  • 그림으로 참고(추천 URL) : 10진수 A,B 진법 관계

/* 코드참고 */
// 2진법 -> 10진법
for (int i = m-1; i >= 0; i--) { // input의 끝자리부터 접근
    result += input[i] * pow(2, j++); // j는 0부터 -> 2^0 + 2^1 + 2^2 + ...
}
// 10진법 -> 2진법
while(num != 0) {
    res=num%2;
    num/=2;
    st.add(res); // st는 스택
}        

6. 곱의법칙

• BOJ16968
• 예로 위 문제에서 input이 dd나 ddd의 경우?
  • dd : 가지수 10*10 = 100개
  • ddd : 가지수 10*10*10 = 1000개
  • 물론, 이때 중복허용한 모든 가지수
    • 예로 2개의 주사위의 경우 6*6=36가지수가 나오는것과 같은 맥락
  • 그럼 중복을 허용하지 않을땐?? 위문제처럼 인접 2개만 중복 불허용경우엔??
    • 00, 11, 22, 33… 99 를 제외한다는 의미 => 이때 중복 가지수가 10개이다.
    • 따라서 중복이 발생하는 구간에 10이 아닌 9를 곱해주면 된다.
      • 중복 가지수가 10개라고 했기때문에 10을 곱하는걸 하나 빼서 9를 곱한 맥락

이분탐색(binarySearch)

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

• Arrays.binarySearch(arr, target) 함수를 활용 : 찾는 수가 등장했는지 안했는지를 이분탐색으로 알려줌(오름차순에 사용)
• 찾으면 해당 index를 반환하고, 못찾으면 -?을 반환한다. (조금 특이함)
  • 못찾을때 : 찾는수보다 큰 최초의 위치(index)를 찾아서 -1을 곱하고 1을 빼서 반환한다.
  • 아래코드 주석 참고
• 물론, sort 처럼 범위 지정할 수 있다.

• 단, parametric search 관련해서 구하려면 직접 binarySearch 를 작성 해줘야 한다.

• 분할정복처럼 st, en, mid 인덱스 활용하며 mid=(st+en)/2 가 기본

• 크기가 홀수, 짝수일 때 mid의 값이 다른게 정상인데 (예로 1,2,3,4 에서 중간값은? 애매)
  이를 신경쓸 필요가 없다. * 중간위치가 조금 다르더라도 결과 구하는데는 전혀 지장없고 속도도 거의 지장없다.

• 반드시 st,en을 1차이 나게끔 0,1로 가정하던지 해서 무한루프에 빠지는지 체크도 중요!! * 무한루프에 빠지게 되는경우 mid=(left+right+1)/2 사용을 권장

이분탐색 자료구조 Arrays.binarySearch(arr, target) 기본 사용법

int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int target1 = 17;
System.out.println(Arrays.binarySearch(arr, target)); // 5 반환
System.out.println(Arrays.binarySearch(arr, target1)); // -6 반환 (=5*(-1)-1)

// EX : BOJ 1920
// input
// 생략...

// run & output -> nlogn 또는 mlogn 
StringBuilder sb = new StringBuilder();
Arrays.sort(inArr1, 0, N); // ASC (범위지정 가능)
for(int i = 0 ; i<M;i++){
    int findIndex = Arrays.binarySearch(inArr1, 0, N, inArr2[i]); // (범위지정 가능)
    if(findIndex<0) sb.append(0).append('\n');
    else sb.append(1).append('\n');
}
System.out.println(sb);

binarySearch 좀 더 자세한 실습 -> 못 찾았을때 음수값의 자세한 의미 설명

range(범위) 를 준 방법 -> 예로 1, 3, 1 은 인덱스 1~3 범위에서 1값 있나 찾고 없어서 -2 위치가 반환

직접 객체에 적용해보기 + 정렬까지 -> y만 고려했을 때

직접 객체에 적용해보기 + 정렬까지 -> y,x 둘다 고려했을 때

정렬만 람다로 했을때

binarySearch, lower_bound, upper_bound 직접 구현 방식

• 이분탐색으로 target의 왼쪽, 오른쪽 위치 구하는 함수 lower_bound, upper_bound 는 애초에 java에서 제공하지 않으므로 직접 구현해줘야 함
• upper_bound() - lower_bound() 형태로 중복수의 개수를 구할 수 있다는점
  • 바킹독님 의 그림부분을 참고
  • lower bound는 데이터내 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴
  • upper bound 는 K값보다 처음으로 큰 값이 나오는 위치를 리턴
  • 중복수 예를 들어보면,
    • {5,5,5,6} 이 있을 때 lower bound(5)는 0, upper bound(5)는 3 이므로
    • 3-0=3 으로 중복개수 3개 정답 (5의 중복개수를 구한것)

// BOJ 10816 -> 근데, 문제를 보면 알겠지만 해시로도 풀림 (find가 O(1) 이니까)
// -> 아래 풀이와 같이 두가지 풀이를 다 알고 있자
static int n=5;
static int[] a = {1,2,2,2,3};
// 분할정복 -> index 활용방식
public static int binarySearch(int target, int len) { // len = n-1 이 들어올거임
    int st = 0;
    int en = len;
    while(st <= en) { // 찾기위해 '=='까지 포함
        int mid = (st+en)/2;
        if(a[mid] < target) st = mid+1;
        else if(a[mid] > target) en = mid-1;
        else return mid; // 찾음
    }
    return -1; // 못찾음
}
public static int lower_bound(int target, int len) {
    int st = 0;
    int en = len;
    while(st < en) {
        int mid = (st+en)/2;
        if(a[mid] < target) st = mid+1; // target 발견시 st는 그 첫 위치 유지됨
        else en = mid; // (a[mid] >= target) -> en=mid 반복시 target 끝이 보장됨
    }
    return st; // 그림보면 알겠지만 결국 'st=mid=en' 이 되므로 en 리턴도 상관없을 거임
}
public static int upper_bound(int target, int len) {
    int st = 0;
    int en = len;
    while(st < en) {
        int mid = (st+en)/2;
        if(a[mid] <= target) st = mid+1; // '초과 값 위치' 구하는게 목표니까 mid+1 한것
        else en = mid; // (a[mid] > target)
    }
    return st;
}
/**
추가) 응용ver -> 백준2467 - 용액 -> 이해안되면 문제를 읽어볼것
 * 기존 문제점 : lower_bound 는 target 못 찾으면 그 뒤의 값을 가져오는데 정작 필요한건 앞의 값일 수도 있다. (문제 특성상) 그렇다고 앞의 값을 가져오게 로직을 수정해도 그 뒤의 값이 또 필요할 수도 있다.
 * 결론 : 따라서 이분탐색을 사용하되 내부 로직에는 두 값의 합(sum)에 따라 갱신해야 한다.
 * st 가 커질수록 합이 커질거고, en 이 작아질수록 합이 작아지는걸 생각
 * 따라서 sum < 0 과 sum > 0 과 sum == 0 때로 나눠 구현하자.
 * 또한 기존 문제점에서 언급했듯이, 찾는값이 없을때 앞의 값이 클수도 뒤의 값이 클수도 있어서
 * 찾는 과정에서 계속 outArr(정답값)도 갱신해야한다.
 */
for (int i = 0; i < N; i++) { // NlogN 복잡도
    int st = i+1;
    int en = N-1;
    while (st <= en) {
        int mid = (st+en)/2;
        int temp = inArr[i] + inArr[mid];
        if(sum >= Math.abs(temp)) {
            sum = Math.abs(temp);
            outArr[0] = inArr[i];
            outArr[1] = inArr[mid];
        }
        if(temp < 0) st = mid+1;
        else if(temp > 0) en = mid-1;
        else break; // temp == 0 을 찾은것
    }
}

1. 좌표압축

나중에 문제를 풀다보면 입력값의 범위는 1에서 10^9 정도로 굉장히 큰데 그거를 배열 인덱스처럼 쓰고 싶을 수 있습니다.
그러면 뭔가 크기 순으로 번호를 0번부터 매기고 싶다는 생각이 들텐데 이런 일을 하는게 좌표압축입니다.

• (BOJ 18870 문제 기준) 좌표압축 방법 : 정렬 -> 중복 제거 -> 이후 이분탐색 수행
  • List 로 입출력 한 경우에는 Set 으로 중복제거하는게 매우 간편
  • 아래 예시 코드는 그냥 앞, 뒤 값 비교해서 중복제거

//BOJ 18870
//문제에서 "중복제외하고 나보다 작은수가 몇개인가" 를 물어보는중
//따라서 정렬 및 중복제거후 "이분탐색" 로 구한 위치가 자신보다 작은수의 개수가 됨
//(결론) 이 문제에서의 좌표압축은?? 정렬 -> 중복제거 -> 이분탐색
Arrays.sort(inArr, 0, N); // 정렬
int index = 0;
for(int i = 0 ; i<N-1;i++){
    if(inArr[i] != inArr[i+1]) {
        inArr[index++] = inArr[i]; // 중복제거
    }
}
inArr[index] = inArr[N-1]; // 마지막 원소 넣기
for(int i = 0 ; i<N;i++){
    sb.append(lower_bound(outArr[i],index+1)); // 이분탐색
    // lower_bound 말고 binarySearch 도 당연히 가능
    // 해당 상황에서는 둘다 똑같은 이분탐색 효과 동일
    sb.append(" ");
}
System.out.println(sb);

좌표압축 또다른 예

// 문자 -> index로 변환 함수(좌표압축 함수)
public static int getID(char c) { 
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26; // 26은 A~Z 이후에 자리를 두기 위함
} // 아스키코드는 A가 a보다 작음

2. 최장 증가 부분 수열(LIS)

이분의 글을 참고 -> 그림보면 이해하기 쉬움!

정렬을 하지 않고!! 바로 이분 탐색 응용! -> lower_bound 사용 + 역추적 사용

• 참고) N이 100정도면 DP로 해결가능 -> DP는 매우 간단

int[] check = new int[N+1]; // 역추적
int[] outArr = new int[N+1];
check[0]=0;
outArr[0]=inArr[0]; //init
int j = 0; //init -> size
for(int i=1; i<N; i++){
    if(outArr[j] < inArr[i]) {
        outArr[j+1] = inArr[i]; // update
        check[i]=j+1;
        j+=1;
    }else{
        int idx = lower_bound(inArr[i], j, outArr);
        outArr[idx] = inArr[i]; // update
        check[i]=idx;
    }
}

3. N=40 범위 해결 아이디어

백준1208_부분수열의 합 2 문제의 경우 모든 경우의수를 따지면 2^40 으로 시간초과가 발생한다.

따라서 이를 N/2 로 절반씩 나눠서 구하면 2^20, 2^20 으로 대략 2백만 밖에 되지 않으므로 시간초과를 벗어날 수 있다.

• 참고 : 잘 정리하신 분

투 포인터

투 포인터는 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

• 이분 탐색으로 투 포인터 문제를 풀던가, 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우가 많다.
• 예시로 수 고르기 를 풀어본다 -> 용액 도 있는데 이분탐색이나 투포인터로 풀 수 있다.
  • 아래 코드는 2개의 포인터를 적절히 조건에 맞게 움직여서 해를 구하는 모습이다.
  • 문제 특성상 “두 수의 차이가 M이상” 인 숫자들을 구하는게 중요하므로,
  • j 가 while문으로 한번에 커져도 그 사이값은 i의 +-M 범위를 벗어나질 않기 때문에,
  • O(N) 복잡도로 끝날 수 있는 것이다.

// BOJ 2230
Arrays.sort(inArr);
int result=2000000100;
int i = 0; int j = 1; // 투 포인터
for(i = 0; i<N; i++){
    while(j<N&&Math.abs(inArr[j]-inArr[i])<M) j++;
    if(j==N) break;
    result = Math.min(result, Math.abs(inArr[i]-inArr[j]));
}

// BOJ 2467
/**
 * - 아이디어
 *     정렬된 원소의 가장 왼쪽과 오른쪽부터 원소를 뽑아보겠습니다.
 *     즉, 두 개의 포인터 l, r의 위치를 0, N - 1로 선택하고, 이 두 포인터가 가리키는 값을 항상 채택하는 전략을 사용하겠습니다. 우리는 이 두개의 포인터를 적절히 이동시켜 0에 가까운 값을 항상 유지할 수 있고, 정답을 찾을 수 있습니다.
 *
 *     1. v[l] + v[r] == 0 일 때
 *     우리가 찾던 두 개의 값이므로 바로 이 두 값을 출력하면 끝입니다.
 *     2. v[l] + v[r] < 0 일 때
 *     두 값의 합이 음수면, l이라는 포인터를 오른쪽으로 이동(l++)해서 이 합을 증가시킬 수 있습니다.
 *     3. v[l] + v[r] > 0 일 때
 *     같은 원리로 r 포인터를 왼쪽으로 이동해서 이 합을 감소시킬 수 있습니다.
 *
 *     이를 두 포인터가 만나기 전까지(l < r) 반복하면 문제를 해결할 수 있습니다.
 */
l=0; r=N-1; // 투포인터
outArr = new int[2];
int sum = Integer.MAX_VALUE;
while(l<r) {
    int temp = Math.abs(inArr[l]+inArr[r]); //크기로 보기 위해 절대값
    if(sum >= temp) {
        sum = temp;
        outArr[0] = inArr[l];
        outArr[1] = inArr[r];
    }
    if(inArr[l]+inArr[r] == 0) break;
    else if(inArr[l]+inArr[r] < 0) l++;
    else if(inArr[l]+inArr[r] > 0) r--;
}
if(l>=r) l--; //원복
//output
System.out.println(outArr[0]+" "+outArr[1]);

해시

해시 함수 : 임의 길이의 데이터를 고정될 길이의 데이터로 대응시키는 함수 (5135:Kim,…)

해시 테이블 : 아래 그림

• 같은 키가 삽입될 수 있어서 충돌은 어쩔 수 없다.
• 대표적인 충돌회피 방법은 Chaining, Open Addressing 이 존재한다.
  • Chaining : 연결리스트로 회피
  • Open Addressing : Probing 방식으로 데이터 저장해서 회피
    • Linear Probing : 충돌 발생 시 오른쪽으로 1칸씩 이동
      • 단점 : Clustering(군집화) 발생
    • Quadratic Probing : 충돌 발생 시 오른쪽으로 1,3,5,… 칸씩 이동
      • 단점 : 약하긴 하지만 Clustering(군집화) 발생
    • Double Hashing : 충돌 발생 시 이동 칸의 수를 새로운 해시함수로 계산하는 방식
      • 단점 : 적중률이 낮아짐

해시 테이블을 기반으로 이루어진 라이브러리

• HashSet, HashMap, LinkdedHashMap(참고) 이 3개만 기억
  • Python 의 set, dict 자료구조랑 유사
    • set : value만 존재 => 중복 불가에 주로 사용
      • 특히 순서를 지키지 않기 때문에 get하려면 처음부터 순회(iteration)를 통해서 구해야하므로 이런 경우 반드시 map을 사용 권장
    • map : key, value 쌍으로 존재 => 보통 이것을 사용
      • 조회할 때 최적화 하려면 entrySet 을 활용
  • LinkdedHashMap는 순서를 지키고 싶을때 사용(물론 set도 존재)
• 이름이 비슷한 BST 자료구조인 TreeSet, TreeMap 과 구분할 것
  • BST는 정렬 순서를 유지하는 대신에 해시보다 느리므로, “속도, 정렬” 2가지를 놓고 자료구조 선택하면 된다.
    • insert, erase, find update 동작이 해시는 O(1), RBT는 O(logN)
    • 그러나, RBT는 원소가 크기 순으로 정렬되어 있다는 큰 장점이 있다.
      • 즉, 정렬되어 있다 보니lower_bound 같은걸 logN에 바로 구할 수 있다.

// 1. HashSet
HashSet<String> hs = new HashSet<>();
hs.add("java");
System.out.println(hs.contains("java")); // true

// 2. HashMap
HashMap<String, Integer> hm = new HashMap<>();
hm.put("java", 0); // save => 기존 값이 있어도 덮어씌움
hm.get("java"); // load
// 키(="java")가 없으면 put으로 새로 생성
if (!hm.containsKey("java")) hm.put("java", 1); 
// 키(="java")가 있으면 해당 값 출력, 없으면 설정한 defalut값(=3) 출력
hm.getOrDefault("java", 3);
// 키가 있으면 1씩 증가시키는 응용방식!
hm.put("java", hm.getOrDefault("java", 0)+1);
// keySet() 함수로 맵 순회
for(String key : hm.keySet()) { 
	hm.get(key); // 순서가 보장되지 않음
}
       
// 3. LinkdedHashMap => 값들 HashMap이라 동일하다 가정
for(String key : hm.keySet()) {				
	lhm.get(key); // 순서가 보장
}

keySet, entrySet 를 적절히 사용해야 최적화 할 수 있다.

• key만 순회할 때 keySet 은 적절하다. 단, value도 필요할 때는??
• value도 필요할 때는 entrySet 이 적절하다.
  • hm.get(key) 를 하는 순간 또 keySet을 찾는 과정을 반복하기 때문이다. (자세한 내용을 아래링크)
  • 참고 링크 : entrySet 사용이유

// 비권장
for (String key : hm.keySet()) { // keySet을 하고
    if (hm.get(key) != 0) { // hm.get(key)를 하는것은 비권장
        answer = key;
    }
}

// 권장
for (Entry<String, Integer> entry : hm.entrySet()) {
    if (entry.getValue() > 0) {
        answer = entry.getKey();
        break;
    }
}

이진 검색 트리, 레드 블랙 트리(BST, RBT)

자바의 TreeSet, TreeMap 은 이진 검색 트리 + 자가 균형을 이루는 RBT 자료 구조로 정의되어서 제공한다.

참고로 BST를 구현을 해야할 것 같을때는 배열로는 구현X, 차라리 class로 구현하자.

해시에서 비교를 했기 때문에 간단히 설명

• TreeSet : 중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장 순서를 유지하지도 않는다.
  • 여전히 get메소드 없고, iterator를 사용
  • TreeSet<Integer> set = new TreeSet<Integer>(Collections.reverseOrder()); //내림차순
  • Integer inArr2[] = set.toArray(new Integer[set.size()]); //Set to Array

• TreeMap : TreeSet과 동일한데 추가로 key, value 쌍으로 저장된다.

• prev, next나 lower_bound 이런게 필요할 때 유용
• 개념 정리 게시글 참고 : 고급트리 개념

// 1. TreeSet
TreeSet<Integer> ts = new TreeSet<>();
ts.add(2);
ts.add(4);
ts.add(3);
ts.add(5);
ts.add(1);
ts.add(1); // 중복 x
System.out.println(ts.contains(0));	// true
System.out.println(ts.size()); // 5
System.out.println(ts.headSet(3)); //처음 ~ 3 전까지
System.out.println(ts.tailSet(3)); //3 ~ 끝까지
System.out.println(ts.subSet(3, 5)); //3 ~ 5 전까지
Iterator<Integer> iter = ts.iterator();
while(iter.hasNext()) {
    System.out.print(iter.next());
}
System.out.println();

// 2. TreeMap
TreeMap<String, Integer> tm = new TreeMap<>();
tm.put("TreeMap1", 10);
tm.put("TreeMap2", 20);
tm.put("TreeMap3", 30);
System.out.println(tm.get("TreeMap3")); //30
System.out.println(tm.containsKey("TreeMap3"));	//true
System.out.println(tm.size()); // 3
System.out.println(tm.firstKey()); //처음 Key값
System.out.println(tm.lastKey());  //마지막 Key값
System.out.println(tm.firstEntry()); //처음 Entry값
System.out.println(tm.lastEntry()); //마지막 Entry값
System.out.println(tm.headMap("TreeMap2")); //처음 ~ TreeMap2 전까지
System.out.println(tm.tailMap("TreeMap2")); //TreeMap2 ~ 끝까지
System.out.println(tm.subMap("TreeMap1", "TreeMap3")); //TreeMap1 ~ TreeMap2 까지

우선순위 큐

우선순위 큐는 pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐이다.
힙은 완전 이진트리로 구성된 자료구조 이다.

힙(최대 힙, 최소 힙) 자료구조를 사용해서 만든 우선순위 큐

• 원소 추가 - O(logN)
• 우선순위 높은 원소 확인 - O(1)
• 우선순위 높은 원소 제거 - O(logN)
• 배열 자료구조 + 우선순위 큐의 경우 => 순서대로 O(1), O(N), O(N)
• TreeSet 도 최소값과 최대값을 빼고, 원소 추가하고 다 가능하고 복잡도도 심지어 동일하다.
  • 그래도 굳이 priority_queue 를 사용하는 이유는 같은 O(logN)이라고 해도 TreeSet 보다 빠르고, 공간도 적게 차지한다.
  • 따라서 priority_queue 의 기능만 딱 필요할 경우엔 TreeSet이 아닌 priority_queue 를 사용해주자!

힙을 배열로 나타낼 때

• x번지의 왼쪽, 오른쪽 자식 : 2x, 2x+1
• x번지의 부모 : x/2

최소 힙, 최대 힙 특징

• 최소 힙 : 부모가 자식보다 작음
• 최대 힙 : 부모가 자식보다 큼

PriorityQueue 제공!!

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // 최소힙
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder()); // 최대힙

pq.add(3);
pq.remove();
pq.peek(); // root

우선순위 비교를 직접 커스텀 할 경우!!

• (추가) 정렬은 앞에서 정리한 방식을 사용하자. 이방식 사용하지 말고.

public static void main(String[] args) throws IOException {
    PriorityQueue<Pair> pq=new PriorityQueue<>(Pair::compareTo);
    pq.add(new Pair(1,2));
    pq.add(new Pair(1,1));
    pq.add(new Pair(2,3));
    pq.add(new Pair(2,1));

    while(!pq.isEmpty()){
        Pair p=pq.peek(); // root
        System.out.println(p.first+" "+p.second);
        pq.remove();
    }
}

static class Pair {
    int first;
    int second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    // Pair 클래스 내에 비교 함수!!
    public int compareTo(Pair p) {
        if(this.second < p.second) {
            return -1; // 음수는 오름차순
        }
        else if(this.second == p.second) {
            if(this.first < p.first) {
                return -1;
            }
        }
        return 1;
    }
}

그래프

그래프는 인접행렬과 인접리스트로 표현할 수 있다.

추가로 간선리스트로도 표현 가능하다.

• 보통 인접리스트 사용이 많며 E가 V^2보다 훨씬 작을 때(sparse=희소) 사용한다.
• 모든 간선 길이가 동일 하면 “BFS”로 거리를 구할 수 있고, 길이가 다르다면 “플로이드, 다익스트라” 알고리즘을 활용해야 한다.
  • (뇌피셜) 물론 객체에 거리 담아서 BFS 순회하면 거리계산 되긴 할것이다.

간선리스트 작성 예시

List<int[]> list = new ArrayList<>();
for(int i=0; i<M; i++) {
    stk = new StringTokenizer(br.readLine());
    int v1 = Integer.parseInt(stk.nextToken());
    int v2 = Integer.parseInt(stk.nextToken());
    int c = Integer.parseInt(stk.nextToken());
    list.add(new int[] {v1,v2,c}); // 인접리스트 보다도 더 간단한 형태
}
for(int i=0; i<M; i++) {
    System.out.println(Arrays.toString(list.get(i)));
}

1. 그래프의 BFS, DFS 순회

이미 BFS, DFS 정리가 많이 되어있기 때문에 “인접리스트, 인접행렬” 사용 모습을 제시한다.

(1) 인접행렬

static void dfs(int n) {
    visited[n] = true;
    sb.append(n).append("->");
    for(int i=1; i<=4; i++) {
        if(!matrix[n][i] || visited[i]) continue;
        dfs(i);
    }
}
static void bfs(int n){
    Queue<Integer> qu = new ArrayDeque<>();
    qu.offer(n);
    visited[n]=true;
    while(!qu.isEmpty()){
        int v = qu.poll();
        sb.append(v).append("->");
        for(int i=1; i<=4; i++) {
            if(!matrix[v][i] || visited[i]) continue;
            qu.offer(i);
            visited[i]=true;
        }
    }
}
//OUTPUT
/*
1->2->4->3
1->2->3->4
*/

(2) 인접리스트

static List<List<Integer>> adjList = new ArrayList<>();
static List<List<int[]>> adjList2 = new ArrayList<>(); // 따로 class 안만들고 int배열...
static boolean[] visit;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
    for(int i=0; i<5; i++) {
        adjList.add(new ArrayList<Integer>());
    }
    adjList.get(1).add(2); adjList.get(1).add(4);
    adjList.get(2).add(3); adjList.get(2).add(4);
    adjList.get(3).add(2);
    adjList.get(4).add(3);
	adjList2.get(1).add(new int[] {1,2,3}); // 이런 문법식도 있다.
    
    visit = new boolean[5];
    bfs(1);
    System.out.println(sb);

    sb.setLength(0);
    visit = new boolean[5];
    dfs(1);
    System.out.println(sb);
}

static void dfs(int n) {
    visit[n]=true;
    sb.append(n).append("->");

    List<Integer> list = adjList.get(n);
    for(Integer i : list) { // v 로부터 갈 수 있는 정점만 들어 있다.
        if ( visit[i] ) continue;
        dfs(i);
    }
}

static void bfs(int n) {
    Queue<Integer> qu = new ArrayDeque<>();
    qu.offer(n);
    visit[n]=true;

    while(! qu.isEmpty()) {
        int v = qu.poll();
        sb.append(v).append("->");

        List<Integer> list = adjList.get(v);
        for(Integer i : list) { // v 로부터 갈 수 있는 정점만 들어 있다.
            if ( visit[i] ) continue;
            visit[i] = true;
            qu.offer(i);
        }
    }
}
//OUTPUT
/*
1->2->4->3
1->2->3->4
*/

2. 그래프 사이클 탐색(순회)

dfs(1) 실행가정 : dfs(1)->dfs(2)->dfs(3)->dfs(1) 사이클형성 때 dfs(1) 시점에 finished[]가 false라서 사이클 확인이 가능

dfs(3)->dfs(2)->dfs(1) 순서로 탐색 종료 처리됨(=finished[]가 true되는 순서)

• 사이클 찾는 문제 -> 백준16724 피리 부는 사나이

• 사이클 아닌것을 찾는 문제도 참고 -> 백준9466_텀 프로젝트

static void dfs(int node)
{
  // 해당 노드가 몇번째에 방문되었는지 기록
  discovered[node] = node_order++;

  for (int nxt: graph[node])
  {
    if (discovered[nxt] == -1) //방문안한 경우
      dfs(nxt);
    else if (!finished[nxt])
      ++cycle;
    // else는 cross edge인 경우 : Back edge나 Forward edge가 아닌 a->b로의 간선
  }

  // 해당 노드의 함수 호출이 종료되었음을 명시
  finished[node] = true;
}

트리

트리는 무방향이고 사이클이 없는 연결 그래프이다.

• 트리의 순회방식 - BFS&DFS 순회, 이진 트리의 순회 등등
• 여러가지 트리 - Segment
• 참고로 BST, RBT는 위에서 이미 정리 그리고 우선순위 큐에 사용한 힙도 (완전)이진트리
  • 좀 더 다양한 트리(Splay, OST, Range, Interval)는 고급트리 개념 에서 참고
  • 힙은 완전이진트리+위 아래 관계, 이진탐색트리는 좌우 관계로 기억

1. 트리의 BFS, DFS 순회

• 트리를 BFS 할 때 root부터 순회하므로 임의의 노드에서 그 노드의 부모는 이미 방문한거고, 자식들만 방문을 안한 상태인 것이다.
• 따라서 따로 visited배열 필요없이 p배열(부모) 을 알고 있으면 된다. -> 중복순회X 라는것

// DFS는 큐->스택 바꾸면 동일하게 동작
static List<Integer>[] inArr = new ArrayList[10];
static int[] p = new int[10]; // 부모 배열
static int[] depth = new int[10]; // 트리 깊이 기록
static void bfs(int root) {
	Queue<Integer> qu = new LinkedList<>();
    qu.add(root);
    while(!qu.isEmpty()) {
        int cur = qu.peek();
        qu.remove();
		System.out.println(cur);
        for (int nxt : inArr[cur]) {
            if(p[cur] == nxt) continue; // 부모는 방문한 상태라서 continue
            qu.add(nxt);
            p[nxt] = cur; // parent 기록
            depth[nxt] = depth[cur] + 1; // dist배열 채우듯이 동일
        }
    }
}

2. 트리의 지름

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.

이를 구하는 로직은 생각보다 간단하다.

• 시작할 임의의 노드에서 DFS 1번을 통해 가장 긴 정점을 구한다.
• 해당 구한 정점에서 DFS 1번을 통해 또 가장 긴 정점을 구한다.
• 총 DFS 2번을 통해서 2개의 정점을 구했고 이 두정점의 거리가 트리의 지름이 된다.

3. 이진 트리의 순회(전,중,후,BFS,DFS) + 분할정복

이진트리는 자식을 2개씩 가지는 트리이다. -> 총 노드 개수 약 2ⁿ개

인덱스 : 부모는 idx/2, 자식은 idx*2, idx*2+1 이라는 특징

• 레벨 순회(=bfs(root)) : 높이 순서대로 방문한다.
  • root를 시작점으로 bfs 돌리면 높이 순서대로 위에서부터 차례로 순회한다.
• 깊이 순회(=dfs(root)) : 깊이 순서대로 방문한다.
• 전위, 중위, 후위 순회 -> 구현 간단해서 코드 생략
  • 전위 : 위 -> 왼 -> 오
  • 중위 : 왼 -> 위 -> 오
    • 특히 왼쪽에서 오른쪽으로 차례대로 선택하여 순서를 정한것과 같다.
  • 후위 : 왼 -> 오 -> 위
• 분할정복 : 재귀적인 분할정복 기법으로 이진트리를 순회하는 방식

분할정복 코드

• 아래 코드는 프로그래머스 문제중 이진트리판별 문제의 코드인데,
• 루트노드가 0일땐 서브트리 노드들도 모두 0 이어야 하는 특별한 조건을 넣은 상태
  • 문제에서 준 조건일 뿐 실제로 이진트리가 이렇다는건 아니다.
• 트리 -> 분할정복 -> 루트위주 연산 이부분을 꼭 기억하자.

/* 분할정복 예시 코드 - isBinaryTree() 시작 가정 */
// 제일 하위 노드부터 시작
public Boolean isBinaryTree(String binary) {
    // base condition
    if(binary.length()==0) return true; // leaf 노드에서의 재귀므로 end지점

    int root = binary.length()/2; // 이진트리의 루트노드 찾는 간단한 방식(부모)
    String left = binary.substring(0, root);
    String right = binary.substring(root+1);
    if(binary.charAt(root) == '0') { // 루트 노드가 0이라면 서브 트리도 모두 0
        return isZeroTree(left) && isZeroTree(right);
    }
    else { // 루트 노드가 1이라면 서브 트리 검사
        return isBinaryTree(left) && isBinaryTree(right);
    }

}

public Boolean isZeroTree(String binary) {
    // base condition
    if(binary.length()==0) return true;

    int root = binary.length()/2;
    String left = binary.substring(0, root);
    String right = binary.substring(root+1);
    if (binary.charAt(root) == '1') { // 루트 노드가 1이라면 실패
        return false;
    }
    else { // 루트 노드가 0이라면 서브트리 계속 확인
        return isZeroTree(left) && isZeroTree(right);    
    }
}

일반적인 BFS, DFS

static int[] tree = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
static StringBuilder sb = new StringBuilder();

public static void main(String[] args) {
    // 제일 상위(root)노드부터 시작
    bfs(1);
    System.out.println(sb);

    sb.setLength(0); // sb 초기화
    dfs(1);
    System.out.println(sb);
}
static void dfs(int depth) {
    //base condition
    if(depth >= tree.length) return;
    //recursion
    sb.append(tree[depth]).append(" ");
    dfs(depth*2); // 자식
    dfs(depth*2+1);
}
static void bfs(int depth) {
    Queue<Integer> qu = new ArrayDeque<>();
    qu.offer(depth);

    while(! qu.isEmpty()){
        int curIdx = qu.poll();
        sb.append(tree[curIdx]).append(" ");
        // 현재 curIdx 에서 갈 수 있는 곳을 qu 에 답는다. (자식)
        if(curIdx*2 < tree.length) qu.offer(curIdx*2);
        if(curIdx*2+1 < tree.length) qu.offer(curIdx*2+1);
    }
}
/*
OUTPUT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
 */

문제풀이 : 사칙연산 유효성 검사_1233 SWEA

• 입력은 1번 노드부터 N번 노드까지 이진트리 형태로 주어짐

// 반복문 ver -> 꼭 재귀가 아니어도 for문도 풀이가 된다는것
static int N, ans;
static char[] node;
static StringBuilder sb = new StringBuilder();

public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    for(int t=1; t<=10; t++) {
        N = Integer.parseInt(br.readLine());
        node = new char[N+1];

        for(int i=1; i<=N; i++) { // 두번째 입력항목만
            node[i] = br.readLine().split(" ")[1].charAt(0);
        }

        if( N%2 == 0) { // 자식 노드가 1개인 경우 바로 0 처리
            sb.append("#").append(t).append(" ").append(0).append('\n');
            continue;
        }

        ans=1;
        int idx = N; // 마지막 노드부터 유효성 검사

        while( idx != 1 ) {
            // 자식 노드가 모두 숫자이고, 부모노드가 연산자이어야 함.
            if ( ! Character.isDigit(node[idx])
                || ! Character.isDigit(node[idx-1])
                || Character.isDigit(node[idx/2])) {
                ans = 0;
                break;
            }
            node[idx/2] = '1'; // 부모 노드를 숫자로
            idx -= 2; // 자식노드 2개 확정이라 -2 씩 접근 가능
        }
        sb.append("#").append(t).append(" ").append(ans).append('\n');
    }
    System.out.println(sb);
}

// 재귀 ver
static int N, ans;
static char[] node;
static StringBuilder sb = new StringBuilder();

public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    for(int t=1; t<=10; t++) {
        N = Integer.parseInt(br.readLine());
        node = new char[N+1];

        for(int i=1; i<=N; i++) { // 두번째 입력항목만
            node[i] = br.readLine().split(" ")[1].charAt(0);
        }

        if( N%2 == 0) { // 자식 노드가 1개인 경우 바로 0 처리
            sb.append("#").append(t).append(" ").append(0).append('\n');
            continue;
        }

        // 재귀호출
        ans = dfs(1) ? 1 : 0; // root 부터 재귀호출 시작
        sb.append("#").append(t).append(" ").append(ans).append('\n');
    }
    System.out.println(sb);

}

// x 위치의 노드가 유효한지 return
static boolean dfs(int x) {
    // 기저 조건
    if( x > N ) return false;

    if( Character.isDigit(node[x])) { // => 숫자 노드 이면 자식이 없어야 한다.
        if( x*2 > N ) return true;
        return false;
    }else { // 연산자 노드
        // 두 자식 노드의 유효성에 의존
        // 두 자식 노드가 모두 유효해야 true
        return dfs(x*2) && dfs(x*2+1);
    }

}

4. Segment Tree(구간합)

여러개의 데이터가 연속으로 있을 때 배열 에서는 그 구간의 합을 구할때 복잡도가 N이 걸리는데, 이걸 세그먼트 트리 를 이용해서 logN으로 개선시키려는 목적

• 리프 노드: 배열의 연속된 값 그 자체
• 내부 노드: 왼쪽 자식과 오른쪽 자식의 합
• 아래 그림을 꼭 기억하면 충분히 segmentBuild 함수정도는 만들 수 있을 것이다.
  • 재귀를 너무 이해하려고 하는것 보다 아래 상태공간 트리를 재귀함수로 짜려고 노력하는게 중요하다.

/**
 * BOJ 2042
 * 구간 합 구하는 함수 : segmentSum
 * 트리의 노드 수정하는 함수 : segmentUpdate
 * 세그먼트 트리 만드는 함수 : segmentBuild
 */
static int N, M, K;
static long[] inArr;
static long[] outArr;

// node(outArr)가 담당하는 구간 : start, end
public static long segmentBuild(int start, int end, int node) {
    if(start == end) { // base condition
        outArr[node] = inArr[start];
        return outArr[node];
    }

    int mid = (start+end) / 2; // 왼, 오 구간 나누기
    outArr[node] = segmentBuild(start, mid, node*2) + segmentBuild(mid+1, end, node*2+1);
    return outArr[node];
}

// 구하는 합 구간 : left, right
public static long segmentSum(int start, int end, int left, int right, int node) {
    // 1. 겹치지 않는 경우 => base condition
    if((left < start && right < start) || (left > end && right > end)) return 0;

    // 2. 완전히 포함되는 경우 => base condition
    if(left <= start && right >= end) return outArr[node];

    // 3. 나머지 경우(자식 트리 탐색) => 왼, 오 탐색
    int mid = (start+end) / 2;
    return segmentSum(start, mid, left, right, node*2) + segmentSum(mid+1, end, left, right, node*2+1);
}

// 수정할 노드 인덱스 : idx, 수정할 값 : dif
public static void segmentUpdate(int start, int end, int idx, long dif, int node) {
    // 1. 겹치치 않는 경우
    if((start < idx && end < idx) || (start > idx && end > idx)) return;
    // 2. 완전히 포함되는 경우
    if(start <= idx && end >= idx) outArr[node] += dif;

    // base condition (무한루프 안빠지게)
    if(start==end) return;
    // 3. 나머지 경우(자식 트리 탐색)
    int mid = (start+end) /2;
    segmentUpdate(start, mid, idx, dif, node*2);
    segmentUpdate(mid+1, end, idx, dif, node*2+1);
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());
    inArr = new long[N];
    outArr = new long[N*4];
    for(int i = 0 ;i <N; i++){
        inArr[i] = Long.parseLong(br.readLine());
    }
    // run & output
    StringBuilder sb = new StringBuilder();
    segmentBuild(0, N-1, 1); // 인덱스 1부터 저장해야 인덱스 연산 편안
    for(int i = 0 ; i<M+K; i++){
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        long c = Long.parseLong(stk.nextToken()); // type 조심

        if(a==1) {
            // segmentUpdate
            // b번째 수에 c를 더하는게 아닌,
            // b번째 수를 c로 바꿔야 하는건 `c-inArr[b-1]` 를 더해야 한다는 의미이다.
            segmentUpdate(0, N-1, b-1, c-inArr[b-1], 1);
            inArr[b-1] = c; // b번째 수를 값 c로 변환
        } else{ // a==2
            // segmentSum
            sb.append(segmentSum(0, N-1, b-1, (int)c-1, 1)).append('\n');
        }
    }
    System.out.println(sb);
}

위상정렬

위상정렬(Topological Sort) : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬

BFS(큐)로도 풀이가 가능하고 DFS로도 풀이가 가능한데 둘다 보여주겠다.

• 단순히 부모 자식관계를 위배하지만 않으면 되므로 생각보다 간단한 정렬이다.
• indegree가 0인게 제일 부모이며 최외각에 존재하는건 자명하다.
• 위상정렬은 특히 DP 관점으로도 볼 수 있는데 BOJ1005 를 보자.

// BOJ 2252
public static List<Integer>[] inArr = new ArrayList[32005];
public static int[] outArr = new int[32005];
public static int[] indegree = new int[32005];

public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    int N = Integer.parseInt(stk.nextToken());
    int M = Integer.parseInt(stk.nextToken());
    for(int i=0; i<=N; i++) inArr[i] = new ArrayList<>();
    for(int i=0; i<M; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int n1 = Integer.parseInt(stk.nextToken());
        int n2 = Integer.parseInt(stk.nextToken());
        inArr[n1].add(n2); // graph (방향 그래프)
        indegree[n2]++;
    }
    //run
    Queue<Integer> qu = new ArrayDeque<>();
    for(int i=1; i<=N; i++) {
        if(indegree[i]==0) qu.offer(i);
    }
    int idx = 0;
    while(!qu.isEmpty()) {
        int node = qu.poll();
        outArr[idx++] = node;
        for(int nxt : inArr[node]) {
            indegree[nxt]--;
            if(indegree[nxt]==0) qu.offer(nxt); // indegree 가 0이면 큐 삽입
        }
    }
    //output
    for(int i=0; i<N; i++) {
        sb.append(outArr[i]).append(" ");
    }
    System.out.println(sb);
}

// BOJ 1005
/**
 * outArr배열을 dp배열처럼 사용
 * bottom-top 방식의 "for문" 이 "위상정렬" 로 치환으로 이해하자
 */
while (!qu.isEmpty()) {
    int size = qu.size();
    for (int s = 0; s < size; s++) {
        int cur = qu.poll();
        for (int nxt : graph[cur]) {
            //dp처럼 값 갱신
            outArr[nxt] = Math.max(outArr[cur] + buildTime[nxt], outArr[nxt]);
            //큐 삽입시점
            inDegree[nxt]--;
            if (inDegree[nxt] == 0) {
                qu.offer(nxt);
            }
        }
    }
}

SCC(Strongly Connected Component) 도 추가로 BOJ 문제 하나 풀어보겠다.

• SCC 개념익히기 좋은 글 : 네이버 블로그
• 출력때 TreeMap 활용

/**
 * BOJ 2150
 * 1. G를 DFS로 순회하면서 finish time을 구한다 => 위상정렬 구하는 또다른 방식중 하나
 * 2. G의 에지 방향을 반대로 한 𝐺^𝑇 (transpose of G)에서 DFS를 이용해 순회
 * => 단, 앞에서 구한 finish time의 역순을 고려하면서 DFS 적용
 * 3. 𝐺^𝑇 에서 도달가능한 것들의 집합은 SCC가 된다
*/
static int V, E;
static List<Integer>[] inArr = new ArrayList[10005];
static List<Integer>[] reArr = new ArrayList[10005];
static List<Integer>[] outArr = new ArrayList[10005];
static int[] f = new int[10005]; // finish time
static boolean[] visited = new boolean[10005];

public static void main(String[] args) throws IOException {
    for(int i = 0 ; i<10005; i++) {
        inArr[i] = new ArrayList<>();
        reArr[i] = new ArrayList<>();
        outArr[i] = new ArrayList<>();
    }
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    V = Integer.parseInt(stk.nextToken());
    E = Integer.parseInt(stk.nextToken());
    for(int i = 0 ; i<E;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        inArr[a].add(b);
        reArr[b].add(a);
    }

    // run
    // 1. Graph를 DFS로 순회하면서 finish time을 구한다
    Stack<Integer> st = new Stack<>();
    for(int i = 1; i<=V; i++) {
        if(!visited[i]) {
            dfs(i, st);
        }
    }
    Arrays.fill(visited, false);
    int SCCNum = 0;

    // 2. G의 에지 방향을 반대로 한 𝐺^𝑇 (transpose of G)에서 DFS를 이용해 순회
    // => 단, 앞에서 구한 finish time의 역순을 고려하면서 DFS 적용 (역순=내림차순 고려)
    while(!st.isEmpty()) {
        int cur = st.peek(); st.pop();

        if(visited[cur]) continue; // 이미 SCC 그룹에 속해 있다는 것
        redfs(cur, SCCNum);
        SCCNum++;
    }

    // output
    StringBuilder sb = new StringBuilder();
    sb.append(SCCNum).append('\n');

    TreeMap<Integer, Integer> map = new TreeMap<>(); // key를 기준으로 오름차순 정렬.
    for(int i = 0 ; i<SCCNum; i++) {
        Collections.sort(outArr[i]);
        map.put(outArr[i].get(0), i); // key : SCC 그룹의 첫번째 항, value : 인덱스.
    }

    // map의 value를 이용하여 => RBT 특성상 정렬되었기 때문
    // 첫번째 항이 작은 순서대로 출력. => 문제에서 출력 조건때문에!
    map.keySet().forEach(key -> {
        int cur = map.get(key);

        for (int nxt : outArr[cur]) {
            sb.append(nxt + " ");
        }
        sb.append("-1\n");
    });
    System.out.println(sb);
}

public static void dfs (int depth, Stack st) {
    visited[depth] = true;

    for(int nxt : inArr[depth]) {
        if(!visited[nxt]) {
            dfs(nxt, st);
        }
    }
    st.add(depth); // 탐색 종료시점
}

public static void redfs(int depth, int SCCNum) {
    visited[depth] = true;
    // 3. 𝐺^𝑇 에서 도달가능한 것들의 집합은 SCC가 된다
    outArr[SCCNum].add(depth);

    for(int nxt : reArr[depth]) {
        if(!visited[nxt]) {
            redfs(nxt, SCCNum);
        }
    }
}

최소 신장 트리(MST)

• 바킹독 : https://blog.encrypted.gg/1024
• 예전에 정리한 개념글 : MST-Prim,Kruskal

크루스칼, 프림 알고리즘이 대표적

크루스칼 알고리즘은 Union Find라는 알고리즘을 선행학습 하고 아래 코드를 이해할 것.

-> 예전에 정리한 개념글 위에 링크 확인

크루스칼

// BOJ 1197
/**
MST - kruskal
1. 비내림차순 정렬(가중치 기준) => 제일 작은 가중치부터 선택하려고 하는것
2. Union Find(=합집합 찾기) 이용 : 같은 그래프에 속하는지를 판별하기 위함

흐름 : find(root) -> equal(p,q) -> merge(q->p)
- initial(n)은 전체를 자기자신을 루트로 가지게 9개의 트리가 독립적으로 만들어진 상태
- find(i)는 자신이 속한 트리의 루트가 누구인지 찾음
- equal(p,q)는 동일한지 확인
- merge(p,q)는 p집합, q집합을 합병(q의 root가 p의 root를 가리키게 바꾸는것)
*/
public static int[] p = new int[10005]; // 부모기록 배열(-1 init)
static int find(int x) {
    if(p[x] < 0) return x; // 부모가 없는경우 자신이 부모
    return p[x] = find(p[x]); // 부모 찾을때 까지 재귀
}
static boolean isUnion(int u, int v) {
    u = find(u); v = find(v); // u,v 노드의 root(각 집합에서의 root를 찾는것)
    if(u==v) return true;
    if(p[u] > p[v]) {
        int temp = u;
        u=v; v=temp;
    } // swap(u,v)
    p[u] += p[v]; // 자식이 많은쪽에 merge => 여기선 p[u]로
    p[v] = u; // 부모 기록
    return false;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    int V = Integer.parseInt(stk.nextToken());
    int E = Integer.parseInt(stk.nextToken());
    List<Edge> inArr = new ArrayList<>(E); // 또는 그냥 배열로 고고
    for(int i = 0;i<E;i++){
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken()); // 가중치
        inArr.add(new Edge(a,b,c));
    }

    // run
    // 1. 비내림차순 정렬(가중치 기준)
    ObjectSort ob = new ObjectSort();
    Collections.sort(inArr, ob);

    // 2. Union Find(=합집합 찾기) 이용 : 같은 그래프에 속하는지를 판별하는 알고리즘
    Arrays.fill(p, -1); // init
    int result = 0;
    int cnt = 0;
    for(Edge edge : inArr){
        if(isUnion(edge.a, edge.b)) continue;
        result += edge.c;
        cnt++;
        if(cnt == V-1) break; // 종료 시점 (모든 노드 방문한 경우)
    }

    // output
    System.out.println(result);
}
static class Edge {
    int a;
    int b;
    int c;
    public Edge(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}
static class ObjectSort implements Comparator<Edge> {
    @Override
    public int compare(Edge o1, Edge o2) {
        return o1.c - o2.c; // 오름차순
    }
}

프림 알고리즘은 우선순위 큐를 이용해서 구현을 하는데, 구현이 좀 복잡하다.

프림

/**
 * 프림 핵심 -> chk, pq, cnt
 */
public static List<Pair>[] inArr = new ArrayList[10005];
public static boolean[] chk = new boolean[10005]; // MST CHECK

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

    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    int N = Integer.parseInt(stk.nextToken());
    int M = Integer.parseInt(stk.nextToken());
    for(int i=0; i<=N; i++) inArr[i] = new ArrayList<>();
    for(int i=0; i<M; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int n1 = Integer.parseInt(stk.nextToken());
        int n2 = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
        inArr[n1].add(new Pair(n1,n2,c));
        inArr[n2].add(new Pair(n2,n1,c)); // 무방향
    }
    //run
    chk[1] = true; // 1번 정점부터 시작하겠음
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    for(Pair nxt : inArr[1]) {
        pq.offer(nxt);
    }
    int cnt=0; int result=0; // 현재선택된 간선 수 와 총비용
    while(cnt < N-1) {
        Pair cur = pq.poll();
        if(chk[cur.n2]) continue;
        chk[cur.n2] = true; // 새로운 정점을 MST에 추가
        cnt++; result+=cur.c;
        for(Pair nxt : inArr[cur.n2]) {
            if(chk[nxt.n2]) continue;
            pq.offer(nxt); // 큐 삽입 시점
        }
    }
    System.out.println(result);
}

static class Pair implements Comparable<Pair>{
    int n1; int n2; int c;
    public Pair(int n1, int n2, int c) {
        this.n1=n1;this.n2=n2;this.c=c;
    }

    @Override
    public int compareTo(Pair o) {
        return this.c-o.c; // 최소 가중치 간선부터.. 오름차순
    }
}

최단 경로 트리

• 바킹독 : https://blog.encrypted.gg/1035, https://blog.encrypted.gg/1037
• 예전에 정리한 개념글 : Floyd, Dijkstra
• 유형
  • 거리가 일정??? BFS 로 최단 거리 구하기
  • 거리가 다르다??? 플로이드(모든정점-N^3) or 다익스트라(하나의정점-ElgE) 로 구하기
    • 다익스트라 의 경우 가중치 음수는 사용 못하는데, 이땐 벨만포드 알고리즘이라는 것을 사용한다. (필요시 공부해 볼 것)
    • 중요한점
      플로이드 는 모든 정점에서 모든 정점과의 최단 경로를 구하고,
      다익스트라 는 하나의 정점에서 모든 정점과의 최단 경로를 구한다.
      • 이때, 다익스트라 는 하나의 정점에서 하나의 정점과의 최단 경로를 구할 수 있다는 점도 이해하자.
      • 즉, 꼭 모든 정점과의 경로로만 생각하지말고, A->B 처럼 하나의 정점에서 하나의 정점의 최소경로로도 생각 할 수 있다고 이해하라는 것

플로이드 알고리즘은 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이라 O(n³)의 큰 복잡도를 가진다.
다만, 구현이 3중 for문으로 간단히 할 수 있으며 n이 1000정도면 이 알고리즘을 써도 된다.

• 최단 거리 테이블(2차원) 이 채워진다 => 코드보면 d배열 관련인데 생각보다 쉬운 로직!
• 근데, 경로까지 구하고싶으면 테이블 하나 더 만들어서 기록해놔야 한다 => nxt배열에 기록

// BOJ 11780
// n이 100이라 플로이드 가능
// 3중 for문에서 k순서가 제일 처음이란걸 꼭 기억
// run 주석 부분이 핵심@@@
public static int[][] d = new int[105][105];
public static int[][] p = new int[105][105];
public static int n, m;

public static void main(String[] args) throws IOException {
    // input => 1 4 2, 1 4 1 처럼 들어올 수 도 있으니 처음부터 d 에 min 값으로 갱신하자.
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine());
    n = Integer.parseInt(stk.nextToken());
    stk = new StringTokenizer(br.readLine());
    m = Integer.parseInt(stk.nextToken());
    for(int i = 1 ; i<=n ;i++) {
        Arrays.fill(d[i], 10000000); // init 플로이드
    }
    for(int i = 1; i<=m; i++){
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
        d[a][b] = Math.min(d[a][b], c);
        p[a][b] = b; // 경유 경로 기록

    }
    for(int i = 1; i<=n;i++) d[i][i] = 0; // 자기 자신의 경로는 당연히 비용 0

    // run => DP 방식(i,j,k만 잘이해하면 생각보다 간단)
    for(int k = 1; k<=n; k++) { // k를 경유하는 곳이라 생각하면 됨.
        for(int i = 1; i<=n; i++) { // i->j 를 가는 경로 비용을 구하는것
            for(int j = 1; j<=n; j++) {
                if(d[i][k]+d[k][j] < d[i][j]){
                    //d[i][j] = Math.min(d[i][j], d[i][k]+d[k][j]);
                    d[i][j] = d[i][k]+d[k][j];
                    p[i][j] = p[i][k]; // 경유 경로 기록
                }
            }
        }
    }

    // output => 출력이 여러개 있음.
    StringBuilder sb = new StringBuilder(); // 가중치
    for(int i = 1 ; i<=n;i++){
        for(int j = 1; j<=n; j++){
            if(d[i][j] == 10000000) sb.append(0).append(' ');
            else sb.append(d[i][j]).append(' ');
        }
        sb.append('\n');
    }
    System.out.print(sb);

    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            sb = new StringBuilder(); // 경로
            if(d[i][j] == 0 || d[i][j] == 10000000) {
                System.out.println(0);
                continue;
            }
            int st = i;
            int sizes = 1;
            while(st != j) { // 자기 자신 가리키는 순간 탈출
                sb.append(st).append(' ');
                st = p[st][j];
                sizes++;
            }
            sb.append(j);
            System.out.print(sizes);
            System.out.println(" "+sb);
        }
    }
}

다익스트라 알고리즘 은 하나의 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이므로 복잡도는 플로이드보다 한단계 작은 O(n²) 이다.

• 참고 : 가중치가 음의 값이 있으면 이 알고리즘 사용 불가
• 동작원리는 간단한데 한 정점에서 갈 수 있는 최단 거리 정점을 택하면서 갱신해나가면 된다.
• 여기서 개선된 알고리즘이 있는데 우선순위 큐를 활용한 알고리즘이다. 이 로직을 기억
  • 우선순위 큐에 거리를 다 넣어둔다음 매번 최소인걸 선택하는 로직
  • 물론 경로까지 구하는 방법은 플로이드 알고리즘 때와 유사

/**
 * BOJ 11779
 * 참고 : 다익스트라 특성상 경로를 여러개 구할 수 있기 때문에, 어떤 경로든 백준에서 정답 처리한다.
 * run 주석 부분이 핵심@@@
 */
static int[] d = new int[1005]; // 최단 거리 테이블
static int[] pre = new int[1005]; // 이전 경로 기록

public static void main(String[] args) throws IOException {
    Arrays.fill(d, 100000000); // 거리배열 초기화
    List<Pair>[] inArr = new ArrayList[1005];
    for(int i = 0 ; i<1005; i++) inArr[i] = new ArrayList<>();
    PriorityQueue<Pair> pq = new PriorityQueue<>(); // 최소힙

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(stk.nextToken());
    stk = new StringTokenizer(br.readLine());
    int M = Integer.parseInt(stk.nextToken());
    for(int i = 0 ; i<M;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int u = Integer.parseInt(stk.nextToken());
        int v = Integer.parseInt(stk.nextToken());
        int w = Integer.parseInt(stk.nextToken());
        inArr[u].add(new Pair(v, w));
    }
    stk = new StringTokenizer(br.readLine(), " ");
    int st = Integer.parseInt(stk.nextToken()); // 시작 노드
    int en = Integer.parseInt(stk.nextToken()); // 도착 노드
    // input 끝

    // run
    d[st] = 0; // 시작 노드는 가중치 0
    pq.add(new Pair(st, d[st])); // 시작노드, 가중치 추가
    while(!pq.isEmpty()) {
        Pair cur = pq.poll();
        if(d[cur.v] != cur.w) continue; // 기존 거리배열의 비용과 우선순위큐 비용이 다르면 PASS -> 해당 우선순위큐 값은 버려야함. 최단 거리가 아닌 원소이기 때문
        for(Pair nxt : inArr[cur.v]) {
            if(d[nxt.v] <= d[cur.v]+nxt.w) continue; // 기존 거리배열의 비용이 새로운 비용보다 작으면 최소비용이므로 PASS
            d[nxt.v] = d[cur.v]+nxt.w;
            pq.add(new Pair(nxt.v, d[nxt.v]));
            pre[nxt.v] = cur.v; // 이전 경로 기록
        }
    }

    // output
    System.out.println(d[en]); // 최소 비용
    // 경로 구해서 출력
    List<Integer> path = new ArrayList<>();
    int cur = en;
    while(cur != st) {
        path.add(cur);
        cur = pre[cur];
    }
    path.add(cur);
    System.out.println(path.size());
    StringBuilder sb = new StringBuilder();
    for(int i = path.size()-1; i>=0; i--) {
        sb.append(path.get(i)).append(' ');
    }
    System.out.println(sb);
}
static class Pair implements Comparable<Pair>{
    private int v; // 도착노드
    private int w; // 가중치
    public Pair(int v, int w) {
        this.v = v;
        this.w = w;
    }
    // 우선순위 큐 비교 오버라이딩
    @Override
	public int compareTo(Pair o) {
		return this.w-o.w; //비용 오름차순 (가장 작은것이 먼저나오게)
    }
}

컴퓨터그래픽스 관련

CCW, 교차여부, 다각형 면적, 다각형 포함, 볼록 껍질(외피=Convex Hull), 평면 소거법(직사각형 합집합=Plane Sweeping) 관련

• 개념 정리 게시글 참고 : 컴퓨터그래픽스 개념

1. 기본 기하 연산(between, interaction)

• between, interaction 함수만 보면 충분!!

/*
EX : BOJ 17387
ccw 함수(cw : counter clockwise = 시계방향)
direction 함수 : 세점의 회전방향 검사에 따라서 1,-1,0 반환(오른손 활용)
between 함수 : 점 c가 선분 (a,b)에 위치하는가 검사
interactionProp 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하지 않는 경우
interaction 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하는 경우

자료형 왠만하면 long long 쓰자
*/
public static List<Point> inArr = new ArrayList<>();
public static long ccw(Point a, Point b, Point c) {
    // 깊은 복제
    Point a1 = new Point(a.x, a.y);
    Point b1 = new Point(b.x, b.y);
    Point c1 = new Point(c.x, c.y);
    // 원점 이동
    a1.x -= c1.x;
    a1.y -= c1.y;
    b1.x -= c1.x;
    b1.y -= c1.y;
    // det(행렬식) 계산
    return a1.x*b1.y-a1.y*b1.x;
}

public static int direction(Point a, Point b, Point c) {
    // 좌 : 1, 우 : -1, 일 : 0
    if(ccw(a,b,c) > 0) return 1;
    if(ccw(a,b,c) < 0) return -1;
    return 0; // ccw(a,b,c)==0
}

// 점 c가 a,b직선 상에 존재하는지 판별함수
public static boolean between(Point a, Point b, Point c) {
    // 1. 일직선 상에 존재하나 먼저 확인
    if (ccw(a, b, c) != 0) return false;
    else {
        // 2. 수직 여부 확인 후 범위제한
        if (a.x == b.x) {
            if ((c.y >= a.y && c.y <= b.y) || (c.y >= b.y && c.y <= a.y)) return true;
        }
        else {
            if ((c.x >= a.x && c.x <= b.x) || (c.x >= b.x && c.x <= a.x)) return true;
        }
        return false;
    }
}

// 추가조건 : 교차점 포함(끝 점이 교차하는 그런것들 다 포함)
public static int interaction(Point a, Point b, Point c, Point d) {
    // (a,b,c)*(a,b,d) ==-1 && (c,d,a)*(c,d,b)==-1 성립하면 교차
    // 추가조건 때문에 <=0로 판별
    if (direction(a, b, c) * direction(a, b, d) <= 0 && direction(c, d, a) * direction(c, d, b) <= 0) {
        // direction 함수는 방향만을 나타내기 때문에 만약 0인 경우 일직선상,
        // 두 직선이 서로 접하는지 범위제한을 줘서 판단할 필요가 있음(between 함수 활용)
        if (direction(a, b, c) * direction(a, b, d) == 0 && direction(c, d, a) * direction(c, d, b) == 0) {
            // 점 c또는 d가 a,b직선 상에 존재하나 판단
            // 점 a또는 b가 c,d직선 상에 존재하나 판단
            if (between(a, b, c) || between(a, b, d)|| between(c, d, a) || between(c, d, b))
                return 1;
            else
                return 0;
        }
        else
            return 1;
    }
    else
        return 0;
}

// <참고>
// 선분 교차 검사 (교차점 제외) => 선분 ab, cd
bool interactionProp(Point a, Point b, Point c, Point d) {
    // (a,b,c)*(a,b,d) ==-1 && (c,d,a)*(c,d,b)==-1 성립하면 교차
	return direction(a, b, c) * direction(a, b, d) < 0 && direction(c, d, a) * direction(c, d, b) < 0;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    for(int i = 0 ; i<2;i++){
        stk = new StringTokenizer(br.readLine(), " ");
        long x1 = Long.parseLong(stk.nextToken());
        long y1 = Long.parseLong(stk.nextToken());
        long x2 = Long.parseLong(stk.nextToken());
        long y2 = Long.parseLong(stk.nextToken());
        inArr.add(new Point(x1,y1)); // 직선 1개
        inArr.add(new Point(x2,y2)); // 직선 1개
    }
    // run & output
    System.out.println(interaction(inArr.get(0), inArr.get(1), inArr.get(2),inArr.get(3)));
}
static class Point {
    long x; long y;
    public Point(long x, long y) {
        this.x = x; this.y = y;
    }
}

2. 다각형 면적과 포함 계산

/*
BOJ 2166
area 함수 : 다각형 면적 구하기
*/
public static List<Point> inArr = new ArrayList<>();

public static long ccw(Point a, Point b, Point c) {
    // 깊은 복제
    Point a1 = new Point(a.x, a.y);
    Point b1 = new Point(b.x, b.y);
    Point c1 = new Point(c.x, c.y);
    // 원점 이동
    a1.x -= c1.x;
    a1.y -= c1.y;
    b1.x -= c1.x;
    b1.y -= c1.y;
    // det(행렬식) 계산
    return a1.x*b1.y-a1.y*b1.x;
}

// 외적 전부 더하기
public static double area() {
    double ret = 0;
    int n = inArr.size(); // 다각형의 정점 개수
    for(int i = 1; i<n; i++) {
        int nxtI = (i+1) % n; // 마지막에 index n->0으로 바뀜
        ret+=ccw(inArr.get(i), inArr.get(nxtI), inArr.get(0)); // index 0 정점 기준 외적 구했음
    }
    return Math.abs(ret) / 2.0;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<N;i++){
        stk = new StringTokenizer(br.readLine(), " ");
        long a = Integer.parseInt(stk.nextToken());
        long b = Integer.parseInt(stk.nextToken());
        inArr.add(new Point(a, b));
    }

    // run & output4
    double result = Math.round(area()*10)/10.0; // 소수 둘째자리에서 반올림 (첫재 자리까지 표기)
    System.out.printf("%.1f", result); // 자바는 지수를 24E8 이런형태로 출력해서 printf 문을 사용
}
static class Point {
    long x; long y;
    public Point(long x, long y){
        this.x = x; this.y = y;
    }
}

/**
BOJ 1688
insidePolygon 함수 : 다각형 포함 구하기
다각형 포함 문제 (교차점 홀수면 내부 포함 인정)
*/
public static List<Point> barrier = new ArrayList<>();
public static List<Point> friends = new ArrayList<>(); // 대연, 영훈, 범진

public static long ccw(Point a, Point b, Point c) {
    // 복제
    Point a1 = new Point(a.x, a.y);
    Point b1 = new Point(b.x, b.y);
    Point c1 = new Point(c.x, c.y);
    // 원점이동
    a1.x -= c1.x;
    a1.y -= c1.y;
    b1.x -= c1.x;
    b1.y -= c1.y;
    // det(행렬식) 계산
    return a1.x* b1.y- a1.y* b1.x;
}

// 점 c가 a,b직선 상에 존재하는지 판별함수
public static boolean between(Point a, Point b, Point c) {
    // 1. 일직선 상에 존재하나 먼저 확인
    if (ccw(a, b, c) != 0) return false;
    else {
        // 2. 수직 여부 확인 후 범위제한
        if(a.x == b.x) { // 세로선
            if((c.y>=a.y&&c.y<=b.y)||(c.y>=b.y&&c.y<=a.y)) return true;
        }else{ // 가로선
            if((c.x>=a.x&&c.x<=b.x)||(c.x>=b.x&&c.x<=a.x)) return true;
        }
        return false;
    }
}

public static boolean leftTurn(Point a, Point b, Point c) {
    if(ccw(a,b,c)>0) return true;
    return false;
}

public static boolean insidePolygon(int friIndex) {
    int crossing = 0; // 교차 홀수여야 내부라 판단
    int n = barrier.size();
    Point fri = friends.get(friIndex);
    for (int i = 0 ; i<n; i++){
        int iNxt = (i+1) % n;
        Point a = barrier.get(i);
        Point b = barrier.get(iNxt);
        // 1. 경계면인지 확인(여기선 경계면도 포함이라서 true 로)
        if(between(a,b,fri)) return true;
        // 2. 교차점 판별(범위 비교로 판단)
        if((a.y<fri.y && b.y>=fri.y&&leftTurn(a,b,fri)) ||
           (b.y<fri.y && a.y>=fri.y&&leftTurn(b,a,fri)))
            crossing++;
    }
    if(crossing%2!=0) return true;
    return false;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        long a = Long.parseLong(stk.nextToken());
        long b = Long.parseLong(stk.nextToken());
        barrier.add(new Point(a,b));
    }
    for(int i = 0 ; i<3; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        long a = Long.parseLong(stk.nextToken());
        long b = Long.parseLong(stk.nextToken());
        friends.add(new Point(a,b));
    }

    // run
    for(int i = 0 ; i<3; i++) {
        if(insidePolygon(i)) System.out.println(1);
        else System.out.println(0);
    }

}
static class Point {
    long x; long y;
    public Point(long x, long y) {
        this.x = x; this.y = y;
    }
}

3. 볼록 외피(Convex Hull)

O(NlogN ) 방법 소개 - 참고 사이트 : https://www.crocus.co.kr/1288

/*
1. 우선 기준점을 잡는다. (보통 기준점은 y좌표가 가장 작은 것을 기준으로 한다.)
=> y좌표, x좌표 기준 오름차순 정렬해서 기준점을 P[0]으로 바로 잡자

2. 그리고 이 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다.
=> 각도에 따라 정렬 핵심 (참고 : 원점 이동한 상대위치로 각도 구함)
=> arctan(y,x) 활용 : 두 점사이의 절대각도 구함

3. 컨벡스 헐 알고리즘(그라함 스캔(Graham's Scan) 알고리즘)을 이용한다.
=> 사이트 그림보면 이해하기 쉬움
*/
public static List<Point> inArr = new ArrayList<>();

public static long ccw(Point a, Point b, Point c) {
    // 복제
    Point a1 = new Point(a.x, a.y);
    Point b1 = new Point(b.x, b.y);
    Point c1 = new Point(c.x, c.y);
    // 원점이동
    a1.x -= c1.x;
    a1.y -= c1.y;
    b1.x -= c1.x;
    b1.y -= c1.y;
    // det(행렬식) 계산
    return a1.x* b1.y- a1.y* b1.x;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<N;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        long a = Long.parseLong(stk.nextToken());
        long b = Long.parseLong(stk.nextToken());
        inArr.add(new Point(a,b));
    }

    // run
    // y좌표, x좌표 기준 오름차순 정렬
    ObjectSort ob = new ObjectSort();
    Collections.sort(inArr, ob);
    // 기준점(=inArr.get(0))기준 상대위치 기록 (따라서 i=1부터)
    for (int i = 1; i<N; i++){
        inArr.get(i).p = inArr.get(i).x - inArr.get(0).x;
        inArr.get(i).q = inArr.get(i).y - inArr.get(0).y;
    }
    // => 기준점에서 각도 비교로 반시계 정렬(기준점(=0) 제외)
    List<Point> subList = inArr.subList(1, N); // 추출 리스트
    Collections.sort(subList, ob); // 정렬
    List<Point> inArr2 = new ArrayList<>();
    inArr2.add(inArr.get(0));
    inArr2.addAll(subList); // 병합

    // 1st, 2st로 바로 초기값 사용
    Stack<Integer> st = new Stack<>(); // index 기록하므로 그냥 int자료형 사용
    st.add(0); st.add(1); // 0, 1 index 푸시

    // 전처리 끝
    // 알고리즘 시작
    int next = 2;
    while (next < N) {
        while (st.size() >= 2) {
            int first, second;
            second = st.peek();
            st.pop();
            first = st.peek();

            // leftTurn 사용
            if (ccw(inArr2.get(first), inArr2.get(second), inArr2.get(next)) > 0) {
                st.add(second);
                break;
            }
        }
        st.add(next++); // next push
    }

    // output
    System.out.println(st.size());
}
public static double getAngle(Point a) {
    return Math.atan2(a.q, a.p); // 아크탄젠트로 각도 계산
}
static class ObjectSort implements Comparator <Point> {
    @Override
        public int compare(Point a, Point b) {
        if(getAngle(a) != getAngle(b)) return Double.compare(getAngle(a), getAngle(b));
        if(a.y != b.y) return Long.compare(a.y, b.y);
        return Long.compare(a.x, b.x); // == a.x < b.x ? -1 : (a.x==b.x?0:1)
    }
}
static class Point {
    long x; long y; // 절대위치
    long p; long q; // 상대위치
    public Point(long x, long y){
        this.x = x; this.y = y;
        this.p = 0; this.q = 0;
    }
}

4. 평면 소거법(Plane Sweeping) => 합집합

• BOJ2185 를 풀어야하는데, 아래 코드로는 풀리지 않는다..
• 아래코드는 좌표가 겹치지 않고, 왼쪽아래 오른쪽위 좌표 순서로 받는것을 가정했을때 올바르게 동작한다.

public static List<Rectangle> inArr = new ArrayList<>();
public static List<Integer> Q = new ArrayList<>();
public static List<Integer> S = new ArrayList<>();
public static int[] counts = new int[10005];

public static int unionArea() {
    int sweepLine = 0; int delta = 0; int area = 0; // 면적
    for (int i = 0; i<Q.size(); i++) { // x값 전부 순회!
        sweepLine = Q.get(i);
        Rectangle R = new Rectangle(0,0,0,0);
        // 0. 사용할 사각형 선택(x값 겹칠때 마다 선택)
        for(int j = 0 ; j<inArr.size(); j++) {
            if(inArr.get(j).x1 == Q.get(i) || inArr.get(j).x2==Q.get(i)) {
                R = inArr.get(j);
                break;
            }
        }

        // 1. counts배열 구하기(y값 활용)
        // sweepLine이 만나는 사각형의 왼쪽 가로선만 +1, 오른쪽 가로선은 -1
        if (sweepLine == R.x1) delta = 1;
        else delta = -1; // => R.x2와 만난다고 볼 수 있음

        int y1 = R.y1; int y2 = R.y2;
        for (int j = 0 ; j<S.size(); j++) {
            if(y1 <= S.get(j) && S.get(j) < y2)
                counts[j] += delta; // S[j]~S[j+1] 구간에 겹쳐진 사각형의 수
        }

        // 2. 면적 계산 시작
        // 현재 내부면적 세로줄(S[j + 1] - S[j])
        int curLen = 0;
        for (int j = 0; j < S.size(); j++) {
            if (counts[j] > 0) { // counts배열 있는 값만(사각형 있는 경우에만)
                curLen += S.get(j+1) - S.get(j);
            }
        }

        // 현재 내부면적 가로줄(Q[i+1]-Q[i])
        if ((i + 1) < Q.size()) {
            // 사각형 면적 : 세로*가로
            area += curLen * (Q.get(i+1) - Q.get(i)); // 현재 구한 면적 더함
        }
    }
    return area;
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    int temp = 0;
    for(int i = 0 ; i<N;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int x1 = Integer.parseInt(stk.nextToken());
        int y1 = Integer.parseInt(stk.nextToken());
        int x2 = Integer.parseInt(stk.nextToken());
        int y2 = Integer.parseInt(stk.nextToken());
        inArr.add(new Rectangle(x1, y1, x2, y2));
        Q.add(x1); Q.add(x2); S.add(y1); S.add(y2);
    }
    // x축, y축 기록한 배열들 꼭 오름차순으로 정렬 후 사용
    Collections.sort(Q);
    Collections.sort(S);

    // run & output
    System.out.println(unionArea());
}
static class Rectangle {
    int x1; int y1; int x2; int y2;
    public Rectangle(int x1, int y1, int x2, int y2) {
        this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2;
    }
}

Network Flow(=Max-Flow, Min-Cut, 이분 매칭)

Ford-Fulkerson(DFS.복잡도:flow), Edmonds-Karp(BFS.복잡도:VE^2), Dinic’s Algorithm(BFS,DFS.복잡도:EV^2) 가 있으며 여기서 Dinic's 만 암기해도 충분

아래 코드에서는 Dinic's 와 멀티 Source, Sink의 경우 예를 소개한다.

• Ford-Fulkerson과 Edmonds-Karp는 DFS, BFS만 다르며 나머지는 로직이 정확히 동일

• Dinic’s 는 BFS로 레벨트리 구하고, DFS(재귀)로 연산을 진행

• 중요한 점

  • “이분 매칭” 문제를 “Max-Flow” 문제로 치환해서 풀 수 있다.

  • “Min-Cut” 문제는 그냥 “Max-Flow” 로 풀었을 때 답과 동일하다.

  • 보통 문제를 푸는 방식은 문제에 적합하게 “그래프” 를 설계한 후 풀어나간다.

    • “그래프” 그리는 TIP (아래 그림은 Jerry And Tom예시)

      

      • 그래프에는 에지를 그릴텐데 반드시 유량이 아닌 용량을 적어줄 것
        • 햇갈리면 안되는게 유량은 나중에 계산할 때 값 생기기 시작
      • 멀티 Source, Sink의 경우?? 외부에 S, T 노드를 임의로 추가해서 사용
        • Max Flow는 S->T 로 흐르는 최대 유량을 구하는 형태이기 때문
        • 임의로 S, T를 추가했으므로 그래프 그릴때 용량을 잘 설정해야함
      • 복잡한 문제들은 에지를 안주고 직접 에지를 구해야 할때도 존재
        • 예시 문제 : Jerry and Tom
        • 참고 : 해당 예시에서는 에지를 직접 구해야하며, 해당 에지는 “선분교차” 여부에 따라 구해진다.
• 참고 용어
  • Residual network graph : 잉여(=잔여) 그래프
  • Level graph : 레벨 그래프(=트리의 각 노드들 깊이 표현)
  • Argmenting path : 가능한 s->t 경로
    • 이것을 BFS or DFS 로 구함

/*
BOJ 14286 문제. Min-Cut 문제 => "Max-Flow"
<Dinic's Algo>
0. init 잉여그래프(c:용량으로)
1. 레벨그래프를 구함 - BFS를 사용
2. flow를 찾음 - DFS와 레벨그래프 사용(차단유량 찾기. 1개가아닌 가능한 전부) with 잉여그래프
3. update 잉여 그래프 = 유량 update 를 의미
4. TotalFlow 에 구한 flow들을 더함
=> 1~4 를 반복 - 레벨그래프 구하기 불가할 때 까지(1번 과정이 불가할때까지)

참고 : 코드상에서 work는 속도 개선용일 뿐, reverseIdx는 굉장히 중요(ArrayList에 기록하다보니 필요하게 됨)
 */
static int N, M, S, T;
static List<Node>[] inArr = new ArrayList[505];
static int[] level = new int[505];
static int[] work = new int[505]; // 속도 개선용

public static boolean bfs() {
    Arrays.fill(level, -1);
    Queue<Integer> qu = new LinkedList<>(); // bfs

    level[S] = 0; // start
    qu.add(S);
    while(!qu.isEmpty()) {
        int curIdx = qu.peek(); qu.remove();
        for(Node cur : inArr[curIdx]) {
            // 잔여용량 부족이나 레벨이미 채워진 경우엔 continue
            if(cur.c<=cur.f || level[cur.nxtIdx] != -1) continue;
            level[cur.nxtIdx] = level[curIdx] + 1; // => 깊이 기록을 의미
            qu.add(cur.nxtIdx);
        }
    }
    if(level[T] != -1) return true;
    return false; // 이 경우는 BFS 순회 실패의 경우. 즉, Dinic's 의 종료시점
}

// "residual capacity : 잔여용량" 의 개념이 중요
public static int dfs(int curIdx, int curRsdCap) {
    // base condition
    if (curIdx == T) return curRsdCap; // 끝 도달시 return

    //        for (Node cur : inArr[curIdx]) {
    for(int i = work[curIdx]; i<inArr[curIdx].size(); i++) {
        Node cur = inArr[curIdx].get(i);
        // 잔여용량 부족이나 레벨 차가 1이 아닌 경우엔 continue
        if(cur.c<=cur.f || level[cur.nxtIdx] - level[curIdx] != 1) continue;
        // 최소 유량 탐색
        int nxtRsdCap = cur.c-cur.f; // 잔여용량 : 용량-유량
        int minFlow = dfs(cur.nxtIdx, Math.min(nxtRsdCap, curRsdCap));
        // 3. update 잉여 그래프 = 유량 update 를 의미
        if(minFlow > 0) {
            cur.f += minFlow;
            inArr[cur.nxtIdx].get(cur.reverseIdx).f -= minFlow;
            work[curIdx] = i;
            return minFlow;
        }
    }
    work[curIdx] = inArr[curIdx].size();
    return 0;
}

public static void main(String[] args) throws IOException {
    // init
    for(int i = 0 ;i <505;i++) inArr[i] = new ArrayList<>();
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    int a, b, c;
    for(int i = 0 ;i <M;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(stk.nextToken());
        b = Integer.parseInt(stk.nextToken());
        c = Integer.parseInt(stk.nextToken()); // weight
        // 0. init 잉여그래프(c:용량으로)
        inArr[a].add(new Node(b, inArr[b].size(), c,0));
        inArr[b].add(new Node(a, inArr[a].size()-1, c,0)); // 양방향 간선
    }
    stk = new StringTokenizer(br.readLine(), " ");
    S = Integer.parseInt(stk.nextToken());
    T = Integer.parseInt(stk.nextToken());

    // run
    int totalFlow = 0; // 제거된 최소 간선 가중치 합
    while(true) {
        // 1. 레벨그래프를 구함 - BFS를 사용
        if(!bfs()) break;
        // 2. flow를 찾음 - DFS와 레벨그래프 사용(차단유량 찾기)
        Arrays.fill(work, 0); // 속도 개선용으로 사용(안써도 됨)
        int flow = dfs(S, 10000000); // 10000000 : 임의로 설정한 잔여용량
        // 3. TotalFlow 에 구한 flow들을 더함
        totalFlow += flow;
    }

    // output
    System.out.println(totalFlow);
}
static class Node {
    int nxtIdx; // 연결 노드인겸 index
    int reverseIdx; // 역방향 노드의 배열 index
    int c; // capacity(용량)
    int f; // flow(유량)
    public Node (int nxtIdx, int reveresIdx, int c, int f) {
        this.nxtIdx = nxtIdx; this.reverseIdx=reveresIdx; this.c = c; this.f = f;
    }
}

/*
멀티 Source, Sink 의 문제로 볼 수 있다.
풀이
0. 시작(S), 끝(T)를 임의로 지정해서 일반적인 S->T maxflow로 바꾼다.
1. 쥐와 간선에 대한 정보는 "선분 교차 판정"을 이용 => 간선
2. 최대 유량으로 해결 => Dinic's 사용하겠음

EX) S = 0, T = H+M+1
참고 : 양방향이긴 하지만, 실제로 반대방향은 용량이 없는 0으로 꼭 설정
또한, 경계선은 포함하지 않는다고 했으므로 intersect 가 훨씬 간단
*/
static List<Node>[] inArr = new ArrayList[505];
static int[] level = new int[505];
static int[] work = new int[505]; // 속도 개선용
static int N, K, H, M; // N모서리 개수, K용량, H쥐구멍 개수, M쥐의 수
static int S, T; // 시작, 끝
static Point[] house = new Point[1005];
static Point[] hole = new Point[55];
static Point[] mouse = new Point[255]; // H*K

public static long ccw(Point a, Point b, Point c) {
    // 깊은 복제
    Point a1 = new Point(a.x, a.y);
    Point b1 = new Point(b.x, b.y);
    Point c1 = new Point(c.x, c.y);
    // 원점 이동
    a1.x -= c1.x;
    a1.y -= c1.y;
    b1.x -= c1.x;
    b1.y -= c1.y;
    // det(행렬식) 계산
    return a1.x*b1.y-a1.y*b1.x;
}

public static int direction(Point a, Point b, Point c) {
    // 좌 : 1, 우 : -1, 일 : 0
    if(ccw(a,b,c) > 0) return 1;
    if(ccw(a,b,c) < 0) return -1;
    return 0; // ccw(a,b,c)==0
}

// intersect => 직선 2개 교차 판별 (끝점 포함 => 0 가능을 의미)
public static boolean intersect(Point a, Point b, Point c, Point d) {
    // (a,b,c)*(a,b,d) ==-1 && (c,d,a)*(c,d,b)==-1 성립하면 교차
    return direction(a, b, c) * direction(a, b, d) <= 0 && direction(c, d, a) * direction(c, d, b) <= 0;
}

public static boolean bfs() {
    Arrays.fill(level, -1);
    Queue<Integer> qu = new LinkedList<>(); // bfs

    level[S] = 0; // start
    qu.add(S);
    while(!qu.isEmpty()) {
        int curIdx = qu.peek(); qu.remove();
        for(Node cur : inArr[curIdx]) {
            // 잔여용량 부족이나 레벨이미 채워진 경우엔 continue
            if(cur.c<=cur.f || level[cur.nxtIdx] != -1) continue;
            level[cur.nxtIdx] = level[curIdx] + 1; // => 깊이 기록을 의미
            qu.add(cur.nxtIdx);
        }
    }
    if(level[T] != -1) return true;
    return false; // 이 경우는 BFS 순회 실패의 경우. 즉, Dinic's 의 종료시점
}

// "residual capacity : 잔여용량" 의 개념이 중요
public static int dfs(int curIdx, int curRsdCap) {
    // base condition
    if (curIdx == T) return curRsdCap; // 끝 도달시 return

    //        for (Node cur : inArr[curIdx]) {
    for(int i = work[curIdx]; i<inArr[curIdx].size(); i++) {
        Node cur = inArr[curIdx].get(i);
        // 잔여용량 부족이나 레벨 차가 1이 아닌 경우엔 continue
        if(cur.c<=cur.f || level[cur.nxtIdx] - level[curIdx] != 1) continue;
        // 최소 유량 탐색
        int nxtRsdCap = cur.c-cur.f; // 잔여용량 : 용량-유량
        int minFlow = dfs(cur.nxtIdx, Math.min(nxtRsdCap, curRsdCap));
        // update 잉여 그래프 = 유량 update 를 의미
        if(minFlow > 0) {
            cur.f += minFlow;
            inArr[cur.nxtIdx].get(cur.reverseIdx).f -= minFlow;
            work[curIdx] = i;
            return minFlow;
        }
    }
    work[curIdx] = inArr[curIdx].size();
    return 0;
}

public static void main(String[] args) throws IOException {
    // init
    for(int i = 0; i<505; i++)
        inArr[i] = new ArrayList<>();
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());
    H = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    int a, b;
    for(int i = 0 ;i <N;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(stk.nextToken());
        b = Integer.parseInt(stk.nextToken());
        house[i] = new Point(a, b);
    }
    for(int i = 0 ;i <H;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(stk.nextToken());
        b = Integer.parseInt(stk.nextToken());
        hole[i] = new Point(a,b);
    }
    for(int i = 0 ;i <M;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(stk.nextToken());
        b = Integer.parseInt(stk.nextToken());
        mouse[i] = new Point(a,b);
    }

    // run
    // 0. 시작(S), 끝(T)를 임의로 지정해서 일반적인 S->T maxflow로 바꾼다.
    S=0; T=H+M+1; // 시작S: 0, 끝T: H+M+1

    // 1. 쥐와 간선에 대한 정보는 "선분 교차 판정"을 이용 => 간선
    // Edge 구하기 1
    // (초기세팅) 모든 쥐(M)들은 1만큼의 용량 존재, 모든 쥐구멍(H)은 K만큼의 용량 존재
    for (int i = 1; i <= M; i++) { // S=0이므로 i=1부터
        inArr[0].add(new Node(i, inArr[i].size(), 1, 0));
        inArr[i].add(new Node(0, inArr[0].size()-1, 0, 0)); // 양방향
    } // 1~M 사용
    for (int i = M + 1; i <= M + H; i++) { // T=H+M+1이므로 i<=M+H까지
        inArr[i].add(new Node(M+H+1, inArr[M+H+1].size(), K, 0));
        inArr[M+H+1].add(new Node(i, inArr[i].size()-1, 0, 0)); // 양방향
    } // M+1~M+H 사용

    // Edge 구하기 2
    // 쥐와 쥐구멍 에지 생성(교차 확인을 통해)
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < H; j++) {
            boolean flag = true;
            for (int k = 0; k < N; k++) {
                int idx = (k + 1) % N;
                if (direction(hole[j], house[k], house[idx]) == 0) continue; // 쥐구멍이 벽에 있다는건 교차로 판별하면 안됌
                if (intersect(mouse[i], hole[j], house[k], house[idx])) { // 쥐, 쥐구멍 교차 확인
                    flag = false; // 중간에 모서리가 존재한다는 의미
                    break;
                }

            }
            if (flag) {
                // 용량 1 존재. 만약 교차 안했으면 에지자체가 없는거. 그래프 연결 안되어있는것.
                inArr[i+1].add(new Node(M + j + 1, inArr[M+j+1].size(), 1, 0));
                inArr[M+j+1].add(new Node(i + 1, inArr[i+1].size()-1, 0, 0)); // 양방향
            }
        }
    }

    // 2. 최대 유량으로 해결 => Dinic's 사용하겠음
    // run
    int totalFlow = 0; // 제거된 최소 간선 가중치 합
    while(true) {
        // 1. 레벨그래프를 구함 - BFS를 사용
        if(!bfs()) break;
        // 2. flow를 찾음 - DFS와 레벨그래프 사용(차단유량 찾기)
        Arrays.fill(work, 0); // 속도 개선용으로 사용(안써도 됨)
        int flow = dfs(S, 10000000); // 10000000 : 임의로 설정한 잔여용량
        // 3. TotalFlow 에 구한 flow들을 더함
        totalFlow += flow;
    }

    // output
    if (totalFlow == M) System.out.println("Possible");
    else System.out.println("Impossible");
}

static class Node {
    int nxtIdx; // 연결 노드인겸 index
    int reverseIdx; // 역방향 노드의 배열 index
    int c; // capacity(용량)
    int f; // flow(유량)
    public Node (int nxtIdx, int reveresIdx, int c, int f) {
        this.nxtIdx = nxtIdx; this.reverseIdx=reveresIdx; this.c = c; this.f = f;
    }
}

static class Point {
    long x; long y;
    public Point(long x, long y) {
        this.x = x; this.y = y;
    }
}

정수론

피타고라스 관련 구하는 방법은 아래를 참고

/**
 * BOJ16123 메모리 초과 문제로 해결 불가
 * 따라서 원시 피타고라스 쌍 구하는 과정만 익혀보겠음.
 *
 * 그냥 피타고라스는 a^2+b^2=c^2 을 만족하기만 하면 되고
 * 원시 피타고라스는 gcd(a,b,c)=1 즉, 최대공약수=1 까지 만족
 * 아래 알고리즘은 원시 피타고라스를 구하는 것이고, 피타고라스 전부를 구하고 싶다면
 * 구한 a,b,c에 스칼라배를 통해서 나머지 피타고라스 수까지 구하면 된다.
 */
static List<Point> outArr = new ArrayList<>();

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    long L = Long.parseLong(br.readLine()); // n < m <= L
    long a, b, c;
    for(int m = 2; m<=L; m++) {
        if(m%2==0) { // 짝수
            for(int n=1; n<m; n+=2) { // 홀수
                a = (long) (Math.pow(m,2)-Math.pow(n,2));
                b = 2*m*n;
                c = (long) (Math.pow(m,2)+Math.pow(n,2));
                outArr.add(new Point(m,n,a,b,c));
            }
        }
        else { // 홀수
            for(int n=2; n<m; n+=2) {
                a = (long) (Math.pow(m,2)-Math.pow(n,2));
                b = 2*m*n;
                c = (long) (Math.pow(m,2)+Math.pow(n,2));
                outArr.add(new Point(m,n,a,b,c));
            }
        }
    }
    System.out.println(outArr.size()); // 원시 피타고라스 쌍 개수
    // outArr 에 구한 원시 피타고라스 존재
}
static class Point {
    long m; long n; long a; long b; long c;
    public Point(long m, long n, long a, long b, long c){
        this.m=m; this.n=n; this.a=a; this.b=b; this.c=c;
    }
}

일차 디오판토스 방정식 의 개념을 사용한 문제 풀이이며, 문제는 아래 코드 주석에 적혀있다.

중요한점은 확장된 유클리드 개념도 사용했다는 점이며, 나머지는 아래 사진을 보고 이해할 것.

**ax+by=c의 해 존재를 판별하는 방법 => gcd(a,b)

c 성립 유무로 판단**

확장 유클리드 알고리즘을 통해서 gcd(a,b) = a*s+b*t 의 s,t,g 를 구해내고
아래 그림처럼 k를 구한 후 x, y 정수 해를 구할 수 있다.

아래는 아래 코드의 문제를 해결하기 위한 아이디어를 나타낸 그림이다.

/*
입력
5
2 4 18
1 9 12
4 9 100
4 8 19
3 12 100
출력
5
4
14
-1
-1
 */

/**
 * 세 양의 정수 a, b,c 를 읽은 후, ax+by=c을 만족하는 정수 x, y를 찾되
 * |x|+|y|이 최소가 되도록 하는 값을 구하면 되며, 해를 구할수 없는 경우 -1을 출력한다.
 */
public class 디오판토스_과제물 {

    public static void main(String[] args) throws IOException {
        String file = "./eq.inp";
        FileInputStream fileStream = new FileInputStream(file);
        BufferedReader br = new BufferedReader(new InputStreamReader(fileStream));
        StringTokenizer stk;
        StringBuilder sb = new StringBuilder();
        int T = 0;
        int a, b, c;
        int r, r1, r2, s, s1, s2, t, t1, t2, q, g;
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i<T; i++) {
            //cin >> a >> b >> c;
            stk = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(stk.nextToken());
            b = Integer.parseInt(stk.nextToken());
            c = Integer.parseInt(stk.nextToken());
            r1 = a; r2 = b;
            s1 = 1; s2 = 0;
            t1 = 0; t2 = 1;
            while (r2 > 0) {
                q = r1 / r2;
                r = r1 - q * r2;
                r1 = r2; r2 = r;
                s = s1 - q * s2;
                s1 = s2; s2 = s;
                t = t1 - q * t2;
                t1 = t2; t2 = t;
            }
            g = r1; s = s1; t = t1; // 확장 유클리드 완료

            // 해존재 유무 판별. g|c 가능 여부로 판단.
            if (c % g != 0) {
                sb.append(-1).append('\n');
                continue;
            }
            q = c / g; // c/g 몫 기록
            
            // 초기해 x0, y0 구함
            int x0 = s * q; int y0 = t * q;

            // 증가 방향인지 감소 방향인지 확인
            int x1 = x0 + (b / g) * 0;
            int y1 = y0 - (a / g) * 0;
            int x2 = x0 + (b / g) * 1;
            int y2 = y0 - (a / g) * 1;
            int cur1 = Math.abs(x1) + Math.abs(y1);
            int cur2 = Math.abs(x2) + Math.abs(y2);
            boolean check = false; // false : 증가, true : 감소방향
            if (cur1 < cur2) check = true;
            else check = false;

            int k = 0;
            int x = x0 + (b / g) * k;
            int y = y0 - (a / g) * k;
            int cur = Math.abs(x) + Math.abs(y);
            int prev = cur;
            while (true) { // 2차 방정식
                // update k
                if (check) k--;
                else k++;

                // run
                x = x0 + (b / g) * k;
                y = y0 - (a / g) * k;
                cur = Math.abs(x) + Math.abs(y);

                // break
                if (cur > prev) {
                    break;
                }
                prev = cur;
            }

            sb.append(prev).append('\n');
        }

        FileOutputStream fs = new FileOutputStream("./eq.txt");
        fs.write(sb.toString().getBytes());
//        System.out.println(sb);
    }

참고

Java 기본

inner class, inner static class

• inner class 는 외부 클래스로 따로 빼는걸 추천하고, 내부 클래스는 static 사용을 권장
• 참고URL

class MyClass {
    class InnerClass{} // inner class
    static class InnerStaticClass{} // inner static class
}

primitive type, reference type

• primitive type 스택 사용 및 값 복사(깊은 복사)
  • 대표적 예시로 기본 타입 : boolean , byte , char , short , int , long , float, double
• reference type 힙 사용 및 주소값 복사(얕은 복사)
  • Array, Object, String 등등
  • 단, String은 값이 바뀔때 새로운 메모리 주소에 값을 생성하기 때문에 “깊은 복사” 로 생각하기도 하지만 기본 동작은 “얕은 복사” 라는점을 잘 이해하자
• c++의 STL은 깊은 복사가 이루어지는데, 이 때문에 java에서 혼동이 많이 왔었다. 잘 구분!!

String a = "hello"; // a : hello
String b = a; // b : &a (a주소값 가지는 중)
a = "world"; // a : world (새로운 메모리 주소에 새로 world 저장)

// 출력결과 (마치 깊은 복사를 진행한것 같은 효과)
a : world
b : hello

자바는 소수점 표기도 특징이 있다.

• 3E10 이런 형태로 지수 표기를 함.
  • 본인은 이런경우 그냥 printf 를 사용해서 해결함
    • ex : System.out.printf("%.1f", result);
• 소수점 관련 함수는 보통 Math.round(), String.format() 을 주로 사용
  • 둘다 소수점 n번째 자리까지 반올림!!
    • 참고 - 올림 : Math.ceil(), 버림 Math.floor();
  • 단, Math.round() 와 String.format() 의 차이점이 있음 - 소수점 뒤의 0 절삭유무

// 차이점
double test = 3000.000;
System.out.println(Math.round(test*1000)/1000); // 3000
System.out.println(String.format("%.3f", test)); // 3000.000
// 참고로 원하는 소수점 n번째 표현은? 아래 예시는 n=3
double pi = 3.141592
System.out.println(Math.round(pi*1000)/1000.0); // 3.142
/*
즉, 
3.141592*1000 => 3141.592 여기서 round => 3142
3142/1000.0 => 3.142
*/

날짜 계산 - Date.getTime() 활용

• 날짜 관련해서 다양한 클래스들이 존재하는데, 날짜 차이를 계산하는 하나의 예시를 기록해두겠다.
• 계산 과정에서 double 타입으로 해줘야 오차가 거의 없다.
• format 을 활용해서 원하는 형식으로 자유롭게 커스텀 가능하다.
• date 를 활용해서 .getTime 을 통해 날짜 계산도 오차 없이 가능하다.

// EX : BOJ 25318
// 2019/07/03 03:43:21 이런식으로 입력들어왔다고 가정
stk = new StringTokenizer(br.readLine(), " "); // ["2019/07/03", "03:43:21"]
String a = stk.nextToken(); // "2019/07/03"
String b = stk.nextToken(); // "03:43:21"
DateFormat format = new SimpleDateFormat("yyyy/MM/ddh:m:s"); // "2019/07/0303:43:21"
Date date = format.parse(a+b); // Thu Oct 14 10:12:31 KST 2021
inArr[i] = date; // inArr 배열에 전부 기록
// ... 생략

// inArr[N] 번째 날짜와 inArr[i] 번째 날짜의 차이 계산 과정
double Sec = (inArr[N].getTime() - inArr[i].getTime()) / 1000; // ms -> s
double days = Sec/(24*60*60); // s -> d : 이 값이 두 날짜의 차이 "일" 수이다.
double p = Math.max(Math.pow(0.5, days/365), Math.pow(0.9, N-i)); // 이건 그냥 문제의 공식
sum1 += p*lArr[i];
sum2 += p;
long result = Math.round((sum1/sum2)*10/10.0); // 소수점 첫번째 자리에서 반올림 -> 정수형

입출력 I/O와 디버깅

일반 Scanner 방식보다 빠른 방식

• INPUT으로 BufferedReader, StringTokenizer 사용

  • System.in 으로 입력을 InputStreamReader 로 받아서 BufferedReader 에 담는다.

  • br.readLine() 를 " " 기준으로 잘라서 StringTokenizer 에 담는다. (split 처럼)

  • 만약 입력의 끝나는 부분을 알고싶다면???

    • br.readLine()==null 로 알 수 있으며, 테스트는 Ctrl+D 를 입력하면 된다.

    • 테스트케이스(입력)가 몇개인지 모를 때 예시 코드

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      //테케가 몇개인지 모를 때
      while(true) {
          String t = br.readLine();
          if ( t==null || t.length()==0 ) break;
          //풀이...
      }
      

  • 파입 입출력을 System.in 으로 사용 가능하게 설정도 가능!

    • System.setIn(new FileInputStream("input.txt"));

    • 이후 System.in 사용하면 됨.

• OUTPUT으로 StringBuilder 사용

  • System.out.println 도 많이쓰지만, 많은 출력땐 StringBuilder 를 권장
  • sb.setLength(0); -> 초기화 하기
  • sb.setLength(sb.length()-2); -> 끝에 2칸 지우기

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

public class Main {
	static int[][] arr = new int[301][301];

	public static void main(String[] args) throws IOException {
        // 1. 입력!!
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(stk.nextToken());
		int m = Integer.parseInt(stk.nextToken());
		// 그 다음 부터 n(행)번 입력 받기 (m은 열)
		for (int i = 0; i < n; i++) {
			stk = new StringTokenizer(br.readLine(), " "); 
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(stk.nextToken());
			}			
		}
        
		// 2. 출력!!
		StringBuilder sb = new StringBuilder(); 
		sb.append("n : " + n + ", m : " + m).append('\n');
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				sb.append(arr[i][j]);
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
}

디버깅에 활용 추천 메소드!

• 1차원 : System.out.println(Arrays.toString(inArr));
• 2차원 : for문과 System.out.println(Arrays.toString(inArr[i]));
• 객체 출력에는 toString 오버라이딩 추천 -> 범위지정?? Arrays.copyOfRange 활용
• 실제 디버깅 팁
  • 이클립스 : F8 브레이크포인트 이동, F6 함수단위 이동, F5 한줄씩 이동
  • if문 넣어서 원하는 곳에 한번에 이동(브레이크포인트 함께사용)
  • 보고싶은 변수 드래그하면 한번에 볼 수 있음

// 실제로 아래 4줄이 1줄로 줄어듬!
//for(int j=1; j<=N; j++) {
//System.out.print(inArr[j]+" ");
//}
//System.out.println();
System.out.println(Arrays.toString(inArr)); // 1차원
System.out.println(Arrays.toString(Arrays.copyOfRange(dp[i], 0, K+1))); // 2차원(범위 지정)

// toString 오버라이딩으로 객체 내용 보기 간편
@Override
public String toString() { return "Node [y=" + y + ", x=" + x + "]"; }

문자열 - string, char[]

주의사항

• c++처럼 java도 string은 문자열을 이어붙일때 잘못 사용하면 O(N^2) 복잡도를 발생시킬 수 있다.
  • s+'a' 라는 새 문자열 객체를 만든후 s에 더하기 때문에 s+'a' 만큼 매번 추가로 길이가 필요하기 때문이다.
• 따라서 반드시 아래 방식으로 사용해야한다 - O(N)
  • 'a' 만 생성되어서 s 에 더하기 때문에 a 만큼 길이만 추가로 필요하기 때문에 빠르다.
  • StringBuilder 를 사용해야한다.
• 한번에 초기화하는 fill 메소드 설명
  • 배열, 리스트 - Arrays.fill(), Collections.fill()
• String 변경 불가, StringBuilder 변경 가능
• parseInt() : String -> int
  • intValue() : Integer -> int

// 1. O(N^2) 복잡도 코드
String s = "hi";
s = s+" hello"
// 2. O(N) 복잡도 코드
StringBuilder sb = new StringBuilder();
sb.append("hi").append(" hello").toString();
s.insert, delete, deleteCharAt, setCharAt, reverse, setLength 등등 다양

아래 문법들은 기본적으로 암기

• char[] to string to int
  • int num = Integer.parseInt(new String(val));
• string to char[]
  • char[] inChar = inStr.toCharArray();
• char length
  • val.length
• string length
  • val.length()

String s = "abcde";
s.length();
s.isEmpty();
s.charAt(2); // index 2로 문자찾기
s.indexOf("c"); // 문자로 첫번째 인덱스 찾기
s.lastIndexOf("c"); // 문자로 마지막 인덱스 찾기

s.substring(2, 4); // 2~3 문자열
s.substring(3); // 3~ 문자열
s.replace('b', 'k'); // akcde (새로운 객체 생성!!)

s.equlas("abcde"); // 비교(기존 ==은 주소를 비교)
s.contains("bc"); // 포함여부
s.compareTo("abcdd"); // 동일:0, s가 사전순 앞:-1, s가 사전순 뒤:1, 마지막 문자만 다르면 마지막 문자의 사전순 차이 반환(여기선 1)
// TIP : s - "abcdd" = ? 로 보면 간단하다. 예로 5 - 10 = -5는 음수로 앞을 의미한다.
s.split(" ");
s.trim(); // 앞뒤만 공백 제거
s.toLowerCase();
s.toUpperCase();

Integer.parseInt("300"); // Str -> Int
Integer.toString(300); // Int -> Str

한번에 초기화하는 fill 메소드 - Arrays, Collections

int[] myArray = new int[10];
Arryas.fill(myArray, 0); // 0으로 init
List<Integer> myList = new ArrayList<>(10);
Collections.fill(myList, null); // null로 init

Array, List(ArrayList)

List는 인터페이스라서 ArrayList(클래스) 로 구현, Array는 우리가 잘 아는 그 배열이다.

Array와 List의 차이는 정적, 동적 길이란 차이가 있고 length, size() 를 쓰는 차이도 있다.

• 참고로 String은 length()

// Array init
int arr[] = {0,1,2}; // length:3
int[] arr = new int[3]; // length:3

// ArrayList init
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList("apple", "banana"));
List<Integer> list = new ArrayList<>(); 
// method
list.add(값), list.get(index), list.set(index, 값), list.remove(index), list.remove(값), list.removeAll(list2) 등등
    
// 문자열 배열을 List로 변환
String[] temp = "abcde";
List<String> list = new ArrayList<>(Arrays.asList(temp));

// List를 문자열 배열로 변환
List<String> list = new ArrayList<>();
String[] temp = list.toArray(new String[list.size()]);

// 정수 배열을 List로 변환
int[] temp = { 123, 789, 456 };
List<Integer> list = new ArrayList<>(Arrays.asList(temp));

// List를 정수 배열로 변환
List<Integer> list = new ArrayList<>();
int[] temp = list.stream().mapToInt(i->i).toArray();

// 중복없이 값을 넣고 싶을 때 (원래는 sort후 중복 무시하는 형태로 얻었었는데, 좀 귀찮았음)
if (list.indexOf(value) < 0) {	// 없으면 -1 리턴
	list.put(value);
}

// 리스트 값 하나씩 가져올 때 (int 일 경우)
for(int i = 0; i < list.size(); i++) {
	list.get(i).intValue();
}

Collections

Array말고 List쪽의 메소드라 볼 수 있다.

int[] arr = { 123, 789, 456 }; // array
List<Integer> list = new ArrayList<>(Arrays.asList(arr)); // array to list(arraylist)

Collections.max(list)
Collections.min(list)
Collections.sort(list) // asc
Collections.sort(list, Collections.reverseOrder()) // desc
Collections.reverse(list) // { 456, 789, 123 }

Collections.frequency(list, 123) // 123 요소 개수 반환
Collections.binarySearch(list, 123) // 이분검색(못찾을때 좀 특이함)
// 없으면 123보다 큰 최초의 위치를 찾아서 -1을 곱하고 1을 빼서 반환 (-4)

자를 때(분할할 때)

특정 정수를 자를 때

// remain에 자른 정수를 담음
while(value != 0) { // ex : 123 -> 12 -> 1 -> 0
    remain = value % 10; // 123%10=3 -> 12%10=2 -> 1%10 = 1
    value /= 10; // 123/10=12 -> 12/10=1 -> 1/10=0
}

스트링처럼 split이나 substring을 배열에서 하려면?

str.substring(3,5); String[] arr = str.split(""); // String의 경우
Arrays.copyOfRange(원본배열, 시작, 끝); // 배열의 경우