모임사진

• 무상실

  

• 자율주행 스튜디오

  

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

• 1446 지름길

  • 다익스트라, dp등 많은 방법으로 풀리는 문제

  • 다익스트라

    • 각 미터마다 다익스트라 검사
    • 지름길이 있을 경우, 도착점에 가서 다익스트라 검사.
    • 계속해서 min 값을 찾아 업데이트하며 진행

  • dp

    • 처음에 dp를 최댓값으로 전부 초기화
    • 0부터 차례차례로 지름길로 가는게 빠른지 아닌지 검사하며 min값으 dp 값을 업데이트
    • 최종적으로 목적지에 해당하는 dp값이 답임.

    

• 1261 알고스팟

  • priority queue 사용방법
    • 벽을 가장 적게 부술 수 있는 경우를 기록해 우선순위 큐에 담음
    • 우선순위큐는 벽을 가장 적게 부술 수 있는 순으로 정렬되어있음.
      • 우선순위큐를 활용해 가장 벽을 작게 부술 수 있는 경우부터 bfs를 하게됨.
  • dp 사용방법
    • bfs를 하며 각 노드에 도달가능한 최소치를 기록해놓음.
    • 안부수고 도달가능한 지점을 방문하며, 주변의 노드들에 최소치를 업데이트

• 117799 최소비용 구하기 2

  • 연관된 문제 https://www.acmicpc.net/problem/1916
  • 기본적인 다익스트라 알고리즘 + 역추적
    • 다익스트라 알고리즘을 진행하면서 업데이트에 영향을 준 노드의 번호도 기록해 놓는다.
    • 업데이트에 영향을 준 노드를 역추적하며 순서를 찾는다.

• 9466 텀 프로젝트

  • DFS풀이방법

    • visit 배열을 만들어 각각의 탐색마다 방문여부 측정, 이미 방문한 노드에 반복된다면 사이클이 형성된 것.
    • done 배열을 만들어 다음 탐색에서 한번더 확인하는 일이 없게 함.

  • Union Find 풀이방법

    

    • 진입 차수가 0인 노드들을 삭제 (반복)
    • 전부 삭제 후에도 진입차수가 남아있는 노드들은 사이클을 형성 ⇒ 그룹형성
    • 그룹이 형성되지 않은 노드의 갯수를 세면 된다.

• 13460 구슬 탈출 2

  • 구슬이 겹칠 때 어떻게 처리하냐가 중요

    • 현진

      • 일단 둘다 이동시키고 구슬이 겹칠 때, 상황에 맞게 이동시킴

    • 종빈

      • 상,하,좌,우 경우를 나눠, 구슬의 위치를 비교해 먼저 이동시켜야 할 구슬을 정한뒤 순서대로 이동

    • 민제의 풀이 방법

      

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

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

  • https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=java

  푼사람 : 민제 못푼사람 : 종빈,지훈,현진 (집에서 풀어보기)

• 풀이방법

  1. 랜덤 생성된 노드는 어떤것인가?
     1. 위상정렬을 사용해 진입차수가 0이고 진출차수가 2인 노드를 구하면 된다
  2. 그래프의 형태를 어떻게 구별할 것인가?
     1. 진출 차수가 0인 노드가 있는 그래프 ⇒ 막대 형태
     2. 하나의 노드가 진출차수, 진입차수 모두 2 이상 ⇒ 8자형
     3. 전체그래프의 개수는 1에서 구한 노드의 진출차수
     4. c-b-a = 도넛모양 그래프의 개수

  

각자 공부 사항 및 소감

• 김민제
• 노종빈