Partially Committed

오늘 풀어볼 문제 상황은 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]..

배열이 주어지고, 배열 내에서 특정 조건을 만족하는 원소 쌍을 검색하는 문제 상황을 해결하는 방법에 대하여 공부해보자. 가령, 이런 상황이다. 유한 길이의 1 - d array 가 주어졌을 때, 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍을 찾아라. 어떠한 조합으로도 targetNum 을 만들 수 없다면 empty vector 을 반환하라. 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍은 유일하다. 면접에서 이 문제를 물어봤다고 가정하고, 차근차근 논리를 전개해보자. 먼저, 역으로 물어봐야 할 것은 어느 정도의 시간과 메모리를 허용하는지, 당연한 소리겠지만 원소의 타입은 integer 인지 그리고 2개의 원소에 대해서 조건을 만족하면 되는지, 반환해야하는 vector 내의 원소..