Developer Chaed

이번 2017 하반기 카카오 공채 코딩시험에서 나왔던 문제를 다시 정규표현식을 이용해 풀어보려합니다. 당시엔 정규표현식을 몰랐기에 문자열 처리에 애를 먹었는데 정말 간단해지네요. http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 문제 설명과 해설은 위의 링크를 참고하세요. 1S2D*3T 를 문제에 맞게 분리하는게 관겁입니다. 문제에 따르면 위의 문자열은 1S , 2D*, 3T로 분리되어야 합니다. 언뜻 그냥 하드코딩으로 해도 금방할것같지만 문자열 처리가 생각보다 예외처리를 한다던지 조건이 많다보니 쉽지많은 않습니다. 정규표현식을 C++에서 이용하기 위해선 http://www.cplusplus.com/reference/regex/regex..

https://ko.wikipedia.org/wiki/%EC%A0%95%EA%B7%9C_%ED%91%9C%ED%98%84%EC%8B%9D 프로그래밍을 하며 문자열 처리를 할 때 정규표현식을 쓰면 간단히 해결 되는 경우가 있습니다. 여지껏 정규표현식 공부를 미뤄두었다가 이제서야 공부하게 되네요. 우선 연습이 필요할텐데 이를 위한 사이트가 있음을 알게 되었습니다. https://regexr.com/ 또 c++11부턴 정규표현식을 위한 라이브러를 지원합니다. http://www.cplusplus.com/reference/regex/ 이를 잘 활용하면 문자열 처리를 좀 더 손쉽게 할 수 있을것입니다. --------------------------------------------------------------..

문제 링크 문제를 이해하는데는 어렵지 않으나 푸는데 약간의 지장이 있었습니다. 그래도 round1 치곤 쉬운문제 아닐까 싶었지만 larget-set은 처음에 풀지 못하였습니다. 다행히도 조건 하나를 추가해서 해결할 수 있었습니다. 문제에서 INPUT으로 주어지는 문자열을 잘 조합하여 오름차순의 숫자를 완성하는겁니다. OZONETOWER라면 ZERO ONE TWO가 되겠고 이를 다시 012로 출력하면 완성입니다. small-set을 풀때는 그래프와 동적계획법을 이용하여 풀었으나 large-set은 실패하였습니다. 후의 방법으로 해결하고 나니 닭잡는데 소잡는 칼을 쓴 겪이였습니다. 역시 해결방법은 의외로 간단하고 짧게 나오는 법인가 봅니다. main은 읽는게 전부입니다. 다만 선처리로 문자열의 각 영문자가 ..

이어서 올리는 코드잼 기출문제 입니다. 역시 해석하는데 시간 좀 걸렸습니다. 해석하고 나면 별게 아닌데 영어가 허접하니 뭐 놓치는게 없나 꼼꼼이 읽다보면 시간을 많이 필요로 하네요.. 여하튼 문제에 따라 주어진 팬케이크들의 상태를 모두 happy-side로 바꾸는겁니다 즉 +로 말입니다. ----++가 있으면 ++++++ 이렇게요 문제의 조건에 따르면 한번 팬케이크를 뒤집을 땐 순서가 뒤 바뀝니다. 다음과 같이 말이죠 if we number the pancakes 1, 2, ..., N from top to bottom, you choose the top ipancakes to flip. Then, after the flip, the stack is i, i-1, ..., 2, 1, i+1, i+2, ...

얼마전에 있던 구글 코드잼 Qualification Round 통과를 위해 연습문제를 몇개 풀었습니다. 이 문제는 2016년도 기출문제네요. 문제는 어렵지 않습니다. 단지 large data-set을 풀어 내야한다는것만 주의하면 되겠습니다. 영어로 문제가 나오다보니 해석하는데 애를 먹을 수 있습니다. 또 정확하게 해석해야지 잘못하면 조바심에 조건들을 놓쳐 문제를 잘 못 풀어낼수도 있습니다. "문제 링크" 문제에 따르면 주어지는 각 case의 input값을 1,2,3.... 을 곱해서 각 곱하여 나온 결과 값들이 결국에 0~9 자릿값이 모두 나오냐는 문제입니다. 만약 한없이 곱했지만 결국 7이라는 숫자가 나오지 않는다면 INSOMNIA를 출력해야 합니다. 두 가지만 유의해서 풀면 되겠습니다. 1. 언제까지..

