반응형
길동이는 설을 맞이해서 서울에서 생활하는데 부산에 있는 부모님 댁에 가려고 합니다.

다음과 같이 시간이 주어질때 가장 빨리 부모님 댁에 갈 수 있는 시간은 어떻게 될지 그리고 경로는 어떻게 될지 여러분이 길동이한테 설명을 해 주세요.





 

문제풀이) 먼저 서울에서 출발을 하는데 서울에서 가장 빨리 갈수 있는 광주를 선택 합니다.

광주에서 빨리 갈 수 있는 대전을 선택 후 대전에서 빨리 갈 수 있는 강릉을 선택후 강릉에서 부산을 선택하는 경로를 생각해 볼 수 있습니다. 이때는 1시간 + 3시간 + 1시간 + 1시간 = 6시간이 걸립니다.

하지만 여기서 가장 빨리 갈 수 있는 방법은 서울에서 대전을 거쳐 강릉-> 부산으로 가는 길이 5시간으로 가장 빠릅니다.

이 것을 찾는 방법으로는 다음과 같이 생각을 해 볼 수 있습니다.

칠판에 다음과 같이 도시를 테이블에 그려 봅니다.

처음에는 위와 같이 갈 수 없다고 생각을 한 후에 무한 시간으로 셋팅을 한 후에 서울에서 출발 하므로 서울은 0시간이 걸립니다.

테이블에 서울의 위치를 0으로 설정합니다.

이렇게 한 후에 서울,광주,대전 강릉,부산 중에서 가장 빨리 갈 수 있는 서울위치에서 갈 수 있는 모든 시간을 설정 해 봅니다.

이렇게 광주,대전,강릉 도착시간을 계산할 수 있고 이 중에서 이미 확인한 서울을 제외한 위치 중 가장 빨리 도착하는 위치까지 온시간 + 다른 위치로 이동하는 시간을 계산해 볼 수가 있습니다.

이렇게 다른곳으로 이동하는 시간을 테이블에 넣어 봅니다.

이때 대전은 서울에서 바로 가는 값이 광주를 거쳐 가는 값보다 적기 때문에 바꾸지 않고 작은 값을 유지합니다.

이 상태에서 아직 가보지 않은 대전,강릉,부산 중에서 값이 가장 작은 대전에서 다른곳으로 이동할 수 있는곳 위치로 이동을 해 봅니다

대전에서 이동해 보면 부산까지는 8시간이므로 광주를 거쳐서 오는시간이 유리하므로 변경하지 않고 강릉까지의 시간만 갱신을 해 주면 됩니다.

마지막으로 강릉에서 갈 수 있는 곳을 가보면 다음과 같이 부산에 5시간만에 갈 수 있게 됩니다.

이렇게 출발점이 주어지고 어느곳의 최단시간, 혹은 최단거리로 갈 수 있는지 체크 하는 알고리즘이 다익스트라 알고리즘이 있습니다.

 

다익스트라 알고리즘은 자동차 네비게이션과 같이 현재 위치에서 목적지를 탐색할때 빠르게 검색하는 알고리즘으로 사용하고 있는 알고리즘입니다.

 

이러한 문제를 풀어 보면서 컴퓨터가 동작하는 원리를 하나씩 알아 가는 재미를 느낄 수 있을것 같네요.^^

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.^^

 

인천 서구 검단신도시 원당컴퓨터학원

 

 

 

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 과고,영재고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학 

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. 핑구야날자 2021.04.10 06:38

    재미있는 코딩이 되겠네요 최단 경로를 찾는 경우는 정말 다양한 텐데 재밌을 거 같아요

  2. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.04.10 07:28 신고

    현실과 좀 맞으면 더 이해가 빠르겠습니다..ㅎㅎ

  3. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.04.10 09:08 신고

    최단경로 알고리즘을 생각하는 문제군요.
    잘 보고 갑니다~ 즐거운 주말 보내세요

  4. Favicon of http://pangyione.com/ BlogIcon 청결원 2021.04.10 21:18

    포스팅 잘 보고 갑니다
    즐거운 주말 보내세요~

  5. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2021.04.12 05:55 신고

    최단경로 찾기..
    잘 보고가요

  6. Favicon of https://lsmpkt.tistory.com BlogIcon 가족바라기 2021.04.13 00:12 신고

    유용한포스팅 잘보고 갑니다
    편안한밤되세요^^

  7. Favicon of http://deborah.tistory.com BlogIcon 데보라 2021.04.13 06:57

    재미 있는 코딩을 이렇게 잘 정리 해주셨네요.

+ Recent posts