Partially Committed

오늘 다룰 주제는 Non-Constructible Value(Change) 이다. positive integer 로 구성된 array 가 주어졌을 때, 각각의 원소들의 합으로 나타낼 수 없는 최소의 값을 Non-Constructible Value 라고 정의한다. 예를 들어, coins 배열이 [1, 2, 5] 로 주어졌을 때 각각의 원소들로 만들어낼 수 있는 값은 1, 2, 3, 5 이므로 Non-Constructible Value 는 4 이다. 가장 먼저 떠올릴 수 있는 방법은 주어진대로 꾸덕꾸덕 구현하는 것이다. 주어진 배열을 ascending order 으로 sorting 한 다음에 모든 원소들의 합을 구한다. 그러면 Non-Constructive Value 는 1~max_sum+1 중 하나일 것이..

오늘 풀어볼 문제 상황은 Tournament Winner 이다. Problem solving 실력을 겨루는 Tournament Winner 는 아래의 규칙을 따른다. 각각의 team 은 서로 다른 언어(C#, Python ...)를 사용한다. 경기 방식은 round-robin 리그제이며 각 경기 당 home team, away team 이 지정된다. 대진표는 competitions 2차원 배열에 제시되며 경기 결과는 results 배열로 주어진다. competitions = [ ["HTML", "C#"], ["C#", "Python"], ["Python", "HTML"], ] results = [0, 0, 1] 위와 같이 주어졌을 때, 각각의 대진표의 앞의 팀은 home, 뒤에 팀은 away 이다. 그리..

오늘은 보다 간단한 문제에 대해서 알아보자. Ascending order 로 정렬된 input array 가 주어졌을 때, Sorted Sqaured output array 를 반환하라는 문제 상황이다. 예를 들어 [1,2,3,4,5] 가 주어지면 [1,4,9,16,25] 를 반환한다. 가장 쉽게 떠오르는 것은 그냥 input array 를 순회하며 squared value 를 원소로 가지는 배열을 만든 다음 sorting 해서 반환해주는 방법이다. 이렇게 구현한 경우에는 시간 복잡도는 O(NlogN) 이고 공간 복잡도는 O(N) 이다. #include using namespace std; // time : O(NlogN) // space : O(N) vector sortedSquaredArray(vec..

오늘은 보다 간단한 상황에 대해서 공부해보자. 바로 Subsequence 판단 문제인데, Subsequence 의 정의는 아래와 같다. In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. - wiki 배열이 주어졌다고 가정하면, 원소의 순서를 바꾸는 행위 없이 일부 원소만 delete 하여 origin array 로부터 subsequence 을 만들어낼 수 있다. 예를 들어 [1,5,7,9] 에 대해서 [1, 5]..