면접/세미나 대비용 정리임두, 같이 풀어봅시다 🙌🏻

1) O(1) — 상수 시간

// 배열의 첫, 중간, 마지막 원소를 접근
// 입력 크기와 관계없이 항상 같은 횟수 연산
int accessEdges(int[] a) {
    int first = a[0];
    int mid   = a[a.length / 2];
    int last  = a[a.length - 1];
    return first + mid + last; // O(1)
}

2) O(log n) — 로그 시간

// 이진 탐색
int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (arr[m] == target) return m;
        if (arr[m] < target)  l = m + 1;
        else                  r = m - 1;
    }
    return -1;
}

3) O(√n) — 제곱근 시간

// 약수 개수 세기
int countDivisors(int n) {
    int cnt = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cnt += (i * i == n) ? 1 : 2;
        }
    }
    return cnt;
}

4) O(n) — 선형 시간

// 배열 합 구하기
long sum(int[] a) {
    long s = 0;
    for (int x : a) s += x;
    return s;
}

5) O(n log n) — 정렬/분할정복

// 정렬 후 k번째 원소 얻기
int kthAfterSort(int[] a, int k) {
    java.util.Arrays.sort(a); // 평균 O(n log n)
    return a[k];
}

6) O(n²) — 이중 루프

// 모든 쌍 검사
int countPairsLE(int[] a, int T) {
    int n = a.length, cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] <= T) cnt++;
    return cnt;
}

7) O(n³) — 삼중 루프

// 세 원소 합이 0인 경우의 수
int tripleZeroCount(int[] a) {
    int n = a.length, cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
                if (a[i] + a[j] + a[k] == 0) cnt++;
    return cnt;
}

8) O(2^n) — 부분집합/백트래킹

// 모든 부분집합 탐색
void subsets(int[] a, int idx, java.util.List<Integer> cur) {
    if (idx == a.length) {
        return; // 처리
    }
    subsets(a, idx + 1, cur);          // 선택 X
    cur.add(a[idx]);
    subsets(a, idx + 1, cur);          // 선택 O
    cur.remove(cur.size() - 1);
}

9) O(n!) — 순열 생성

// 순열 생성
void permute(int[] a, boolean[] used, java.util.List<Integer> cur) {
    if (cur.size() == a.length) {
        return; // 처리
    }
    for (int i = 0; i < a.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        cur.add(a[i]);
        permute(a, used, cur);
        cur.remove(cur.size() - 1);
        used[i] = false;
    }
}

10) O(n) — 트리 DFS

// 트리 전체 DFS
import java.util.*;

class TreeDFS {
    List<List<Integer>> g = new ArrayList<>();
    boolean[] vis;

    TreeDFS(int n) {
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        vis = new boolean[n + 1];
    }
    void addEdge(int u, int v) {
        g.get(u).add(v); g.get(v).add(u);
    }
    void dfs(int v, int p) {
        vis[v] = true;
        for (int nxt : g.get(v)) {
            if (nxt == p) continue;
            if (!vis[nxt]) dfs(nxt, v);
        }
    }
}

📝 시간복잡도 계산 연습 문제

문제 1

int foo(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x > 0) {
            x >>= 1;
            cnt++;
        }
    }
    return cnt;
}

풀이: 각 i마다 while은 log i번 → 합 Σ log i = Θ(n log n). 정답: O(n log n)

문제 2

int bar(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            cnt++;
    return cnt;
}

풀이: 내부 반복은 (n - i + 1). 합 = n(n+1)/2 = O(n²). 정답: O(n²)

문제 3

int baz(int[] a, int T) {
    java.util.Arrays.sort(a); // O(n log n)
    int l = 0, r = a.length - 1, cnt = 0;
    while (l < r) {
        if (a[l] + a[r] <= T) { cnt += (r - l); l++; }
        else r--;
    }
    return cnt;
}

풀이: 정렬 O(n log n) + 투포인터 O(n). 지배항은 정렬. 정답: O(n log n)

문제 4

void dfs(int v, int p) {
    size[v] = 1;
    for (int nxt : g.get(v)) {
        if (nxt == p) continue;
        dfs(nxt, v);
        size[v] += size[nxt];
    }
}

풀이: 모든 노드와 간선을 1번 방문 → O(n). 정답: O(n)

문제 5

int rec(int n) {
    if (n <= 1) return 1;
    return rec(n / 2) + 1;
}

풀이: T(n) = T(n/2) + O(1). 로그 깊이만큼 → O(log n). 정답: O(log n)

문제 6

int rec2(int n) {
    if (n <= 1) return 1;
    return rec2(n/2) + rec2(n/2) + n;
}

풀이: T(n) = 2T(n/2) + O(n). 마스터정리 → O(n log n). 정답: O(n log n)

문제 7

int qux(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i *= 3)
        for (int j = 1; j <= n; j++)
            cnt++;
    return cnt;
}

풀이: 바깥은 log n, 안쪽은 n. 곱해서 O(n log n). 정답: O(n log n)

문제 8

int myst(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j * j <= i; j++)
            cnt++;
    return cnt;
}

풀이: 내부는 √i번. 합 Σ√i ≈ n^(3/2). 정답: O(n^(3/2))

문제 9

void backtrack(int[] a, int idx) {
    if (idx == a.length) return;
    backtrack(a, idx + 1);
    backtrack(a, idx + 1);
}

풀이: 각 원소마다 선택/비선택 → 2^n 가지. 정답: O(2^n)

문제 10

int g(int n) {
    if (n <= 1) return 1;
    return g(n-1) + g(n-1);
}

풀이: T(n) = 2T(n-1) + O(1). 지수적으로 증가. 정답: O(2^n)

트리 종류는 이전에 다뤘으니, 이번에는 “트리 위에서 실제로 자주 쓰는 알고리즘”에 집중해보도록 한다.

0. 트리 복습 🌳

• 정의: 노드(Node)와 간선(Edge)로 이루어진 계층적 자료구조.

• 특징: 사이클이 없고, n개의 노드가 있으면 간선은 n-1. (연결 트리 기준)

• 용어:

  • 루트(root), 부모/자식(parent/child), 형제(sibling)
  • 깊이(depth): 루트에서 노드까지 간선 수
  • 높이(height): 트리/노드의 최대 깊이

• 표현:

  • 인접 리스트(자주 씀): List<List<Integer>> graph
  • 부모 배열: parent[v]
  • 자식 리스트: children[v] (루트 고정 트리일 때 편함)

1. 시간복잡도(Time Complexity) ⏰

1-0. 시간복잡도와 공간복잡도

참고링크

1) 시간 복잡도(Time Complexity)

• 알고리즘이 실행될 때 _필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 ‘효율적인 알고리즘’을 나타내는 척도_를 의미
• 즉, _입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표_를 의미
• 시간 복잡도는 ‘빅오 표기법(Big-O notation)’를 통해 표현하며, _‘수치가 작을수록 효율적인 알고리즘’_을 의미

2) 공간 복잡도(Space Complexity)

• 알고리즘이 실행될 때 필요한 ‘메모리 공간의 양’을 의미
• 즉 알고리즘의 효율성을 판단_하는 데 사용되며 **_일반적으로 메모리 사용량이 적을수록 더 효율적인 알고리즘**

공간 복잡도는 일반적으로 알고리즘의 시간 복잡도와 함께 고려되며 알고리즘이 실행되는 환경에 따라 달라질 수 있음. ex) 일부 알고리즘은 실행될 때 추가적인 메모리를 필요로 하지 않지만 다른 알고리즘은 입력 데이터의 양에 따라 필요한 메모리 공간이 증가할 수 있음.

따라서 알고리즘을 설계할때에는 시간 복잡도와 공간 복잡도를 함께 고려해야 함.

1-1. 왜 필요한가?

• 입력 크기 n이 커질수록 실행 시간이 어떻게 증가하는지 비교하는 척도.
• 코드 한 줄의 시간보다 증가율이 중요(기계/언어/환경에 독립).

1-2. 표기법 3형제

• Big-O, O(f(n)): 최악 기준 상한 (보수적/기본적으로 이걸 씀) : 빅오 표기법
• Big-Ω, Ω(f(n)): 최선 기준 하한 : 오메가 표기법
• Big-Θ, Θ(f(n)): 상한=하한 (정확한 증가율) : 세타 표기법

1-3. 자주 보는 증가율 ex.

1-4. 어떻게 계산하는가 ?

(A) 반복문 합치기

• for (i=1..n) → O(n)
• for + for (중첩) → O(n²)
• for (i=1; i<=n; i*=2) → i가 1,2,4,...,n → O(log n)

(B) 등차/등비 합

• 1 + 2 + ... + n = n(n+1)/2 = O(n²)
• 1 + 2 + 4 + ... + n ≈ 2n = O(n)

(C) 재귀식

• T(n) = T(n/2) + O(1) → O(log n) (이진탐색)

