문제 링크 : 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/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/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..