코딩테스트 - 패스트캠퍼스 챌린지 49일차

수강한 강의

Part 5. 패캠 제작 문제 풀이

Chapter 01. 문제풀이
- 나동빈의 패캠 제작 문제 해설 3

학습 후기

1. https://www.acmicpc.net/problem/21937

21937번: 작업

추천 풀이 시간: 30분

문제 유형: 깊이 우선 탐색, 너비 우선 탐색

문제에서 특정 작업 X를 끝내기 위해 우선으로 완료되어야할 작업들을 구하기에 간선의 방향을 반대로 한 뒤 작업 X에서부터 너비 우선 탐색(BFS)를 수행하여 문제를 해결한다.

 

2. https://www.acmicpc.net/problem/21938

21938번: 영상처리

추천 풀이 시간: 30분

문제 유형: 너비 우선 탐색, 깊이 우선 탐색

먼저 문제에서 주어진 RGB 값을 가지고 평균을 구하고 주어진 경계값 T와 비교하여 모든 픽셀의 색상을 255 또는 0으로 바꾸어서 새로운 화면을 만든다.

새로 만들어진 화면에서 값이 255인 픽셀은 물체로 인식하고 값이 255인 픽셀들이 상하좌우로 인접해 있다면 같은 물체로 인식하기에 DFS로 연결 노드를 확인하여 물체의 개수를 확인한다.

 

3. https://www.acmicpc.net/problem/21939

21939번: 문제 추천 시스템 Version 1

추천 풀이 시간: 50분

문제 유형: 자료구조, 구현

먼저 문제의 요구사항대로 추천 시스템을 구현한다. 그리고 우선순위를 다룰 수 있는 자료구조가 필요하다. 우선 순위에따라 자료를 저장하고, 조회해야 하기 때문이다. 따라서 이진 탐색 트리에 기반하는 TreeSet을 사용한다. 중복된 값을 저장하지 않는 집합이며, 기본적으로 데이터를 정렬된 상태로 관리하기에 우선순위 처리가 가능하다.

TreeSet 관련 메소드

add(item): item 삽입

remove(item): item 삭제

first(): 우선순위가 높은 데이터 조회

last(): 우선순위가 낮은 데이터 조회

TreeSet 자료구조를 사용하기에 해당 클래스는 Comparable 인터페이스의 compareTo 함수를 Override해 주어야한다.

 

4. https://www.acmicpc.net/problem/21940

21940번: 가운데에서 만나기

추천 풀이 시간: 40분

문제 유형: 최단 경로, 플로이드 워셜

특정 도시 X로 이동했다가 다시 돌아오는데 걸리는 왕복 시간을 구해야 하는 문제이다. 모든 도시에 대하여 다른 모든 도시로의 최단 거리를 계산해야 하므로 플로이드 워셜 알고리즘을 이용한다. 플로이드 워셜 알고리즘은 3중 for문을 사용하며 시간복잡도가 O(V^3)이므로 문제에서 도시 N은 3 <= N <= 200이므로 플로이드 워셜 알고리즘으로 문제를 해결할 수 있다.

 

수강 인증샷

https://bit.ly/37BpXiC

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

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