알고리즘 수업시간에 배운걸 끄적인다.


고차 다항식 계산을 프로그램에 적용한다면


몇몇 사람들은 식 그대로 사용할 지도 모른다.


예를 들어서.. 10x^3+5x^2+3x+6 = y 라는 식이 존재한다고 하면


C언어 기준으로 



1
2
3
4
5
6
7
int main()
{
    int x = 10;
    int y = 10*x*x*x + 5*x*x + 3*x + 6;
    printf("y is %d\n",y);
    return 0;
}
cs

라고 작성할 수 있다.(일부는 라이브러리를 사용하여 제곱 계산을 할 수도 있겠지만..)


하지만 Horner's role을 사용하여 계산 횟수를 줄일 수 있다.


식을 묶어버린다면,



(10x^2+5x+3)x+6 

=((10x+5)x+3)x+6

으로 변한다.


식을 다시 작성해 본다면


1
2
3
4
5
6
7
int main()
{
    int x = 10;
    int y = ((10*x+5)*x+3)*x+6;
    printf("y is %d\n",y);
    return 0;
}
cs

요렇게 바뀐다.


첫 번째 코드는 연산이 곱셈 6번, 덧셈 3번

두 번째 코드는 연산이 곱셈 3번, 덧셈 3번


곱셈이 무려 3번이나 줄어들었다.



'Algorithm' 카테고리의 다른 글

자료구조. 순회(전위 중위 후위)  (0) 2018.03.19
자료구조 트리. Tree  (0) 2018.02.21
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
다익스트라 알고리즘  (0) 2016.11.14

다익스트라 알고리즘(dijkstra's algorithm)


두 정점 사이간 최소 거리를 구하는 알고리즘의 일종.



간단히 이론적인 것을 설명하자면..


N개의 정점을 모두 돌아다니는데 N과 연결된 정점을 찾아 거리를 계산해주는 것이다.


Start(시작점), End(도착점)이 존재하는데 각 점과 Start의 거리의 초기 값은 inf(무한대)이고


정점을 찾아다니며 최소 거리를 갱신하는 것이다.


-실제로는 inf 값을 넣지않고 큰 값, 혹은 일정한 값을 넣는다.(음수도 가능?할지도)




예를 들어 


정점 5개가 존재하고 각 정점을 0~4로 이름을 매긴다.


각 정점 간 관계는 아래와 같다.



또한 각 정점 간 거리는 아래와 같다.





 Start가 0, End가 3이라 놓는다면


0은 1과 2밖에 연결이 안 되어 있으니, 탐색은 0->1, 0->2로 시작된다.


이때 0->1, 0->2는 0으로부터 각 정점간 최단 거리이므로 3, 2가 최단거리가 될 것이다.





또한 1은 2와 3이랑 연결이 되어있다.


이때 탐색 루트는 0->1->2 , 0->1->3이 되는 것인데


0->1->2 루트의 거리는 5이고 이전에 0->2는 2이므로 최단거리 갱신이 안된다.


0->1->3 루트는 첫 탐색이므로 7이 최단거리가 된다.





0->2->3, 0->2->4 탐색을 해보자.


0->2->3 루트는 이미 0->1->3으로 0->3간 최단 거리가 설정되있다. 


하지만 0->2->3 루트는 거리가 3이므로 기존에 7보다 작으므로 최단거리 갱신이 된다.




0->3까지 최단거리는 이로써 3이 된다.


원래는 C++, C는 우선순위 큐를 이용하여 작성해야만 변수가 사라진다.


지금은 C# 코드만 ..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
 
namespace Rextester
{
    public class Program
    {
        //빈공간이라는 것을 의미하는 변수
       private static int BigSize = 50000;
 
        //n개의 정점간 관계를 나타내는 이차원 배열
        private static int[,] map=new int[,]{{BigSize,3,2,BigSize,BigSize},
                                {BigSize,BigSize,2,4,BigSize},
                                {BigSize,BigSize,BigSize,1,3},
                                {BigSize,BigSize,BigSize,BigSize,4},
                                {BigSize,BigSize,BigSize,BigSize,BigSize}};
        //각 정점과 start와의 최소 거리
        private static int[] dist=new int[]{BigSize,BigSize,BigSize,BigSize,BigSize};
 
        //트래커, 이전에 어떤 정점을 거쳐온건지 체크
        private static int[] prev=new int[]{-1,-1,-1,-1,-1};
        public static void Main(string[] args)
        {
            serch(0,4);
        }
        private static void serch(int start, int end){
            if(start>5 || end>5) // 일단은 정점이 5개므로 초과로 입력되는 것을 막는다.
                Console.WriteLine("error");
            dist[start]=0; // start initialization // 시작 정점은 최소거리가 0이므로 초기화를 시켜준다.
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    if(map[i,j]!=BigSize){  // 정점 간 간선이 존재한다면
                        if(dist[j]==BigSize){ // 그리고 첫번째 방문이라면
                            dist[j]=dist[i]+map[i,j]; // 바로 최소거리가 된다.
                            prev[j]=i; //그리고 이전 정점을 넣어준다.
                        }
                        else if(dist[j] > dist[i]+map[i,j]){ // 첫 방문이 아니고 이전에 설정된 최소거리가 지금 최소거리보다 크다면
                            dist[j]=dist[i]+map[i,j];
                            prev[j]=i;
                        }
                    }
                }
            }
            Console.WriteLine("length:"+dist[end]);
            trck(start,end);
        }
        private static int trck(int start,int tmp){ // 최소거리가 되는 정점을 찾는다.
            if(tmp==start){ 
                Console.Write(start);
            }else{
                Console.Write(tmp+"->");
                return trck(start,prev[tmp]);
            }
            return 0;
                
        }
    }
}
cs


