패스트캠퍼스 챌린지 34일차
[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.
백준 2606번 문제 : 바이러스
문제 해석
2. 데이터의 크기는 정점 = 100, 간선 = 100개이다. O(N^3)의 시간 복잡도 내에 풀이 가능하다.
문제 풀이
1. 전형적인 그래프 문제로 DFS, BFS 알고리즘을 통해 네트워크 연결 상태를 확인한다.
2. 인접 정점 리스트와 방문 리스트를 생성한다.
3. 재귀 또는 반복문을 통해 연결되어 있는 모든 정점을 방문한다.
복기
1. BFS와 DFS를 구현하였다. 모두 반복문을 활용하였고 BFS는 큐 자료구조를, DFS 스택 자료구조를 이용했다.
2. 성능은 DFS가 높게 나왔는데 코드 길이에서는 큰 차이가 없다. deque와 list에서 성능 차이가 있었을 것 같다고 생각했는데, 강의에서는 컴퓨터의 수가 적으므로 재귀 함수 최소 호출과 코드가 짧아 DFS가 유리하다고 했다.
3. 반면에 데이터가 많을 경우 BFS가 유리하다고 한다. 재귀 함수를 호출하게 되면 연산도 그만큼 늘어나기 때문이다.
백준 1012번 문제 : 유기농 배추
문제 해석
1. 시간 제한은 1초, Python3 기준 2,000만번 연산 가능하다.
2. 입력 데이터는 배추 밭 가로 길이 = 50, 세로 길이 = 50, 위치 개수 = 2,500, 배추 위치 = 50개가 주어진다.
3. 인접해 있는 배추들의 수를 구하면 이에 필요한 지렁이 수를 구할 수 있다.
문제 풀이
1. (X, Y)의 튜플 형태의 위치 값을 활용한다.
2. 인접한 배추들의 수를 구하기 위해 연결 상태를 확인한다.
3. 이를 위해 DFS 또는 BFS 알고리즘을 사용한다.
복기
1. 좌표가 주어진 문제를 풀 경우 directions를 통해 상, 하, 좌, 우에 대한 이동값을 넣어줄 수 있다.
2. 각 좌표를 돌며 방문 표시를 해주어 다음 탐색에서 제외시켜준다.
백준 1325번 문제 : 효율적인 해킹
문제 분석
1. 시간 제한은 5초로, Python3 기준 1억번 연산 가능하다.
2. 입력받는 데이터는 N = 10,000, M = 100,000개이다.
3. 컴퓨터를 최대로 많이 해킹할 수 있는 경우, 그 시작 컴퓨터 번호를 찾아낸다.
문제 풀이
1. 컴퓨터와의 연결 상태는 신뢰성에 따라 단방향으로 이루어 진다.
2. 이에 따라 정점 및 간선 연결을 해주고 dfs, bfs 알고리즘을 통해 풀이한다.
복기
1. 제한 시간이 5초라 여유가 있을 것으로 판단했는데, bfs 알고리즘 이외에도 최댓값을 구하는 과정에서 for문이 적용돼서 시간이 제한적이었다.
2. 최댓값을 구하기 위해 여러가지를 시도했었는데, 시간 초과가 발생하여 강의를 참고하여 진행했다. 강의에서는 조건문을 분기하여 갱신을 해줬던 것이 참신했는데 이러한 부분을 잘 활용한다면 시간복잡도를 최소화할 수 있겠다.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.