<aside> 💡

APS(Algorithm Problem Solving) 기본 학습

• 기초 자료 구조 이해 중심

  • 입출력을 제외한 내장함수 사용하지 않음
  • 기본적인 내장함수의 동작원리 이해해야 함

• AI 활용 방법

  • 교과서가 아닌 학습에 도움 받는 용도로만 사용함
  • 문제 전체 넘기고 코드 요구하는 행위 금지임
  • 대화 통해 문제점 찾도록 작은 단위로 질문하는 게 좋음

• Tip

  • 다른 사람이 작성한 코드 많이 읽어보는 거 중요함
  • 코드는 눈으로만 보는 게 아니라 직접 따라 입력해야 함
  • 코드가 외워질 정도로 반복해야 이해 잘 됨 </aside>

• 컴퓨터 분야에서 알고리즘을 표현하는 방법

  1. Pseudocode(슈도코드, 의사코드)
  2. 순서도

  

• 좋은 알고리즘이란?

  

  1차 목표는 정확성

• 시간 복잡도

  • 알고리즘의 작업량을 표현

  • 실제 걸리는 시간을 측정

  • 실행되는 명령문의 개수를 계산

  • 빅-오 표기법을 언급하는 경우가 많음

    • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
    • 계수는 생략하여 표시

    

배열 (Array)

: 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

• 배열의 필요성
  • 프로그램 내에서 여러 개 변수 필요할 때 배열 유용함
  • 각각 다른 변수명으로 자료 접근하는 건 비효율적일 수 있음
  • 배열 쓰면 한 번의 선언으로 여러 변수 선언 가능함
  • 단순히 변수 여러 개 선언하는 개념은 아님
  • 변수 여러 개로 하기 어려운 작업도 배열로 쉽게 처리 가능함

1) 1차원 배열

• 선언 예시

  arr = list()  
  arr = []  
  arr = [0] * 10  
  arr = [1, 2, 3]
  

• 알고리즘 유형

  • 배열 원소의 합 계산하기
  • 배열 원소 중 최댓값 max_v 찾기
  • 배열 원소 중 최댓값의 인덱스 max_idx 찾기
  • 최댓값이 여러 개인 경우 마지막 인덱스 max_idx 찾기
  • 찾는 값이 배열이 있으면 해당 원소의 인덱스, 없으면 -1을 idx에 넣기

정렬

: 2개 이상의 자료를 키(특정 기준)에 의해 작은 값부터 큰 값(오름차순), 혹은 그 반대의 순서대로(내림차순) 재배열하는 알고리즘

완전 검색

<aside> 💡

[Baby-gin game]

</aside>

• 완전 검색
  • 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
  • brute-force 혹은 generate-and-test 기법이라고도 불림
  • 모든 경우의 수를 테스트 한 후, 최종 해법을 도출하는 방법으로 일반적으로 경우의 수가 상대적으로 작을 때 유용함
• 완전 검색의 필요성
  • 완전 검색으로 시작함
    • 모든 경우의 수를 생성하고 테스트하기 때문에 느림. 대신 해답 못 찾을 확률은 적음
    • 자격검정평가 등에서 문제 나오면, 일단 완전 검색으로 해답부터 찾고 시작함. 이후 성능 개선 위해 다른 알고리즘 써서 비교함
• 완전 검색을 활용한 baby-gin 접근
  • 고려할 수 있는 모든 경우의 수 생성하기
    • 6개의 숫자로 만들 수 있는 모든 숫자 나열 (중복포함)
  • 해답 테스트하기
    • 앞의 3자리와 뒤의 3자리를 잘라, run와 triplet 여부를 테스트하고 최종적으로 baby-gin을 판단함
• 순열

  • 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

  • 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현

    nPr

  • 단순하게 순열을 생성하는 방법

    • {1, 2, 3} 을 포함하는 모든 순열을 생성하는 함수
    • 동일한 숫자가 포함되지 않았을 때, 각 자리 수 별로 loop를 이용해 아래와 같이 구현 가능

    for i1 in range(1, 4):
        for i2 in range(1, 4):
            if i2 != i1:
                for i3 in range(1, 4):
                    if i3 != i1 and i3 != i2:
                        print(i1, i2, i3)
    

탐욕 알고리즘 (Greedy)