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

류호석배 코딩테스트 2회

 

문제 1 : 폰 호석만 ( BOJ 21275 )

 • 출제 의도

  - 완전 탐색 접근을 통해서 모든 경우를 직접 하나하나 찾아내 보자

  - 본 문제에서 경우란, 조건을 만족하게 A,B를 모두 결정해보는것

  - 진법 변환을 구현 할 수 있는가?!

 

 완전 탐색 접근

  - 가능한 A,B의 조합 : (2,2) (2,3) ... (36,36)

  매 조합 마다 진법 변환을 수행

 

주의할 점

 1. 변환시에 2^63을 넘어가지 않는가

 2. 등장하는 문자가 진법으로 올바른가

---

문제 2 : 계보 복원가 호석 ( BOJ 21276 )

 • 출제 의도 

 - 관련 강의 : 그래프, 트리

   - 그래프의 정점이 문자열인 경우는 어떻게 하는가

   - 그래프, 그 중에서도 Rooted Tree에 대한 올바른 이해를 했는가

  

• 생각의 흐름 1 : 정점을 번호로 바라보기

  - 그래프의 간선을 저장하는 방식은 정점이 숫자일 떄 편하다

  인접 행렬 => con[i][j] = i번 정점과 j번 정점이 연결되어있다

  인접 리스트 => con[i].push_back(j)

  - 정점마다 주어지는 이름을 숫자로 바꾸고 싶다

   -> 자료구조 중 HashMap<String, Integer>를 사용하라

  - 문자열을 숫자로 바꿔서 저장하고, 원하는 문자열을 탐색하는 행위를 모두 0(1)에 수행해주므로 

    현재 상황에서 매우 좋은 자료구조

 

• 생각의 흐름 2 : Root 찾기

- 모든 정점이 자신의 조상을 기억한다

- Root 정점들은 조상이 존재하지 않는다, 즉 조상이 없는 정점들을 Root라 판단하면 된다.

 

• 생각의 흐름 3 : 직속 부모, 자식 관계 찾기

 - 어떤 정점이 자신의 조상을 전부 기억한다면?

  -> 자신의 Depth를 계산할 수 있다.

 - 모든 정점이 자신의 Depth를 안다면 부모 정점은?

  -> 자신보다 Depth가 1낮은 정점

 즉, Depth를 통해 조상들 중에 부모를 찾을 수 있다.

 

---

문제 3 : 짠돌이 호석 ( BOJ 21277 )

 • 출제 의도 

  - 2차원 배열이 주어졌을때

    1. 배열 평행 이동이 능숙한가?

    2. 배열 돌리기가 능숙한가?

  두가지에 대한 구현력 확인 문제

 

• 생각의 흐름 1 : 비교 순서

  - 먼저, 두 퍼즐을 모두 회전시켜 볼 필요가 있을까?

   -> 아니다. 첫번째 퍼즐은 고정시키고 두번째 퍼즐만 4방향 회전을 시켜도 된다.

 

• 생각의 흐름 2 : 배열 회전

• 생각의 흐름 3 : 평행 이동

 

시간/공간 복잡도

 1. 4번의 회전

 2. 가로 방향으로 약 100번의 이동 가능성 

 3. 세로 방향으로 약 100번의 이동 가능성 

 4. 배열 전체에 대해 겹치는 부분 확인 O(NM) 

  총 연산 횟수는 4 * 100 * 100 *50 * 50= 1억에 비례

 

---

문제 4 : 호석이 두마리 치킨 ( BOJ 21278 )

 • 출제 의도 

 - 문제를 올바르게 이해 했는가

 - 모든 거리 관계를 파악할 줄 아는가? 전처리를 통해 계산하는것을 떠올린는가?

 - BFS를 통한 최단 거리를 떠올리고 구현하는가?

 

• 생각의 흐름 1 : 최단 시간 키워드 발견

  -> 최단 거리 알고리즘

• 생각의 흐름 2 : 가능한 모든 조합으로 치킨집을 세워보기

• 생각의 흐름 3 : 두 건물 x와 y 사이의 최단거리 dist(x,y) 

  -> 문제점 발생 : dist함수가 너무 많이 호출됨

      해결책 : 미리 계산해 놓을 수 있다면 O(1)에 dist(x,y)를 가져온다 

      D[i][j] = i에서 j로 가는 최단 거리

 

시간/공간 복잡도

 - 전처리를 통해 불필요한 시간 증가를 해소, 이를 통해 O(N^3)으로 문제 해결

 

 

 

 

 

 

48일차 인증

 

 

 

 

 

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

https://bit.ly/37BpXiC

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