패스트캠퍼스 챌린지 35일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

 

백준 10282번 문제 : 해킹

 

 

문제 해석

1. 시간 제한은 2초, Python3 기준 약 4,000만번 연산이 가능하다.

2. 입력되는 데이터의 최대 개수는 컴퓨터(vertex) 10,000개, 의존성(edge) 100,000개 그리고 해킹 당한 컴퓨터 100,000개가 주어진다.

3. 컴퓨터와 의존성에 따라 감염될 컴퓨터의 수 그리고 그에 걸리는 시간을 구한다.

 

문제 풀이

1. 기본적인 다익스트라 최단 경로 알고리즘 문제이다.

2. 우선순위 큐를 사용하여 시간 복잡도 O(NlogD)로 해결할 수 있다.

 

 

복기

1. 정점과 간선 그리고 가중치 형태의 그래프를 그릴 수 있을 경우, 다익스트라 알고리즘을 사용할 수 있다. 이를 위해 인접 정점 리스트, 가중치 리스트 그리고 우선순위 큐를 생성하여 이용한다. 이때 가중치 리스트에는 무한 값으로 inf(1e9)로 값을 초기화 해준 뒤, 방문에 따라 갱신해주며 가중치를 찾아나간다.

2. 그래프를 그릴 수 있는지, 각 정점 간의 관계와 가중치 여부를 미리 파악할 수 있다면 어떤 알고리즘을 사용해야할지 판단이 잘 될 것 같다.

 

백준 5719번 문제 : 거의 최단 경로

 

 

문제 해석

1. 시간 제한은 1초이며, Python3 기준 약 2,000만번 내에 연산가능하다.

2. 거의 최단 경로를 찾는 문제로, 최단 경로를 제외한 경로 중에 가장 짧은 거리를 구하는 문제이다.

3. 데이터는 장소의 수 = 500, 도로의 수 = 10,000로 구성된다.

 

문제 풀이

1. 다익스트라의 최단 경로 알고리즘을 통해 거의 최단 경로를 찾는다.

 

 

 

복기

1. 다익스트라와 bfs를 통해 최단 경로를 한번 찾고 이를 제거해준뒤 다시한번 다익스트라를 통해 경로를 찾아주었다.

2. 강의를 참고하여 풀었으나 시간 초과가 발생했고, 어찌된 영문인지 강의에서 나온 코드 기록을 보니 시간 초과가 발생한 것을 확인할 수 있었다. 서버의 오류일지 모르겠으나 코드를 보완한 후 다시 풀어봐야겠다.

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.