• T(n) = 2T(n/2) + O(n) → O(n log n) (병합정렬)

• 트리 DFS: 각 노드를 딱 한 번 방문 → T(n) = Σ T(child) + O(1) = O(n)

  • 이유: 모든 간선을 많아야 두 번(양방향 방문)만 통과 → O(n)

1-5. 트리 알고리즘과 복잡도 정리표

2. 트리 순회: DFS/BFS, 모든 트리 문제의 뼈대 🦴

여기 사이트 정리 굳 👀

2-1. DFS (전위/중위/후위) — 재귀 버전

2. 트리 순회 (DFS / BFS)

DFS는 “한쪽 길을 끝까지 파고들었다가, 막히면 뒤로 돌아와서 다른 길을 탐색”하는 방식이다. 미로 탐험한다고 생각하면 쉽다. 출발점에서 한쪽 길을 계속 따라가다가 막히면 돌아와서 다른 길을 가는 것과 같다.

예시 트리:

        1
       / \
      2   3
     / \   \
    4   5   6

DFS 세 가지 순서

• Preorder (전위): Root → Left → Right 👉 1 2 4 5 3 6 (루트 먼저 → 마치 “대표자가 먼저 말하고 나머지가 뒤따르는” 느낌)

• Inorder (중위): Left → Root → Right 👉 4 2 5 1 3 6 (왼쪽 → 부모 → 오른쪽 → 특히 이진 탐색 트리에서는 오름차순 정렬 결과가 나옴)

• Postorder (후위): Left → Right → Root 👉 4 5 2 6 3 1 (모든 일을 다 처리한 뒤에 부모가 마지막으로 보고받는 느낌)

📌 비유:

• Preorder = “부모님이 먼저 아이들에게 말 걸기”
• Inorder = “왼쪽 아이 → 부모님 → 오른쪽 아이 순서로 대화하기”
• Postorder = “아이들끼리 먼저 다 놀고, 부모님이 마지막에 확인하기”

DFS 재귀 코드 (Java)

class Node {
    int key;
    Node left, right;
    Node(int k) { key = k; }
}

class Traversal {
    // 전위: Root -> Left -> Right
    void preorder(Node cur) {
        if (cur == null) return;
        System.out.print(cur.key + " ");
        preorder(cur.left);
        preorder(cur.right);
    }

    // 중위: Left -> Root -> Right
    void inorder(Node cur) {
        if (cur == null) return;
        inorder(cur.left);
        System.out.print(cur.key + " ");
        inorder(cur.right);
    }

    // 후위: Left -> Right -> Root
    void postorder(Node cur) {
        if (cur == null) return;
        postorder(cur.left);
        postorder(cur.right);
        System.out.print(cur.key + " ");
    }
}

⏱ 복잡도: 모든 노드를 1번씩 방문 → O(n) ⚠️ 주의: 트리가 한쪽으로만 긴 경우(편향 트리)에는 재귀 깊이가 너무 깊어져서 StackOverflow가 날 수 있다 → 이때는 스택을 직접 쓰는 반복문 방식으로 구현하면 안전하다.

BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 DFS와 다르게, 한 줄로 줄 세우는 것처럼 같은 레벨의 노드를 먼저 전부 방문한 다음 그다음 레벨로 넘어간다. 학교에서 운동장에서 “키 순서대로 줄 서라”가 아니라, “1학년 먼저, 2학년 다음, 3학년 다음” 이렇게 학년별로 모이는 느낌이라고 보면 된다.

예시 트리:

레벨별: [1] → [2,3] → [4,5,6]

👉 결과: 1 2 3 4 5 6

BFS 코드 (큐 활용)

import java.util.*;

class LevelOrder {
    void levelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node cur = q.poll();             // 맨 앞 꺼내기
            System.out.print(cur.key + " "); // 방문 처리
            if (cur.left != null)  q.add(cur.left);
            if (cur.right != null) q.add(cur.right);
        }
    }
}

⏱ 복잡도: 모든 노드와 간선을 한 번씩 → O(n) ⚠️ 큐에는 한 레벨이 통째로 들어가므로, 트리의 최대 너비만큼 메모리가 필요하다.

👉 요약:

• DFS = 깊게 파고드는 탐색 (미로 끝까지 가보기)
• BFS = 넓게 훑는 탐색 (운동장에서 학년별로 줄 세우기)

트리 문제는 결국 이 두 가지 패턴을 얼마나 자유롭게 쓸 수 있는지가 관건이다.

// 트리 노드 정의 (이진트리 예시)
// 실제 코테에서는 인접 리스트 + DFS를 더 자주 씀
class Node {
    int key;
    Node left, right;
    Node(int k) { key = k; }
}

class Traversal {
    // 전위: Root -> Left -> Right
    void preorder(Node cur) {
        if (cur == null) return;
        System.out.print(cur.key + " ");
        preorder(cur.left);
        preorder(cur.right);
    }

    // 중위: Left -> Root -> Right
    // 이진 "탐색" 트리(BST)에서는 "오름차순" 순회가 됨
    void inorder(Node cur) {
        if (cur == null) return;
        inorder(cur.left);
        System.out.print(cur.key + " ");
        inorder(cur.right);
    }

    // 후위: Left -> Right -> Root
    // 서브트리 계산(크기/합) 등 후처리에 유용
    void postorder(Node cur) {
        if (cur == null) return;
        postorder(cur.left);
        postorder(cur.right);
        System.out.print(cur.key + " ");
    }
}

• 복잡도: 방문을 각 노드 1번 → O(n)
• 실전 팁: 깊은 트리에서 재귀 깊이 주의(필요하면 스택으로 반복 구현)

2-2. BFS (레벨 순회) — 큐 사용

import java.util.*;

class LevelOrder {
    void levelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node cur = q.poll();               // 맨 앞 꺼내기
            System.out.print(cur.key + " ");   // 방문 처리
            if (cur.left != null)  q.add(cur.left);
            if (cur.right != null) q.add(cur.right);
        }
    }
}

• 복잡도: 각 노드·간선 1번씩 → O(n)

3. 트리의 지름(Tree Diameter): 가장 먼 두 노드 거리

3-1. 핵심 아이디어 (2-번 DFS/BFS)

1. 임의 노드 A에서 가장 먼 노드 X를 DFS/BFS로 찾음
2. X에서 가장 먼 노드 Y를 또 DFS/BFS로 찾음
3. dist(X, Y)가 지름

• 근거: 트리는 사이클이 없고, 최장 경로의 한 끝점은 임의 점에서의 최장 거리 노드 중 하나가 됨.
• 복잡도: DFS/BFS 2번 → O(n)

3-2. 구현 (무가중치, 인접 리스트)

import java.util.*;

// 무가중치 트리 지름
class TreeDiameter {
    List<List<Integer>> g;   // 인접 리스트
    boolean[] vis;
    int far;                 // 가장 멀리 있는 노드
    int maxDist;             // 그 거리

    TreeDiameter(int n) {
        g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        vis = new boolean[n + 1];
    }

    void addEdge(int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }

    // DFS로 가장 먼 노드/거리 갱신
    void dfs(int cur, int dist) {
        vis[cur] = true;
        if (dist > maxDist) { maxDist = dist; far = cur; }
        for (int nxt : g.get(cur)) {
            if (!vis[nxt]) dfs(nxt, dist + 1);
        }
    }

    int diameter(int start) {
        // 1) start에서 가장 먼 노드 far 찾기
        Arrays.fill(vis, false);
        maxDist = 0;
        dfs(start, 0);

        // 2) far에서 가장 먼 거리 = 지름
        Arrays.fill(vis, false);
        maxDist = 0;
        dfs(far, 0);
        return maxDist; // 간선 수 기준 지름
    }
}

가중치 있는 트리(길이가 있는 간선)는 dist + w로 누적만 바꾸면 됨. (DFS/BFS 대신 다익스트라 불필요: 트리는 유일 경로라 음수만 아니면 DFS로 충분)

4. LCA (Lowest Common Ancestor, 최소 공통 조상) ⭐️

두 노드 u, v의 공통 조상 중 가장 가까운 조상을 찾는 문제. 면접/코테 단골 등장.

4-1. 단순 방법 (루트까지 경로 비교) — O(n)

• u의 조상들을 집합/배열에 저장
• v에서 루트까지 올라가며 처음 만나는 u의 조상 반환
• 간단하지만, 질의가 많으면 비효율

4-2. Binary Lifting — 전처리 O(n log n), 질의 O(log n)

아이디어

• parent[v][k] = 정점 v의 2^k번째 조상
• 전처리로 parent와 depth를 채워둠
• 질의 시 깊이를 맞춘 후, 큰 점프(2^k)로 동시에 끌어올리며 공통 조상 직전까지 이동

장점: LCA를 여러 번 물어볼 때 아주 빠름

구현

import java.util.*;

class LCA {
    int N, LOG;
    List<List<Integer>> g;
    int[][] parent;   // parent[v][k] = v의 2^k번째 조상
    int[] depth;

