모임사진

14:00~15:30 백준 과제 문제 코드, 알고리즘 리뷰

• 회전 초밥

  • 투 포인터를 정해두고 이동하며 풀면 된다.
  • 인덱스를 처리하는 과정에서 k개만큼 뒤에 초밥을 추가할 수도 있고, (i+k-1)%6으로 인덱스를 처리할 수도 있다.
  • 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다. → 오해의 소지가 충분히 있는 것 같다.

• 신입 사원

  • 그리디 풀이 방법

    • (5 5)를 스택에 넣는다

      

    • (4 1)은 (5 5)보다 서류심사, 면접시험 순위가 모두 높기 때문에 (5 5)를 제거하고 (4 1)을 스택에 추가한다.

      

    • (3 2)는 (4 1)보다 면접시험 순위가 낮기 때문에 스택의 변화 없이 (3 2)를 추가한다.

      

    • 마찬가지로 (2 3)과 (1 4)를 추가하면 위와 같고, 정답은 스택의 사이즈인 4이다.

      

• 테트로미노

  • DFS라는 것을 연상하기 힘들었던 문제
  • ‘ㅜ’자 모양 테트로미노를 잘 처리해주어야 한다.

• 할로윈의 양아치

  • Union-Find와 DP(배낭 문제)를 합쳐놓은 문제이다.

15:30~17:00 코딩테스트 기출문제 풀이

• 1주차 오프라인 코딩테스트 문제 (카카오)

  • 지훈,종빈 - 포기
  • 민제 - 성공

  

• 풀이방법 (설명이 쉽지 않다…)

  1. 루트부터 시작하여 방문 가능한 다음 노드를 next에 추가한다.
  2. next에 visited를 true로 설정해주고 재귀를 진행한다.
  3. 재귀를 진행한 후에는 visited를 false로 되돌리고 다음 next 재귀를 진행한다.

1. 0번에서 1, 8을 next에 넣는다.
2. visited[1]을 true로 설정하고 solve(1)을 진행한다.
3. solve(1)을 다 처리한 후 visited[1]을 false로 설정한다.
4. 이어서 visited[8]을 true로 설정하고 solve(8)을 진행한다.

각자 공부 사항 및 소감

• 김민제
• 노종빈