[Algorithm] 38. 반전 수열(Inversion Sequence)

인트로 수열을 응용한 문제이다. 반전 수열(Inversion Sequence) 문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 [4, 8, 6, 2, 5, 1, 3, 7] 1 앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2 앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3 앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 21.
• textsms

[Algorithm] 삽입 정렬(Insertion Sort) 코드와 시간 복잡도 (+ 예제)

인트로 기초 정렬 알고리즘 마지막 파트인 삽입 정렬(Insertion Sort)을 알아보자. 재밌게도 삽입 정렬은 데이터의 배치에 따라 O(N) 시간 복잡도를 가진다. 개인적인 생각으로 버블 정렬의 한 단계 진화한 모습이 삽입 정렬이 아닐까 한다. 삽입 정렬과 관련된 문제는 해당 포스팅을 참고하세요 :) [Algorithm] level0 : LRU(Least Recently Used) [Algorithm] level0 : LRU(Least Recently Used) 인트로 LRU 페이지 교체 알고리즘을 간단하게 구현하는 문제이다. 문제에서도 설명하겠지만 LRU란 가장 오랜시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체정책중 하나이다. 문 kangworld.tistory.com 삽입 정렬(In..

• format_list_bulleted Algorithm/정렬
• · 2021. 8. 20.
• textsms