알고리즘 기본 개념

 

 

1.  알고리즘과 자료구조

 

 

     자료구조는 효율적으로 데이터를 저장하는 구조이며, 알고리즘은 저장한 데이터로 문제를 효율적으로 푸는 방법을 의미한다.

     따라서 자료구조와 알고리즘의 특성을 파악해 해결해야할 문제에 따라 적절한 자료구조와 알고리즘을 선정해야 한다.

 

 

    1 )  자료 구조

 

          자료 구조 :  컴퓨터에서 데이터를 효율적으로 관리하고 구조화시키는 방법

         

          - 자료구조에서 중점적으로 봐야 할 특성

              * 데이터의 순서가 보장되는가

              * 중복 데이터가 저장되는가

              * 검색 효율성

              * 수정 효율성   

                      

          - 자료구조의 종류 

 

      

 

 

    2 )  알고리즘

 

           알고리즘 :  어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합 

 

            - 알고리즘에서 신경써야 할 부분

                 * 효율성 => 시간 복잡도, 공간 복잡도

                 * 정확도

           

                     

         

2.  알고리즘의 효율성 측정

 

      알고리즘의 효율성을 측정하는 척도는 시간복잡도와 공간복잡도가 있다.

      좋은 알고리즘이란 시간복잡도와 공간복잡도를 모두 충족시키는 알고리즘이다.

      하지만 시간과 공간은 반비례하는 경향이 있다. 

      따라서 데이터의 용량이 커지고 있는 추세에 따라 공간복잡도보다는 시간복잡도를 고려해야 한다.

 

 

      1 )  시간복잡도

             시간복잡도 : 문제를 해결하기 위한 연산 횟수

                 파이썬 프로그램에서는 1초에 2000만 번 ~ 1억 번의 연산을 수행한다.

             

             - 시간 복잡도 유형

                 * 빅-오메가 : 최선일 때의 연산 횟수

                 * 빅-세타 : 평균일 때의 연산 횟수

                 * 빅-오 : 최악일 때의 연산 횟수

                 코딩 테스트에서는 빅-오 표기법을 기준으로 생각하는 것이 좋다.

 

            - 빅-오 표기법

 

                * 시간복잡도 계산 주의점

                  상수는 시간복잡도 계산에서 제외

                  가장 많이 중첩된 반복문의 수행 횟수를 기준으로

 

 

    2 )  공간복잡도

           공간복잡도 : 프로그램을 실행 및 완료하는 데에 필요한 저장공간의 양           

            - 공간복잡도 계산 

                 총 저장 공간  =  고정 공간  +  가변 공간

                 * 가변 공간에 따라 공간복잡도를 판별한다

 

 

                             

3.  알고리즘의 정확도

 

      알고리즘의 정확도는 디버깅을 통해서 판별한다.

      디버깅을 통해 알고리즘의 논리 오류를 확인하고 수정한다.

       

      - 파이썬 알고리즘에서 자주 나오는 오류

        * 변수 초기화 오류

        * 인덱스 범위 지정 오류

        * 잘못된 변수 사용 오류

        * 파이썬 자동 형 변환 오류

 

 

 

 

알고리즘 열심히 공부해야징...

 

+) 2023.03.04

visual studio code에서 디버깅 시도