    LCA(int n) {
        N = n;
        LOG = 1;
        while ((1 << LOG) <= N) LOG++; // ceil(log2(N))
        g = new ArrayList<>();
        for (int i = 0; i <= N; i++) g.add(new ArrayList<>());
        parent = new int[N + 1][LOG];
        depth = new int[N + 1];
    }

    void addEdge(int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }

    // 루트 root 기준으로 depth/부모 채우기
    void dfs(int v, int p) {
        parent[v][0] = p;                         // 바로 위 조상
        for (int k = 1; k < LOG; k++) {
            parent[v][k] = parent[parent[v][k-1]][k-1]; // 2^k = 2^(k-1) + 2^(k-1)
        }
        for (int nxt : g.get(v)) {
            if (nxt == p) continue;
            depth[nxt] = depth[v] + 1;
            dfs(nxt, v);
        }
    }

    // 전처리: root에서 DFS 시작
    void preprocess(int root) {
        depth[root] = 0;
        dfs(root, 0); // 루트의 부모는 0(없음)으로
    }

    int lca(int a, int b) {
        // 1) 깊이 맞추기: a를 더 깊은 노드로 가정
        if (depth[a] < depth[b]) { int t = a; a = b; b = t; }

        // a를 b 깊이까지 끌어올림
        int diff = depth[a] - depth[b];
        for (int k = 0; diff > 0; k++) {
            if ((diff & 1) == 1) a = parent[a][k];
            diff >>= 1;
        }
        if (a == b) return a;

        // 2) 최상위부터 공통 조상 직전까지 점프
        for (int k = LOG - 1; k >= 0; k--) {
            if (parent[a][k] != parent[b][k]) {
                a = parent[a][k];
                b = parent[b][k];
            }
        }
        return parent[a][0];
    }
}

• 전처리: DFS 한 번 + parent 테이블 채우기 → O(n log n)
• 질의: O(log n)
• 주의: 트리가 1-index인지/루트가 어디인지 통일!

5. 서브트리 & 경로 응용

5-1. 서브트리 크기/합 구하기 — DFS 한 번으로 끝

• 후위 순회(왼쪽·오른쪽 처리 후 현재 처리) 아이디어로, 자식 결과를 모아 부모 값 갱신.

import java.util.*;

class SubtreeCalc {
    List<List<Integer>> g;
    int[] size;    // 서브트리 크기 (자기 자신 포함)
    long[] sum;    // 서브트리 값의 합 (예: 노드 가중치가 있을 때)
    int[] value;   // 각 노드의 값 (예시)

    SubtreeCalc(int n) {
        g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        size = new int[n + 1];
        sum = new long[n + 1];
        value = new int[n + 1];
    }

    void addEdge(int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }

    void setValue(int v, int val) {
        value[v] = val;
    }

    // 부모 p, 현재 v
    void dfs(int v, int p) {
        size[v] = 1;
        sum[v] = value[v];
        for (int nxt : g.get(v)) {
            if (nxt == p) continue;
            dfs(nxt, v);
            size[v] += size[nxt];  // 자식 서브트리 크기 누적
            sum[v]  += sum[nxt];   // 자식 서브트리 합 누적
        }
    }
}

• 복잡도: DFS 한 번 → O(n)
• 활용: “서브트리 질의”, “잘라내기 비용”, “부분 트리 조건 판정” 등

5-2. 루트→리프 경로 합이 특정 값인지 (백트래킹)

class PathSum {
    // 이진트리 Node 재사용
    boolean hasPathSum(Node root, int target) {
        if (root == null) return false;
        // 리프에 도달했을 때 합이 정확히 target이면 true
        if (root.left == null && root.right == null) {
            return target == root.key;
        }
        // 왼쪽/오른쪽으로 내려가면서 남은 합 갱신
        return hasPathSum(root.left,  target - root.key) ||
               hasPathSum(root.right, target - root.key);
    }
}

• 복잡도: 모든 노드 1번 → O(n)
• 포인트: “리프에서 판정”, “부분합 전달”

6. Euler Tour + 세그먼트 트리

_트리 문제를 배열 문제로 바꿔서 ! _ 구간 쿼리(합/최솟값/최댓값)를 O(log n)에 처리하는 테크닉

간단하게 보도록 하자.

6-1. 아이디어

• DFS로 들어올 때 in[v]에 타임스탬프, 나갈 때 out[v] 저장
• v의 서브트리 노드는 Euler 배열에서 [in[v], out[v]] 구간에 연속 배치
• 이후 세그먼트 트리/펜윅 트리로 구간 합/최솟값 등을 빠르게 질의

class EulerTour {
    List<List<Integer>> g;
    int time = 0;
    int[] in, out, euler; // euler[time] = 해당 시점의 노드 번호

    EulerTour(int n) {
        g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        in = new int[n + 1];
        out = new int[n + 1];
        euler = new int[n + 1]; // 진입 시점만 기록할 경우 크기 n
    }

    void addEdge(int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }

    void dfs(int v, int p) {
        in[v] = ++time;
        euler[time] = v;
        for (int nxt : g.get(v)) if (nxt != p) dfs(nxt, v);
        out[v] = time;
    }
}

• 전처리: DFS 한 번 → O(n)
• 질의: 세그먼트/펜윅으로 O(log n)
• 응용: “서브트리 합 갱신/조회”, “서브트리 최솟값”

7. 트라이(Trie)와 문자열 검색

문자열 검색/자동완성에서 문자 길이 m에 대해 O(m) 에 탐색

간단하게 보도록 하자.

import java.util.*;

class Trie {
    static class Node {
        Map<Character, Node> child = new HashMap<>();
        boolean end;
    }
    Node root = new Node();

    void insert(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.child.computeIfAbsent(c, k -> new Node());
        }
        cur.end = true;
    }

    boolean search(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.child.get(c);
            if (cur == null) return false;
        }
        return cur.end;
    }

    boolean startsWith(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.child.get(c);
            if (cur == null) return false;
        }
        return true;
    }
}

• 삽입/탐색: 문자열 길이 m에 대해 O(m)
• 실전: 자동완성/사전/접두사 판정

8. 시간복잡도 요약 표

8-1. 트리 알고리즘 요약

8-2. 복잡도 계산 감 잡기 표

9. Tip : tree 에서 무엇을 조심해야 하는가

• 방문 체크/부모 체크: 인접 리스트 DFS에서 if (nxt == parent) continue; 잊지 않기
• 루트 통일: LCA/서브트리 문제는 어떤 노드를 루트로 볼지 고정
• 1-index vs 0-index: 입력과 배열 인덱스 혼용 주의
• 재귀 깊이: Java는 깊은 트리에서 StackOverflow 가능 → 필요 시 반복 DFS(스택)로 변환
• 입출력 최적화: 코테 시 BufferedReader/StringBuilder 사용
• 가중치/무가중치 구분: 거리 계산할 때 +1인지 +w인지 혼동 금지
• 테스트 케이스: 단노드, 일자형(편향) 트리, 별형(star), 균형형 등 엣지 케이스 체크

📎 : 최소 예제 입력 구성 tip

• 지름: 1–2–3–4–5 (일자형) → 답 4

• LCA:

       1
     /   \
    2     3
   / \   / \
  4  5  6  7

  • LCA(4,5)=2, LCA(4,6)=1, LCA(6,7)=3

1️⃣ 자료구조란?

🚀 자료구조의 개념 이해

자료구조(Data Structure)는 데이터를 효율적으로 저장, 관리, 검색하기 위한 방법.

데이터를 단순히 모아두는 것이 아니라, 문제 해결에 적합한 방식으로 조직화하는 과정이다.

왜 자료구조가 중요한가?

• 데이터가 많아질수록 단순한 구조로는 한계가 생긴다.
• 예를 들어 100개의 데이터를 찾는 것과 1억 개 중에서 찾는 것은 효율성 차이가 극명하다.
• 자료구조를 잘 선택해야 메모리 낭비를 줄이고, 연산 속도를 최적화할 수 있다.

2️⃣ 알고리즘(Algorithm)과의 관계

• 알고리즘: 문제 해결을 위한 단계적 절차.

• 자료구조: 알고리즘이 데이터를 다루는 무대.

같은 알고리즘이라도 어떤 자료구조 위에서 동작하는가에 따라 성능이 달라진다.

예시) 탐색 문제

• 배열에서 선형 탐색 → O(n)
• 정렬된 배열에서 이진 탐색 → O(log n)
• 해시테이블 탐색 → 평균 O(1)

3️⃣ 시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘 실행 시간이 입력 크기 n에 따라 어떻게 변하는지를 나타냄.

• 빅오(Big-O) 표기법으로 분석한다.

✅ 주요 시간 복잡도

