실제 연산량 줄이기 - 알고리즘 문제해결기법 입문
알고리즘 문제해결기법 입문
    • 01
      About Course
    • 공부하는 방법
      문제 모범 답안
      알고리즘이란
      알고리즘이 어려운 이유
    • 02
      0. Introduction & Tutorial
    • 알고리즘과 자료구조
      문제 해결하기
      약속하기
      문제의 구성
      입력과 출력
      문제0A-출력해보기
      문제0B-입력받아보기
      문제0C-반복해보기
      문제0D-저장해보기
      문제0E-테스트케이스
    • 03
      1. 코드와 친해지기
    • 챕터1 강의노트 (임시)
      코드와 친해지기
      반복문과 친해지기
      문제1A-최대값 함수
      문제1B-배열의 최대값
      문제1C-카운팅하기
      문제1D-합 구하기1
      문제1E-합 구하기2
      문제1F-탐색하기1
      문제1G-탐색하기2
      문제1H-탐색하기3
      문제1I-선택정렬 구현하기
      문제1J-합 구하기3
      단원 되짚어보기 & 해설
    • 04
      2. 알고리즘의 연산량
    • 연산량과 시간복잡도
      챕터2 강의노트 (임시)
      실제 연산량 줄이기
      문제2A-도토리 키재기
      문제2B-오름차순인가?
      문제2C-다양성
      문제2D-문자열의 비교
      문제2E-소수의 판별
      문제2F-데스티니
      문제2G-버블정렬 구현하기
      문제2H-픽셀 수 세기
      문제2I-정주행
      문제2J-승부 조작
      단원 되짚어보기
    • 05
      3. 공간 활용하기
    • 배열의 특징
      챕터3 강의노트(임시)
      배열 활용하기
      문제3A-전화번호
      문제3B-페인트
      문제3C-응모
      문제3D-피보나치 나머지
      문제3E-색종이
      문제3F-과유불급
      문제3G-팬미팅
      문제3H-두 카드
      문제3I-세 카드
      문제3J-네 카드
    • 06
      4. 자주 사용되는 수학 알고리즘
    • 챕터4 강의노트(임시)
      문제4A-스도쿠 보드
      문제4B-Probing
      문제4C-최대공약수와 최소공배수
      문제4D-수열의 순환
      문제4E-소인수 분해
      문제4F-소수 세기
      문제4G-배열 흔들기
      문제4H-카잉 달력
      문제4I-골드바흐의 추측
      문제4J-공약수 게임
    • 07
      5. 구현 훈련하기
    • 문제5A-놀이 공원
      문제5B-거대 놀이 공원
      문제5C-레이저 타워
      문제5D-레이저 타워 건설하기
      문제5E-숫자 채우기1
      문제5F-숫자 채우기2
      문제5G-숫자 채우기3
      문제5H-두 직사각형
      문제5I-두 선분
      문제5J-로봇 청소기
      문제5K-고성능 로봇 청소기
      문제5L-NBA농구
      문제5M-와일드 카드
      문제5N-패턴 검사
      문제5O-단어 퍼즐
      문제5P-이름 짓기
    • 08
      6. 자료구조 활용하기
    • 챕터6 강의노트 (임시)
      문제6A-괄호 문자열
      문제6B-탑
      문제6C-히스토그램
      문제6D-조세퍼스 문제
      문제6E-폭탄 제거
      문제6F-폭탄 제거 순서 정하기
      문제6G-불안정 지역
      문제6H-중복 제거하기
      문제6I-정사각형
      문제6J-빈도수 세기
      문제6K-시장 추천하기
      문제6L-배열 합치기
      문제6M-이중 우선순위 큐
      문제6N-중앙값 큐
      문제6O-피자 하와이
    • 09
      7. 재귀 함수와 분할 정복
    • 챕터7 강의노트(임시)
      [문제07A] 모든 조합 출력하기
      [문제07B] 하노이의 탑
      [문제07C] 단지 번호 붙이기
      [문제07D] Merge Sort 구현하기
      [문제07E] Quick Sort 구현하기
      [문제07F] 히스토그램
      [문제07G] Counting Inversion Pairs
      [문제07H] Finding Closet Pair
    • 10
      8. DFS/BFS
    • 챕터8 강의노트(임시)
      [문제08A] - 그래프의 탐색 1
      [문제08B] - 그래프의 탐색 2
      [문제08C] - 그래프의 최장 경로
      [문제08D] - 그래프의 최단 경로
      [문제08E] - 바이러스
      [문제08F] - 미로 탈출하기
      [문제08G] - 토마토
      [문제08H] - 소수 경로
      [문제08I] - 스도쿠 보드 채우기
      [문제08J] - N Queen
    • 11
      9. 그래프 알고리즘
    • 챕터9 강의노트(임시)
      [문제09A] 해밀턴 경로
      [문제09B] 외판원 순회 문제
      [문제09C] 한 붓 그리기
      [문제09D] 그래프의 연결성
      [문제09E] 최소 신장 트리 1
      [문제09F] 최소 신장 트리 2
      [문제09G] 그래프의 최단 거리
      [문제09H] 그래프의 최단 거리 2
    • 12
      10. 동적 계획법
    • [문제10A] 가장 긴 부분 증가수열 (LIS)
      챕터10 강의노트(임시)
      [문제10B] 팬스 수리하기
      [문제10C] 아르바이트
      [문제10D] 회선 설치하기
      [문제10E] 2차원 누적합
      [문제10F] 퀼팅(Quilting)
      [문제10G] 가장 긴 공통 부분 문자열 (LCS)
      [문제10H] Ah-choo!
      [문제10I] 곱하기는 귀찮아
      [문제10J] 올바른 괄호 문자열
      [문제10K] 배낭 문제 (Knapsack Problem)
      [문제10L] 7 Segment Display
    • 13
      11. 문제를 푸는 다른 방법
    • 챕터11 강의노트(임시)
      [문제11A] 지하철을 빠르게 빠르게
      [문제11B] 감시 로봇
      [문제11C] 복도 통과하기
      [문제11D] Selling Cells
      [문제11E] 인구조사
      [문제11F] 그래프 최소 분할
    • 14
      12. 문자열 알고리즘
    • 챕터12 강의노트 (임시)
      [문제12A] Rabin Karp
      [문제12B] KMP
      [문제12C] 실패함수 계산하기
      [문제12F] Trie 구현하기
    • 15
      Appendix - Java
    • 16
      Appendix - C++
    실제 연산량 줄이기
    04 2. 알고리즘의 연산량
    실제 연산량 줄이기

    시간 복잡도의 한계

     시간 복잡도는 입력 크기에 비례한 연산량을 추측하는 판단 기준이 될 수 있습니다. 하지만 함수의 계수와 낮은 랭크의 항을 무시하게되기 때문에 실제 연산량과 시간 복잡도를 통해 계산한 연산량의 차이는 상당히 클 수 있습니다. 물론 입력 데이터의 크기가 커지면 커질수록 그 차이는 줄어들겠지만요. 그리고 또 하나 주의해야 할 점은 분명히 함수들은 값의 범위에 따라서 대소관계가 다르다는 점입니다. 아래의 그래프를 보면 떠올릴 수 있습니다. 낮은 랭크의 시간 복잡도가 항상 높은 랭크의 시간 복잡도보다 적은 연산량을 보장하지는 않는다는 뜻입니다. 그렇기에 시간복잡도는 터무니 없이 큰 연산량을 요구하는 알고리즘을 분간하는 데에는 큰 도움이 될 수 있지만, 같은 시간 복잡도를 가지는 알고리즘이나 입력 데이터 수가 작은 알고리즘의 구체적인 성능을 예측하기에는 시간 복잡도 이외의 추가적인 지식과 감이 필요할 수 있습니다. 실제로 빈번히 사용되고 있는 알고리즘들 중에는 최악의 경우에 대한 시간 복잡도는 크지만 통계적인 실제 성능은 상당히 빠른 경우가 빈번합니다. 

    <입력 값의 범위에 따라 다른 함수 대소 관계>

    가지치기

     가지치기란, 불필요한 반복이나 함수의 호출을 도중에 빠져나오거나 차단하는 테크닉을 말합니다. 함수나 반복문을 수행하는 도중에 더 이상 수행할 가치가 없다고 판단되는 연산들을 생략하면 성능상으로 큰 이득을 얻을 수 있습니다. 물론 이 테크닉을 적용하기 위해서는 자신의 알고리즘에 대해 명확히 이해를 하고 있어야 하며, 이 부분에서 연산들을 생략해도 정답을 구하는 데에 전혀 지장이 없다는 확신이 있어야 합니다. 생략한 연산으로 인해 실제 얻을 수 있는 출력 값이 달라진다면 이는 잘못 된 가지치기의 사례라고 할 수 있습니다. 가지치기는 시간 복잡도 자체를 간소화할 수도 있고, 그렇지 않더라도 실제 연산량을 몇 분의 일로 줄이는 등의 효과를 낼 수 있습니다. 아래의 예시 상황을 떠올려 두 방법을 비교해 봅시다.

    "한 학교의 학생 N명이 키에 대해서 오름차순으로 서 있다. 이 중 생일이 12월인 학생 중에 가장 키가 큰 학생을 찾으려고 한다. 최대 몇 명을 검사해야 할까?"


    1.  우리는 앞에서 반복문을 이용해 조건하에서 최대 값을 찾는 연습을 했습니다. 그렇기에 앞에서부터 한 명씩 확인해 나가며 생일이 12월인 학생 중 키가 가장 컸던 학생을 기억하고 있으면 반복문이 종료된 후에 그 정보를 확정할 수 있다는 사실을 떠올릴 수 있습니다. 시간 복잡도로 표현하면 O(N)이라고 할 수 있습니다. 
    2. 반대의 방향으로 찾아봅시다. 키가 큰 학생부터 차례로 조사를 해 나가다가 생일이 12월인 학생이 발견되면 그 학생이 정답이 됩니다. 그렇기에 더 키가 작은 학생은 더 이상 조사해 볼 가치가 없습니다. 물론, 최악의 경우 생일이 12월인 학생이 키가 제일 작은 학생 단 1명인 경우 모든 학생을 조사해야 하기에 시간 복잡도는 O(N)입니다.


     위의 두 방식 모두 실제로 정답을 찾을 수 있으며, 같은 시간 복잡도를 가집니다. 하지만 완전히 랜덤한 테스트 케이스에 대하여 무수히 많이 테스트를 해 보았을 때, 평균적인 소요 시간은 엄청나게 차이가 날 것입니다. 가지치기는 함수나 반복문 안에서 조건문과 return, continue, break등의 명령어를 조합해 구현할 수 있습니다. 어느 정도 코딩이 익숙해지고 자신의 로직에 대한 확신이 생기면 가지치기는 숨 쉬듯 자연스럽게 적용될 수 있습니다. 그 전 까지는 다양한 사례를 통해 경험적으로 공부하는 것이 좋습니다. 하지만 과도한 가지치기는 많은 if문으로 인해 코드의 가독성을 상당히 해칠 수 있기에 주의합시다. 

     가지치기는 알고리즘과 문제의 조건마다 달라지기 때문에 일반적인 적용 방법을 설명할 수는 없습니다. 강의에서는 다양한 사례를 통해 가지치기를 할 수 있는 방법을 소개합니다.

    더 중요한 것은 좋은 알고리즘

     분명 가지치기는 연산량을 줄일 수 있는 좋은 방법 중 하나입니다. 하지만 가지치기를 하여도 최악의 경우 결국 시간 복잡도와 비슷한 수의 연산을 행하게 될 수 있습니다. 가장 근본적으로는 알고리즘 자체를 개선하는 것을 우선해야 합니다. 즉, 가지치기는 자신의 알고리즘을 개선하는 데에 사용될 수 있을 뿐 더 좋은 알고리즘으로 대체하는 것이 아닙니다. 자신의 알고리즘이 제 시간 내에 수행될 수 없을 것 같다면, 근본적으로 낮은 복잡도를 가지는 알고리즘을 설계할 수 있는지 고민해야 합니다. 그러기 위해서 가장 우선되어야 하는 것은 바로 자신의 알고리즘이 제 시간내에 동작할 수 있는지 없는지 판단하는 것입니다. 뒤의 문제들을 함께 풀어보면서 어떠한 과정으로 풀이를 고쳐나갈 수 있는지 경험해봅시다.

    Q & A
    Q&A forum that anyone can ask and answer.
    Share your questions and answers with other students and grow together!

    Registered Questions(0)