패스트캠퍼스 챌린지 36일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 28일 오늘의 강의

 

백준 2212번 문제 : 센서

 

 

문제 해석

1. 최대 K개의 집중국을 설치해야한다.

2. 집중국들의 수신 가능 영역의 길이 합을 최소화하는 것이 목표이다.

3. 정렬된 센서들의 위치와 간격을 리스트로 생성하고, 집중국의 수만큼 간격이 먼 곳부터 정리(설치)한다.

 

 

 

복기

1. 단순히 머리로만 생각해서 문제를 해석하고 풀이하는 것보다 문제의 상황과 조건을 도식화해보고 예제 데이터를 참고해서 알고리즘을 구현하는 것이 더 효율적이었다.

2. 그동안 나의 스타일은 코드로 구현하면서 문제를 이해하고 보완하는 것이었는데 접근이 잘못될 경우가 있기 때문에 1번 방식을 발전시킬 필요가 있다.

3. 최소 거리의 합을 구할 때는 위치 데이터를 정렬한 뒤 거리 데이터를 생성 그리고 조건에 따라 삭제하고 데이터를 합산한다.

 

백준 1461번 문제 : 도서관

 

 

문제 해석

1. 책들을 원래 위치로 정리해야한다. 마지막 책을 정리할 땐 0으로 돌아오지 않아도 된다.

2. 책의 위치를 양의 정수와 음의 정수를 나누고, 이를 우선순위 큐를 활용해서 문제를 해결한다.

 

 

오답(좌), 정답(우)

 

1. 오답과 정답 사이에 문제의 접근 방식은 같았으나, 답을 구하는 방향성이 달라 오답 처리가 되었다. 나는 책을 정리하는 데  필요한 최소 이동거리를 구하는 상황에서 가까운 쪽에서부터 책을 정리하는 게 효율적이라고 생각했으나 이와 반대로 가장 먼 곳을 제외한 나머지에서 멀리 있는 곳부터 정리하는게 효율적이었다.

2. 경우의 수와 반례를 통해 코드를 개선하는 것이 중요했는데 복잡하게 생각하다보니 경우의 수를 살펴볼 때도 무척 복잡해졌다. 먼저 간단하게 원리를 도식화한 뒤 경우의 수를 살펴보는게 좋을 것 같다.

 

백준 1781번 문제 : 컵라면

 

 

문제 해석

1. 데드라인을 초과하는 문제는 풀 수 없다.

2. 정렬과 우선 순위 큐를 통해 O(NlogN) 내에 풀 수 있다.

 

 

복기

1. 데드라인에 따라 우선순위 힙의 크기를 유지하는 게 참신했다. 데드라인을 초과할 경우 최솟값이 나오기 때문에 반복문이 끝나면 sum 함수를 통해 최댓값을 계산하면 된다.

2. Python3는 시간 초과가 발생했다. 데이터가 200,000개이고 for문 안에 heapq 메소드 등 내부 연산으로 시간 복잡도가 높아진 경우이다. 다행히 PyPy3로 주어진 조건 내에 풀이하였다.

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.