|
|
Program Lang./Algorithm 2017. 10. 11. 16:19
1. 설명 그래프에 대해서 깊이 우선 순위 구현 및 차 후에 다시 보기 위해서 여기에 남김. 깊이 우선 순위 구현은 재귀호출 기반과 스택 자료 구조를 이용해서 각각 구현해 보았다. C++ STL 버전은 아직 올리지 않았지만 STL기반으로 구현하면 정말 깔끔하다.
2. 소스 코드 Gist에서 관리한다.
3. 실행결과
1. 현재 그래프 출력 2. 재귀호출에 의한 깊이 우선 탐색 3. 스택에 의한 깊이 우선 탐색 0. 종료 ======================================== >> 1
고속도로 망의 인접 리스트 정점 서울의 인접 리스트 -> 대전 -> 춘천 정점 대전의 인접 리스트 -> 서울 -> 대구 -> 전주 정점 춘천의 인접 리스트 -> 서울 -> 대구 정점 대구의 인접 리스트 -> 대전 -> 춘천 -> 부산 정점 전주의 인접 리스트 -> 대전 -> 광주 정점 부산의 인접 리스트 -> 대구 -> 광주 정점 광주의 인접 리스트 -> 전주 -> 부산 ======================================== 1. 현재 그래프 출력 2. 재귀호출에 의한 깊이 우선 탐색 3. 스택에 의한 깊이 우선 탐색 0. 종료 ======================================== >> 2
깊이 우선 탐색 결과 : 서울 대전 대구 춘천 부산 광주 전주 ======================================== 1. 현재 그래프 출력 2. 재귀호출에 의한 깊이 우선 탐색 3. 스택에 의한 깊이 우선 탐색 0. 종료 ======================================== >> 3
깊이 우선 탐색 결과 : 서울 대전 대구 춘천 부산 광주 전주 ======================================== 1. 현재 그래프 출력 2. 재귀호출에 의한 깊이 우선 탐색 3. 스택에 의한 깊이 우선 탐색 0. 종료 ======================================== >> 0
Program Lang./C++ 2017. 7. 9. 10:48
1. 목적
Object Generator 정의는 다음과 같다. 함수 탬플릿으로 클래스 탬플릿의 객체를 생성하는 기술. 정의만으로는 이 기술이 얼마나 멋진지 와 닿지 않는다. 아래 소스 코드를 이용해서 설명을 진행하도록 한다.
2. 소스코드 아래 코드의 예제는 make_tuple의 동작을 알아보기 위해서 make_tuple과 유사 동작을 하는 xmake_tuple을 만들어 보았다.
tuple을 print하는 help function은 일단 무시한다. 우리가 tuple 객체를 생성하는 방법은 아래와 같이 두가지 방식이 있다. 일반 클래스 객체를 선언하기 위한 방법과 동일하게 tuple template에 type 정보를 주고 각 type에 해당하는 argument를 주는 방식이다. 두 번째 방법은 tuple에서 제공하는 make_tuple() 함수를 이용해서 tuple 객체를 생성하는 것이다.
그럼 첫번째 방식과 두 번째 방식의 차이는 무엇인가? 여러가지 차이가 있지만 여기서는 Object Generator 관점에서 살펴본다.
두 번째 방식은 함수 템플릿은 암시적/명시적 객체 인스턴스화가 가능한 반면, 클래스 탬플릿은 명시적인 객체 인스턴스만 가능하다. C++17부터는 클래스 탬플릿도 암시적 객체 인스턴스화가 가능하지만, 이는 논외로 한다. make_tuple() 함수를 통해서 명시적 Type을 지정하지 않고 Argument로 전달된 객체의 타입으로 tuple의 객체 인스턴스화가 가능하다. 즉 함수 탬플릿의 암시적인 객체 생성 기법을 이용해서 클래스의 명시적 객체 생성이 가능한 것이다.
3. 결론
C++ 표준에는 함수 탬플릿의 암시적 객체 생성 기법을 통해서 클래스 탬플릿의 명시적 객체 생성을 할 수 있는 함수들을 많이 제공하고 있다. 이는 Object Generator 기법에 그 근간이 있다.
Program Lang./Algorithm 2017. 6. 18. 10:09
1. 소스 코드
문제해결을 위한 창의적 알고리즘(중급) 예제 문제, 복습 목적 하위 트리 전개는 사건을 기준으로 한다. 경찰차 위치가 하나의 처리된 사건으로 가정하고 다음 사건을 정의하는 부분을 주의 깊게 보자
Program Lang./Algorithm 2017. 5. 31. 14:09
1. 소스 코드
문제해결을 위한 창의적 알고리즘(중급), 100페이지 4문제로 미로가 주워지고 'S'에서 출발해서 'G'로 끝나점까지의 최단 거리를 찾는 문제이다. 기존에 두더지 문제를 잘 풀었다면 어렵지 않게 해결할 수 있다.
문제 해결은 깊이 우선 또는 너비 우선 순위로 해결할 수 있지만 너비 우선 순위로 풀어 보았다.
2. 실행 결과
find road : 6
# S # # #
# - - - #
# - # - #
# - - - -
# # # G #
최단 거리 : 6
Program Lang./Algorithm 2017. 5. 31. 14:01
1. 소스 코드 문제해결을 위한 창의적 알고리즘(중급), 77페이지 문제에 있는 문제로 두더지 굴이 몇 개 있으며, 각 두더지 굴의 깊이를 출력하는 문제이다.
2. 실행 결과
0 2 2 0 3 0 0
0 2 2 0 3 0 3
2 2 2 0 3 0 3
0 0 0 0 3 3 3
0 4 0 0 0 0 0
0 4 4 4 4 4 0
0 4 4 4 0 0 0
두더지 굴 개수 : 3
7 8 9
Program Lang./Algorithm 2017. 5. 31. 13:41
1. 목적
공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.
여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.
2. 코드 설명
너비 우선 탐색 기반은 비선형 탐색의 한 종류로 Queue 기반으로 Stack 기반의 깊이기반 탐색에서 10만번 이상을 수행 시에 Stack Overflow에 대한 제약 사항을 해결할 수 있는 하나의 방식이다.
3. 실행 결과 깊이 우선 순위 탐색과 달리 Path가 나눠져서 도달하지는 않는다.
end of map : min = 12
-1 -1 -1 -1 -1
0 0 0 0 -1
-1 -1 -1 -1 -1
-1 0 -1 0 0
-1 -1 -1 -1 -1
최단거리 : 12
Program Lang./Algorithm 2017. 5. 31. 10:06
1. 목적
공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.
여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.
2. 코드 설명
깊이 우선 탐색 기반은 Stack 기반이고, 기존에 방문한 Node에 대해서 원하는 답을 얻지 못할 경우 다시 현재 Node 전의 Node로 이동해야 하는데 이 때 현재 Node 탐색에 사용된 중간 결과는 모두 원래되로 돌려줘야 한다. Back Tracking 기반이라는 의미로 해석된다. 흔히 운영체제나 이런 곳에서 Stack 되감기 이런 말을 들을 수 있는데 이 문제에서 많은 영감을 얻을 수 있다.
3. 실행 결과 결론적으로 두 가지 Path로 종점에 도달하였고, 그 중 최소값을 선택하는 문제이다.
end of loop .. distance : 16
end of loop .. distance : 12
최단거리 : 12
Program Lang./C++ 2017. 5. 12. 14:38
1. 목적
이제 마무리 단계에 왔다. 바로 work의 사용법이다. work는 io_service start 전에 post()에 기술된 handler함수가 먼저 종료되는 상황에서 io_service start를 차 후에 호출하더라도 실제 post의 핸들러 함수는 돌지 않는다. 이를 방지 하기 위해서 항상 block되어 돌도록 하기 위해서 사용한다.
2. 코드 설명
아래 코드에서 현재 상태로 코드를 돌리면 아무 동작을 하지 않는다. 비동기 동작과 유사한 동작을 위해서 post에 전달하는 방식을 thread로 변경하였다. 이 부분이 앞의 예제와 변경된 사항이다.
3. 정리
주석 처리된 부분을 풀고 빌드해서 실행해 보면 정상적으로 동작한다. 이것으로 boost asio 기본 API 함수들의 동작에 대해서 알아보았다. 이제 Network이나 Timer의 동작을 좀 더 명확하게 이해할 수 있는 기반을 갖췄다고 개인적으로 생각이 듭니다.
Program Lang./C++ 2017. 5. 12. 12:27
1. 목적
boost asio 정리 -4는 정리 3에서 multi-thread에서 동일 handler로 처리될 경우 공유 자원에 대한 접근을 제어하기 위해서 lock대신 boost strand를 적용한 예제이다. strand는 handler 처리에 대해서 순차적인 처리를 보장해서 공유 자원 접근에 대한 제어를 lock 객체와 유사하게 해 준다.
2. 코드 설명
post()함수에 strand.wrap()함수로 handler를 한번 wrapping해 주면 strand 동작을 위해서 해 줄 일은 끝난다. 하지만 여기서 눈여겨 봐야할 부분이 strand1과 strand2 두 개의 객체를 선언하였는데 strand1로만 post함수를 wrapping했을 경우와 post 함수를 각각 strand의 wrap함수로 했을 때 동작은 다르다. 결론은 strand 하나의 객체로 wrapping해야지만 진정한 동기를 맞출 수 있다.
아래 코드는 start 함수의 strand wapping 하는 부분의 일 부분만 캡쳐한 것이고, 첫번째로 같은 strand 객체로 wrapping 했을 때 코드와 결과이다.
결과: 첫번째 post에 할당된 handler가 모두 완료되고, 두번째 handler가 순차적으로 돌고 있다.
아래 코드는 post 함수에 서로 다른 strand 변수를 사용했을 때의 코드 조각이다.
결과: 서로 경쟁적으로 돌고 있음을 알 수 있다. 실행 결과를 보기 좋게 하기 위해서 루프는 5번만 돌렸다.
3. 전체 코드
4. 정리
strand를 이용한 공유 자원 처리 방법까지 알아보았다. 이제 남은 것은 work에 대한 것이다. work의 동작을 비동기IO아닌 예제에서 알아보기에는 좀 어려운 점이 있지만 예제 차원에서 억어지로 다음절에서 알아본다.
Program Lang./C++ 2017. 5. 12. 12:00
1. 목적
boost asio 정리 -2는 io_service 처리를 single thread로 하였다. 여기서는 mulit-thread처리 방식에 대해서 알아본다. 하지만 내용은 매우 간단하다. io_service thread를 여러개 만들면 된다.
2. 코드 설명
기존의 코드와 형태가 좀 바꿨다. boost thread group를 통해서 io_service를 2개 생성함을 볼 수 있다. (boost::thread_group io_threads). 결론적으로 io_service에 대한 처리를 multi-thread로 처리하는 것이다. 또한 post() 함수를 통해서 2개의 handler함수를 추가함을 알 수 있다.
3. 실행결과
기존 정리 -2와 유사하지만 차이는 io_service를 multi-thread로 처리한 것이고, 출력 결과도 post에 정의된 handler가 하나 모두 완료하고 다른 것이 순차적으로 되는 것이 아니라 random하게 실행된다. 여기서는 loop가 작아서 자세히 보이지 않지만 loop를 늘리면 random하게 보일 것이다. thread Id에 주목해보면 서로 번갈아 가면서 동작하는 것을 알 수 있다.
4. 정리 이제 strand에 대한 이야기를 해야 할 시간이 온 것 같다. 위의 예제의 문제에 대해서 이미 파악했을 것이다. post()함수에 do_print()함수가 두 개 동일한 함수가 호출되어서 결론적으로 multi-thread의 처리가 동일 handler에서 처리되는 것으로 do_print()함수에 공유자원이 있다면 공유자원에 대한 mutual access가 필요해진다. stackoverflow에 lock 객체를 쓰는 것이 낫나 아니면 strand를 쓰는 것이 호율적이냐에 대해서 논의가 많다. 각자의 구현이 따라 잘 판단해서 처리해야 하는 것이 답으로 보인다. strand에 대한 필요성과 이 예제의 문제를 개선하기 위한 방법을 알아본다.
|