• O(1) : 상수 시간 (해시테이블 접근)
• O(log n) : 로그 시간 (이진 탐색, 균형 트리 탐색)
• O(n) : 선형 시간 (배열 전체 탐색)
• O(n log n) : 효율적 정렬 (퀵/병합/힙 정렬)
• O(n²) : 단순 정렬 (버블, 삽입, 선택)

// 예: 선형 탐색 (O(n))
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // 찾지 못함
}

// 예: 이진 탐색 (O(log n)) -> 배열이 정렬되어 있어야 함
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

2. 자료형에 따른 분류

자료구조는 크게 기본 자료구조(Primitive Data Structure) 비기본 자료구조(Non-Primitive Data Structure) 로 나눌 수 있다.

🔹 Primitive Data Structure (기본 자료구조)

프로그래밍 언어에서 제공하는 가장 기본적인 단위 자료형으로, 더 이상 쪼갤 수 없는 기본 블록이다.

• Integer (정수형)

  • 수학에서의 정수에 해당하지만, 컴퓨터에서는 메모리 크기에 따라 표현할 수 있는 범위가 제한된다.
  • 예: int, long

• Float (실수형)

  • 수학에서의 실수 개념과 유사하나, 컴퓨터는 유한한 비트 수로 소수를 표현하기 때문에 근사값만 저장할 수 있다.
  • 예: float, double

• Character (문자형)

  • 하나의 문자 또는 기호를 저장. 공백 문자(띄어쓰기, tab, enter 등)도 포함된다.
  • 예: 'a', 'Z', ' '

• Pointer (포인터)

  • 실제 데이터 값 대신 메모리 주소를 저장하는 특수한 자료형.
  • 포인터를 이용해 메모리에 접근하거나 동적 메모리 관리가 가능하다.

👀 꿀팁 For 코테

• short는 32 다음 쉼표( , ) 1개
• int는 2 다음 쉼표( , ) 3개
• long은 9 다음 쉼표( , ) 6개
• float / double은 각각 소수 7 / 15 자리

🔹 Non-Primitive Data Structure (비기본 자료구조)

기본 자료구조를 응용하여 만든 복합 자료구조. 데이터의 크기와 구조를 유연하게 다룰 수 있다.

• Arrays (배열)

• Lists (리스트)

• Files (파일)

• Linear (선형 구조)

  • 데이터가 일렬로 나열되는 구조.
  • 예: 스택(Stack), 큐(Queue), 배열(Array), 연결 리스트(Linked List)

• Non-Linear (비선형 구조)

  • 데이터가 계층적, 망 형태로 연결되는 구조.
  • 예: 트리(Tree), 그래프(Graph)

3. 비기본 자료구조 7개 ⭐️⭐️⭐️

☝🏻 선형 자료구조

데이터가 일렬로 나열되는 구조.

1️⃣ 배열(Array)

• 메모리에 연속적으로 저장.
• 인덱스를 통해 임의 접근 가능 → O(1).
• 삽입/삭제는 전체 이동 필요 → O(n).

int[] arr = {10, 20, 30};
System.out.println(arr[1]); // O(1) 접근

→ 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용

→ 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용

2️⃣ 연결 리스트(Linked List)

• 노드(Node) 단위로 데이터와 포인터(다음 노드 주소)를 저장. "순차적"
• 동적인 데이터 삽입/삭제 빠름 → O(1) (포인터만 수정).
• 임의 접근 불가 → O(n).

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

public class Main {
    public static void main(String[] args) {
        Node n1 = new Node(10);
        Node n2 = new Node(20);
        Node n3 = new Node(30);

        n1.next = n2;
        n2.next = n3;

        System.out.println(n1.data);       // 10
        System.out.println(n1.next.data);  // 20
        System.out.println(n2.next.data);  // 30
    }
}

• 각 요소는 Node
• 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함
• 첫 번째 요소는 Head
• 마지막 요소는 Tail

종류:

1. 단일 연결 리스트(Singly Linked List)
2. 이중 연결 리스트(Doubly Linked List)
3. 원형 연결 리스트(Circular Linked List) ...

🧐 배열과 연결 리스트는 아래의 자료 구조들을 구현하는 데 사용되는 기본 자료 구조 ⬇️⬇️⬇️

3️⃣ 스택(Stack)

• LIFO (후입선출) (Last In First Out).
• 연산: push(), pop().
• 활용: 함수 호출 스택(재귀 프로그래밍), 실행취소(Undo), 괄호 검사.

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.pop()); // 20

4️⃣ 큐(Queue)

• FIFO (선입선출) (First In First Out).
• 활용: 작업 대기열 시스템, 운영체제 스케줄링, 멀티스레딩 스레드관리.
• 변형: 원형 큐, Deque(양방향 큐), 우선순위 큐.

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
System.out.println(queue.poll()); // 1

✌🏻 비선형 자료구조

데이터가 계층적 또는 네트워크 구조를 이루는 형태.

5️⃣ 트리(Tree)

• 루트(root)에서 시작해 자식(child) 노드로 확장되는 구조.

  • 최상위 노드(루트)를 가지고 있음
  • 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다.

• 계층적 관계를 표현.

→ Binary Trees(이진트리) → Binary Search Tree(이진 검색 트리) → Heap(힙) ...

6️⃣ 그래프(Graph)

• 정점(Vertex)과 간선(Edge)으로 구성.
  • nodes/vertices(노드/정점) 사이에 edge(엣지)가 있는 collection
• 네트워크, SNS 친구 관계, GPS 최단 경로 탐색 등에 활용.

• directed(방향) 그래프는 일방통행
• undirected(무방향) 그래프는 양방향

🤞🏻 탐색(Search) 자료구조

지금까지는 ,,

• 선형 자료구조 (Linear) 데이터가 일렬로 저장 → 배열, 연결리스트, 스택, 큐

• 비선형 자료구조 (Non-linear) 데이터가 계층적/망 형태 → 트리, 그래프

  
  

해시테이블 : 해시 함수로 인덱스를 계산해 저장하는 자료구조

→ 데이터가 배열처럼 일렬로 저장되긴 하지만, 내부적으로 해시 함수를 통한 매핑에 의존 → 충돌 처리 시 연결리스트나 트리 같은 다른 자료구조를 함께 사용.

전통적인 Linear / Non-linear 분류에는 딱 들어가지 않음.

해시테이블은 배열과 유사하게 연속적인 메모리 공간을 기반으로 하지만, 해시 함수와 충돌 처리 방식(체이닝, 개방 주소법 등)을 사용하기 때문에 전통적인 선형/비선형 자료구조 분류에는 속하지 않는다. 대신 탐색(Search) 자료구조 또는 매핑(Map) 자료구조로 따로 분류하는 것이 일반적이다.

7️⃣ Hash table(해시 테이블)

• 해시함수를 사용하여 변환한 값을 색인(index)으로 삼기 → 키(key)와 데이터(value)를 저장

• 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적 → 데이터베이스 인덱스 구현 → 사용자 로그인 인증 → "set" 데이터 구조 구현

보통 테이블 내에 더 작은 서브그룹인 버킷(bucket)에 키/값(key/value) 쌍(pair)을 저장

❗️❗️ 해시값 충돌이 자주 일어날 수 있음

→ 해시 충돌 개선 : 다양한 방법으로 해시 함수를 개선 Or 해시 테이블의 구조 개선(chaining, open addressing 등)의 방법이 사용.

3. 해시테이블, 해시 충돌

해시 테이블과 충돌 해결

✏️ 개념

1. 해싱

• 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업

• 암호화에 쓰이는 해시 알고리즘 사용하여 변환 (ex. MD5)

• 여기서는 암호화에 쓰인 방식이 아닌, 자료구조로 사용하고자 하는 해시 테이블을 다루기 때문에 정수값으로 변환되는 해시 알고리즘 사용

2. 해시 테이블

• 해싱을 사용하여 데이터를 저장하는 자료구조 : 해시 테이블
• 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조

• Key → 해시 함수 → 인덱스 → Value 저장

• 기본연산 : 탐색(Search), 삽입(Insert), 삭제(Delete)

• 평균 탐색/삽입/삭제 시간: O(1)

  • 기존 자료구조인 이진탐색트리나 배열에 비해서 굉장히 빠른 속도

💥 해시 충돌 (Collision)

서로 다른 키가 동일한 해시 값을 가질 때 발생.

❓ 왜 일어나는가 ?

• 적재율(Load Factor) 의 이해 적재율이란 해시 테이블의 크기 대비, 키의 개수를 말함. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K / N. Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 됨.

• 충돌이 발생할 경우와, 그렇지 않을 경우 만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1) 에 수행. but, 충돌이 발생할 경우 탐색과 삭제 연산이 최악의 O(K) 만큼 걸리게 됨. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌이 전부 발생했음을 말함. 따라서, 충돌을 최대한으로 줄여서 연산속도를 빠르게 하는 것이 해시 테이블의 핵심 → 이에 중요하게 작용하는 것이 바로 해시함수를 구현하는 해시 알고리즘.

