[JAVA] 알고리즘 기본 정리

알고리즘이란? 

: 알고리즘은 문제를 해결하기 위한 단계적 절차나 규칙을 의미를 뜻하며, 논리적 사고력 향상과 효율적인 문제 해결을 위해 학습하게 됨

 

또한 알고리즘을 통해 문제 이해도, 코드 구현 능력, 효율적인 해결 방안  도출 능력을 같이 종합적으로 평가하는 부분으로도 사용됨

 

알고리즘의 표현 방법

: 알고리즘을 다른 사람에게 전달하거나 구현하기 위해서는 과정을 명확하고 간결하게 표현하는 것이 중요. 이를 대표하는 방법으로는 의사코드와 자연어 표기법을 사용하는 방법이 있음. 

 

좋은 알고리즘의 조건

좋은 알고리즘이란 크게 네가지로 분류하여 확인해볼 수 있다.

① 정확성 

 : 알고리즘이 정확하게 동작 하는가?

• 입력한 값에 대해 올바른 결과가 나오는가
• 정해진 단계를 따라 실행되며 멈추는 시점이 있는가
• 같은 입력값에 따라 같은 결과값이 항상 나오는가

② 효율성

 : 알고리즘이 효율적인가?

• 시간 복잡도 : 실행시간이 너무 오래걸리지 않는가
• 공간 복잡도 : 컴퓨터의 메모리를 적절히 사용하는가

③ 명확성

 : 알고리즘이 이해하기 쉬운가?

• 각 단계가 명확하고 이해하기 쉬워야 함
• 다른 사람도 읽고 이해할 수 있어야 함
• 필요한 경우 주석을 활용(단계를 설명하는 용도)

④ 확장성 

 : 알고리즘이 실용적이고 관리하기 좋은가?

• 다양한 상황에서 사용할 수 있어야 함
• 나중에 수정하거나 개선하기 쉬워야 함
• 문제가 생겼을 때 어디가 잘못됐는지 찾기 쉬워야 함

알고리즘 성능 분석

 : 알고리즘이 얼마나 효율적으로 동작하는지를 측정하는 방법이며, 시간(실행 속도)과 공간(메모리 사용량)을 기준으로 평가

이 중에서 가장 중요하게 챙겨가야 할 포인트는 바로 시간 복잡도이며, 주로 빅오(Big-O) 표기법을 사용하여 나타냄

• 시간복잡도는 프로그램의 응답 시간과 직결

빅오 표기법 예시

시간복잡도	대표 알고리즘	특징
O(1)	배열 인덱스 접근, 스택/큐 삽입/삭제	입력 크기와 관계없이 항상 같은 시간
O(log N)	이진 탐색, 균형 이진 탐색 트리	입력이 커져도 시간이 로그 값으로 증가
O(N)	배열 순차 탐색, 최대/최소값 찾기	입력과 시간이 비례하여 증가
O(N log N)	병합정렬, 퀵소트, 힙정렬	가장 효율적인 비교 기반 정렬 알고리즘
O(N²)	버블정렬, 삽입정렬, 선택정렬	입력이 커지면 입력 크기의 제곱으로 시간 증가
O(2^N)	부분 집합 생성	입력이 커지면 지수적으로 증가
O(N!)	순열 생성	입력이 증가할 때마다 시간이 팩토리얼로 폭발적 증가

 

+. 시간 제한에 따른 알고리즘 가능여부 

 : 시간 제한을 고려하여 적절한 알고리즘을 선택할 줄 알아야 함

❗️테스트 케이스 당 실행 시간 1~2초인 경우의 예시 

시간복잡도	데이터 크기 상한	알고리즘 예시	비고
O(log N)	10¹⁸ (64비트 정수 최대값)	이진 탐색, 균형 이진 탐색 트리	N이 매우 커도 빠르게 동작
O(N)	10⁸ (1억)	배열 순회, 1중 반복문	1초에 수행 가능
O(N log N)	10⁶ (백만)	병합정렬, 퀵정렬	N=10⁷에서 2.3초 소요
O(N²)	10⁴ (만)	버블정렬, 2중 반복문	1초 정도 소요
O(2^N)	20	부분집합 생성	N=30만 되어도 10초 소요
O(N!)	10	순열 생성	N이 조금만 커져도 시간이 기하급수적 증가

 

알고리즘 문제 해결 5단계

1단계: 문제 이해 및 요구사항 분석하기
     - 문제를 천천히 정독하기
     - 예제 입출력을 통해 문제의 의도 파악하기
     - 주어진 입력과 출력 형식을 정확히 파악하기
     - 제약 조건과 요구사항, 규칙 정리하기

2단계: 접근 방법 구상하기
     - 비슷한 유형의 문제 생각하기
     - 어떠한 유형의 알고리즘을 사용할지 정하기
     - 문제를 해결하기 위한 기본 아이디어 고안 혹은 문제 해결 절차에 대해 단계별로 나누기 및 도식화
     
