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

제 6회 (4주차) - 스위핑 알고리즘의 이론적 학습과 구현, 및 백준 응용 문제 풀기

어려운 내용이 아닌 그냥 한번 훑으면서 같은 라인 단위로 만드는 방법이었다.

아직 스위핑 알고리즘이 뭔지 감을 잡지 못하였다.

해당 문제는 손님이 뒤로 가는 상황일 경우 역주행을 효율적으로 하는 것을 묻고 있다.

현재 나의 위치에서 내 위치 전으로 역주행 하는 상황이 앞에 안 나올 때, 모든 손님을 역주행 하면서 한번에 도착 지점으로 이동 시키면 가장 효율적 이게 된다.

방법은 아는데 구현을 어떻게 해야 될지 모르겠어, HashMap 과 HashSet을 그냥 남발하듯이 사용했다.

또한 내가 특정 지점에 도착 했는데, 역주행을 앞으로 내 위치 전으로 안해도 되는 상황이라는 것을 특정 하는 것이 어려웠다.

후에 다시 개념을 정리하고 풀면서, 스위핑에 대한 이해를 높일 수 있었다.

그림을 보면 뒤로 가야 하는 상황에 대해, 겹치는 선분을 하나로 만들어서 2배하여 더해야 한다.

그럼 뒤로 가는 경우에 대해 선분을 다 만들고, 스위핑 기법을 활용 하면 끝난다.

이렇게 하면 HashMap 과 HashSet을 이용하지 않고, 효율적으로 문제를 풀 수 있다.

남은 시간에는 오일러 피 함수를 알게 된 김에 폴라드로 알고리즘을 이용하여 푸는 문제를 풀어봤다.

순간적으로 63 비트를 넘기 때문에, python으로 구현하였다.

황현석 코드 일지