제 5회 (3 주차) 모각코 결과
5회차 (3주차) - 트리에서의 다이나믹 프로그래밍 문제 풀어보기
BaekJoon/트리.java at main · Hy3ons/BaekJoon (github.com)
생각보다 그리 어렵지 않았다.
남은 시간에는 이분 매칭을 복습하여 풀었다.
흐르고있는 유량의 감소와 증가 유무를 정확하게 판별하고, 최소거리로 흘려버리면 된다.
제 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으로 구현하였다.
댓글
댓글 쓰기