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

패스트 캠퍼스 자체 문제 제작 - 2,3

 

문제 1 : 학부 연구생 민상( https://www.acmicpc.net/problem/21922 )

 - 문제 내용 링크 참조

 

구현 아이디어

 1. 바람이 물건에 부딪혔을 때, 방향이 바뀌는 기능을 정확히 구현

   - 바람의 현재 상태를 (i,j 방향) 으로 표현 

   - 방향은 상,하,좌,우 가 존재

 2. 시뮬레이션을 위해 이미 방문한 적이 있는 위치를 기록

  - 따라서 방문된 위치 정보를 3차원 배열 visited[i][j][dir] 형태로 관리

 

단순한 시뮬레이션 문제이므로, 반복문을 사용하거나 DFS/BFS를 이용하여 자신의 기호에 따라 탐색 진행 

 

---

문제 2 : 곡예비행( https://www.acmicpc.net/problem/21923 )

 - 문제 내용 링크 참조, 다이나믹 프로그래밍

 

구현 아이디어

 

 1. 다이나믹 프로그래밍을 2번 수행

   - 상승 비행에 대한 최대 비행 점수 계산

   - 하강 비행에 대한 최대 비행 점수 계산

 2. 두 개의 다이나믹 프로그래밍을 완전히 별도로 수행한 뒤에, 나중에 결과를 합침

 

---

문제 3 : 도시건설( https://www.acmicpc.net/problem/21924 )

 - 문제 내용 링크 참조, 최소 신장 트리

 

구현 아이디어

 1. 모든 건물이 도로를 통해 연결되도록 한다.

  - 단, 도로의 비용 합이 최소가 될 수 있도록 한다

 최소 간선 트리를 활용하여 간단히 해결 가능한 문제

 크루스칼 알고리즘 사용 

---

문제 4 : 짝수 팰린드롬( https://www.acmicpc.net/problem/21925 )

 - 문제 내용 링크 참조, 그리디 알고리즘, 다이나믹 프로그래밍

 

구현 아이디어

- 원소를 하나씩 확인하며, 해당 위치에서 시작하는 최소 크기의 짝수 팰린드롬을 찾으시오

  - 최소 크기를 고려하는 이유 : [1,1,3,5,5,3,1,1] 수열을 확인

  - 모든 원소는 짝수 팰린드롬에 포함 되어야 한다

    - 따라서 해당 위치에서 짝수 팰린드롬이 만들어지지 않으면 종료

---

문제 5 : 작업( https://www.acmicpc.net/problem/21937 )

 - 문제 내용 링크 참조, 깊이 우선 탐색, 너비 우선 탐색, 난이도 하

 

구현 아이디어

 - 작업 X를 끝내기 위해서는 작업 X 전에 먼저 해야 하는 작업들을 수행해야 한다.

 - 따라서 작업 X를 기준으로 DFS나 BFS를 수행하여 문제를 해결할 수 있다

   - 간선의 방향을 반대로 고려한 뒤에 작업 X에서 부터 너비우선탐색(BFS)를 수행해보시오

---

문제 6 : 영상처리( https://www.acmicpc.net/problem/21938   )

 - 문제 내용 링크 참조, 깊이 우선 탐색, 너비 우선 탐색, 난이도 하

 

구현 아이디어

 - 먼저 세가지 색상에 대하여 평균을 구하고, Threshold 값 기준으로 값을 갱신

   - 값이 255인 픽셀에 대하여 연결요소의 개수를 구한다

---

문제 7 : 문제 추천 시스템 Version1( https://www.acmicpc.net/problem/21939   )

 - 문제 내용 링크 참조, 자료구조, 구현 , 난이도 중

 

구현 아이디어

 - 문제에서 요구하는 대로 추천 시스템 구현

 - 우선순위를 다룰 수 있는 자료구조 필요

   - 우선순위에 따라서 데이터를 저장

   - 우선순위에 따라서 데이터를 조회(출력)

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

  - 중복된 값을 저장하지 않음

  - 기본적으로 데이터를 정렬된 상태로 관리 (우선순위 처리 가능)

---

문제 8 : 가운데에서 만나기 ( https://www.acmicpc.net/problem/21940   )

 - 문제 내용 링크 참조, 최단경로, 플로이드 워셜 , 난이도 중

 

구현 아이디어

 - 왕복 시간 : 도시 X로 이동했다가 다시 돌아오는데 걸리는 시간

 - 해당 문제는 플로이드 워셜 알고리즘 이용으로 해결

   1. 모든 도시에 대하여 다른 모든 도시로의 최단거리 계산

   2. D[C][X] + D[X][C]의 최댓값이 가장 작은 도시 X를 출력하면 정답

 

 

 

 

해당 문제들의 구현은 메모장에 따로 관리하며 요구사항 및 구현 아이디어를 한번씩 다시 읽고 구현을 계속 반복해야 한다

 

44일차 인증

 

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

https://bit.ly/37BpXiC

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