알고리즘 문제 풀기

그리디 알고리즘

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

• 로컬 최적해(locally optimym solution)를 구할 수 있으나 글로벌 최적해는 보장하지 않음.

• 그리디 알고리즘 활용 대상 문제.

1. 탐욕선택 속성을 갖고 있는
2. 최적 부분 구조 문제.

• 그리디 알고리즘 vs 다이나믹 프로그래밍

코딩테스트

• 연습장과 필기도구 활용

  • 값의 변화나 최종 결과 기록하며 풀이.

• 모든 테스트 케이스를 통과하도록

  • 모든 테스트를 통과하는 로직을 짜자.

• IDE 과의존 주의.

  • IDE 없이도 개발 가능해야한다.

• 잘못 접근한 풀이에 대한 대처

• 최적화보다 문제해결능력이 중요.

알고리즘 성능 평가

• 복잡도
  • 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수. 연산의 횟수를 적게 한다면, 걸리는 시간을 줄일 수 있음. 중요!
  • 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양. 배열을 사용하지 않고 문제를 풀라는 뜻.
• 빅오(Big O) 표기법
  : 입력값이 무한대로 향할 때 함수의 상한을 설명하는 표기 방법.
  • 반복문 안에 반복문을 삽입하는 것은 지양하도록 하자.
• 시간 복잡도 계산
  N의 범위가 커질수록 시간복잡도를 줄여나가야 한다.

python

• 느리다
• 하지만 편하다
• 일부 기업 등에서 지원하지 않는다.

// > 소수점 아래는 다 버림.

• 리스트 자료형
  리스트는 대괄호 안에 원소를 넣어 초기화.

• 인덱싱
  리스트 출력에 -가 들어가면 뒤에서 연산함.

• 슬라이싱
  구간을 정해서 출력 가능. 2:5 과 같이 사용.
  

  • 주의! 리스트는 항상 0부터 시작. 또한 뒤의 숫자는 '숫자 전'까지만 포함.
    즉 [2:5]라면, 3번째 ~ 5번째가 되는 것.
    2 = 0번째 1번째 2번째 3번째
    5 = 0번째 1번째 2번째 3번째 4번째 5번째 6번째(이어야하는데 6번째 직전까지니까)

• 주석은 앞에 #달아주면 됨.

• 반복문. for i in range(a, b) a에서 b 전까지 출력.

• append()
  새로운 값 삽입.

• sort()
  리스트의 순서 정렬.

• sort(reverse = True)
  순서 오름차순으로 정렬.

• a.reverse()
  a 리스트 원소 뒤집기.

• a.insert(a,b) 시간복잡도를 높이므로 안 쓰는게 좋음
  원소 삽입

• a.count(x)
  값이 x인 데이터 개수

• a. remove(x)
  값이 x인 데이터 삭제

  • 특정 값 모두 제거하기
    remove_set = {3,5}
    result = [i for i in a if i not in remove_set]
    print(result)

• 문자열 자료형
  큰 따옴표와 작은 따옴표를 구분하지 않는다.

• 문자열 연산
  문자열 변수에 + 를 사용하면 연결됨.
  *를 사용하면 반복 가능
  인덱싱도 가능

  • print(a[2:4])

• 튜플 자료형.
  리스트랑 비슷하다. 공간 복잡도가 좀 덜하다.
  () 사용. 안에 있는 값을 수정할 수 없다.
  수정하지 않아도 되는, 혹은 수정되어선 안되는 값(key)을 튜플로 다룰 수 있다.

• 딕셔너리 자료형
  키와 값을 쌍으로 데이터로 가지는 자료형.
  

• 집합자료형
  중복 허용 안함. 순서가 없다.
  합집합 print(a | b)
  교집합 print(a & b)
  차집합 print(a - b)

• 표준입력방법
  
  input() 키보드로 값 입력 가능.
  split() 공백을 기준으로 입력.