문제 링크 : https://www.acmicpc.net/problem/11050 문제 자체는 매우 쉬운 문제이지만조합을 구하는 방법을 익혀볼 수 있는 문제이다. 조합을 구하는 과정을 간단히 알아보면 아래와 같다.조합의 수학적 정의는 위와 같고, 이는 n개 중에서 r개를 고르는데이때 순서는 상관이 없다는 의미이다. (1,2,3 이나 3,2,1 이나 똑같다) 우선 5개의 숫자가 있고 5개중에서 4개를 고르는 경우는 이미 계산했다고 가정한다.그렇게 5개중 4개를 골랐을 때 뽑힌 숫자가 1,2,3,4이다.이제 5개 중에서 3개를 고르는 경우를 생각해보면 아래와 같은 경우의 수가 있다. 아직 선택되지 않은 5를 선택하고 5개 중 4개를 골랐을 때 선택된 1,2,3,4 중에 2개를 선택하는 경우 또는 5를 선택하..

문제 링크 : https://www.acmicpc.net/problem/11725 이 문제는 트리를 구현하는 기본적인 문제이다.루트노드가 1번으로 고정되어 있기 때문에 그저 양방향 인접 리스트로 그래프를 표현하고1번 노드부터 탐색하며 부모노드를 찾아주면 된다. 예제 입력 1번을 그래프로 표현하면 위와 같다.여기서 루트노드가 1번이기 때문에 루트노드부터 시작해서4번 노드의 부모는 1번, 6번 노드의 부모는 1번2번 노드의 부모는 4번, 7번 노드의 부모는 4번이런 식으로 순차적으로 부모를 찾아주면 된다.이 과정에서는 DFS나 BFS를 사용하면 된다. 그래프를 리스트로 표현할 때는 방향이 없는 간선이므로 이와 같이 인접리스트로 표현해주면 된다. package boj;import java.util.*;impo..

문제 링크 : https://www.acmicpc.net/problem/11403 특정 정점에서 각 정점까지 연결이 되어있는지를 물어보는 문제이다.플로이드 워셜 알고리즘을 이용하면 되는데 여기서 이 문제는 최단거리를 물어보는 문제가 아니기 때문에 이 문제와는 다르게 최단거리를 업데이트해주는 부분만 변형해 주면 된다. 플로이드 워셜이 S부터 E까지의 최단 거리는 S와 E 사이에 있는 K 정점을 기준으로 S -> K + K -> E까지의 거리가 기존의 S -> E 까지의 거리보다 가깝다면 업데이트를 해주는 방식이었다. 이 문제에서는 S -> K 까지 연결되어 있고 K -> E까지 연결되어 있다면 S -> E는 연결되어 있다는 로직으로수정해 주면 된다. package boj;import java.util.*;..

문제 링크 : https://www.acmicpc.net/problem/11657 이 문제는 1번 도시에서 출발해서 각 도시까지의 최단 거리를 출력하는 문제이다. 여기까지만 보면 다익스트라 알고리즘을 이용하면 될 것처럼 보이지만다익스트라 알고리즘을 사용하기 위한 조건중 하나는 무조건 에지가 양수여야 한다는 것이다.하지만 이 문제를 조건을 보면 에지의 값이 음수도 가능하다. 따라서 다익스트라가 아닌벨만 포드 알고리즘을 사용해서 풀어야 한다. 벨만 포드 알고리즘은 시작 정점부터 각각의 정점까지의 최단거리도 구할 수 있지만 음수 사이클이 존재하는지여부도 알 수 있다. 예제 1번을 보면 위와 같이 음수 사이클이 생성되는 것을 알 수 있다. 벨만 포드 알고리즘을 수행하기 위해서 우선 거리배열을 선언하는데 이때 출..