20260126 [TIL] - 자료구조 및 알고리즘 INTRO

1. 알고리즘 개념

1) 알고리즘이 뭐임?

• 입력(Input): 재료(예: 숫자 2개, 장바구니 목록)
• 과정(Process): 어떤 순서로 무엇을 할지(예: 더한다 -> 조건 검사한다 -> 출력한다)
• 출력(Output): 완성된 결과(예: 합, 최댓값, 결제금액)
• 끝나는 조건(Stop): 언제 멈추는지(예: 다 검사하면 종료)
• 예를 들어 "장바구니 합계"는 상품을 하나씩 보면서 가격, 수량을 더한다 - > 합이 5만원 이상이면 배송비 0원

 

2) 좋은 알고리즘이란?

1. 정확성: 항상 정답이 나오나? (같은 입력이면 같은 결과)
2. 효율성: 너무 오래 걸리지 않나? (시간) / 메모리를 너무 쓰지 않나? (공간)
3. 명확성: 사람이 읽어도 이해되나? (코드 / 설명이 깔끔한가?)
4. 확장성: 나중에 기능 추가 / 수정하기 쉬운가?

 

3) 시간복잡도(Big-O)는 뭐임

`시간복잡도` = 데이터가 커질수록 "얼마나 느려지는지"의 성장 속도
정확히 몇 초가 아니라 n이 커지면 연산 횟수가 어떤 모양으로 늘어나는지를 본다

• `O(1)`: 버튼 한 번 누르기 (항상 1번)
• `O(n)`: 줄 서 있는 사람 n명 한 명씩 인사하기
• `O(n2)`: 반 친구 n명 x n명 서로 악수하기
• `O(log n)`: 업다운 게임처럼 반씩 줄여서 찾기
• `O(n log n)`: 정렬 같은 방식

 

4) 시간복잡도(Big-O)를 일단 외우는 법

✅ `O(1)`

항상 한 번 (데이터가 커져도 똑같이 1번)
예) 배열에서 arr[3] 꺼내기

✅ `O(n)`

n개를 한 번씩 (줄 서 있는 사람 n명 한 명씩 체크)
예) for문 하나: for i=0..n-1

✅ `O(n²)`

n개를 n번씩 (반 애들 전부 서로 악수 = 폭발)
예) for문 2개 겹침

반복이 몇 번 도는가?

• for문 1개 → 보통 O(n)
• for문 2개 겹침 → 보통 O(n²)
• for문이 “따로따로” 2개(연속) → O(n) (2n이지만 n으로 봄)
  → “합+최댓값을 한 번에” vs “따로 두 번에”가 둘 다 O(n)인 이유

 

1. 입력: 뭐 받지?
2. 출력: 뭐 내지?
3. 반복: 몇 번 도나? (n? n²?)
4. 조건: if가 있나?

 

---

2. 알고리즘 문제 풀이 5단계

1단계: 문제 이해

• 입력이 뭐야? (뭘 받지?)
• 출력이 뭐야? (뭘 내지?)
• 규칙/제약이 뭐야? (범위, 조건, 금지사항)
• 예시를 보고 “진짜 하고 싶은 일”을 한 줄로 적기
  → 예: “N원을 최소 동전 개수로 거슬러줘라”

✅ 이 단계의 산출물(결과물):
“입력/출력/규칙” 3줄 정리

 

2단계: 접근 방법 생각 (어떤 방식으로 풀지)

• 가장 단순한 방법부터 떠올리기 (일단 떠올리기 쉬움)
• 더 좋은 방법(빠른 방법)이 필요한지 “N 크기”로 감 잡기
• 흐름을 말로 순서대로 적기 (자연어 알고리즘)

✅ 산출물:
“1)~2)~3)~” 순서표(레시피)

 

3단계: 구현 설계 + 검토

• 의사코드(코드 비슷한 말)로 옮기기
• 예외/극단 케이스 생각하기 (0, 최대값, 빈 경우 등)
• 시간복잡도 “대충” 보기 (반복이 몇 번?)

✅ 산출물:
의사코드 + 예외 케이스 메모 + 시간복잡도 한 줄

 

4단계: 코드 작성

 

• 변수명/함수명을 의미 있게
• 단계별로 그대로 옮기기

 

5단계: 테스트/디버깅

 

• 예시 입력으로 먼저 확인
• 극단 케이스로 확인 (0, 최소/최대, 경계값)
• 중간 값 출력(로그)로 어디서 틀리는지 찾기
• 시간초과면: 입력 처리/자료구조/중복계산 제거

 

---

3. 완전탐색(Brute Force) 정리

1) 완전 탐색이란?

완전탐색(Brute Force)은 가능한 모든 경우를 하나씩 전부 시도해 보는 방법이다. 정답을 놓치지 않는 대신, 경우의 수가 많아지면 시간이 오래 걸릴 수 있다.

• 장점: 구현이 단순하고 정답을 반드시 찾을 수 있음
• 단점: 데이터가 커지면 시간 초과가 나기 쉬움

 

2) 완전탐색은 언제 쓰나?

• 입력 크기(N)가 작아서 전부 시도해도 시간 안에 끝나는 경우
• 다른 방법이 떠오르지 않을 때 첫 접근법으로 사용
• "정답을 무조건 찾아야 하는데 경우의 수가 별로 없을 때"

 

3) 대표 예시: 두 수의 합이 target이 되는 조합 찾기

정수 배열 `numbers`에서 서로 다른 두 원소를 골라 합이 target이 되면 그 두 원소의 인덱스를 반환한다

예)
numbers = `[2, 11, 7, 15]`
target = `9`
2 + 7 = 9 -> 답은 인덱스 `[0, 2]`

 

4) 왜 이중 for문이 나오나?

"두 수를 고른다"는 건 곧 모든 2개의 조합을 확인한다는 뜻이다.

• 첫 번째 숫자를 하나 고른다 (i)
• 그 다음 숫자들 중 하나를 고른다 (j)
• `numbers[i] + numbers[j] == target`인지 확인한다

여기서 `j`를 `i+1`부터 시작하는 이유:

• 같은 원소를 두 번 쓰지 않기 위해
• (i, j)와 (j, i) 같은 중복 비교를 피하기 위해

 

5) 의사코드 (자연어)

1. i를 0부터 끝까지 돌면서 첫 번째 숫자를 선택한다
2. j를 i+1부터 끝까지 돌면서 두 번째 숫자를 선택한다
3. 두 숫자의 합이 target이면 인덱스 (i, j)를 반환한다
4. 끝까지 없으면 빈 배열을 반환한다

public class Solution {
    public static int[] findPairs(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {          // 첫 번째 수 선택
            for (int j = i + 1; j < numbers.length; j++) {  // 두 번째 수 선택 (중복 방지)
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i, j};                 // 정답 찾으면 즉시 반환
                }
            }
        }
        return new int[]{}; // 못 찾으면 빈 배열
    }
}

 

6) 시간 복잡도

배열 길이가 N일 때

• 바깥 반복문: 최대 N번
• 안쪽 반복문: 평균적으로 N번에 가까움
• 그래서 전체 비교 횟수는 대략 N×N 수준 → O(N²)

참고로 정확한 횟수는 (N-1)+(N-2)+...+1 = N(N-1)/2 이지만
Big-O는 가장 큰 성장항만 보므로 O(N²)로 표현한다.

 

완전 탐색은 "일단 다 해 본다"라서 이해는 쉽지만, N이 커지면 O(N²)처럼 시간이 빠르게 늘 수 있다.
그래서 코테에서는 입력 크기를 보고 완전탐색이 가능한지 먼저 판단해야 된다.