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

패켐 제작문제 해설 8,9

 

문제 내용 링크 참조

 

문제 1 : 가희의 고구마 먹방  (https://www.acmicpc.net/problem/21772)

 - 난이도 중, 완전탐색, 백트래킹, DFS

 

• 핵심 아이디어

 - 전형적인 완전 탐색 문제

 - 깊이 우선 탐색(DFS)을 이용하여 모든 경우의 수 계산

  - 각 위치에서 상,하,좌,우 이동 가능

  - 입력 조건 상 10칸 까지도 이동할 수 있으므로, 최대 약 4^10개의 경우의수 존재

 

---

문제 2 : 가희와 프로세스 1  (https://www.acmicpc.net/problem/21773)

 - 난이도 중, 우선순위 큐, 자료구조

 

• 핵심 아이디어

 - 우선순위 큐를 활용한 스케줄러 구현 문제

 - 우선순위는 다음과 같이 정의되며, 이를 위해 별도 클래스 구현 필요

  1. 우선순위 값이 제일 큰 프로세스

  2. 우선순위 값이 제일 큰 프로세스가 여러 개라면, ID가 가장 작은 프로세스

- 최대 100,000초 까지만 시뮬레이션 하면 되므로, 단순히 1초마다 처리하면 된다.

 

---

문제 3 : 가희와 로그파일  (https://www.acmicpc.net/problem/217724

 - 난이도 중, 문자열, 이진탐색

 

• 핵심 아이디어

 - 기본적으로 O(QlogN)의 시간 복잡도로 동작하는 알고리즘 설계

  - 이진 탐색을 이용하여 해결

 - 레발 값이 1부터 6까지만 존재하므로, 각 레벨마다 별도 리스트 생성

 

---

문제 4 : 가희와 파일 탐색기

 - 난이도 하, 정렬

 

• 핵심 아이디어 

 - 사용자 정의 기준에 따라서 정렬을 수행하는 문제

 - 정렬을 위한 별도의 클래스를 구현하여 문제 해결

 - 기본적인 정렬 라이브러리를 사용하여 O(NlogN)의 시간 복잡도로 정렬

 

---

문제 5 : 가희와 키워드  (https://www.acmicpc.net/problem/22233)

 - 난이도 중, 자료구조, 해시 ,집합

 

• 핵심 아이디어

 - 메모장에 남아 있는 키워드의 개수를 출력

   - HashSet을 이용해 각 키워드를 효율적으로 관리 할 수 있다.

---

문제 6 : 가희와 은행   (https://www.acmicpc.net/problem/22234)

 - 난이도 중, 시뮬레이션, 큐

 

• 핵심 아이디어

 - 라운드 로빈 알고리즘과 유사

 - 출력해야 하는 시간은 최대 200,000초 이다

  - 따라서 매 초마다 큐에서 원소를 꺼내어 처리하는 방식 반복

  - 200,000초를 넘어서는 데이터를 무시해도 괜찮다.

 

 

 

 

47일차 인증

 

 

 

 

 

 

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

https://bit.ly/37BpXiC

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