프로그래머스 연속된 부분 수열의 합 문제 바로가기 Bruteforce Simple is best라는 생각에 바로 bruteforce로 풀어보았다. 결과는… 시간초과 시간 복잡도가 $ O(n^{2}) $ 이기에 n이 조금만 커져도 기하급수적으로 증가한다. #include <string> #include <vector> #include <numeric> using namespace std; vector<int> solution(vector<int> sequence, int k) { vector<int> setting(k, 1); vector<int> answer; for (int start=0; start<sequence.size(); start++){ vector<int> temp; int i=start; while (reduce(temp.begin(), temp.end()) < k){ temp.push_back(sequence[i]); if (reduce(temp.begin(), temp.end()) == k){ if (setting.size() > temp.size()){ setting = temp; answer = {start, i}; } } i++; } } return answer; } 테스트 1~5 통과 테스트 6 이후 → 시간 초과 Two Pointer 어떻게하면 불필요한 연산을 줄일 수 있을까 고민했다. 사실 스스로 그 답을 찾아내진 못했고, Two Pointer이라는 힌트를 얻었다. Two Pointer는 starting 위치에 따라서 연산을 새로 시작하지 않고 기존의 계산 결과를 활용한다. 따라서 bruteforce에 비해서 현격히 적은 시간을 소요로 한다. 시간 복잡도: $ O(n) $ ...

SF, 즉 Science Fiction의 범위는 어디까지일까? 천 개의 파랑을 읽으면서 SF 소설의 특성에 대해 생각해보았다. 대부분의 SF는 100년 후와 같이 먼 미래를 상정하거나, 현실에서는 불가능한 기술을 가진 평행우주의 내용을 다루는 느낌이 강하다. 그러나 이 책의 경우 30년 정도의 가까운 미래의 내용을 담고 있는데, 우리가 살아가는 삶과 비슷해서 오히려 독특하게 느껴졌다. 소설 속 인물들이 마치 이웃집에서 살고 있을 것 같은 기분이 들었기 때문이다. 소재를 잠시 제쳐두면 대부분의 줄거리는 사람간의 애정과 사랑을 깨닫게 해주는 힐링소설의 틀을 갖고 있다. 서로에 대한 마음을 겉으로 표현하지 않는 삭막한 인간관계에서 온기는 가지지 않지만 따뜻한 정신을 가진 안드로이드 로봇이 그들을 맺어준다. 촉각을 지니지 못해 체온과 공기도 느낄 수 없지만 깊은 마음을 가진 콜리를 보다보면, 우리의 모습을 반성하게 된다. 인간은 표현하지 않으면 서로의 마음을 알 수 없는데 고마움과 미안함을 전달하지 못하는 우리가 더 로봇에 가까운 것 같기도 하다. (어랏 이런 말은 ‘콜리’에게 실례려나…?) ...