해시 알고리즘이 견고하지 못하게 되면 해시함수로 도출된 값들이 같은 경우가 빈번하게 발생하게 되므로 잦은 충돌로 이어지게 됨.

💪🏻 충돌 해결 기법

1️⃣ 테이블 구조 개선

1. 체이닝(Chaining) : 테이블 구조 개선

   • 각 인덱스에 연결 리스트를 두어 충돌 데이터를 저장.

2. 개방 주소법(Open Addressing) : 테이블 구조 개선

   • 빈 슬롯을 탐사하며 저장.
     • 원래라면 해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법
   • 선형 탐사
   • 제곱 탐사
   • 이중 해싱

3. 재해싱(Rehashing)

   • 테이블 크기를 늘려 다시 해싱.

Map<String, String> map = new HashMap<>();
map.put("apple", "사과");
map.put("banana", "바나나");
System.out.println(map.get("apple")); // 사과

2️⃣ 해시 함수 개선

1. 나눗셈법(Division Method)

• 아주 간단하게 해시값을 구하는 방법으로 미리 해시 테이블의 크기인 N 을 아는 경우에 사용 해시함수를 적용하고자 하는 값을 N 으로 나눈 나머지를 해시값으로 사용하는 방법

2. 곱셈법(Multiplication Method)

• kA mod 1 의 의미는 kA 의 소수점 이하 부분을 말하며 이를 N 에 곱하므로 0부터 N 사이의 값이 됨 이 방법의 장점은 N 이 어떤 값이더라도 잘 동작한다는 것이며 A 를 잘 잡는 것이 중요

4. 트리 (Tree) 응용

📌 기본 개념

• 그래프의 특수한 형태(사이클 없는 연결 구조).

• 용어: 루트(root), 리프(leaf), 깊이(depth), 높이(height) 로 표현

📌 주요 트리 종류

1. 편향 트리 (Skew Tree)

   • 트리가 각 레벨에 대해 최소 개수의 노드를 가지면서, 하나의 자식 노드만을 가지는 트리

   

2. 이진 트리(Binary Tree) ⭐️⭐️⭐️

   • 모든 노드의 자식 ≤ 2.
     • 각 노드가 자식 노드를 최대 2개까지 가질 수 있는 트리

   

2-1. 완전 이진 트리 (Complete Binary Tree)

• 각 레벨의 왼쪽에서 오른쪽으로 빈 공간 없이 노드가 채워진 이진 트리

  (마지막 레벨을 제외하고 모든 레벨의 노드가 채워져 있다.)

  

2-2. 포화 이진 트리 (Perfect Binary Tree)

• 모든 레벨의 노드가 포화 상태로 차있는 이진 트리

  

2-3. 전 이진 트리 (Full Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리

3. 이진 탐색 트리(BST) ⭐️⭐️⭐️

• 효율적인 탐색을 위해 각 노드의 왼쪽 서브 트리에는 노드보다 작은 값만, 오른쪽 서브 트리에는 노드보다 큰 값만 포함되도록 구성하는 이진 트리

• 중복된 노드를 포함하지 않는다.
• 트리 순회 시 중위 순회 방식 : 왼쪽 < 부모 < 오른쪽 규칙
• 평균 O(log n), 최악 O(n)

3. AVL 트리 / Red-Black 트리

   • 균형을 유지하는 트리.

4. 힙(Heap) ⭐️⭐️⭐️

   • 완전 이진 트리 기반
   • 우선순위 큐 구현, 힙 정렬 알고리즘 에 사용.

• 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값
• 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값

5. 트라이(Trie)

   • 문자열 검색 최적화.
   • 검색 알고리즘

6. B-트리 / B+트리

   • 데이터베이스 인덱스 구조.
   • 파일 시스템

📌 트리 응용

• 검색 및 정렬: BST, AVL, Red-Black Tree
• 우선순위 관리: 힙 → 우선순위 큐
• 문자열 검색: Trie (자동완성, 사전)
• DB 인덱스: B-트리, B+트리
• 컴파일러 파싱: 구문 트리
• 네트워크 라우팅: 트리 기반 경로 탐색

// 간단한 이진 탐색 트리 삽입
class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

class BST {
    Node root;

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insertRec(root.left, key);
        else if (key > root.key) root.right = insertRec(root.right, key);
        return root;
    }
}

정리표 ...

현재 다소 기 죽어있습니다.

눌린 기를 펴기 위해, BE 개발자 취업 면접 대비 예상질문을 1일 5선씩 답해보기로 했다 ! 맛있게 먹어보자, 옴냠냐 ~

문제 출처는 ➡️ 스파르타코딩클럽 블로그(link !)

❗️ 면접 유의사항 3종

1️⃣ 개발자로서의 강점과 약점을 명확하게 구성하라.

어떤 개발자이신가요? 어떤 개발자가 되고 싶으신가요?

모든 지원자에게는 각자만의 스토리와 특징, 강점이 있습니다.
이를 이용해서 나의 강점과 약점을 인지하고, 강점은 더욱 부각하고 약점은 개선하는 모습을 보여줄 수 있는 답변들을 구성해 보세요.

백엔드 개발자는 완벽한 구성과 논리 구조 아래 돌아가고 구성되는 하나의 기계와 같은 부분을 작업하는 사람인 만큼, 한 가지에 푹 빠지는 집중도에 관한 역량이 중요한데요.
이처럼 백엔드 개발자가 가져야 하는 역량들 중 내가 가지고 있는 장점과 묶을 수 있는 게 어떤 것이 있을 지 떠올려 보시는 것을 추천합니다.

별 것 아닌 일들도, 나의 강점과 연결지어 극대화해 나라는 개발자를 소개하는 시간이니까요.
인성면접 질문으로도 단골 등장하는 부분이니, '나'는 '어떤 개발자인가' 에 대해 구체적으로 생각해 보세요.

2️⃣ 가시적으로 성과 또는 결과를 말하라

'좋은 결과가 있었습니다.', '보람차게 배웠습니다', '많이 개선되었습니다.' ... 이는 추상적이고 정확한 결과를 예상할 수 없어 평가가 어렵다. 그에 따라 계속해서 뭘 배웠는지, 얼마나 개선했는지 꼬리 질문을 하게 된다.

대단한 성과나 결과인지는 중요하지 않습니다.
중요한 것은, 소소하게라도 결과를 내기 위해 일해 본 경험이 있고 그를 자기 발전의 양분으로 잘 삼아 성장할 수 있는 개발자인지를 증명하는 것입니다.
속도가 얼마에서 얼마로 개선되었는지, 메모리가 얼마에서 얼마로 줄었는지 숫자를 이용해 이야기하세요.

백엔드의 개발자의 경우, 구현한 결과물이 당장 눈앞에 보이는 것은 아니기 때문에 어떻게 표현해야 할 지 어려울 수 있는데요.
이러한 경우, 포트폴리오에 준비했던 프로젝트의 아키텍처를 제시해 보는 것도 좋은 방법입니다.

실제로 포트폴리오에 아키텍처 등의 시각 자료를 포함하고 서류 합격률이 솟구친 사례를 참고하세요.

3️⃣ 포트폴리오의 프로젝트 경험과 회고에 대해 튼튼히 준비하라

최근에는 신입 지원자들도 다양한 프로젝트 경험을 통해 역량을 증명하는 경우가 많습니다.
실무와 가장 가까운 경험이기 때문에 나의 역량을 증명하기 위한 굉장히 좋은 방법 중 하나인데요.

하지만 이렇게 프로젝트 경험을 내보일 때는 이 경험의 내용과 그를 통해 배운 것,
회고를 탄탄히 준비해야 합니다.

특히 팀 프로젝트일 경우, 이 중 내가 진짜 한 일이 어디서부터 어디까지인지를 명확히 하는 것이 중요합니다.
면접관들은 지원자의 진짜 실력과 역량을 알아보기 위해 프로젝트 경험에 대해 자세한 질문을 할 수밖에 없다는 것을 기억하세요.

개발 과정에서 사용한 기술들에 대한 설명과 해당 기술을 선택한 이유, 트러블 슈팅 과정, 그를 통해 배운 것과 문제 해결 뒤 어떤 개선점이 있었는지를 상기 부분에 말한 것처럼 명확한 지표를 이용해 말하는 것을 유념하세요.

🫵🏻 오늘의 질문 x 5

1) Call by reference란 무엇이고 보통 어떻게 쓰이는지 설명해 보세요.

• Call by value (값에 의한 호출): 변수 값 자체를 복사해서 메서드에 전달.

• Call by reference (참조에 의한 호출): 변수의 주소(참조)를 전달해서 메서드에서 원본 데이터에 영향을 줄 수 있음.

  
  Spring으로 개발을 할 때는 JAVA를 사용하고, JAVA는 `Call by value`를 따른다. ```java // 기본형 변수

void change(int x) { x = 10; } public static void main(String[] args) { int a = 5; change(a); System.out.println(a); // 출력은 여전히 5 }

위의 예제에서 a 값이 그대로인 이유는, change 함수로 값 5만 복사돼서 넘어갔기 때문이다.
하지만 여기서 중요한 건 기본형과 **참조형(객체)**의 차이가 된다.
</br>

```java
// 참조형 변수(객체)를 넘겼을 때

