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

수강한 강의

Part 5. 패캠 제작 문제 풀이

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

학습 후기
1. https://www.acmicpc.net/problem/21941

21941번: 문자열 제거

추천 풀이 시간: 50분
문제 유형: 다이나믹 프로그래밍
다이나믹 프로그래밍으로 문제 해결이 가능하다. 주어진 문제의 문자열의 점수를 치환이 가능한 해당 위치에 기록하고 문자열 시작부터 index를 증가시키며 해당 위치에서 점수의 합이 가장 클 때를 배열에 저장하며 문제를 해결한다. 치환이 가능하지 않을 때는 문자열 하나에 1점으로 치므로 해당 인덱스까지 진행해 온 점수 + 1과 치환 가능한 문자열 점수를 더했을 때의 점수를 비교하여 큰 값을 배열에 업데이트하며 다이나믹 프로그래밍으로 푼다.

 

처음 풀이를 보지 않고 풀 때에는 지울 수 있는 문자열의 가치를 점수 / 문자열 길이로 하고 우선순위 큐에 넣어 가치가 높은 문자열부터 차례로 해당 문자열에서 찾아 지우고 남은 문자열은 1점으로 계산하여 문제를 풀었다.

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

21942번: 부품 대여장

추천 풀이 시간: 60분
문제 유형: 자료구조, 구현
부품을 얼마나 오래 빌렸는지 분 단위로 계산해야 하기에 날짜 정보가 담긴 문자열을 분 단위로 치환하는 과정이 필요하다. 또, 대여 기록을 관리하기 위한 자료구조가 필요한데 이때 HashMap을 이용하여 사람마다 대여한 부품, 타임스탬프 정보를 저장한다.

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

21943번: 연산 최대로

추천 풀이 시간: 60분
문제 유형: 완전 탐색, 그리디
해당 문제는 더하기 연산자와 곱하기 연산자의 수가 주어지고 주어진 양의 정수에 연산자를 조합하여 최댓값을 구해야 한다. 이때 연산자를 나열하는 것은 완전 탐색에서 중복 없이, 순서대로(덧셈, 곱셈의 순서가 바뀌면 사칙연산 우선순위에 의하여 결과가 바뀐다.) 나열하는 경우이므로 경우의 수는 N!이 된다.

오늘로서 패스트캠퍼스 50일간의 챌린지 끝났다. 하루에 한 강의씩 들으며 쉬운 거는 바로바로 이해하고 넘어갔지만 어려운 거는 시간이 오래 걸려 밀린 문제도 있다. 더 자세한 후기는 다음 포스팅에 남기겠습니다. 이직할 때까지 끝난 게 아니기에 앞으로는 백준 알고리즘 문제를 풀며 포스팅을 남길 예정이다. 꼭 성공하자!

수강 인증샷

https://bit.ly/37BpXiC

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

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