https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 각 노드의 부모를 찾는 문제이다. 예제 입력을 보면 누가 부모이고 자식인지 알 수 없다. 그래서 각 노드를 서로 넣어주어야 한다. for(int i = 1; i < N; i++){ scanf("%d %d", &firstPoint, &secondPoint); map[firstPoint].push_back(secondPoint); map[secondPoint].push_back(firstPoint); } 이 문제는 1을 상위노드로 지정해주었기 때문에 1을 시작으로..

golang http Server Router 설정하기 [golang/golang-webServer] - golang http server 시작하기 ServeMux ServMux는 http package에서 추출된 구조체 타입이다. 들어오는 모든 요청을 처리하 수 있기때문에 ListenAndServe의 argument handler 또한 multiplexer이다. 당연히 ServeMux의 객체를 만들어서 handler argument에 넣어줄 수 있다. 이전 글의 예제에서 자기가 원하는 url path를 설정하여 요청을 받을 수 있다. 해당 url을 받은 후 그에 필요한 연산 및 특정한 응답을 해줍니다. 만약 ServeMux가 /api/, /api/users 리우트를 갖고 있고 client가 /api/u..

golang http server 시작하기 1. 기본 tool 설정 go에서는 네트워크를 다루는 net package를 제공한다. net에는 http가 포함되어 있고 http 요청을 보낼 수 있는 클라이언트도 만들 수 있고 http 서버도 만들 수 있다. http package http 요청과 요청을 받을 수 있는 패키지입니다. 다른 언어들과 다르게 http 보안 서버를 만들 수 있게 제공합니다. import "net/http" 2. 간단한 http 서버 만들어보기 ListenAndServe 함수 func ListenAndServe(addr string, handler Handler) error 이 함수를 이용하영 http 서버를 시작하고 process를 lock 시킵니다. http 요청을 받을 수 있고..

최단 경로(3) 벨만 포드 벨만포드는 다익스트라와 다르게 각 정점을 하나씩 제외하면서 우선순위 큐에 넣는 것이아닌 입력된 모든 path를 반복문 돌려서 최단 경로를 구할 수 있다. 또한 다른 알고리즘과 다르게 -가중치의 값또한 해결할 수 있다. 하지만 -가중치로 인한 계속 -가되는 -cycle이 생성될 수 있다. 그러므로 알고리즘을 작성한 후 -cycle이 존재하는지 체크해야할 필요가 있다. 그리고 다른 최단거리 알고리즘과 Relax 함수는 비슷하다. if(vertex[end] > vertex[start] + map[start][end]) vertex[end] = vertex[start] + map[start][end]; 초기 정점의 설정 값은 INF로 설정해준다. 만약 알고리즘을 돌다가 시작점이 INF..

최단거리(2) 플로이드 플로이드는 벨만 포드, 다익스트라와 다르게 모든 정점에서 다른 모든 정점까지의 거리를 구하는 방법입니다. 일단 이전 다익스트라와 같이 Relax 함수가 핵심입니다. map[start][end] = min(map[start][mid] + map[mid][end], map[start][end]); 이렇듯 다른 정점을 거쳐서 가는 것이 더 빠르냐 아니면 바로 가는 것이 더 빠르냐 비교하여 작은 값을 넣는 것이 핵심입니다. 플로이드는 모든 출발 정점에서 도착 정점까지의 거리를 구하는 것임으로 n까지의 반복문을 3중으로 돌려야합니다. sudo 코드 처음에 각 지점 별 weight를 저장한 후 weight가 없는 곳이라면 INF로 설정하겠습니다. 왜냐하면 초기에 0이면 min연산을 통해 값을..

최단 거리(1) 다익스트라 알고리즘 최단거리 알고리즘에는 다익스트라, 플로이드, 벨만포드 세가지 방법이 있습니다. 다익스트라와 벨만포드는 한 시작점에서 다른 정점까지의 최단거리를 구하는 것이고 플로이드는 모든 정점에서 모든 정점까지의 최단 거리를 구하는 것입니다. 오늘은 3가지 중 다익스트라에 대해 정리해보겠습니다. 1. 다익스트라는 시작 정점에서 다른 정점까지의 거리를 모두 무한대로 세팅한 후 시작합니다. s 정점까지의 가중치와 연결된 정점까지의 가중치 값을 더해서 연결된 정점까지의 가중치 보다 작다면 값을 바꿔줍니다. 2. 이전 라운드를 제외한 다른 정점들 사이에서 최단 거리를 구해줍니다. 새로운 정점 s를 뽑는 방법은 가장 작은 가중치를 갖는 정점을 뽑습니다. 정점 s를 시작으로 다른 연결된 정점들..