프로그래밍/알고리즘(6)
-
알고리즘 : Postfix Notation
1. PostFixNotation사람이 사용하는 중위 표기식 계산은 컴퓨터 계산으로 활용하기 힘들다.계산식의 우선순위를 논리적으로 판단하기 힘들기 때문이다.그로 인해 후위 표기 방법을 사용하며, 중위 표기식을 후위 표기로 변환하는 알고리즘들이 만들어진다. 그 중 하나인 다익스트라가 고안한 방법을 포스팅 합니다. 위에서 우선순위 판단이 힘들어 중위 표기를 후위 표기로 변환하여 계산한다고 했습니다.예로 확인하겠습니다. 계산식1 : 1+2+3+4 -> 우선 순위가 없으므로 계산에 문제 없음.계산식2 : 1+2*3+4 -> 곱하기 연산을 먼저 계산하여야 한다.계산식3 : 1+(2*3-(4-2)+3) -> 괄호부터 연산하여야 한다. ‘계산식 1’의 경우 우선 순위가 없으므로 순차적으로 계산함에 있어 아무런 문제도..
2014.05.20 -
알고리즘 : ConvexHull (Graham's Scan)
외곽선 찾기(ConvexHull) 알고리즘 1. 개요2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 나머지 모든 점을 내부에 포함하는 다각형을 만든다. 이를 볼록 껍질(CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예. 2. 알고리즘 : Graham's Scan 사용(1) P0을 선택합니다. - P0은 y축 가장 아래에 위치한 점을 선택합니다. - 가장 아래 위치한 점이 여러 개 존재 시 x축 가장 좌측을 선택합니다. (2) P0을 기준으로 모든 점들에 대한 각도를 구한다. (3) 구한 점들의 각도 중 가장 낮은 각을 가진 점을 순서대로 P1, P2 선택 (4) 다음 점 Pn을 선택하여, 점을 추가 할 것인지 교체 할 것인지 정한다. - 이전 두 점에 대해 조..
2014.05.01 -
알고리즘:등고선법을 통한 최단경로 찾기
등고선 알고리즘 길 찾기 알고리즘 중 하나로 등고선 알고리즘을 이용하면 길의 유무와 최단 거리를 찾아 낼 수 있다. 알고리즘1. 시작 점과 도착 지점을 정한다.2. 도착 지점 주위의 이동가능한 길에 번호를 적는다.3. 번호를 입력한 곳 주위의 이동 가능한 길에 번호를 적는다.4. 1~3 반복하여, 시작 지점에 도달하면 종료. 시작지점에 도달하지 못하고 더 이상 길이 없는 경우 길이 없는 것으로 판단. 소스코드등고선 알고리즘(){ //위치 값을 기록할 Queue 선언 std::queue ContourLineQueue 반복문 { 조건문(Queue.empty() && StartPoint==true) { break(); } Precess();//등고선 그리기(1~3 과정 수행) Queue.pop(); } Lin..
2014.03.27 -
알고리즘:Recursive Backtracking
미로를 생성하는 알고리즘 중 가장 간편해 보이는 Recursive Backtracking 알고리즘. Recursive Backtracking 알고리즘의 동작은 아래와 같습니다. (내가 보기에는...)1. 무작위로 한 곳을 선택합니다.2. 선택된 위치에서, 인접한 곳(상,하,좌,우)을 랜덤하게 탐색합니다.3. 탐색한 곳의 벽이 전부 막혔다면 뚫고 그 장소로 이동합니다.4. 인접한 곳에 이동할 곳이 없다면, 이전 위치로 돌아 갑니다.5. 위 내용을 반복하여 모든 장소를 방문하면 미로가 완성 됩니다. 예) 개발은 MFC 환경에서 그리드를 이용했습니다.(후회 중...)그리드 연결 및 표 생성은 생략하며, 알고리즘의 주요 부분만 포스팅 소스코드 1. 미로를 생성하기 위해 BackTracking() 함수를 작성하였..
2014.03.11 -
알고리즘:달팽이관
달팽이관 알고리즘- 2차원 배열을 달팽이관 처럼 접근하는 알고리즘. 동작- 아래와 같은 그림으로 동작하는 알고리즘을 작성 그림표현숫자로 표현 12345161718196152425207142322218131211109 알고리즘 작성- 보통 배열을 이용한 알고리즘의 경우 접근 순서대로 배열의 위치를 적어 보는 것이 편리하다.- 배열 좌표(0,0)(0,1)(0,2)(0,3)(0,4)(1,0)(1,1)(1,2)(1,3)(1,4)(2,0)(2,1)(2,2)(2,3)(2,4)(3,0)(3,1)(3,2)(3,3)(3,4)(4,0)(4,1)(4,2)(4,3)(4,4) - 2차원 배열(5*5) 좌표의 위치를 보면 위 표와 같으며 2차원 배열에 접근하기 위해서 2중 반복문을 사용하겠다.- 반복문을 토대로 접근 순서를 표시..
2013.04.16 -
알고리즘 카테고리 목적
프로그래밍 공부를 계속 하면서 MFC, OpenGL, 안드로이드와 같이 개발에 관련 된 라이브러리를 사용하면서OpenAPI를 사용하는 일이 많아졌다. 하지만 반대로 기본 알고리즘을 작성하는 일은 거의 없어진것 같다.물론 프로그래밍 기초 문법을 배울때 한번 씩 코딩을 했었지만, 가끔은 간단한 알고리즘을 코딩하는 시간이 필요하다고 생각되어 게시판을 생성한다.
2013.04.16