2월 1주차 백준 문제풀이 파이썬(듣보잡, 회의실 배정, 바이러스, 최대 힙, 집합 연결요소의 개수, 좌표압축)

2월 1주차 문제해설

• 1764 - 듣보잡 ✔
• 1931 - 회의실 배정 ✔
• 2606 - 바이러스 ✔
• 11279 - 최대 힙 ✔
• 11723 - 집합 ✔
• 11724 - 연결 요소의 개수 ✔
• 18870 - 좌표 압축 ✔

---

1764번 - 듣보잡 & 11723 - 집합

• 1764: 시간제한 : 2초 | 메모리제한 : 256MB
• 11723: 시간제한 : 1초 | 메모리제한 : 4MB

1764번

• 파이썬 내장 클래스인 set의 intersection() 메소드를 사용하면 두 set 사이의 교집합을 얻을 수 있다. 이를 활용하면 된다.

11723번

• 파이썬 내장 클래스인 set를 활용하면 쉽게 풀 수 있다.
• add는 add()를 활용
• remove는 숫자가 없는 경우에도 동작하기 위해 remove()가 아닌 discard()를 사용해야한다. remove()를 사용하면서 set내에 없는 엘리먼트를 삭제하면 keyError가 발생하지만 discard()는 그렇지 않다.
• check는 in 키워드를 사용하자
• toggle은 remove()와 add() 메소드를 사용하자. if문에서 엘리먼트의 존재여부를 판단했으므로 remove()를 사용해도 된다.
• all는 update([...])를 사용하자. 리스트에 들어있는 모든 엘리먼트들을 add()해준다.
• empty는 celar() 메소드를 사용하자. set을 공집합으로 만들어준다.

---

1931번 - 회의실 배정

시간제한 : 2초 | 메모리제한 : 128MB

그리디 알고리즘, 정렬을 활용해야 풀 수 있는 문제다.

우선 가장 많은 회의실 사용 횟수를 구할 수 있는 방법을 떠올리라고 하면 3가지를 선택할 것이다.

1. 빨리 시작하는 순서대로 정렬하기
2. 회의가 짧은 순서대로 정렬하기
3. 빨리 끝나는 순서대로 정렬하기

하나씩 반례를 찾아보자

1. 가장 빨리 시작하는 순으로 정렬하기

• 가장 빠르게 시작하는 회의가 엄청 길다면 다른 몇개의 회의를 진행 할 수 없을 수도 있다.

2. 짧은 것들 순으로 정렬하기

• 2개의 회의시간 중간에 짧은 회의 하나가 겹처버리면 2번 회의를 진행 할 수 있는 걸 1번만 카운트 하게 된다.

3. 가장 빨리 끝나는 순으로 정렬하기

• 회의가 시작되려면 그 이전에 회의가 끝나 있어야 한다. 더 빠르게 회의가 끝나는 순서대로 정렬 하면 그 순간순간 최적의 답을 찾을 수 있다.(그리디 알고리즘)
• 주의할 점은 끝나는 시간이 같다면 시작시간이 빠른 순서대로 골라야 한다. (예시: 1~3, 3~3)

3번을 활용해서 각 회의시간을 입력 받은 후 끝나는 시간 순서대로 정렬 후 시작하는 시간 순서대로 다시 한번 정렬해주면 된다.

여기서 파이썬 기본 내장함수인 sort()를 사용할 것이다. sort() 함수는 파라미터로 key 값을 튜플 형태로 전달 할 수 있고, 각 인자 순서대로 오름차순 정렬해준다.

예시 : array = array.sort(key = lambda x : (x[1],x[0]))

---

2606번 - 바이러스 & 11724번 - 연결 요소의 개수

• 2606: 시간제한: 1초 | 메모리제한: 128MB
• 11724: 시간제한: 3초 | 메모리제한: 512MB

그래프 이론 중 BFS, DFS를 활용해서 풀 수 있는 문제다.

출처 : https://nick.balestrafoster.com/2015/depthFirst-vs-breadthFirst/

DFS

Depth Fisrt Search(깊이 우선 탐색법)으로 각 노드의 연결된 첫 자식부터 순차적으로 탐색해 나가는 방식이다. 빠르다는 장점이 있지만, 탐색한 경로가 최적의 경로가 아닐 수 있다. 재귀로 구현한다.

BFS

Breadth(깊이 우선 탐색법)으로 모든 자식 노드를 순서대로 탐색하고 그 노드들의 자식노드.. 순으로 탐색해 나가는 방식이다. 두 노드간의 최단경로를 찾고 싶을때 주로 사용하고 DFS보다 구현이 살짝 어렵다.

문제해설

• 2606번은 노드와 링크를 입력 받은 후 DFS,BFS 등을 구현한 후 1번 노드와 연결된 모든 노드를 탐색 하였으면 지금까지 방문한 노드의 개수 중 자기자신인 1개를 제외한 수를 출력하면 된다.

• 11724번은 1번 노드부터 마지막 노드까지 순서대로 DFS,BFS를 이용해 탐색하되 방문한 노드에 기록되지 않은 노드만 탐색하면 된다. 그 후 각 탐색이 끝날 때마다 카운트를 1개씩 늘려 그 수를 출력하면 된다.

---

11279 - 최대힙

시간제한: 1초 | 메모리제한: 128MB

출처: https://www.geeksforgeeks.org/max-heap-in-java/

최대 힙 : 부모노드가 자식노드보다 작지만 않으면 성립하는 힙. 완전 이진 트리이다.

가장 큰 값을 출력할땐 최상위 노드를 제거하고 최하위 노드를 최상위 노드 위치에 넣은 뒤 자식 노드들과 비교하며 내리면 된다. 새로운 노드를 추가할땐 최하위에 노드를 삽입하고 부모노드와 비교해가며 위치를 바꾸면 된다.

---

18870 - 좌표압축

시간제한: 2초 | 메모리제한: 512MB

주어진 좌표들 중 특정 영역 내의 좌표 값을 구하고 싶은데, 각 좌표 사이의 거리가 너무 넓으면 메모리, 시간에 제한이 걸릴 수도 있다. 이럴때 좌표 압축을 시행하는데, 각각의 좌표를 상대적인 좌표로 나타내면 된다.

• 예시 : [-10000000,0,10000000] -> 좌표압축 시행 후 -> [0,1,2]

dots에 각 점을 넣고 dotset으로 중복된 좌표를 제거 해준다. 그리고 dictonary클래스를 이용해 dotdic에 key값을 좌표값으로, value값을 for문을 통해 0부터 len(dotset)-1까지 지정해주면 각 좌표당 할당된 새로운 좌표를 얻을 수 있다.