Partially Committed

오늘 다뤄볼 상황은 문자열이 주어졌을 때, Palindrome 인지 아닌지 Check 하는 것이다. Palindrome 이란 String 을 거꾸로 뒤집었을 때 원본이랑 동일한 것을 의미한다. 예를 들어 abcdcba 는 reverse 해도 abcdcba 이므로 Palindrome 이다. 어떻게 알고리즘을 구성할 수 있을까? 가장 먼저 떠올릴 수 있는 풀이는 실제로 문자열을 뒤집은 다음 원래 문자열과 비교해서 같은지 아닌지를 판단하는 것이다. 아래와 같이 코드를 작성할 수 있다. using namespace std; // time : O(N) // space : O(N) bool isPalindrome(string str) { // Write your code here. string reverse = "..

오늘 다룰 주제는 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..