DFS (깊이 우선 탐색) 소개 Root Node 혹은 다른 임의의 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack과 재귀함수(Recursion)으로 구현한다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 사용용도 경로찾기 u, v가 주어졌을 때 u -> v로 가는 경로를 찾을 때 그래프의 사이클을 찾을 때 back edge 즉, 순환을 만들어 주는 마지막 edge를 찾는다. 시간복잡도 두 가지의 자료구조(인접 리스트, 인접 행렬)로 구현할 수 있다. 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V)..

BFS (너비 우선 검색) 정리 소개 Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i

동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 ..

지난번 포스팅을 참조하면, 배열을 List로 변환할 때, Arrays.asList() 메소드를 사용하면 됩니다. 하지만, 배열의 원소가 int와 같은 primitive type인 경우 Arrays.asList()는 좀 다른 결과를 리턴합니다. 0. Arrays.asList()로 int 배열 변환하기 - Fail 코드 import java.util.Arrays; import java.util.List; public class IntArrayConvertToList { public static void main(String[] args) { // int 배열 int[] arr = { 1, 2, 3 }; // Arrays.asList() List intList = Arrays.asList(arr); // 결과..

배열을 List로 Arrays.asList() new ArrayList(Arrays.asList()) Collectors.toList() ArrayList를 배열로 toArray() - java.util.List 배열을 List로 1. Arrays.asList() 코드 import java.util.Arrays; import java.util.List; public class ArrayConversion { public static void main(String[] args) { String[] arr = { "A", "B", "C" }; // 배열 -> List로 변환 List list = Arrays.asList(arr); System.out.println(list.get(0)); // "A" Sys..

Character toCharArray() String을 char 배열로 변환하는 것 이 메소드를 활용해 자리변환등을 할 수 있었다. char[] chars = string.toCharArray(); isUpperCase() / isLowerCase() 해당 문자가 대문자/소문자인지를 확인하는 메소드 toUpperCase() / toLowerCase() 해당 문자를 대문자/소문자로 변환하는 메소드 isAlphabetic() 해당 문자가 알파벳인지 확인하는 메소드 isDigit() 해당 문자가 숫자인지 확인하는 메소드 getNumericValue() 해당 문자가 숫자인지 확인하는 메소드 char c1 = '3'; Character.getNumericValue(c1) // 3

리턴 타입 메소드 이름(매개 변수) 설명 char charAt(int index) 특정 위치의 문자를 리턴합니다. boolean equals(Object anObject) 두 문자열을 비교합니다. byte[] getBytes() byte[]로 리턴합니다. byte[] getBytes(Charset charset) 주어진 문자셋으로 인코딩한 byte[]로 리턴합니다. int indexOf(String str) 문자열 내에서 주어진 문자열의 위치를 리턴합니다. int length() 총 문자의 수를 리턴합니다. String replace(CharSequence target, CharSequence replacement) target 부분을 replacement로 대치한 새로운 문자열을 리턴합니다. Strin..

String -> int (문자열을 숫자로) String 문자열을 int로 변환하기 위해서는 java.lang.Integer 클래스의 parseInt()와 valueOf() 메소드를 사용할 수 있습니다. Integer.parseInt() static int parseInt​(String s) java.lang.Integer 클래스의 static 메소드인 parseInt() 메소드는 파라미터로 숫자로 변환할 문자열을 입력받고, 입력받은 문자열을 integer로 변환한 int 값을 리턴합니다. 코드 public class StringToInt { public static void main(String[] args) { String str1 = "123"; String str2 = "-123"; int int..

java 배열 메소드 정리 분류 메소드 명 return type 설명 배열 변환 Arrays.asList(array) List 해당 메서드는 배열(Array)을 기반으로 Collection 함수의 ArrayList로 형변환을 하여 반환해주는 함수입니다. 배열 복사 Arrays.copyOf(array, copyArrayLenght) T[] 해당 메서드는 배열 전체를 복사하여서 복사할 길이 만큼 지정하여 복사한 새로운 배열로 반환해주는 함수입니다. 배열 복사 Arrays.copyOfRange(array, startIntex, endIndex) T[] 해당 메서드는 원본 배열의 시작 인덱스와 끝 인덱스를 지정하여서 복사한 새로운 배열로 반환해주는 함수입니다. 배열 채우기 Arrays.fill(array, n)..

요즘은 그런 일이 잘 없지만 예전에는 프로그램을 짜면서 bit operation을 잘 써야하는 경우가 있었다. bit operation을 쓰는 이야라하면 bit operation이 대부분 가벼운 명령어로 + 정도의 로드를 가졌기 때문에 속도가 빨랐랐고, 컴퓨터가 bit를 기반으로 하기 때문에 코드 좀 더 깜끔하게 짤 수 있었다. 가끔 메모리가 부족할 때면 1byte 변수하나를 8개의 bit로 나눠 쓰려는 목적으로 사용하기도 했다. 요즘에야 컴퓨터도 좋아지고 자원이 넉넉해져서 효율적인 측면 보다는 프로그램의 구조적인 측면을 더 중요하게 보는 경향이 있어서 bit operation을 굳이 쓰지 않아도 되기 때문에 크게 쓸 일은 없지만 컴퓨터 아키텍쳐상 bit operation은 여전히 cpu 기본 opera..