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

패켐 제작문제 해설 4,5

문제 내용 링크 참조

 

문제 1 : 문자열 제거  (https://www.acmicpc.net/problem/21922)

- 다이나믹 프로그래밍, 난이도 중

 

구현 아이디어

인덱스		0	1	2	3	4	5	6	7	8	9
문자열		a	b	c	x	y	z	x	a	b	c

 - 문자 지우기, abc, xyz 로 문제를 나누어서 풀이한다

---

문제 2 : 문자열 제거  (https://www.acmicpc.net/problem/21942)

- 자료구조, 구현 , 난이도 중

 

구현 아이디어 

1. 부품을 얼마나 오래 빌렸는지 분 단위로 계산 해아한다

  - 날짜 정보가 담긴 문자열을 타임 스탬프(timestamp)로 변경

  - 타임스탬프 : 2021-01-01  00:00 으로부터 몇 분 지났는지

2. 대여 기록을 관리하기 위한 자료구조가 필요

  - HashMap을 이용해 각 사람마다 (대여한 부품, 타임 스탬프) 정보 저장

 

 

---

문제 3 : 연산 최대로 (https://www.acmicpc.net/problem/21943)

 - 난이도 중, 완전탐색, 그리디

 

구현 아이디어

 - 곱하기 연산자를 기준으로 그룹을 분리할 수 있다

  EX) 곱하기 연산자의 개수 Q가 2일떄  ㅁ * ㅁ * ㅁ 와 같다

 - 따라서 본 문제의 N개의 원소를 Q + 1 개의 그룹으로 나누어 분할하는 문제로 이해할 수 있다

   - 모든 경우의 수에 대하여 결과를 계산한 뒤, 최댓값을 구하면 정답

---

문제 4 : 문제 추천 시스템 Version2  (https://www.acmicpc.net/problem/21944)

  - 난이도 중, 자료구조, 구현

 

구현 아이디어

 - Java에서 이진 탐색 트리에 기반하는 TreeSet을 지원한다

  - 중복된 값을 저장하지 않는다 (집합)

  - 기본적으로 데이터를 정렬된 상태로 관리

 

---

문제 5 : 트리 순회   (https://www.acmicpc.net/problem/21856)

 - 난이도 하, 자료구조

 

구현 아이디어 

 - 중위 순회의 동작 과정을 생각하면서 트리를 그려본다

 - 유사 중위 순회 : 가장 오른쪽 아래 노드로 향하는 경로를 제외하고, 각 간선을 2회씩 통과한다.

 

 - 이동 횟수 = 간선을 통과한 횟수

 - 가장 오른쪽 아래 노드로 이동하는 경로를 제외하고, 모든 간선을 2회씩 통과한다

 - 따라서 루트부터 가장 오른쪽 아래 노드로 이동해 본 뒤 정답을 도출할 수 있다

 - 트리 구조이므로 간선의 개수는 N - 1입니다.

 

---

문제 6 : HTML 파싱 (https://www.acmicpc.net/problem/21859)

 - 난이도 중, 구현, 문자열 

 

구현 아이디어

 - 각 <div> 태그 안에 있는 정보만 처리

  - title 속성의 값을 파싱

  - 이후 내부에 있는 <p> 태그를 하나씩 확인하며 문자열 출력

 

 

 

 

 

45일차 인증

 

 

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

https://bit.ly/37BpXiC

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