문제 링크 : https://www.acmicpc.net/problem/2193 이 문제는 동적 계획법(DP)을 사용하면 해결할 수 있는 기본적인 문제이다.DP의 핵심은 문제를 작은 부분으로 나누고 그 부분들을 이용하여큰 문제를 해결하는 것이다.이 과정에서 점화식을 이용하게 되는데, 이때 점화식은 유일하게 존재하는 게 아닌 푸는 사람마다 다른 점화식을 도출할 수 있다. 먼저 문제의 조건을 살펴보면이친수의 시작조건은 무조건 1이어야 한다. 또한 1이 연속으로 나올 수 없다.이런 조건을 가지고 그림을 그려가며 조건을 시각화해보면 아래와 같다. 위와 같이 1은 0으로만, 0은 0과 1로 변형할 수 있다는걸 알 수 있다.이때 1과 0을 각각의 DP배열로 만들거나 2차원 배열을 통해 해결할 수도 있지만하나의 1차..

문제 링크 : https://www.acmicpc.net/problem/1991 이 문제는 이진트리를 활용해서 푸는 문제이다.문제에 들어가기 전 이진 트리에 대해 알아보자 이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.편향 이진 트리는 노드들이 한쪽으로 편향돼 생성된 이진 트리이고,포화 이진 트리는 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리,완전 이진 트리는 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은왼쪽부터 채워진 트리이다. 보통 이렇게 트리를 배열로 표현하는 것이 일반적인데 이렇게 했을 때편리한 점은 아래 정리한 표와 같이 부모 노드, 자식 노드들의 인덱스값을 편하게 계산할 수 있다.이동 목표 노드인덱스 연산제약 조건(N = 노드 개..

문제 링크 : https://www.acmicpc.net/problem/1068 문제 자체는 리프노드의 개수를 세는 문제로 단순하다.하지만 단순 리프노드를 세는 게 아닌 중간에 노드를 삭제했을 때 리프노드의 개수를 구해야 한다. 문제를 2가지 방법을 해결해봤다.첫 번째 방법첫 번째는 자식노드의 개수를 직접 카운팅 하여 자식노드가 없는 노드의 개수를 세는 방식이다.먼저 노드를 삭제하기 이전의 자식노드 개수로 counts배열을 초기화한다.이후 만약 2번 노드를 삭제한다면 2번 노드의 부모노드인 0번 노드의 자식개수를 1개 빼준다.그다음 2번 노드와 2번 노드의 자식들은 자식노드의 개수를 -1로 바꿔준다. package boj;import java.util.*;import java.io.*;public cla..

문제 링크 : https://www.acmicpc.net/problem/1414 문제를 살펴보면 해결하는 방법은 최소신장 트리를 이용하면 간단히 해결할 수 있다.주의해야 하는 것은 문자를 정수로 변경하는 것과A -> A로 돌아오는 간선은 제외하고 생각해야 한다는 것이다. 예제 입력 1번을 그래프로 표현하면 위와 같다. 문제를 해결하는 과정은 아래와 같다.1. 주어진 간선(랜선)의 총합을 구한다 (sum)2. 자기 자신에게 돌아오는 간선(랜선)을 제외하고 나머지 간선을 가중치를 기준 오름차순으로 정렬한다.3. MST알고리즘을 통해 모든 정점을 잇는 거리의 최단거리를 구한다(minSum)4. 만약 고른 간선의 길이가 주어진 정점의 개수 - 1 개가 아니라면 -1을 출력하고, 맞다면 sum - minSum 값..