OILAT

수강한 강의 Part 5. 패캠 제작 문제 풀이 Chapter 01. 문제풀이 - 나동빈의 패캠 제작 문제 해설 3 학습 후기 1. https://www.acmicpc.net/problem/21937 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 추천 풀이 시간: 30분 문제 유형: 깊이 우선 탐색, 너비 우선 탐색 문제에서 특정 작업 X를 끝내기 위해 우선으로 완료되어야할 작업들을 구하기에 간선의 방향을 반대로 한 뒤 작업 X에서부터 너비 우선 탐색(BFS)를 수행하여 문제를 해결한다. ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 2 학습 후기 그래프 탐색할 때 BFS를 사용하여 A에서 B까지 갈 수 있는지와 A에서 다른 경로까지의 최소 이동 횟수도 계산 가능하다. 단, 최소 이동 횟수만 말하는 거지 간선에 가중치가 포함되어 있다면 안된다. 최소 이동 횟수, 최단 시간 키워드가 존재하면 사용해볼 만하다. 1. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.n..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 1 학습 후기 격자형 그래프 해당 좌표를 중심으로 상, 하, 좌, 우를 확인해가며 이동할 수 있는 격자인지 확인 이때 중심 좌표를 기준으로 상, 하, 좌, 우 좌표는 {{1, 0}, {0, 1}, {-1, 0}, {0, 1}}을 사용하여 확인한다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ..

수강한 강의 Chapter 18 그래프 기본 탐색 알고리즘 - 너비 우선 탐색(BFS) - 깊이 우선 탐색(DFS) 학습 후기 알고리즘 문제 중에서 가장 빈번하게 나오는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대한 강의를 들었다. 알고리즘을 코드로 작성하기 전 강사님이 엑셀에서 BFS와 DFS가 어떻게 동작하는지 설명해주셨다. 일단 그래프는 HashMap과 ArrayList를 사용하여 전체 그래프를 표현하였다. 그리고 HashMap의 CRUD, Create(생성), Read(읽기), Update(수정), Delete(삭제)도 알려주셨다. 이 전체 그래프를 보면서 BFS를 어떻게 구현해 나가는지 설명해주셨다. 너비 우선 탐색(BFS) BFS는 자료구조 큐를 활용하여 해당 노드에 방문한 적이 ..