제1회 (1주차) 모각코 목표

1주차 (1회차) - 데이크스트라에 대한 이론 학습 및 코드 구현, 그리고 백준 응용 문제풀기


1504번: 특정한 최단 경로 (acmicpc.net)


데이크 스트라에 대한 이론적인 이해와 함께 단순 데이크 스트라를 이용하여 최단 거리를 구하는 문제가 아닌 그 응용 문제를 풀어 심층적인 이해를 도모 하려 한다.

1 회차가 끝나고 이해한 이론을 쉽게 풀어 쓰려고 한다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

제 6회 (4주차) 모각코 결과

이미지
  제 6회 (4주차)  - 스위핑 알고리즘의 이론적 학습과 구현, 및 백준 응용 문제 풀기 2170번: 선 긋기 (acmicpc.net) 어려운 내용이 아닌 그냥 한번 훑으면서 같은 라인 단위로 만드는 방법이었다. 아직 스위핑 알고리즘이 뭔지 감을 잡지 못하였다. BaekJoon/선 긋기.java at main · Hy3ons/BaekJoon (github.com) 2836번: 수상 택시 (acmicpc.net) 해당 문제는 손님이 뒤로 가는 상황일 경우 역주행을 효율적으로 하는 것을 묻고 있다. 현재 나의 위치에서 내 위치 전으로 역주행 하는 상황이 앞에 안 나올 때, 모든 손님을 역주행 하면서 한번에 도착 지점으로 이동 시키면 가장 효율적 이게 된다. 방법은 아는데 구현을 어떻게 해야 될지 모르겠어, HashMap 과 HashSet을 그냥 남발하듯이 사용했다. 또한 내가 특정 지점에 도착 했는데, 역주행을 앞으로 내 위치 전으로 안해도 되는 상황이라는 것을 특정 하는 것이 어려웠다. BaekJoon/수상 택시.java at main · Hy3ons/BaekJoon (github.com) 후에 다시 개념을 정리하고 풀면서, 스위핑에 대한 이해를 높일 수 있었다. 그림을 보면 뒤로 가야 하는 상황에 대해, 겹치는 선분을 하나로 만들어서 2배하여 더해야 한다. 그럼 뒤로 가는 경우에 대해 선분을 다 만들고, 스위핑 기법을 활용 하면 끝난다. 이렇게 하면 HashMap 과 HashSet을 이용하지 않고, 효율적으로 문제를 풀 수 있다. 공유 소스 보기 (acmicpc.net) 남은 시간에는 오일러 피 함수를 알게 된 김에 폴라드로 알고리즘을 이용하여 푸는 문제를 풀어봤다. 13926번: gcd(n, k) = 1 (acmicpc.net) BaekJoon/gcd（n， k） ＝ 1.py at main · Hy3ons/BaekJoon (github.com) 순간적으로 63 비트를 넘기 때문에, python으로 구현하였다.
자세한 내용 보기

제1회 (1주차) 모각코 결과

이미지
1주차 (1회차) - 데이크스트라에 대한 이론 학습 및 코드 구현, 그리고 백준 응용 문제풀기 1504번: 특정한 최단 경로 (acmicpc.net) 데이크 스트라란?     한 노드에서 다른 노드에 가중치가 있을 때, 그 가중치의 합이 가장 적은 길을 찾는 알고리즘 이다. 이런 데이크 스트라는 다이나믹 프로그래밍의 일종인데, 한 노드에서 탐색을 시작하여,  다른 노드로 갈 때, 현재의 최단 거리 값에서 다른 노드로 이동하는 거리의 합이 이전에 그 노드를 방문하여 얻은 최단 거리보다 짧은 경우 업데이트를 하여, 지속적으로 업데이트, 탐색하는 알고리즘이다.          해당 특정한 최단 경로 문제는 데이크 스트라를 돌렸을 때, dp배열의 값, 최단 거리가 무엇을 의미하는지 정확하게 묻는 문제라고 할 수 있다.     해당 문제는 양방향 간선이다. 즉, 특정한 노드에서 다른 노드로 가는 최단 거리는 그 반대여도 값이 같다는 것이다. 그리고 또한 모든 노드는 다른 노드로 가는 간선이 존재한다.     문제는 1에서 N 으로 가는 최단 거리는 우리가 거쳐가야 하는 두개의 노드가 포함 되어 있지 않을 수도 있다는 것이다.     그럼 어떻게 해결 해야 할까?     간단히 축약하여 그린 그림이다.     우리 시작 지점 1번노드 에서 거쳐야 하는 두개의 노드까지의 최단 거리를 구할  수 있다. 그리고 거쳐야 하는 두개의 노드를 시작점으로 다익스트라를 돌리게 되면,  해당 노드에서의 다른 노드까지의 모든 최단거리가 나오게 된다. 그러면 우리는 총 5개의 최단거리로 이루어진 간선을 얻게 되고 사용 할 수 있다.      우린 시작점에서 거쳐야 하는 노드 중 하나를 최단 거리를 이용하여 도착했을 때, 다른 거쳐야 하는 노드까지 현재 노드에서 최단거리를 이용하여 그 노드에...
자세한 내용 보기