알고리즘
1.[Java] 델타를 이용한 2차원 배열 탐색 (자바 | Java)
DFS/BFS 문제를 접하다 보면(기본적인 예로 미로찾기, 그림 등) 좌표의 성질을 갖는 특정 원소에서 다른 원소로의 이동이나, 그 주변(4방, 8방)을 탐색 하는 로직 구현이 자주 사용된다.일반적으로 좌표를 생각한다면, 다음과 같이 수학에서의 1사분면 좌표를 떠올리게
2.[Java] BFS - 너비 우선 탐색 구현 (자바 | Java)
BFS는 너비 우선 탐색이라고도 부르며, 코딩테스트에서 빈번하게 나오는 알고리즘이다.가까운 노드 부터 우선적으로 탐색하며, 기본적으로 그래프 탐색에 사용된다.두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고자 할 때 주로 사용된다.BFS는 자료구조 큐(Queue)를
3.[Java] 구간 합 구하기 (자바 | Java)
구간 합은 합 배열을 이용하여 구하는 알고리즘이다.구간 합을 활용하기 위해선 먼저 합 배열을 구해야 한다. 배열 A가 있을 때합 배열 S는 다음과 같이 정의 된다.A0부터 Ai까지의 합 SSi = A0 + A1 + A2 + ... + Ai - 1 + Ai이렇게 합 배열
4.[Java] Union-Find 유니온-파인드 구현 (자바 | Java)
유니온-파인드는 그래프 알고리즘 중 하나이다. '합집합 찾기' 라는 의미를 가지고 있다.서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다.여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프(집합)에 속해있는지 확인하는
5.[Java] LCS - Longest Common Substring / Longest Common Subsequence (자바 | Java)
LCS는 통상 Longest Common Subsequence의 준말로, 최장 공통 부분수열을 의미한다.그러나 이와 비슷하게 최장 공통 문자열인 Longest Common Substring도 존재한다.이 둘의 차이점은 아래와 같다.Substring : 전체 문자열에서