재귀호출을 사용하지 않고 최단거리(최소비용) 구하는 알고리즘
최단거리 알고림들은 네트워크, 게임에서도 사용된다.
예를 들어서 지하철 노선도 프로그램에서 최단경로를 찾는다던지
네트워크 사용 할때 최단경로로 연결을 구해야 한다던지
게임에서 캐릭터의 길찾기 알고리즘으로도 사용이 가능하다.
문제를 보면서 알아보자
A에서 C까지 가는 최소 비용은?
A → D → B → C로 가면 총 35만원에 갈 수 있다.
다익스트라 알고리즘을 통해서 A에서 출발해서 모든 도착지점의 최단경로를 구 할수 있다.
다음과 같은 규칙을 반복적으로 실행하면 최소비용을 구할 수 있다.
1.
가장 저렴하게 갈 수 있는 곳을 경유지로 선택한다.
2.
선택된 경유지를 거쳐 다른 곳으로 이동 할 때, 더 저렴한지 확인한다.
3.
더 저렴하다면, 최소비용 전광판에 갱신한다.
경유지로 한번 선택이 되었다면, 중복 방문체크를 위해서 배열에 체크해준다.
방문하지 않은 곳에서 가장 싼 값을 선택한다.
A에서 출발해서 D까지 가는 최소거리는 20이다.
D에서 들렸다가 다른지역 (A,B,C) 가는 비용
vs
전광판에 써있는 다른지역 (A,B,C)가는 비용
D에 들렸다가 B로 가는 비용 20 + 10 = 30
전광판에 써있는 B까지 가는비용은 50 이므로 전광판을 A→D→B = 30으로 수전한다.
A에서 D를 들렸다가 C로 가는 비용은 20 + 25 = 45 이고
바로 A→C로가는 비용은 99999 이므로 값을 수정해준다. 더 싼 값으로
그러면 이제 D 를 거쳐서 가는 역할은 끝났다. D는 방문한곳으로 체크해준다. 중복 경유지를 제거해주기 위해서
이제 새로운 경유지를 통해서 다른 노드들의 비용을 계산하여 다시 비교해보자
방문하지 않은곳 B를 들렸다가 C를 가는데 비용은
이미기록해둔 B경로값(30) + 5 = 35 이고 전광판에 써있는 C를 가는 비용은 45인데 이것보다 작으니 갱신해준다.
이런 과정을 반복하면 최정족으로 A>B : 30만원 A >C : 35만원 A>D 20
이렇게 최소비용을 구할 수 있다.
#include <iostream>
#define NOT 999999
int map[4][4] =
{
0, 50, NOT , 20,
NOT, 0, 5 , NOT,
NOT, NOT, 0 , NOT,
NOT, 10, 25 , 0,
};
int result[4] = { 0, 50, NOT, 20 };
int visited[4] = {1,0,0,0 };
int findMin()
{
int min = 987654321;
int minIndex = -1;
for (int i = 0; i < 4; i++)
{
if (visited[i] == 0
&& result[i] < min)
{
min = result[i];
minIndex = i;
}
}
return minIndex;
}
void dijkstra()
{
int min = 987654321;
int minIndex = 0;
for (int i = 0; i < 3; i++)
{
// 1. via 가 0인곳중에 최소값을 찾기
minIndex = findMin();
// 2. a vs b 해서 a가 더 져럼하면 전광판에 갱신해준다.
// a = 경유지까지 가는 비용 + 경유지에서 목적지까지 가는 비용
// b = a에서 목적지까지 가는 비용
for (size_t j = 0; j < 4; j++)
{
int a = result[minIndex] + map[minIndex][j];
int b = result[j];
if (a < b)
result[j] = a;
}
visited[minIndex] = 1;
}
for (size_t i = 0; i < 4; i++)
{
std::cout << result[i] << std::endl;
}
}
char main()
{
dijkstra();
return 0;
}
Python
복사
문제 1번
한국에서 외국을 나가는데 드는 최소 비용을 찾고자 합니다.
지역은 A ~ E 입니다.
지역으로 이동하는데 드는 비용에 대한 정보를 입력받아주세요.
도착지까지 가는데 드는 비용이 가장 저렴한 지역과 가장 비싼 지역을 출력 해주세요.
(다익스트라 알고리즘을 사용해주세요)
(한국이 A 입니다.)
•
저렴한지역: D(10)
•
비싼지역: C(30)
입력 예제
7
A C 100
A B 25
A D 10
A E 30
D E 5
B C 10
E B 5
출력 결과
D(10)
C(30)
문제 2번
링크드리스트 복습입니다.
Memory Pool 을 사용하여 위와 같이 링크드리스트를 만들어 보세요.
아래 코드를 완벽히 이해한 후, 소스코드를 베끼지 않고, 직접 코딩해서 이 문제를 풀어보세요!
[출력]
For문으로 A ~ E 까지 출력해주세요.
#include <iostream>
using namespace std;
struct Node
{
char ch;
Node* next;
};
Node buf[100];
int bufCnt;
Node* head;
Node* myAlloc(int ch, Node* next)
{
buf[bufCnt].ch = ch;
buf[bufCnt].next = next;
return &buf[bufCnt++];
}
void addNode(char ch, Node *next)
{
head = myAlloc(ch, head);
}
int main()
{
return 0;
}
출력 결과
A B C D E
문제 3번
입력 받은 글자를 링크드리스크에 저장하고 출력 해주세요.
글자들을 역순으로 링크드리스트에 저장하고 for문을 돌려 두 칸씩 뛰어넘으면서 출력하세요.
[예시]
입력 받은 M I N C O D I N G 를 역순으로 저장하면 아래처럼 링크드리스트를 구성이 됩니다.
이제 맨 앞부터 밟을 수 있는 징검다리인 돌 들을 두 칸씩 뛰어넘으면서 출력하면 됩니다.
이때 출력결과는 GIONM 입니다.
[입력]
총 9글자를 입력 받으세요.
[출력]
입력 받은 글자를 링크드리스트에 한 글자씩 역순으로 저장하고, 맨 앞부터 두 칸씩 건너뛰어 출력하세요.
입력 예제
M I N C O D I N G
출력 결과
GIONM
문제 4번
음계를 입력 받고 링크드리스트에 저장 후, 출력 해주세요.
Memory Pool 이용하여 링크드리스트를 만들고, 음계 정보를 순차적으로 저장 하세요.
그리고 링크드리스트를 그대로 출력 해주세요.
•
정방향으로 링크드리스트가 만들어 진다는 것을 유의하세요.
•
[입력]
음계의 개수 N을 입력 받으세요.
그 다음 줄의 각 음계의 값을 입력 받으세요.
[출력]
저장된 링크드리스트를 출력 해주세요.
입력 예제
6
5 3 4 1 2 7
출력 결과
5 3 4 1 2 7
문제 5번
8 마리의 공룡 화석이 발견되었고, 이름과 나이는 아래와 같습니다.
공룡들의 나이들을 DB에 저장하고 공룡들을 찾을 수 있는 시스템을 만드려고 합니다.
DB 사용자들이 공룡의 나이를 입력하면 DB에서 해당 나이에 맞는 공룡의 이름을 검색 합니다.
•
공룡들 나이 중 같은 나이는 없습니다.
[입력]
공룡의 나이를 입력 받습니다.
[출력]
나이에 해당하는 공룡의 이름을 출력합니다.
[힌트1]
공룡들의 나이가 1억이 넘기에 배열에 바로 담을 수 없습니다.
Hash Function을 써서 bucket에 값을 담고, 바로 찾으면 됩니다.
[힌트2]
입력 예제
1000000005
출력 결과
Sour
문제 6번
ID/PASSWORD를 입력받으면 암호화를 해서 Server에 전송하곤합니다.
Hash 함수를 이용하여 입력받은 ID를 암호화 후 출력 해 주세요.
•
HashFunction : hornor's method 이용
계산은 아스키코드 번호를 그대로 사용하면됩니다.
[예시]
A : 65
B : 66
C : 67
...
[입력]
대문자로 문자를 입력 받으세요.
[출력]
암호화 결과 값을 출력하세요.
입력 예제
JASON
출력 결과
35016904
문제 8번
A ~ E 그룹사에서 신입사원들이 모였습니다.
그룹사별 신입사원들의 정보를 Memory Pool + Chaining 을 사용하여 저장해주세요.
그룹사의 이름을 입력 받고 해당 그룹사의 신입사원 ID 들을 모두 출력 해주세요.
•
Hash Function 은 사용하지 않아도 됩니다.
[입력]
출력할 그룹사의 이름을 입력하세요.
[출력]
해당 그룹사의 출력할 ID 는 위 배열의 왼쪽부터 오른쪽 순서대로 출력 해주세요.
입력 예제
A
출력 결과
21 15 3
문제 9번
첩보원 코드 번호를 입력하면, 몇 명을 암살했는지 출력해주는 프로그램을 만들어야합니다.
한글자로 된 첩보원 코드번호와 그들이 암살에 성공한 적들의 수가 아래 처럼 저장되어 있습니다.
첩보원이 적에게 당하지 않도록, Hash를 써서 빠르고 정확한 프로그램을 만들어주어야 합니다.
B를 입력하면 10이 출력되고, Z가 입력되면 16이 출력되는 프로그램을 작성 해 주세요.
[입력]
첩보코드를 입력 하세요.
[출력]
첩보원의 암살 성공횟수를 출력하세요.
[힌트1]
struct Node { char code; int killCount; Node *next; }
C++
입력 예제
B
출력 결과
10
