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

수강한 강의

Part 5. 패캠 제작 문제 풀이

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

학습 후기

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

21922번: 학부 연구생 민상

추천 풀이 시간: 40분

40분에서 최대 2시간까지 생각해보고 풀지 못하면 풀이를 보고 확인한다.

문제 유형: 시뮬레이션, 구현

단순한 시뮬레이션 문제이므로 반복문 또는 DFS/BFS를 사용하여 탐색을 진행한다.

시뮬레이션을 위해 이미 방문한 적이 있는 위치를 기록하는 visited 배열을 이용한다.

문제에서 연구실에 있는 물건의 종류에 따라 바람의 방향을 바꾸기에 이 역할을 수행하는 함수를 따로 만든다.

 

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

21923번: 곡예 비행

추천 풀이 시간: 40분

문제 유형: 다이나믹 프로그래밍(DP)

문제에 주어진 내용에 따라 상승 비행에 따른 DP와 하강 비행에 따른 DP를 수행하여 결과를 합친다.

이전 강의에서 배웠던 DP 문제를 푸는 방법에 대해 복습하여 본다.

1. 풀고 싶은 가짜 문제를 정의한다.

2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?

3. 초기값을 구한다.

4. 점화식을 구한다.

위 과정을 생각하여 문제를 풀어보자

 

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

21924번: 도시 건설

추천 풀이 시간: 40분

문제 유형: 최소 신장 트리

모든 건물이 도로를 통해 연결되도록 하는데 대신 도로 비용의 합이 최소가 되도록 해야 한다. 이때 최소 간선 트리를 활용하여 이 문제를 풀 수 있다.

크루스칼 알고리즘

1. 간선들의 가중치를 정렬한다.
2. 정렬된 간선들을 순회하며 사이클을 형성하지 않는 간선을 선택한다.
- 사이클을 형성하는 간선은 제외한다.
3. 선택된 간선을 최소 신장 트리 리스트에 추가한다.

위 과정을 생각하고 크루스칼 알고리즘을 사용하여 문제를 풀어본다.

 

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

21925번: 짝수 팰린드롬

추천 풀이 시간: 40분

문제 유형: 그리디 알고리즘, 다이나믹 프로그래밍

문제에서 짝수 팰린드롬을 최대한 많이 있도록 나누려고 하기에 원소 각각의 위치에서 짝수 팰린드롬을 확인하여 최소 크기의 짝수 팰린드롬을 찾는다. 각 원소마다 진행하여 짝수 팰린드롬의 조건이 아니면 종료한다.

 

수강 인증샷

https://bit.ly/37BpXiC

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

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