정글 알고리즘

백준 2751번 수 정렬하기 2 실버5

• 문제
• 코드
• 빨리 입력받는 방식으로 바꿨더니 통과

공부한 것

• python의 sort는 Timsort를 이용한다.
  • java의 object sort랑 같다
  • 시간복잡도 평균 O(nlogn), 최악의 경우 O(n)
  • https://stackoverflow.com/questions/25813774/complexity-of-python-sort-method

백준 2751번 수 정렬하기3 브론즈5

• 문제
• 코드
• 메모리 초과 발생
  • n입력 최대 10,000,000
    • int 배열 -> 4 * 100,000,000 = 40,000,000 byte == 약 40MB인데.. 문제에 파이썬 메모리는 더 적다고 나오나?

풀이

• 풀이 찾아보니 계수정렬을 이용할 수 있다
• 이 문제 같이 주어지는 수의 범위가 1부터 10,000까지로 제한되어 있기 때문에 이에 대한 배열을 작성하면 입력값 전체에 대한 배열을 만드는 것보다(약 40MB) 적게 만들 수 있다.

백준 1181번 단어 정렬 실버5

• 문제
• 코드

백준 2557번 일곱 난쟁이 브론즈2

• 문제
• 코드

백준 2557번 블랙잭 브론즈2

• 문제
• 코드

백준 10819번 차이를 최대로 실버2

• 문제
• 코드
• 순열을 직접 구현 하는 것 보다 permutations 임포트 해서 썼을 때가 좀 더 빠르다

백준 10971번 외판원 순회 2 실버2

• 문제
• 코드

푼 것 배운 것

• cost > ans 일 때 return 해줬더니 시간 줄었다