[TIL-260213] 알고리즘: 정렬, 검색(탐색)

이 글은 2026년 2월 13일에 작성된 글입니다.

알고리즘이란?

주어진 문제를 해결하기 위한 단계적인 절차.

알고리즘의 조건

• 입력: 모호하지 않고 잘 정의된 입력 값
• 출력: 명확히 정의된 1개 이상의 출력 값
• 명확성: 각 명령어의 의미가 모호하지 않고 정확
• 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다
• 언어 독립성: 프로그래밍 언어와 상관없이 독립적
• 유효성: 명령어들은 현재 실행 가능한 연산이어야 한다

 

알고리즘의 성능

여러 개의 알고리즘이 있을 때, 성능을 비교하기 위해 연산량(시간 효율성), 메모리 사용량(공간 효율성)을 고려할 수 있는데

둘 중 하나를 골라야 한다면 보통 연산량 즉 🕐알고리즘의 시간 효율성🕐을 선택한다.

 

알고리즘의 작업량을 표현할 때 시간 복잡도(Time Complexity)로 표현한다.

빅오 표기법: 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

 

시간 복잡도의 점근적 성장률 순서(입력 크기 n이 커질 때 증가 속도 기준으로 정렬한 것) 👇

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

따라서 O(1)이 가장 좋은 효율을 가지고 있지만 실제 이런 알고리즘은 없기 때문에 O(logn)으로만 짜도 좋은 알고리즘이라 평가할 수 있다.

 

알고리즘의 유형

• 정렬:
  퀵 정렬, 병합 정렬, 삽입 정렬, 선택 정렬, 버블 정렬 등
• 탐색:
  이진 탐색, 선형 탐색 등
• 그래프:
  DFS, BFS 등
• 그리디:
  각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방법
• 동적 프로그래밍:
  큰 문제를 작은 하위 문제로 나누어 해결하고 그 결과를 저장하며 중복 계산을 피하는 기법
• 문자열 처리:
  문자열 매칭, 부분 문자열 찾기, 편집 거리 계산 등
• 스택과 큐:
  자료를 저장하고 조작하는 데 사용되는 자료구조
• 백트래킹:
  가능한 모든 경우의 수를 탐색하면서 해를 찾는 방법
• 비트 조작:
  이진수 표현, 비트 마스크 등
• 수학적:
  최대공약수, 최소공배수, 소수 판별 등

📌 SW 문제는 코딩하기 전에 먼저 손으로 풀어보는 것이 중요❗❗❗

“First, solve the problem. Then, write the code.”
— John Johnson

 

---

정렬 알고리즘

정렬: 데이터를 정해진 기준에 따라 특성을 기준으로 나열하는 것

 

버블 정렬(Bubble Sort)

두 인접한 데이터의 크기를 비교해 정렬하는 방법

인접한 데이터 간의 swap 연산으로 정렬한다.

시간복잡도 - O(n^2)

import java.util.Arrays;

public class bubbleSort {
    public static void main(String[] args) {
        int[] nums = {42,32,24,68,15};

        for(int i=nums.length-1;i>0;i--) {
            for(int j=0; j < i;j++) {
                // 인접한 두수를 비교, 필요에 따라 swap
                if(nums[j] > nums[j+1]) {
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

 

선택 정렬(Selection Sort)

대상 데이터에서 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법

1️⃣ 최솟값을 찾고

2️⃣ 가장 앞에 있는 데이터와 swap

3️⃣ 남은 부분 없을 때까지 반복

시간 복잡도 - O(n^2)

import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] nums = {42,32,24,68,15};

        for(int i=0; i < nums.length-1; i++) {
            int minIndex = i;
            //최솟값 찾기
            for(int j=i+1;j<nums.length;j++) {
                if(nums[minIndex] > nums[j]) {
                    minIndex = j;
                }
            }

            // 최솟값을 가장 맨 앞의 원소와 위치 바꾸기
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;
        }

        System.out.println(Arrays.toString(nums));
    }
}

 

---

검색(탐색) 알고리즘

검색(탐색): 여러 개의 데이터 안에서 원하는 데이터를 찾아냄

순차 검색 (선형 탐색)

일렬로 되어 있는 자료를 순서대로 검색하는 방법

• 정렬되어 있지 않은 경우 → 시간 복잡도 - O(n)
• 졍렬되어 있는 경우 → 평균 비교 횟수가 반으로 줄어들지만 그래도 → 시간 복잡도 - O(n)

import java.util.Arrays;
import java.util.Scanner;

public class sequantialSearch {
    public static void main(String[] args) {
        int[] nums = {4,9,11,23,2,19,7};
        // 정렬
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));

        Scanner sc = new Scanner(System.in);
        int findNum = sc.nextInt();
        int result = -1;    // 인덱스는 0부터 시작
        for(int i=0; i<nums.length;i++) {
            if(nums[i] == findNum) {
                result = i;
            } else if(nums[i] > findNum) {
                break;
            }
        }

        if(result > -1) {
            System.out.println("찾고자 하는 데이터의 위치는 " + result + "에 있습니다.");
        } else {
            System.out.println("없어요!!!!");
        }

    }
}

 

이진 검색

정렬되어 있는 데이터에서 원하는 값을 찾는 방법

1️⃣ 중앙 원소 고르고

2️⃣ 중앙 원소와 찾는 값 비교

3️⃣ 찾는 값이 중앙 원소보다 작으면 자료의 왼쪽 데이터에 대해서 새로 검색, 크면 자료의 오른쪽 데이터에 대해 새로 검색

4️⃣ 찾는 값을 찾을 때까지 반복

import java.util.Scanner;

public class binarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 4, 7, 9, 11, 19, 23};

        Scanner sc = new Scanner(System.in);
        int findNum = sc.nextInt();
        int result = -1;

        int mid = 0; //중앙값
        int low = 0; //시작위치
        int high = nums.length -1; //종료위치

        while(low <= high) {
            //중간값 찾기
            mid = (low + high)/2;
            if(nums[mid] < findNum) {
                low = mid + 1;
            } else if(nums[mid] > findNum) {
                high = mid - 1;
            } else {
                result = mid;
                break;
            }
        }

        if(result > -1) {
            System.out.println("찾고자 하는 데이터의 위치는 " + result + "에 있습니다.");
        } else {
            System.out.println("없어요!!!!");
        }
    }
}

 

---

❕느낀점

애써 미루고 부정해왔던 알고리즘을 진짜로 공부할 차례가 되었다. 매일 백준 문제를 풀겠다고 다짐만 했던 날들을 뒤로하고 코딩테스트를 준비하기 위해 문제 풀이를 진짜로 연습해야겠다고 생각했다.

 

정렬, 검색까지는 기억이 나는데 그래프, 그리디, 브루트 폴스 알고리즘은 이름만 기억이 나고 좀 가물가물하다. 다음주부터 개념 이해부터 실제 문제 풀이까지 연습해야겠다.

코테 파이팅~~