[강의]백준 알고리즘 4회차

문제

확장게임 (16920, hard)

• 거리를 구해야하므로 BFS를 이용한다.
• 각각의 사람마다 bfs를 확장할 수 있을때까지 반복

풀이1. 시간이 오래 걸림

필기자료 참조..

시작점을 반복해서 찾는 것이 비효율적이다

• N+1번째 BFS의 시작점은 N번째 BFS의 종료시점에서 구할 수 있다.

TIP1. Queue는 P개를 만드는게 좋다 ㅎㅎ.. (다음 BFS의 시작점을 담아두기 위한것도 따로)

TIP2. BFS 종료시점을 알 수 없으므로 WHILE(1)

• 플레이어1.
  1. 시작점을 구해야한다. 모든 칸을 조사한다.(NM)
  2. BFS 실행(NM)
• 플레이어2.
  1. 시작점 찾을 필요 없다
  2. BFS 실행(NM)

BFS 스페셜 저지(16940, BFS), DFS 스페셜 저지(16964, DFS)

• 트리와 노드의 순서를 받은 뒤, BFS를 실행했을 때 노드의 순서와 동일한 지 비교하는 문제.

조금 어려울 수도 있겠다…(DX,DY 2차원행렬을 생각하면? 근데 트리니까 좀 쉬운가.)

풀이1. 어쩔 수 없이 BFS를 직접 실행(QUEUE에서 꺼낼 때 순열과 비교)

• 시작점과의 거리차이를 기반으로 문제를 풀면 쉬워보이지만 안된다.
• queue를 사용해서 조금 문제가 생기는 것!

풀이2. 입력으로 주어진 순서를 이용해서 인접리스트를 정렬한다.

시간복잡도 계산 연습

십자가 2개 놓기(17085)

• 1. 십자가를 구하는 방법
  1. 가능한 중심의 개수(NM)
  2. 가능한 크기의 개수= min(N,M)/2

십자가 2개를 다 구하려 해도 1,000만개 이하이다. 그래서 6중포문 ^오^..

아기상어2(17086, BFS, EZ)

• 결론적으로 BFS로 거리를 구하는 문제.

숨바꼭질 6(17087, GCD)

• 안풀거에요~

등차수열 변환(17088)

• 모든 경우의 수를 다 할 경우 3^100,000으로 절 대 풀 수 없 음.
• 첫 번쨰, 두 번째 수만 정해놓으면 아주 간단해진다.
• 예외1. 두 번째 수가 없는 경우는 따로 처리하라.

TIP: INPUT=1개, OUT=1개이면 1~N까지 브루트포스로 쭉 구하고 IF문으로 전부처리가능ㅋㅋㅋ

세 친구(17089, divide and conquer)

• nC3 = O(N^3) 불가능. (N<=4000)
• ..?

DP수업 조금

• 점화식 없는 DP , 홍철없는 홍철팀

BOJ거리(12026, DP)

• 이전의 행위가 다음 이벤트에 영향을 주지 않는 경우. (답이 정해진 경우)

달리기(16930, 새로풂, BFS)

풀이1. 일반적인 풀이법? (시간이 오래걸림)

• 일반적인 bfs는 해결불가
• visited이어도 다시 방문해야 할 수도 있다.
• 따라서 visited를 사용하지만! 방향까지 저장해야한다.

슬라이드 준비해서 따로 써주신다고 한다~

체스판 위의 공(16957, DP)

• 각 칸별로 다음 이동지를 저장해놓고 다시 사용한다.
• 정확히는 UNION FIND 라는 자료구조임

미로탈출하기(17090)

• 미로에서 탈출 가능한 칸의 개수를 구하는 문제.
• 탈출 = 미로의 범위를 벗어나는 이동

견우와 직녀(16137)

• 안풀어요~.
• 문제 설명이 매끄럽지는 않다 ^^,,, 조심
• 모든 빈칸을 오작교로 만들고 이들을 모두 계산하여 그 중 최소값을 출력하면 된다.
• 모든 칸에는 언제 도착했는지 정보가 필요하다.
• 단, 그 정보는 MOD 연산(오작교의 주기)이 끝난 값으로 저장하면 된다.