제 4회 (3주차) 모각코 목표
4회차 (3주차) - 그리디 문제 풀어보기 (수정) 최소 버택스 커버에 대해 공부, 응용 문제 풀기
최소 버택스 커버 이론에 대해 공부 후, 해당 이론을 응용하는 문제를 풀어 볼 예정이다.
제 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으로 구현하였다.
댓글
댓글 쓰기