3단계: 세부 구현 설계 및 검토하기
     - 문제 해결 절차의 각 단계를 의사코드로 표현하기
     - 발생할 수 있는 예외 상황 찾아보기
     - 극단적인 케이스 고려하기
     - 시간 복잡도 분석하기 

4단계: 코드 작성 및 구현하기
     - 세부 구현으로 표현된 아이디어를 실제 코드로 작성하기
     - 구현 과정에서 변수명, 함수명을 명확하게 작성하기

5단계: 테스트와 디버깅
     - 다양한 테스트 케이스를 통해 코드의 정확성을 검증하기
       * 예시 입출력으로 테스트하기
       * 극단적인 케이스로 테스트하기
     - 오류가 발생하면 디버깅하기
     - 시간 초과의 경우 아이디어 수정 및 코드 최적화하기
       * 효율적인 입력 처리 고려
       * 적절한 자료구조 선택
       * 중복 계산 방지 (메모이제이션) 
       * 유망하지 않은 탐색 가지치기 (백트래킹)

 

알고리즘 유형

구현(Implementation) & 시뮬레이션(Simulation)

• 구현 문제 : 문제의 요구사항을 실제 동작하는 코드
• 시뮬레이션 문제 : 문제에서 요구하는 시나리오, 규칙, 절차를 차례대로 실행하는 능력 요구
  
• 특징
  • 가장 기본이 되는 문제 유형
  • 알고리즘의 난이도 보다는 구현의 정확성이 중요
  • 요구사항을 빠짐없이 코드로 옮기는 것이 핵심
  • 문제의 조건과 제약을 정확히 이해하고 처리해야 함
• 주요 유형
  • 단순 구현 : 주어진 알고리즘이나 규칙을 그대로 코드로 옮기는 문제
    ex) 날짜/시간 계산, 진법 변환, 문자열 처리 등
  • 완전 시뮬레이션 : 문제에서 제시된 과정을 처음부터 끝까지 실행하여 결과를 도출하는 문제
    ex) 주사위 게임, 카드 게임, 보드 게임 시뮬레이션 등
  • 상태 변화 시뮬레이션 : 특정 조건에 따라 시스템의 상태가 변화하는 과정을 구현하는 문제
    ex) 로봇 이동, 뱀 게임, 벽돌 깨기 게임 등
  • 규칙 찾기 및 구현 : 문제의 숨겨진 규칙을 찾아 이를 코드로 구현하는 문제
    ex) 달팽이 배열, 소용돌이 수, 패턴 인식 등 

 

완전 탐색 (Brute Force) : 모든 경우의 수를 빠짐없이 조사하여 정답을 찾는 방법

• 특징
  • 모든 경우를 시도하므로 정답을 놓칠 가능성이 없음 (시간과 공간이 충분하다는 전제 하)
  • 입력 규모가 작을 때 유리하며, 구현이 비교적 간단
• 구현 방법
  • 반복문을 이용한 구현
  • 재귀 함수를 이용한 구현
• 대표적인 문제 유형
  • 순열/조합 계산
    ex) N개 중 K개를 고르는 모든 조합, N개 전부를 나열하는 모든 순열 등 
  • 부분집합 계산
    ex) 부분집합의 합으로 특정 값을 만드는 모든 경우 확인 
  • 그래프 전체 탐색 
    ex) 모든 경로 찾기, 모든 노드 방문 시뮬레이션, DFS/BFS를 통한 모든 가능성 확인

그리디(Greedy) 알고리즘 : 매 순간 최선의 선택을 함으로써 전체 최적해를 구하는 방식

• 특징
  • 다른 알고리즘(예: 완전탐색,동적 계획법 등) 보다 일반적으로 구현이 간단하고 빠른 시간 안에 결과를 얻을 수 있음
• 적용 조건
  • 탐욕 선택 속성(Greedy Choice Property)
    • 매 순간의 최선의 선택이 전체 문제의 최적해가 되어야 함
  • 최적 부분 구조(Optimal Substructure)
    • 부분 문제의 최적해들을 결합해 전체 문제의 최적해를 구할 수 있어야 함
• 대표적인 문제 유형
  • 거스름돈 계산 : 동전 단위가 특정 조건(예: 배수 관계) 에 부합할 때, 큰 단위 동전부터 먼저 사용
  • 회의실 배정 문제 : 종료 시간이 빠른 회의부터 배정하는 방식으로 최대 개수를 찾는 문제
  • 최소 신장 트리(MST) : 크루스칼(Kruskal), 프림(Prim) 알고리즘

백트래킹 (Backtracking) : 완전 탐색을 기반으로 하되, 유망하지 않은 경우(조건 불만족)는 미리 배제(가지치기)하여 탐색 효율을 높이는 기법

• 특징
  • 조건을 만족할 수 없는 상황을 빠르게 배제할 수 있어, 탐색 버위를 크게 축소할 수 있음
  • 대부분 재귀 함수로 구현