class Person {
    String name;
}
void changeName(Person p) {
    p.name = "민용";
}
public static void main(String[] args) {
    Person me = new Person();
    me.name = "해미";
    changeName(me);
    System.out.println(me.name); // 출력은 "민용"
}

me 객체의 name 필드는 바뀌게 된다. me라는 객체의 주소(reference)가 복사되어 넘어갔기 때문에, 객체 안의 상태를 바꾸는 것은 가능하다.

주소 복사만 전달되므로, 객체 내부 상태 변경은 영향을 받으나, 참조 자체를 새로 할당하면 영향을 받지 않게 된다.
이처럼 Spring은 JAVA기반이므로, 기본적으로 Call by Value 방식을 따른다.

하지만 대부분의 데이터는 객체로 다루게 되기 때문에, 메서드에서 객체 속성을 변경하면 바깥에도 영향이 있다. 그래서 개발자 입장에서는 Call by reference처럼 보이는 효과를 경험하게 된다. 이러한 경우 객체의 상태 변경과 관리가 더 효율적이며 예측 가능해진다는 장점이 있다.

+) Call by reference를 따르는 언어? C++이 있다. C의 경우 Call by Value이나, 포인터로 Call by Reference(주소 전달)처럼 구현이 가능하다

2) Override와 Overload 를 설명해 보세요.

마찬가지로 JAVA와 같은 객체지향언어의 기본개념에 대한 질문이다.

• 오버라이딩 (Overriding) : 부모 클래스에서 정의한 메서드를 자식 클래스에서 재정의하는 것
• 오버로딩 (Overloading) : 같은 이름의 메서드를 매개변수의 개수나 타입이 다르게 여러 개 정의하는 것.

// 오버라이딩 (Overriding)
class Parent {
    void sayHello() {
        System.out.println("Hello from Parent");
    }
}

class Child extends Parent {
    @Override
    void sayHello() {
        System.out.println("Hello from Child");
    }
}

// 오버로딩 (Overloading)
class Printer {
    void print(String s) {
        System.out.println(s);
    }

    void print(int n) {
        System.out.println(n);
    }

    void print(String s, int n) {
        System.out.println(s + " " + n);
    }
}

오버로딩은 메서드 이름은 같고, 매개변수가 달라야 한다. 리턴 타입은 같을 수도 있고, 다를 수도 있으나, 리턴타입만 다르면 오버로딩이 되지 않고 같은 메서드로 인식하여 중복선언 에러가 뜨게 된다. 동일 메서드명으로, 다양한 입력을 처리할 수 있게 하기 위해 사용된다.

오버라이딩은 메서드 이름은 같고, 매개변수도 같아야 하고, 리턴타입도 동일하거나 하위타입이어야 한다.

오버라이딩은 오버로딩과 달리, 상속관계가 필수적으로 요구된다. 상위 클래스의 기능을 바꾸기 위한 목적으로 사용되기 때문이다. 이 때, Spring에서는 오버라이딩하는 메서드에 @Override 어노테이션을 붙여준다.

오버라이딩과 오버로딩은 이와같이 개념부터 다르고, 목적성의 분명한 차이를 보인다.

3) JVM이란 무엇이고 왜 필요한지 설명해 보세요.

이 링크 정리 좋다 !

• JVM (Java Virtual Machine) : Java 바이트코드(.class)를 실행하는 가상 머신

즉, 자바로 작성된 코드를 실행할 수 있도록 만들어진 소프트웨어를 뜻한다.

⬇️ JVM의 필요성

VM은 자바 프로그램을 운영체제(OS)와 독립적으로 실행할 수 있도록 도와주며,메모리 관리(GC)와 보안까지 책임지는 자바 실행의 핵심 엔진이다.

Spring도 JVM 위에서 동작하게 된다.

+) JVM의 구성요소

4) Java가 컴파일되는 과정에 대해 설명해 보세요.

0. 컴파일 단계 : 개발자가 .java 파일 작성, javac 컴파일러가 실행되어 .class 바이트코드 파일 생성됨. 이 단계는 JVM 이전 단계, 즉 JDK(Java Development Kit)의 역할 !

   ⬇️ (JVM) 클래스 로딩 5 단계

1. 로드 과정 : 클래스 파일을 가져와 JVM의 메모리에 로드하는 과정 자바 소스 코드(.Java)가 작성되면 자바 컴파일러가 이 소스 코드를 읽어 바이트 코드(.class)로 컴파일한 뒤 이를 클래스 로더에게 전달. 클래스 로더는 동적 로딩으로 필요한 클래스들을 링크하여 JVM 메모리에 업로드해 런타임 데이터를 구성.

   2. 검증 과정 : 자바 언어 명세와 JVM 명세에 구성이 맞는지 검증
   3. 준비 과정 : 클래스가 필요로 하는 메모리를 할당
   4. 분석 과정 : 클래스의 상수 풀 내 모든 심볼릭 레퍼런스를 다이렉트 레퍼런스로 변경
   5. 초기화 과정 : 클래스 변수들을 적절한 값으로 초기화

이러한 과정이 모두 완료되면, 실행 엔진은 JVM 메모리에 업로드된 바이트 코드를 명령어 단위로 가져와 실행 실행 엔진의 2가지 작동 방식

• 인터프리터 방식 : 바이트 코드 명령어를 한 개씩 읽고 실행하는 방식. 명령어별 실행은 빠르지만 전체적인 속도는 느리다는 단점 !
• JIT 컴파일러 사용 방식 : 인터프리터 방식의 단점을 개선하기 위해 등장한 것이 JIT 컴파일러 사용 방식. JIT 컴파일러는 바이트 코드 전체를 컴파일하여 바이너리 코드로 변경하고, 해당 메서드를 바로 바이너리 코드로 실행. -> 전체적인 실행 속도가 인터프리터 방식보다 훨씬 빠르다 !!

5) 클래스와 인스턴스의 차이에 대해 설명해 보세요.

클래스(Class)와 인스턴스(Instance)는 객체 지향 프로그래밍에서 매우 중요한 개념이다.

• 클래스(Class) : 객체의 속성(attribute)과 동작(behavior)을 정의하며, 객체를 생성하기 위한 템플릿 역할. 객체를 생성하기 위한 일종의 설계도로서 여러 객체가 공유하는 특성을 정의 예를 들어, ‘핸드폰’ 클래스는 핸드폰 객체가 가져야 할 속성(색상, 모양, 모델 등)과 동작(터치, 전원 등)을 정의함

• 인스턴스(Instance) : 클래스를 기반으로 생성된 객체 클래스가 설계도라면, 실제로 사용되는 데이터와 객체는 인스턴스 생성을 통해 만들어짐. 클래스의 속성과 동작을 실제 값으로 가지고 있으며, 각각 독립적으로 작동 예를 들어, ‘핸드폰’ 클래스에서 ‘삼성 갤럭시 S24’, ‘애플 아이폰 15’ 와 같은 여러 인스턴스를 생성 가능.

=> 클래스가 객체의 설계를 정의 -> 인스턴스는 클래스에 따라 생성된 실제 객체

클래스에서 여러 인스턴스를 생성할 수 있고, 각 인스턴스는 클래스의 정의에 따라 각각 독립적인 데이터와 동작을 가지고 있다. 클래스는 정의만으로는 메모리에 없고, 인스턴스는 new 키워드 등으로 생성 시 메모리에 존재하게 된다.

아쟈. ~ !! 💪🏻

예.

백준 10951번입니다. 참으로 간단해보이죠? 근데 함정이 있음.

🤔 🤔 ...

1️⃣ 입력값의 개수가 지정되지 않음 2️⃣ 입력을 종료키가 지정되지 않음 ( ex. "@"가 입력되면 입력을 멈춘다

한 마디로 입력이 더 들어오지 않으면 알아서 종료시켜야 채점이 된다는 거다
위 문제는 EOF 개념 을 알아야 풀 수 있다

EOF : End Of File ✋🏻

EOF(End of File)는 파일이나 입력 스트림에서 더 이상 읽을 데이터가 없음을 나타내는 신호야.
즉, 입력이 끝났음을 의미하는 특별한 상태야.

✅ EOF는 언제 발생할까?

1. 파일을 읽을 때
   → 파일의 끝까지 읽고 나면 EOF 발생.

2. 키보드 입력을 받을 때
   → 사용자가 입력 종료 키를 누르면 EOF 발생.

3. 스트림 데이터를 읽을 때
   → 네트워크 소켓, 표준 입력(System.in) 같은 입력 스트림이 더 이상 데이터를 제공하지 않을 때 EOF가 발생.

✅ 자바에서 EOF 감지하는 방법

자바에서는 EOF를 직접 감지하는 기능이 없고, 보통 readLine()이 null을 반환하면 EOF로 간주해.

🔥 1️⃣ BufferedReader로 EOF 처리하기

📌 기본적인 while문을 사용한 EOF 처리

import java.io.*;

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

        while ((line = br.readLine()) != null) { // EOF가 발생하면 null 반환
            System.out.println("입력된 값: " + line);
        }
    }
}

