Algorithm

[Java] 최단 경로

작성자:
Featured image for [Java] 최단 경로

1. 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로. 2. Dijkstra 알고리즘 가. 반복문으로 구현 다익스트라 알고리즘은 음의 가중치가 없는 그래프를 전제조건으로 가진다. 음의 가중치가 없기 때문에 매 순간 시작점에서 가장 가까운 정점의 비용은 더 이상 감소하지 않는다. Prim과 굉장히 비슷하다. Prim과의 차이점은 최소 비용을 계산하는 … 더 읽기

[알고리즘] 3124. 최소 스패팅 트리

작성자:
Featured image for [알고리즘] 3124. 최소 스패팅 트리

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal 나. Prim – PQ

[알고리즘] 1251. 하나로

작성자:
Featured image for [알고리즘] 1251. 하나로

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 이 문제는 모든 노드가 서로 연결될 수 있는 완전 그래프다. 따라서 많은 간선이 생길 수 있다. (E의 최대 개수 = (V(V-1))/2)) 밀집 그래프에서 유리한 반복문으로 구현한 Prim 알고리즘으로 문제를 풀어본다. But! PQ로 구현한 Prim 알고리즘으로 … 더 읽기

[알고리즘] 17471. 게리맨더링

작성자:
Featured image for [알고리즘] 17471. 게리맨더링

0. 문제 17471번: 게리맨더링 1. 문제 이해 2. 제출 가. 통과 solve()에서 가능한 부분집합이 없거나 하나인 경우를 빠르게 걸러낼 생각이었다. 하지만 실제 구현하고 보니 시간복잡도도 상승하고 코드도 더 많이 복잡해졌다. 나. 개선 다. 참고 강사님 코드.

[알고리즘] 15683. 감시

작성자:
Featured image for [알고리즘] 15683. 감시

0. 문제 15683번: 감시 1. 문제 이해 2. 제출 감시되는 공간을 #이 아니라 감시하는 cctv의 수를 저장한다. #으로 방문 체크를 수행하면 원상 복구가 어렵다. (하나의 공간에 여러 cctv가 감시 중인 경우) 수를 더하고 빼는 것으로 쉽게 방문 체크와 원상 복구를 수행할 수 있다. 이때 사용하는 숫자가 벽(6), cctv(1, 2, 3, 4, 5)와 겹치지 않도록 -2, … 더 읽기

[알고리즘] 7465. 창용 마을 무리의 개수

작성자:
Featured image for [알고리즘] 7465. 창용 마을 무리의 개수

  0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! c++로 푼 적 있는 문제다. java로 다시 풀어보고, Union-Find로도 풀어보았다. 1. 문제 이해 2. 제출 가. DFS 나. Union-Find