백준 1759번 문제 바로가기 문제에 대한 첫 인상 단순히 모든 조합을 구하라고 했으면 실버 문제에 해당하겠지만, 자음/모음 갯수를 고려해주는 것이 은근 까다로워서 골드 등급을 부여해준 듯 하다. 문제를 읽고 나서 두 가지 방법이 생각났다. 1) permutation 라이브러리를 사용한다. 2) DFS로 풀어낸다. 두 경우 모두 모든 경우를 커버해야하기 때문에 결국엔 bruteforce로 풀어내야 한다. 라이브러리의 사용법을 이미 알고 있어서 간단히 이용할 수 있는 permutation 라이브러리를 이용했다. Python 풀이 import itertools # input l,c=map(int, input().split()) chars=list(map(str, input().split())) # examples words=itertools.combinations(sorted(chars), l) # 조건 확인 def check(word): vowels = ['a','e','i','o','u'] n = 0 # 모음 갯수 m = 0 # 자음 갯수 for w in word: if w in vowels: n += 1 else: m += 1 return (n, m) answer = [] for word in words: nm = check(word) if nm[0]>=1 and nm[1]>=2: answer.append(''.join(word)) # output for ans in sorted(answer): print(ans) C++ 풀이 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // input int l, c; cin >> l >> c; vector<string> chars(c); for (int i=0; i<c; i++){ cin >> chars[i]; } sort(chars.begin(), chars.end()); vector<string> answer; // permutation vector<bool> vec(chars.size()-l, false); vec.insert(vec.end(), l, true); string vowels = "aeiou"; do { string temp = ""; int n=0, m=0; // n 모음갯수, m 자음갯수 for (int i=0; i<chars.size(); i++){ if (vec[i]){ temp += chars[i]; if (vowels.find(chars[i]) != string::npos){ n++; } else{ m++; } } } if (n>=1 && m>=2){ answer.push_back(temp); } } while (next_permutation(vec.begin(), vec.end())); // output sort(answer.begin(), answer.end()); for (string ans: answer){ cout << ans << endl; } return 0; } 풀어내고 보니까 Python이 확실히 코드가 깔끔하긴 하다. 그렇지만 메모리 사용량과 시간을 보면 C++의 압승 ...

책의 부피가 너무 많이 불어나서 한동안은 이북 구독 서비스를 활용하기로 마음먹었다. 마이너한 작품들의 경우는 epub 형태로 구할 수 없어서 종이책을 구해야하지만, 웬만한 베스트셀러나 유명한 작가의 작품들은 많이 구비되어 있어서 편하게 볼 수 있었다. 지금까지 yes24의 크레마와 kindle, 밀리의 서재를 사용해보았는데, 국내 책 한정해서는 밀리가 책이 다양하고 편리하게 느껴졌다. 이북 리더기를 주문해놓은게 있는데 도착하기만을 기다리고 있다. 사설이 길었다! 김초엽 작가님의 수브다니의 여름휴가는 최근에 공개된 작품인데, 아직 종이책으로는 정칙 출간되지 않아서 밀리의 서재 앱으로만 읽을 수 있었다. 비교적 짧은 분량의 소설이라 한시간반 정도면 다 읽어낼 수 있었다. 쉽게 읽히는 내용에 비해서 마음 속에서 느껴지는 점들을 구체화하기는 정말 어려운 책이었다. 인체개조를 주제로 한 SF소설이었는데, 다른 작품과 다르게 편지를 쓰는 형식을 차용해서 더욱 쉽게 읽어낼 수 있었다. 주인공은 갑자기 말도 없이 멀리 떠나는데 뒷정리를 부탁한 언니에게 편지를 통해 자초지종을 설명한다. ...

백준 5525번 문제 바로가기 서브테스크가 있는 String 탐색 문제. substr()을 이용한 해법 문자열 비교는 substr()을 사용하는 편이 가장 깔끔하게 해결할 수 있다. indexing에 비해서 직관적으로 코드를 작성할 수 있어 가독성이 높아진다. 다만 해당 string을 긁어와야하기 때문에 길이가 길어지면 그만큼 시간 소요가 많다는 단점이 있다. #include <iostream> using namespace std; int main() { int N, M; string S; cin >> N >> M >> S; // create Pn string Pn; for (int i=0; i<N; i++){ Pn += "IO"; } Pn += "I"; // check Pn int count=0; for (int i=0; i<M-2*N+1; i++){ if (S.substr(i,2*N+1) == Pn){ count++; } } cout << count; return 0; } 문자열을 그대로 사용하지 않고 count하는 해법 N과 M의 범위가 1,000,000까지 늘어나면 substr로는 시간 내에 해결이 불가해서 다른 방법들을 찾아 헤맸다. String을 한번만 긁고 더 이상 탐색하지 않는 방식을 고민했는데, 솔직히 다른 분들의 풀이를 참고해서 아이디어를 얻었다.ㅎㅎ ...