'Algorithm' 카테고리의 다른 글

자료구조. 순회(전위 중위 후위)  (0) 2018.03.19
자료구조 트리. Tree  (0) 2018.02.21
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
Horner's role  (0) 2017.03.15
  • form method에 따른 정보 전달

    • 1
      2
      <form action="JOIN.do" method="GET">
      <form action="JOIN.do" method="POST">
      		cs

위와 코드에 따른 처리 방식을 알아보자. 

method="GET"일 경우

- URL = http://localhost:8000/web/JOIN.do?id="test"&pw="1234"

method="POST"일 경우

- URL = htpp://localhost:8000/web/JOIN.do

다른 점은 url에 데이터가 붙냐 안붙냐의 차이.

    • Java에서는 어찌 받을까?

      • doGet()
        • 1
          2
          3
          4
          protected void doGet(HttpServletRequest req, HttpServletResponse, res){
              String id = req.getParameter("id");
              String pw = req.getParameter("pw");
          }
          		cs

      • doPost()
        • 1
          2
          3
          4
          protected void doPost(HttpServletRequest req, HttpServletResponse, res){
              String id = req.getParameter("id");
              String pw = req.getParameter("pw");
          }
          		cs


      • 둘다 받는 방식은 똑같다. (HttpServletRequest를 이용해서 Parameter을 받아온다.)


    • 한글 인코딩
      • Get방식과 Post방식은 인코딩의 차이가 있다.
      • Get
          • Server.xml을 수정한다.
          • 1
            <Connector URlEncoding="EUC-KR">
            		cs

      • Post
        • 1
          req.setCharacterEncoding("EUC-KR");
          		cs

          • 위 코드를 doPost()내부에 적어주면 된다.


'Web' 카테고리의 다른 글

React와 Express 연동하기(1)  (0) 2020.09.11
IntelliJ에서의 Servlet 프로젝트 설정 방법  (0) 2019.09.19
젠킨스 사용해보기  (0) 2017.12.31
Servlet 기초(1)  (0) 2016.11.11

+ Recent posts

티스토리툴바