• 적용 조건
  • 상태 공간 트리 구성 가능성
    • 문제의 해결 과정을 트리 형태로 구조화 할 수 있어야 함
    • 각 단계별 선택지를 명확하게 정의할 수 있어야 함
      ex) 1부터 N까지의 수를 중복없이 나열하는 순열 문제에서 각 자리수 선택
  • 유망성 판단 기준(Promising)
    • 현재 상태에서 더 진행할 가치가 있는지 판단할 수 있는 명확한 기준이 있어야 함
      ex) 길찾기 문제에서 벽이나 이미 방문한 곳인지 확인
  • 가지치기 효율성
    • 유망하지 않은 경우를 제외했을 때 탐색 범위가 충분히 줄어 들어야 함
    • 가지치기 조건 검사가 너무 복잡하지 않아야 함
      ex) 특정 합을 만드는 문제에서 현재까지의 합이 목표값을 넘어선  경우
• 대표적인 문제 유형
  • N-Queen 문제 : 퀸이 서로 공격하지 않도록 배치하는 경우의 수를 찾는 문제
  • 스도쿠 풀이 : 불가능한 경우를 빠르게 가지치기해가며 정답을 찾는 방식
  • 부분집합의 합 : 특정 조건(목표값 등)을 만족하는 부분집합을 찾기

분할 정복 (Divide and Conquer) : 문제를 작거나 유사한 하위 문제로 분할하고, 각 문제를 해결한 뒤 결과를 합쳐 최종 해를 구하는 방식

• 특징
  • 분할 → 정복(해결) → 병합 단계를 거침
  • 분할된 각 부분 문제는 서로 독립적이어야 함
• 적용 조건
  • 분할 가능성 
    • 문제가 동일한 유형의 더 작은 하위 문제들로 나눠질 수 있어야 함
    • 분할된 문제는 원래 문제와 같은 성질을 가져야 함
      ex) 병합정렬에서 배열을 더 작은 배열로 분할할 수 있음
  • 하위 문제의 독립성(Independence)
    • 분할된 하위 문제들은 서로 독립적이어야 함
    • 어떤 하위 문제의 해결이 다른 하위 문제의 해결에 영향을 주지 않아야 함
      ex) 퀵정렬에서 피벗을 기준으로 나눈 두 부분이 서로 독립적
  • 병합 가능성(Mergeability)
    • 하위 문제들의 해답을 병합하여 원래 문제의 해답을 만들 수 있어야 함
      ex) 병합정렬에서 정렬된 두 부분 배열을 하나의 정렬된 배열로 병합 가능
• 대표적인 문제 유형
  • 병합 정렬(Merge Sort) : 배열을 반으로 나눈 뒤 각각 정렬 후 병합
  • 퀵 정렬(Quick Sort) : 피벗(Pivot)을 기준으로 왼쪽은 피벗보다 작은 요소들, 오른쪽은 큰 요소들로 재귀적 정렬
  • 이진 탐색(Binary Search) : 검색 구간을 절반씩 줄여가며 원하는 값을 찾는 방법

동적 계획법 (Dynamic Programming, DP) : 큰 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 해를 저장(메모이제이션) 하여 재활용 함으로써 전체 문제의 최적 해를 구하는 알고리즘 설계 기법

• 특징 
  • 중복 계산을 획기적으로 줄일 수 있어, 지수 시간이 걸리는 문제도 다항 시간 안에 풀 수 있는 경우가 많음
  • Top-Down 방식(메모이제이션) 또는 Bottom-up 방식(타뷸레이션)으로 구현
  • 점화식(Recurrence Relation)을 올바르게 세우는 것이 핵심
• 적용 조건
  • 최적 부분 구조(Optimal Substructure)
    • 작은 부분 문제들의 최적해를 조합하여 큰 문제의 최적해를 구할 수 있어야 함
  • 중복되는 부분문제(Overlapping Subproblems)
    • 동일한 작은 문제들이 반복적으로 나타나야 함
    • 이러한 중복 문제들의 해를 저장해두고 재활용할 수 있어야 함 
      ex) 피보나치 수열에서 f(n)을 구할 때 f(n-2)가 여러번 계산 됨
• 대표적인 문제 유형
  • 배낭 문제(Knapsack Problem) : 무게 제한이 있는 배낭에 물건들을 넣을 때 가치의 합이 최대가 되도록 물건을 고르는 문제
  • 최장 증가 부분 수열(LIS : Longest Increasing Subsequence) : 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이 찾기
  • 경로 문제 : 미로 찾기(최단 경로)

정리하며..

 문제 해결 시에는 문제의 특성과 제약사항을 가장 먼저 파악해야 하며 한개의 알고리즘으로는 시간 초과나 불필요한 연산이 발생할 수 있으므로 다양한 알고리즘 조합과정을 경험해보는 것이 필요함

 

결과 도출에 있어 여러가지 진행 방법이 있을 수 있으니 다양한 방식으로 문제풀이에 접근해 보는 경험치를 쌓아볼 것!