[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까지의 수를 ..
2021. 8. 21.
[Algorithm] 29. 3의 개수는?(small)
인트로 1부터 N까지 숫자에서 3이 몇 개 있는지 구하는 문제이다. N의 범위가 작은 만큼 시간제한이 없는 문제이다. 시간제한이 없다면 코딩 기초 문제에 포함되는 문제이지만 시간제한이 있다면 난이도가 엄청나게 올라가니 본 문제를 풀어보고 시간제한이 있다면 어떤 방식으로 풀어야 할지 고민해보자 나중에 시간이 된다면 시간제한이 버전을 포스팅하려 한다. (링크 추가 예정) 3의 개수는? (시간제한 없음) 문제 자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다. 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다. 자연수 N이 입력..
2021. 8. 12.