🛠 실행 방법 (터미널에서)

java Main

EOF를 입력하는 방법:

• Windows: Ctrl + Z 누르고 Enter
• Mac/Linux: Ctrl + D

🔥 2️⃣ Scanner의 hasNext()를 사용한 EOF 처리

Scanner를 사용하면 hasNext()를 이용해 EOF를 감지할 수 있어.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) { // EOF가 발생하면 false 반환
            String input = sc.nextLine();
            System.out.println("입력된 값: " + input);
        }

        sc.close();
    }
}

📌 Scanner.hasNext()를 사용할 때의 장점

• hasNext()는 파일 입력, 키보드 입력 모두에서 사용할 수 있어.
• Scanner를 이용하면 공백 단위 입력도 쉽게 처리 가능.

✅ EOF를 사용하는 이유

📌 EOF는 어떤 상황에서 유용할까?

1. 입력 개수가 정해지지 않은 문제를 해결할 때

   • 입력 개수가 주어지지 않은 문제에서 EOF까지 계속 읽어야 하는 경우.

2. 파일을 다 읽었는지 확인할 때

   • 파일 끝까지 읽었는지 확인하려면 EOF를 감지해야 함.

3. 네트워크 소켓에서 데이터 스트림이 종료되었는지 확인할 때

   • 네트워크 연결이 닫혔는지 감지할 때 사용.

🎯 정리

💡 결론:
자바에서는 EOF를 직접 감지하는 방법이 없지만,

• BufferedReader.readLine() == null 또는
• Scanner.hasNext() == false

를 사용해서 EOF를 확인할 수 있어! 🚀

문제풀이 ✏️

그렇다고 함.

다음은 활용해서 쓴 나의 코드다.

속도가 느린 느린 scanner()를 쓰고싶지 않아서...

while ((line = br.readLine()) != null) { // EOF를 감지하여 종료

BufferedReader를 활용해서 이렇게 EOF 감지 처리 를 해줌

⬇️ 완성된 나의 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        while ((line = br.readLine()) != null) { // EOF를 감지하여 종료
            StringTokenizer st = new StringTokenizer(line);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.println(a + b);
        }
    }
}

문제가 참 카와이하다 나도 별 보러가고 싶어

아무튼 이중 for문 문제입니다

import java.io.*;

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.print("*");
            }
            System.out.println();
        }
    }
}

그런데... print() 로 이중for문 돌리는 게 너무 조잡하다는(??) 생각이 들었다 (시간도 124ms로 뭔가 못마땅함. 이중for문 너무 느림.)

💗 StringBuilder

import java.io.*;

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

        StringBuilder sb = new StringBuilder(); // <- 얘다 !!!!!!!
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                sb.append("*");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

StringBuilder() !!!!! 이 친구 참 좋다. 시간도 확 줄고 메모리도 확 줄었다.

출력 카테고리에 완전히 넣기는 좀 애매하지만, 출력 이전에 전처리로 해주면 성능이 확 좋아진다

쉽게 말해서 String을 맘대로 주무를 수 있는 함수다

String은 새로 대입하는게 아니고선 부분 수정이 안되는 아이라서... 알고 있다가 정말 편하게 다용도로 써먹을 수 있다

StringBuilder는 문자열(String) 연산을 효율적으로 처리하기 위해 사용하는 클래스야.
자바에서 String은 불변(immutable)이라서 문자열을 수정할 때마다 새로운 객체를 생성하지만,
StringBuilder는 가변(mutable) 객체로 동작해서 문자열을 직접 수정할 수 있어 성능이 훨씬 좋음. 🚀

✅ String vs StringBuilder 비교

✅ StringBuilder 기본 사용법

📌 1️⃣ StringBuilder 생성 방법

StringBuilder sb = new StringBuilder(); // 빈 문자열 생성
StringBuilder sb2 = new StringBuilder("Hello"); // 초기값 설정

📌 2️⃣ 문자열 추가 (append())

StringBuilder sb = new StringBuilder("Hello");
sb.append(" World");
System.out.println(sb); // 출력: Hello World

📌 3️⃣ 문자열 삽입 (insert())

StringBuilder sb = new StringBuilder("Hello");
sb.insert(5, " Java"); // 5번째 위치에 " Java" 삽입
System.out.println(sb); // 출력: Hello Java

📌 4️⃣ 문자열 변경 (setCharAt())

StringBuilder sb = new StringBuilder("Hello");
sb.setCharAt(0, 'Y'); // 첫 번째 문자 'H'를 'Y'로 변경
System.out.println(sb); // 출력: Yello

📌 5️⃣ 문자열 삭제 (delete() / deleteCharAt())

StringBuilder sb = new StringBuilder("Hello World");
sb.delete(5, 11); // " World" 삭제
System.out.println(sb); // 출력: Hello

📌 6️⃣ 문자열 반전 (reverse())

StringBuilder sb = new StringBuilder("Hello");
sb.reverse();
System.out.println(sb); // 출력: olleH

📌 7️⃣ 문자열 길이 (length()) & 용량 (capacity())

StringBuilder sb = new StringBuilder("Hello");
System.out.println(sb.length()); // 문자열 길이: 5
System.out.println(sb.capacity()); // 기본 용량: 16 + 문자열 길이

✅ 성능 비교: String vs StringBuilder

🔥 String 연산 (비효율적)

public class Main {
    public static void main(String[] args) {
        String str = "";
        for (int i = 0; i < 10000; i++) {
            str += i; // 새로운 문자열 객체 생성 (비효율적)
        }
        System.out.println(str.length());
    }
}

• 매번 새로운 문자열 객체가 생성됨 → 메모리 낭비, 속도 느림

🚀 StringBuilder 연산 (효율적)

public class Main {
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            sb.append(i); // 기존 객체 수정 (빠름)
        }
        System.out.println(sb.length());
    }
}

• 기존 객체를 수정하므로 메모리 사용량이 적고 속도가 훨씬 빠름.

✅ 멀티스레드 환경에서 StringBuffer 사용

• StringBuilder는 쓰레드 안전하지 않음.
• 멀티스레드 환경에서는 StringBuffer를 사용해야 함.

StringBuffer sb = new StringBuffer("Hello");
sb.append(" World");
System.out.println(sb); // Hello World

• StringBuffer는 StringBuilder와 기능이 거의 동일하지만, synchronized(동기화) 처리가 되어 있어 멀티스레드 환경에서 안전함.

그렇다고 한다.

근데 이 코드를 인텔리제이에 치니까, 얘가 코드를 여기서도 살짝 더 수정해보지 않겠냐는 거다

궁금해서 수정해봤다

💗 String클래스의 repeat()

import java.io.*;

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

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++) {
            sb.append("*".repeat(Math.max(0, i))); <- 얘다 !!!!!!!
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

그랬더니 이중 for문이 사라졌다

근데 java8에 돌리니 컴파일에러가 떴다...가 설마해서 11로 돌리니 돌아갔다

다음은 여기에 대한 지피티의 설명

java11부터 가능하니 참고하도록 하자 !!

최고 !

어, 그냥 i값 합치는 문제구나 .

백준 3단계는 반복문 chapter 이고 그래서 당연히 그렇게 풀었다

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        for (int i = 1; i <= n; i++) {
           sum += i;
        }
        System.out.println(sum);
    }
}

근데 이 문구가 자꾸 눈에 밟힌거다 ... 어케 푸는데...

그래서 혹시해서 지피티언니한테 물어봤는데

엥. 제공되는 함수는 따로 없댄다. 그래서 냅다 여러분이 풀어두신 코드를 보러 갔습니다 0.<

저는 68ms 나왔는데 여러분 역시 짱이지 말입니다

💬 와. 수학 공식으로 한 줄 계산하고 끝.

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(n * (n + 1) / 2);
    }
}

ㅋㅋ 이과였던 제가 이걸 까먹었다니요

64ms 로 줄어든다

for문은 계속 조건 검사하고, 똑같은거 작동하고 시간+메모리를 기본적으로 잡아먹기 때문에 ...

자신있게 외운 공식이 있으면 안 쓸 이유가 없다 ... 정말임 .....

💯 60ms 성공하신 분의 코드는 이렇다

존경의 의미로 코드복붙 안하고 캡쳐했음 일단 삼항연산자로 n==1일 때 처리를 따로 기깔나게 하셨는데, 저게 무슨 공식인지는 펜 들고 적어보지 않으면 모르겠다 ...
근데BufferedReader가 왜 static으로 저기에 있지 ...?
어라라..

