백준 - 비슷한 단어 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();..
자료구조 정리 With JAVA
이번 블로그에서는 자료구조 정리를 자바를 기준으로 해보려고 한다. 우선, 자바의 전체 자료구조를 보면 아래와 같다. 그 중에서도 대표적인 자료구조는 아래와 같다. 1. 선형 자료구조 - 종류 : 연결리스트, 벡터, 배열, 스택, 큐 1-1. 연결 리스트 - 데이터를 감싼 노드를 포인터로 연결한 자료구조 - 삽입, 삭제가 빠르지만, 접근 및 탐색은 느려진다. 시간 복잡도 - 삽입 삭제 : O(1) - 접근, 탐색 : O(N) 싱글 연결 리스트 - next 포인터만 가진다. class Node{ Node next; } 이중 연결 리스트, 원형 이중 연결 리스트 - prev, next 포인터를 가진다. - 원형 이중 연결 리스트는 처음과 끝 노드도 연결한다. class Node{ Node prev; Node ..
백준 - 내리막길
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까지 가는 경우의 수를 구하라 - 백준 점프 문제와 유사하다. ..
