분류 전체보기 (29) 썸네일형 리스트형 LWM2M 했던 것들 정리 현 회사에 들어와서 임베디드 어플리케이션을 이것저것 개발하였다. 그중에서 주로 하던 것이 수집한 데이터를 서버로 전송하는 기능을 개발하는 것이다. 그 방법에는 여러가지가 있는데, 서로 프로토콜을 만들어서 쓰는 경우가 종종 있는 방법이였고, 다른 하나는 LWM2M 프로토콜을 사용하는 방식이었다. 특히, Network Management System, 즉, 모뎀의 통신 상태나 데이터를 가져오는 기능을 만들때 이 LWM2M 을 자주 사용하였다. 솔직히 아직도 잘 안다고 말할수는 없지만, 내가 만든 어플리케이션 이곳저곳에서 많이 사용하였다. 그래서 이 LWM2M(Light Weight Mechine to Mechine)이 무엇이냐고 물어보면, CoAP 기반의 IoT 장치 리소스 관리 프로토콜이라고 간단하게 말할.. DP 문제. 어렵다 프로그래머스에서 가장 큰 정사각형 찾기 문제를 풀어보는데, 이건 좀 힘들었다. 처음 생각한 방식은 for문 두 개를 돌려서 1인 경우를 찾고, 만약 1이면 우측과 아래로 한칸씩 늘려가면서 정사각형이 맞나 확인하는 방식이였다. 근데 이렇게 하면 for문이 거의 3, 4개가 사용된다. 즉, 복잡도가 O(N3) 이 된다. 그래서 이번에는 힌트를 좀 참조했다. DP (Dynamic Programming) 을 사용하는게 가장 좋다고 한다. 와. DP 는 학부때도 잘 배운 기억이 잘 안난다. 찾아보니 DP, 동적계획법이란게 작은 문제를 모아서 큰 문제를 푸는 것이더라. 학부 때 피보나치 수열 푸는 방법을 교수님이 설명해줄때, 이야기 해주셨던 방법 중 하나였다. 하나는 재귀함수였고, 다른 함수는 이 동적계획법이였다... 모든 조합을 구하는 문제 (순열) 나온 문제는 숫자가 지정되면 가능한 모든 순열을 구하고, 소수의 개수를 구하라는 문제였다. 처음에는 직접 경우의 수를 다 구할려고 했는데, 코드도 엄청 길어지고, 복잡하더라. 거의 대부분의 수학적인 문제는 이미 라이브러리에 구현되있으니 찾으면 나올꺼라 생각했고, 역시나 나왔다. permutation 함수 자체가 이미 있었다. 그래서 나온 방법들은 대부분 비슷했다. do-while 문을 이용하여 다음 수열을 계속해서 만드는 것. 그런데 그냥 do-while문만 하면 총 길이와 같은 경우의 수만 나온다. {1, 2, 3, 4} 가 있으면 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4.. priority queue와 vector의 최소값 vector 에서 최소값과 그 다음 최소값을 빼내어 계산하여 넣고를 반복하는 문제가 나왔다. 처음에는 vector를 deque에 넣어서 sort로 정렬하여 문제를 풀었다. sort(deque.begin(), deque.end()); int less = deque.front(); deque.pop_front(); int less2 = deque.front(); deque.pop_front(); 이 방식을 사용하니 실행시간이 너무 느리게 나와서 효율성 검사에서 전부 실패했다. 찾아보니 C++ 의 sort 는 퀵정렬 기반이여서 O(NlogN)의 시간복잡도를 가진다고 한다. 그래서 좀 더 빠른 방법을 찾다가 priority queue를 찾았다. 사실 학부때에도 priority queue는 써본 기억이 거의 없다.. 괄호와 스택 문제중에 괄호 관련된 문제가 종종 나온다. 아마도 개발하다보면 괄호가 부족해서 오류가 나오는 경우가 종종 발생해서 그런가보다. 간단한 문제로는 괄호가 잘 닫혔는지 확인하는 문제가 나오고, 더 나아가서는 특정 패턴으로 불완전한 괄호를 완성시키는 문제가 나온다. 이런 괄호가 정상적으로 매칭되어있는지 확인할 때, 스택을 사용한다. 여는 괄호가 있으면 닫힌 괄호가 있을테니 각각의 괄호를 카운트해서 숫자가 같으면 맞다고 판단하는 방법을 쓰면 갯수는 맞지만, 괄호의 순서가 다른 경우에는 오답이 된다. 그래서 스택을 써서 괄호가 여는 괄호일때는 스택에 넣고, 닫힌 괄호일때는 여는 괄호를 빼내는 방법을 사용한다. bool complete(string u) { stack s; for(int i=0; i BFS 학부 때 이후로 오랜만에 BFS를 사용했다. 격자에서 영역을 구할 때 사용하였다. 이해한 대로 PPT를 이용하여 간단하게 그려보았다. 기본 원리는 주변을 살펴서 내 그룹이고, 방문 안했으면 queue에 넣고, 다 확인하면 queue에서 다음 것을 빼내어 똑같이 하는 것이다. 학부때는 이걸 재귀함수로 했던것 같은데, queue로 하는게 더 쉬운것 같다. queue에 pair를 사용했는데, 행렬을 각각 넣기 위해서 그랬다. for(int i=0; i 프로그래머스 연습 2주 후... 프로그래머스에서 코딩 연습을 한지 2주가 지났다. 이제 1단계는 넘어섰고, 2단계를 한 5문제 정도 풀었다. 2단계를 오니 슬슬 시간이 걸리기 시작한다. 1단계는 대체로 vector나 배열을 잘 사용하면 풀 수 있는 문제였다면 2단계부터는 슬슬 BFS도 나오고, 큐와 스택을 이용한 설계도 좀 더 치밀하게 해야 한다. pair 도 사용 빈도가 늘어나고 있다. 풀면서 느끼는 점은 지금까지 알고리즘 공부를 게을리 했다는 것이다. 그럼에도 잘도 회사에서 프로젝트 요구사항을 만들었네. 문제가 안풀린다고 조급해하지 말고 최대한 생각하면서 스스로 풀어보려고 한다. pair 와 sort 코딩 문제를 풀다가 나온 문제 중 하나를 어떻게 풀까 생각하다가 pair를 쓰게되었다. 문제가 게임에서 스테이지 별로 나오는 값을 정렬해서 출력해야하는 것이였는데, 값만 출력하면 이게 어떤 스테이지에서 나온 값인지 알 수가 없다. 그래서 pair를 이용하여 스테이지 번호와 값을 맵핑하여 저장하였다. pair 이런 식으로 앞에는 스테이지 번호, 뒤에는 값을 넣었다. vector v; 이것을 vector에 넣고, sort 함수를 이용하여 값에 따차 정렬한다. sort(v.begin(), v.end(), sortbysecond); 이때, 값을 보고 정렬하기 위하여 sortbysecond 라는 함수를 선언하였다. bool sortBySecond(pair a, pair b) { if(a.second > b.sec.. 이전 1 2 3 4 다음
