Algorithm with Java

[알고리즘] 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

[Java] 최소 신장 트리

작성자:
Featured image for [Java] 최소 신장 트리

1. 최소 신장 트리 (MST) 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E … 더 읽기

[Java] 서로소 집합

작성자:
Featured image for [Java] 서로소 집합

1. 서로소 집합 Union-Find 연산이 핵심이다. 가. 연결 리스트로 구현 나. 트리로 구현 연결리스트보다는 트리로 많이 구현한다. (시간 복잡도에서 유리함.) 다. 연산 구현 1) Make-Set(x) 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산. 2) Find_Set(x) x를 포함하는 집합을 찾는 연산. 3) Union(x, y) x와 y를 포함하는 두 집합을 통합하는 연산. 2. 서로소 집합 – 최적화 … 더 읽기

[알고리즘] 풀었던 문제 (240220 ~ 22)

작성자:
Featured image for [알고리즘] 풀었던 문제 (240220 ~ 22)

2636. 치즈 2636번: 치즈 1987. 알파벳 1987번: 알파벳 2623. 음악프로그램 2623번: 음악프로그램 10026. 적록색약 10026번: 적록색약 2667. 단지번호붙이기 DFS Flood Fill 2667번: 단지번호붙이기 1238. Contact 그래프 BFS SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 15961. 회전초밥 그리디 알고리즘 슬라이딩 윈도우 15961번: 회전 초밥