목록java (150)

땀두 블로그

FloydWashall 알고리즘

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 이 알고리즘의 핵심은 '거쳐가는 정점'을 기준으로 판단하는 것이다. 쉽게 말해 i->j로 이동 시 i->k->j의 방식이 가능한지에 대한 판단을 하는 것이다. 이 알고리즘은 3중 for문을 이용하여 시간복잡도는 O(N^3)으로 비교적 속도가 오래걸리지만 input의 범위가 작은 경우 쉽게 문제를 해결할 수 있는 알고리즘이다. import java.util.Scanner; public class floydWarshall { static int INF = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in..
알고리즘 2022. 3. 23. 07:52
트리(tree)

트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0 트리를 간단히 자바 코드로 구현하면 아래와 같이 구현이 ..
알고리즘 2022. 3. 23. 07:52
[백준] 3048번 - 개미

문자열 문제이다. a배열과 b배열이 서로 마주치는 부분이 있는 경우에만 인덱스를 변경시키기 때문에 이것을 판단하기 위한 boolean 배열을 두어서 두 값이 다른지를 판단하였다. 또한 그렇게 판단되어서 값을 바꾸게 되면 반복문 내부 loop를 돌면서 1 증가되는 값이면 새로 변경된 인덱스를 탐색하기 때문에 1을 추가로 더해주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p3048 { public static void main(String[] args) throws IOException { // T..
알고리즘/백준 2022. 3. 22. 08:03
[백준] 1235번 - 학생 번호

문자열 매칭 문제이다. 문자열의 끝에서부터 유일한 값들을 가지게 할 수 있는 집합을 만들어야 하므로 HashSet을 이용해주었고, 한 번의 탐색이 끝나면 HashSet을 초기화하고, 인덱스와 문자의 길이를 변경해주어서 탐색하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; public class p1235 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedRe..
알고리즘/백준 2022. 3. 22. 08:02
[백준] 1120번 - 문자열

문자열 매칭 문제이다. 2중 for문을 이용해서 시작점을 지정해주고, 시작점부터 A의 길이만큼 매칭되는지 유무를 판단하여 count값을 만든다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p1120 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..
알고리즘/백준 2022. 3. 22. 08:02
Prev 1 2 3 4 5 6 7 8 ··· 30 Next