추가로 공부를 해야겠다 생각이 들었다

다음 시간에 봐요

값을 한번에 출력하는 문제다

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

가이드를 문제에서 친절하게 알려준다 그래서 써봤다 ..!

BufferedWriter

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

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

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write((a+b) + "\n");
        bw.flush();
        bw.close();
    }
}

어김없이 등장한 나의 친구 BufferedReader , StringTokenizer ,,

근데 이제 BufferedWriter가 저 BR과 형제라고 보면 된다
BufferedReader ➡️ 입력 BufferedWriter ➡️ 출력
그러니 이 친구도 버퍼를 이용해서 출력하는, 비슷한 매커니즘을 통해 출력하는 그런 친구인거다 ((클릭해서 BufferedReader 개념 한번 더 보고오자))
근데 버퍼를 사용하여 한 줄씩 입력데이터를 받아오는 BufferedReader 와 달리 , BufferedWriter는 데이터를 버퍼에 저장하는 방식이라, 저장된 데이터를 다 썼으면 필요 없어진 버퍼메모리를 신경써야 한다는 점 !
우리 챗지피티 선생님의 정리를 한 번 보자

🔍 BufferedWriter란?

BufferedWriter는 자바에서 제공하는 출력 스트림 중 하나로, 데이터를 버퍼에 저장하여 출력 속도를 높이는 데 사용돼요. 출력할 내용을 임시로 메모리에 저장한 후, 필요 시 한꺼번에 출력하므로 성능이 향상돼요.

📌 BufferedWriter의 특징

1. 버퍼링 사용: 데이터를 한 번에 모아서 출력 → 효율적인 출력 가능.
2. 문자 기반 스트림: 텍스트 데이터를 처리할 때 사용.
3. write() 메서드로 출력: 데이터를 출력 스트림에 씀.
4. flush() 메서드로 강제 출력: 버퍼에 남아 있는 데이터를 강제로 출력.
5. close() 메서드: 스트림을 닫아 리소스를 해제.

✅ BufferedWriter 사용법

기본 문법:

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

• System.out: 콘솔에 출력.
• OutputStreamWriter: 바이트 스트림 → 문자 스트림 변환.

예제 1: 기본 사용

import java.io.*;

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

        bw.write("Hello, World!");
        bw.newLine();  // 줄바꿈
        bw.write("BufferedWriter 예제입니다.");
        bw.flush();    // 버퍼의 내용을 강제 출력
        bw.close();    // 스트림 닫기
    }
}

✅ 파일 출력에 사용

BufferedWriter는 파일에도 데이터를 쓸 수 있어요. FileWriter와 함께 사용하면 파일에 효율적으로 텍스트를 저장할 수 있어요.

예제 2: 파일 출력

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new FileWriter("output.txt"));

        bw.write("Hello, file!");
        bw.newLine();  // 줄바꿈
        bw.write("This is a BufferedWriter example.");
        bw.flush();    // 파일에 강제 쓰기
        bw.close();    // 스트림 닫기
    }
}

• 파일 이름: "output.txt"
• 내용:

  Hello, file!
  This is a BufferedWriter example.

✅ 반복 출력

BufferedWriter는 반복적으로 데이터를 출력할 때도 효율적으로 사용할 수 있어요.

예제 3: 반복 출력

import java.io.*;

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

        for (int i = 1; i <= 5; i++) {
            bw.write("Line " + i);
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

출력 결과:

Line 1
Line 2
Line 3
Line 4
Line 5

📝 BufferedWriter의 주요 메서드

🎯 BufferedWriter vs System.out.println

💬 언니의 팁!

• 대량의 데이터 출력: BufferedWriter가 적합.
• 파일 출력 시 효율적으로 데이터를 저장하려면 BufferedWriter를 꼭 사용해 봐! 😊

추가로 씹뜯맛

for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write((a+b) + "\n");   // <- 여기 !!!!!!!!!

int a, b 를 합산한 값을 출력해야 하는데

bw.write(a + b);

그냥 이렇게 해버리면 a=1, b=1일 때 a + b =11 이라는 놀라운 결과가 나온다 !

왜냐면 BufferedWriter.write() 메서드는 문자열만 출력하기 때문이다

println()과 달리 !

자동 내부 연산을 한 게 아니라 a , b 를 각각 문자열로 출력한거다 그래서 a + b 의 Int 값이 String이 되기 전에 먼저 계산해야 함

방법 1️⃣ : java의 문자열 결합 규칙 쓰기 (간단)

bw.write((a + b) + "\n");

내가 제출한 코드처럼 괄호를 사용하는 방법이 있다 제일 간단하고 쉽다 ...
java는 제일 속에 있는 괄호부터 계산하기 때문에, 속괄호 내에서 아직 int 상태인 a, b를 계산해두는 거다

그러면 출력값으로 2가 제대로 나온다 !

방법 2️⃣ :String 변환 함수 쓰기 (명시적)

bw.write(String.valueOf(a + b) + "\n");

String 변환 함수를 써서 명시적으로 함수 인자는 계산된 Int, 결과는 String으로 바꿔서 나오도록 쓸 수 있다
하지만 굳이 싶다

문자열 결합 규칙을 알면 훨씬 간단하다 !

기초를 잘 배우도록 하자 0.<

매우 기본적인 문자열 입력받아 콘솔창에 출력하기 문제이다 scanner가 익숙하다면 문제 보자마자 가장 먼저 생각나는 것은 아래 코드일 수 밖에 없다

이렇게 나옴.

하지만 우리들은 저 [메모리]와 [시간]을 신경 안 쓸 수가 없다

그래서 다른 사람들이 먼저 시간을 어떻게 줄였는가.. 보면 바로 등장하는 게 BufferedReader와 StringTokenizer다

BufferedReader

요약하자면 BufferedReader 클래스는 이렇다

1. 먼저 [입력 속도를 향상] 시킴으로서 시간 단축을 시켜주는 클래스
2. 문자열로 입력 받고, 한 줄씩 받아오기 때문에 입력값에 후처리가 필요함

그렇다면 후처리는 어떻게 들어가나요 ? 할 때 나오는 게 StringTokenizer다

StringTokenizer

토큰 단위로 자잘자잘히 문자열을 나누는 클래스, 토큰 단위이기 때문에 [공백, 쉼표같은 한 글자짜리 구분자]로 나눈다

이 BufferedReader와 StringTokenizer를 함께 사용하면 입력값이 많고 복잡한 문제일 수록 속도가 눈에 띄게 향상된다

시간이 훅 줄어드는 매직 ... 코테에서 이 둘은 그냥 외워뒀다가 일단 적어두고 시작하는 게 맞다

그런데 문자열 나누는 것 하면 생각나는 게 있다

우리... split 함수 좋아하지 않았나요 ?

얘는 토큰 단위가 아닌, 복잡한 문자열도 구분자로 설정이 된다 split()을 사용해서 문제를 풀어보자

큰 차이가 없어 보이는 결과인데, 토큰 단위로 나누는 게 처리 속도가 더 빠르지 않을까 싶어서 물어봤더니

(정말 최고애 GPT ...)

속도면에서도, 남은 토큰 수 계산해야 할 상황에서도 코테 상황에서 StringTokenizer를 안 쓸 이유가 없다

코테에서 BufferedReader와 StringTokenizer는 무조건 갖고 가자

추가로 씹뜯맛

난 코테가 아주 익숙한 사람은 아니지만 ... 코테를 풀면 꼭 시간, 메모리 순위별로 다른 사람 코드를 훔쳐보는 버릇이 있음

왜냐면 정말 미친(positive) 사람 많기 때문이다 그리고 그 사람들이 쓴 로직이나 꿀클래스를 흡수하면 짜릿하기 때문임
백준 1000번 문제는 매우매우 간단하지만, 그렇기에 어떻게 시간과 메모리를 더 줄였는지가 더 궁금했다

순위권 분들 다들 64ms 걸리시고, 메모리도 적으셔서 코드를 호록쟙쟙 보았다

// 이것이 그 코드
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        StringTokenizer st = new StringTokenizer(line, " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        System.out.println(a + b);
    }
}

예외처리

얼핏 보기엔 내 코드와 비슷해보이지만 보고 아차 한 것이 있었다

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

BufferedReader , Integer.parseInt() 같은, 특히 입출력을 다루는 애들은 오류 발생을 대비해 예외처리가 필요하다는 점.. 을 까먹고 있었다

실전 코딩이라면 try-catch를 사용하겠지만, 코테와 같은 (실제 프로젝트가 아닌) 문제풀이에서는 예외 던지기를 활용하자

그 외에 시간, 메모리가 적은 이유

예외처리를 넣은 해당 코드로 다시 돌려본 것이 아래의 104ms, 예외처리가 없을 때와 시간은 같다

68ms가 어떻게 나오나 했는데 java8과 java11의 차이였다

이 코드 한정인 것 같다

그만 알아보자 👌🏻