자료구조 트립입니다. 저에겐 처음들어보는 자료구조였습니다. 하지만 개념자체는 이해하기 어려운 자료구조는 아니였으며 그 구현의 이해를 이해하는데 조금 시간이 걸렸을 뿐입니다. 제목처럼 트립은 힙과 트리의 결합형입니다. 다시말해 우선순위 힙과 이진트리 탐색의 장점을 합쳐놓은 것으로 주요목적은 트리가 한쪽으로 치우지지 않고 되도록 고르게 노드가 잡혀서 탐색, 삽입, 삭제등의 작업을 O(logN)에 마칠 수 있도록 하는것입니다. 이진트리의 탐색은 구현도 복잡하지만 자칫 잘못하면 운이 나빠 트리가 선형구조로 되어서 O(N)이 될 수도 있기 때문입니다. 또 힙의 장점으로써 하위노드들은 부모노드 보다 우선순위가 낮음을 이용합니다. 우선 트립을 구현한 헤더파일입니다. 보다시피 이진트리나 힙처럼 일반적인 구조를 갖고 있..

https://algospot.com/judge/problem/read/TRAVERSAL 트리에 대한 기초적인 개념이 있는 상태에서 문제를 풀 수 있습니다. 혹시나 트리가 무엇인지 모르시면 트리의 개념과 그 용어들을 살피고 오세요. 문제상에서 전위, 중위 순서의 순서가 먼저 주어지고 이를 통해 후위 탐색의 순서를 출력하는 문제입니다. 탐색의 순서는 재귀적으로 해결할 수 있습니다. 하지만 트리가 주어지지 않은 상태에서는 어떻게 접근해야 할까요. 가령 27, 16, 54가 있다면 중위순회는 왼쪽-루트-오른쪽의 순서로 순회합니다. 즉, 루트가 어디에 있냐만 차이가 생기죠. 결국 어떤 트리의 전위순회 순서가 다음과 같이 주어진다면, [A],[B],[C] 루트는 A입니다. 이를 토대로 중위 순회순서는 [B],[A..

문제는 아래 링크를 참고하세요 https://algospot.com/judge/problem/read/JAEHASAFE 문제를 최초에 잘못이해해서 거의 두시간은 낭비한것 같습니다. 돌리는 방향의 순서가 정해져있는데 혼자서 왼쪽 오른쪽 모든경우의 수를 생각하며 동적계획법까지 고려해서 짯는데 아니더군요 ㅜㅜ 문제를 잘 푸는데 한가지 방법은 문제를 정확하게 이해하는것도 중요함을 다시금.... 이번 글의 알고리즘은 효율적인 알고리즘이 되지 못합니다. 더 좋은 방법이 존재하는데 이는 다음 글을 확인하세요 문제에 따라 주어진 순서대로의 금고 상태를 왼쪽 오른쪽으로 순서있게 돌리며 최소 몇번만에 마지막 상태에 도달 할 수 있는지에 대한 문제입니다. 별거 아닌것 같지만 문자열을 비교해야 한단것 자체가 알고리즘 상에선 ..

https://algospot.com/judge/problem/read/PALINDROMIZE 문제설명은 알고스팟에서 참고하세요. 팰린드롬 문제를 풀기 위해는 먼저 직전의 알고리즘 게시물인 http://puppyrush.tistory.com/26 을 이해할 필요가 있습니다. 물론 다른 방법들도 존재하겠지만요. 팰린드롬을 만들기전에 조건인 제일 짧은 팰린드롬을 만들어야 한다에 주안점을 두어야겠습니다. 가령 anon이라는 문자열로 팰린드롬을 만들려 한다면 anon을 뒤집어 연결시킨 anonona도 팰린드롬이 됩니다. 하지만 제일 짧은 팰린드롬은 anona입니다. a하나만 붙은것이죠. 어떻게 하면 짧은 팰린드롬을 만들어낼 수 있을까요 해법중 하나로 원본 문자열을 뒤집어 kmp알고리즘으로 해결하듯이 접근하는것입..

드디어 KMP 알고리즘이 이해가 되어 글로 쓸 수 있게됐습니다. 아는거에 그치지 않고 누군가에게 설명할 수 있게 된다면 스스로 진정 이해할 수 있다고 할 수 있겠죠. 남에게 도움이 되는건 덤이구요. KMP알고리즘은 문자열 탐색에 있어서 효율적인 방법이 됩니다. c의 strstr , cpp의 string::find , java String.find은 기본적으로 선형시간이 걸리는것으로 알려져 있습니다. cplusplus의 string::find 함수 복잡도는 다음과 같이 설명되어 있군요. ComplexityUnspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case). 즉,..