java

[알고리즘] 4485. 녹색 옷 입은 애가 젤다지?

작성자:
Featured image for [알고리즘] 4485. 녹색 옷 입은 애가 젤다지?

0. 문제 4485번: 녹색 옷 입은 애가 젤다지? 1. 문제 이해 2. 제출 가. Dijkstra algorithm – FOR문으로 구현 나. Dijkstra algorithm – PQ로 구현 그래프의 밀집도가 낮아서 PQ로 구현하는 것이 더 유리했던 것 같다. 왠만하면 PQ로 먼저 구현하도록 하자.

[Java] DP – 응용

작성자:
Featured image for [Java] DP - 응용

1. 이항 계수 구하기 가. 이항 계수 조합으로 이항 계수를 구할 수 있다. 위와 같이 일반화할 수 있다. 나. 조합 공식 조합 공식 – 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다. 이는 재귀 함수로 구현할 수 있다. 중복되는 계산을 줄이기 위해서 메모이제이션을 활용한다. 순수 함수, 중복 부분문제 구조, 최적 부분문제 구조를 만족하기 때문에 … 더 읽기

[Java] Memoization, DP

작성자:
Featured image for [Java] Memoization, DP

1. Memoization 가. 피보나치수열 피보나치수열의 점화식이다. fib1, fib2 … 등이 중복 호출이 발생한다. fib()는 순수 함수다. 💡 순수 함수 그렇기 때문에 fib1, fib2, … 등을 계산 결과는 항상 일정하다. 한 번만 계산하고 결괏값을 재사용할 수 있다. 나. Memoization 하지만 이 방식은 memo라는 추가적인 메모리 공간이 필요하다. 재귀 함수 호출과 memo 저장을 위해서는 많은 메모리를 사용한다. … 더 읽기

[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()에서 가능한 부분집합이 없거나 하나인 경우를 빠르게 걸러낼 생각이었다. 하지만 실제 구현하고 보니 시간복잡도도 상승하고 코드도 더 많이 복잡해졌다. 나. 개선 다. 참고 강사님 코드.