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

패켐 제작문제 해설 6,7

문제 내용 링크 참조

 

문제 1 : 가장 긴 짝수 연속한 부분 수열 (small) (https://www.acmicpc.net/problem/21857)

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

 

핵심 아이디어

 - 길이가 N인 수열에서 K개의 원소를 삭제할 수 있다

  - 결과적으로 짝수로 이루어진 연속한 부분 수열 중에서 가장 긴 것을 계산

 - 본 문제는 다이나믹 프로그래밍으로 해결 가능

  1. 짝수일 경우 : D[i][j] = D[i][j-1] + 1 왼쪽과 연결

  2. 홀수일 경우 : D[i][j] = D[i-1][j-1] 왼쪽위와 연결

---

문제 2 : 가장 긴 짝수 연속한 부분 수열(large)  (https://www.acmicpc.net/problem/21862)

- 난이도 하, 투 포인터

 

핵심 아이디어

 - 길이가 N인 수열에서 K개의 원소를 삭제할 수 있다

  - 결과적으로 짝수로 이루어진 연속한 부분 수열 중에서 가장 긴 것을 계산

 - 본 문제는 투 포인터 알고리즘으로 해결

  1. 짝수일 경우 단순히 end를 오른쪽으로 이동

  2. 홀수일 경우 최대 K까지 end를 오른쪽으로 이동

---

문제 3 : 원상 복구(small)  (https://www.acmicpc.net/problem/21858)

- 난이도 하, 구현, 시뮬레이션

 

핵심 아이디어

 - 카드의 원래 배치를 찾기 위해 단순히 배열의 값을 거꾸로 되돌릴 수 있다

 - 이 경우 시간 복잡도는 O(NK)이므로, 입력 조건상 문제를 해결할 수 있다.

 

---

문제 4 : 원상 복구(large)  (https://www.acmicpc.net/problem/21863)

- 난이도 중, 그래프 이론, 사이클 분할

 

핵심 아이디어

 - 카드들은 사이클을 형성하는 여러 개의 그룹으로 분리할 수 있습니다.

  - 사이클이 발견될 떄마다 결과를 구하는 방식을 반복한다.

 

 - 카드를 하나씩 확인한다

  - 해당 카드부터 출발하여 사이클이 형성될 떄 까지 이동한다.

  - 사이클이 형성되면 사이클에 포함된 카드들을 모두 처리한다

 - 이미 처리된 카드는 건너 뛰면서 모든 카드를 확인한다.

---

문제 5 : 가희야 거기서 자는거 아니야 (https://www.acmicpc.net/problem/21771)

- 난이도 하, 구현, 기초 문법 

 

핵심 아이디어

 - 배개의 일부가 가희에게 의해 가려져 있다면, 가희가 배게 위에서 자고 있습니다.

  -  따라서 전체 배열에서 P가 몇 번 등장하는지 확인하면 된다.

---

문제 6 : 폴더 정리 (small) (https://www.acmicpc.net/problem/21860)

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

 

핵심 아이디어

 - 폴더 자료구조를 정의

 - 각 폴더는 다음의 정보를 포함해야 한다

  1. 하위 파일들

  2. 하위 폴더들

 - 재귀 함수를 이용해 하위 폴더에 접근하여 모든 파일 데이터에 접근할 수 있습니다.

 

---

문제 7 : 폴더 정리 (large) (https://www.acmicpc.net/problem/21861)

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

 

핵심 아이디어

 - 폴더 자료구조를 정의

 - 각 폴더는 다음의 정보를 포함해야 한다

  1. 하위 파일들

  2. 하위 폴더들

 - 재귀 함수를 이용해 하위 폴더에 접근하여 모든 파일 데이터에 접근할 수 있습니다.

 

 

46일차 인증

 

 

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

https://bit.ly/37BpXiC

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