백준 - 비슷한 단어 with JAVA
문자열 A와 B가 있다. 이 때, 문자 하나를 수정, 삭제, 변경해서 같은 문자열을 만든다. 예를 들어, ABC, ABCD 가 있다고 가정하자. [A, B, C, D]에서 [A, B, C]를 빼주면 [D] 만 남는다. 즉 1개만 바꿔주면 된다. 하지만, [A, B, C]에서 [A, B, C, D]를 빼주면 [] 가 되어 변경을 안해줘도 된다고 판단한다. 따라서 이를 주의해서 로직을 작성해야 한다. import java.util.*; // 비슷한 단어 public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String value = sc.next();..
백준 - 내리막길
DFS + DP 기본적으로 맵의 가로, 세로 최대는 500이다. 만약, (0, 0)에서 (499, 499)까지 간다고 가정하자 해당 경우의 수는 굉장히 커진다. 예를 들어, (0, 0)에서 (200, 200)으로 가는 경로가 10000이고 (200, 200)에서 (499, 499)까지 간다고 가정했을 때, 경로가 10000이라면 약, 10억가지의 경우의 수가 나온다. 밑의 두가지 코드의 차이점은 아래와 같다. 1번 코드 : (200, 200) 방문시 DP를 통해 (499, 499)까지 도달 가능하다고 판단하고 돌아간다. 2번 코드 : 항상 끝까지 방문한다. 위의 차이점으로 DP를 통해 시간복잡도를 낮출 수 있다. 추가사항 - 노드1에서 노드2까지 가는 경우의 수를 구하라 - 백준 점프 문제와 유사하다. ..
이코테 - 탑승구 with JAVA
해당 문제가 다른 문제들과 다른 점은 union연산에서 부모를 던진다는 점이다. 왜 부모를 던지는 것일까? 해당 문제의 로직을 살펴보면 만약 1~4 탑승구 중 하나에 착륙이 가능한 비행기가 들어온다면 탑승구 4와 탑승구 3를 union 한다. 이렇게 반복을 하다 부모의 값이 0이라면 착륙이 불가능하게 처리한다. 0을 만들기 위해서는 부모를 던져야 한다. 예를 들어, 2, 2 비행기가 들어왔다고 가정하자 초기 부모는 다음과 같다 [0, 1, 2, 3] 2 비행기 착륙 : 0, 1, 1, 3 2 비행기 착륙 : 0, 0, 1, 3 과 같이 된다. (부모를 던졌다는 가정하에) 따라서, 이 후, 추가적으로 2이하의 수가 들어오면 0을 반환하고 종료된다. 코드 package JAVA.TCT.GraphTheory;..
