고도고도
🍎🍏
고도고도
전체 방문자
7,931
오늘
11
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표

2021. 1. 13. 20:00

- 목표 -

최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습한다.

 

1. 다익스트라

방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오.

 

[입력 값]

6 7

A B C D E F

A B 10

A C 15

B D 12

B F 15

C E 10

D F 1

F E 5

A E

 

[출력 값]

A C 15

C E 10

 

2. 벨만 포드

음의 가중치가 있는 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. 만약, 무한 루프가 발생할 경우 Negative Cycle! 이라고 출력하시오.

 

[입력 값]

5 8

A B C D E

A B -1

A C 4

B C 3

B D 2

B E 2

D B 1

D C 5

E D -3

A D

 

[출력 값]
A B -1

B E 2

E D -3

 

3. 경찰서

범죄 발생시 경찰 도착까지 오래 걸리는 문제를 해결하고자 경찰서의 위치를 변경하고자 한다. 마을과 마을간의 거리와 경찰이 쉽게 다다를 수 있는 거리가 입력으로 주어진다. 가능한 많은 마을에 경찰이 쉽게 다다를 수 있는 곳에 경찰서를 이전하고자 한다. 어떤 마을에 경찰서를 설치해야하는지와 몇개의 마을에 쉽게 다다를 수 있는지 출력하시오.

 

[입력 값]
6 7

A B C D E F

A B 10

A C 15

B D 12

B F 15

C E 10

D F 1

F E 5

10

 

[출력 값]
E 4

 

4. 이후 백준에서 관련된 문제를 풀어본다.

백준 1753번 - 최단경로 (www.acmicpc.net/problem/1753)

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

백준 1916번 - 최소비용 구하기 (www.acmicpc.net/problem/1916)

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

 

저작자표시

'⛹️ 라이프 > 2020 겨울방학 모각코(개인)' 카테고리의 다른 글

[코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표  (0) 2021.01.20
[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과  (0) 2021.01.13
[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표  (0) 2021.01.13
[코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과  (0) 2021.01.05
[코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표  (0) 2021.01.05
[코독하구만 팀] 2020.12.30(수) - 2주차 개인 결과  (0) 2020.12.30
    '⛹️ 라이프/2020 겨울방학 모각코(개인)' 카테고리의 다른 글
    • [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표
    • [코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과
    • [코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과
    • [코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과
    이전 글
    [코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • ···
    • 13
    • 다음