나눔코딩

정의 - 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 - 예) 집에서 회사로 가는 경로를 그래프로 표현할 때 용어 - 노드(Node) : 위치를 말함, 정점(Vertex) 라고 함 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch) 라고도 한다 - 인접 정점(Adiacent Vertex) : 간선으로 직접 연결된 정점 (또는 노드) - 참고용어 - 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수(In Degree) : 방향 그래프에서 외부에서 오는 간선의 수 - 진출 차수(Out Degree) : 방향 그래프에서 외부로..

정의 - 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 분석 - 최악의 경우 리스트 길이가 n 일 때 n 번 비교해야 한다 (찾는 값이 맨 마지막에 있을 경우) - O(n) 순차 탐색 (Sequential Search) public class SequentialSearch { public static void main(String[] args) { int[] arr = new Random().ints(10, 0, 30).toArray();; int index = sequential(arr, 10); System.out.println("arr = " + Arrays.toString(arr)); System.out.println("index = " + index); } pr..

동적 계획법 (Dynamic Programing, DP) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분문제의 해를 재활용해서 보다 큰 크기의 부분문제를 해결 최종적으로 전체 문제를 해결하는 알고리즘 - 상향식 접근법으로 가장 최하위의 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위문제를 풀어나가는 방식 - Memorization (메모제이션) 이란 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술 - 문제를 잘게 쪼갤 때, 부분문제는 중복되는 경우 재활용 된다 - 예) 피보나치 수열 * 요약 1. 작은 문제 부터 먼저 해결하여 값을 저장한다. 2. 점차 큰 크기의 문제 부분을 해결하는 데 중복된 작은 문제는 계산하지 않고 ..

보호되어 있는 글입니다.

📌 배열 (Array) 정의 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구상한 데이터 구조 배열이 왜 필요할까 ? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 (인덱스가 존재) - 문자열과 같은 경우 순차적으로 저장되어 있어야 효율적으로 관리 될 수 있다 - 인덱스를 통해서 연결된 데이터의 일부분을 바로 접근할 수 있다 장점 빠른 접근 가능 : 배열의 첫번째 위치만 알면 인덱스를 통해 몇번째 만큼 떨어진 곳으로 바로 접근 가능 단점 추가 / 삭제가 쉽지 않다 삭제하는 경우 필요없는 공간을 가지고 있어야 한다 미리 최대의 길이를 지정해야 한다 고정된 길이 가변적 `JAVA` 라는 문자열을 저장하기 위해 미리 4정도의 크기를 갖는 배열을 생성해놓아..

병합정렬 (Merge Sort) public class MergeSort { public static void main(String[] args) { int[] numArr = {4, 1, 7, 3, 2, 8, 6}; int[] results = mergeSplit(numArr); System.out.println(Arrays.toString(results)); } private static int[] mergeSplit(int[] arr) { // 길이가 1개 이하 인 경우 return arr if (arr.length lp && right.length > rp) { // 왼쪽 배열의 크기 보다 lp 가 작은 경우 and 오른쪽 배열 크기 보다 rp 가 작은 경우 if (left[lp] > right[..

정의 - 정렬 알고리즘의 꽃 - 기준점(Pivot) 을 정해서, 기준점보다 작은 데이터는 왼쪽(left) 큰 데이터는 오른쪽(right)으로 모으는 함수 - 각 왼쪽 (left), 오른쪽 (right) 는 재귀용법을 사용해서 다시 동일함수를 호출하여 위 작업을 반복한다 - 함수는 왼쪽 (left) + 기준점 (pivot) + 오른쪽 (right) 을 리턴한다 - 왼쪽 퀵 정렬 일 때 0번째가 가장 작은 수 일 경우 최악의 성능이 나옴 (빠르긴 하나, 상황에 따라 성능이 차이가 날 수 있기 때문에 안정적이지 않은 편이다. 그 에 비해 같은 분할정복의 정렬 중 병합 정렬은 항상 동일한 성능을 가지고 있어 안정적이고 퀵 정렬보다는 아니지만 그에 준수 한 속도를 가지고 있다) 분석 - 병합정렬 (Merge So..

재귀 함수 정수 n 이 입력으로 주어졌을 때 n을 1,2,3 의 합으로 나타낼 수 있는 방법의 수 구하기 public class RecursiveCall5 { public static void main(String[] args) { int num = 4; int numberOfCases = recursiveSum(num); System.out.println(numberOfCases); } private static int recursiveSum(int num) { if (num == 1) return 1; else if (num == 2) return 2; else if (num == 3) return 4; return recursiveSum(num - 1) + recursiveSum(num - 2) +..

재귀함수 (Recursive Call) 정수 n에 대해 n 이 홀수이면 3 * n + 1 을 하고, n 이 짝수이면 n 을 2로 나눕니다 이렇게 계속 진행해서 n 이 결국 1 이 될 때 까지 반복하고 이렇게 정수 n 을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요 public class RecursiveCall4 { public static void main(String[] args) { int num = 3; int result = EvenOddRe(num); } private static int EvenOddRe(int num) { System.out.println(num); if (num

회문 (Palindrome) 순서를 거꾸로 읽어도 같은 단어인 회문인지 판단하는 코드 작성 (재귀함수) 예) `LEVEL` 은 거꾸로 읽어도 `LEVEL` 이기 때문에 true, `MOTOR` 는 거꾸로 읽으면 `ROTMO` 이기 때문에 false public class Palindrome { public static void main(String[] args) { String name = "level"; char[] chars = name.toCharArray(); boolean isPalindrome = isPalindrome(chars); System.out.println(isPalindrome); } private static boolean isPalindrome(char[] name) { if ..