KKanging

다이나믹 프로그래밍(동적 계획법)이란? 다이나믹 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하는 방법이다. 이때 작은 하위 문제들의 해결 결과를 저장하고, 중복 계산을 피하여 전체 문제를 효율적으로 해결하는 것이 특징이다. 이렇게 하면 지수적인 시간 복잡도를 갖는 재귀적인 해결 방법보다 훨씬 효율적으로 문제를 풀 수 있다. 위에 설명이 어렵다면 그냥 과정중에 중복되는 계산이 있다면 자료구조에 저장해서 다음에 중복된 계산이 있을때 저장한 값을 활용해서 연산시간의 이득을 얻는 알고리즘이다. 이런 구조 때문에 기억하기 알고리즘이라고 불리기도 한다. 다이나믹 프로그래밍의 특징 중복 부분 문제 (Overlapping Subproblems): 다이나믹 프로그래밍은 동일한 하위 문제들이 반복해서 해결되는 경..

1. 버블정렬 버블 정렬은 간단한 정렬 알고리즘이다. 배열에서 인접한 두 원소를 비교하면서 큰 값을 뒤로 보내는 방식으로 정렬을 수행한다. 반복적으로 진행되며 가장 큰 값이 배열의 가장 마지막으로 이동한다. 이런 식으로 작은 값들이 순차적으로 정렬되어 나열된다. 버블 정렬은 간단하지만 배열의 크기가 커질수록 비효율적인 특징이 있다. 자바 구현 public class BubbleSort { public static void bubbleSort(int[] ary) { int n = ary.length; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j ary[j + 1]) { int temp = ary[j + 1]; a..

Kruskal 알고리즘 Kruskal 알고리즘이란 → 가중치 그래프의 자료구조를 이용하여 최소신장트리를 구성하는 알고리즘이다. → greedy 알고리즘의 대표적인 알고리즘이다 목차 그래프와 최소신장 트리의 개념 greedy 알고리즘이란 kruskal 알고리즘 그래프란 → 노드(정점 vertex)와 그 노드를 연결하는 간선을(edge) 하나로 모아놓은 자료구조 무방향 그래프: 간선이 방향이 없는 그래프 방향 크래프: 간선의 방향이 있는 그래프 그래프의 표현 방법 인접 행렬 인접 리스트 인접행렬 가중치 그래프란 그래프의 간선에 가중치(weight)를 부여한 것 트리란 → 그래프의 한 종류 → Cycle이 불가능 (그래프에서 사이클(Cycle)이란 어떤 특정 정점에서 출발하여 간선과 정점들을 지 나 다시 처음..

이분 탐색이란 이분 탐색의 특징 일반적으로 크기가 N인 배열이 순서대로 정렬되어 있을 때 사용할 수 있다. 수행시간이 O(logn)으로 완전 탐색 알고리즘 보다 훨씬 단축된다. 이분탐색은 왜 필요로 할까 위와 같은 N=5 배열이 있고 우리는 배열의 원소를 찾는 과정을 수행한다고 가정해보자 만약 브루트 포스 알고리즘 ( 완전 탐색 알고리즘)을 사용한다면? 1을 찾는다면 한번에 찾을 수 있다. 하지만 20을 찾는다면 20을 찾을 때까지 5번의 수행을 해야한다. 위 예시는 배열의 크기가 작지만 1024개의 크기라고 가정하면 1024번을 수행한다. 이분탐색의 원리 찾는 대상 20 mid 인덱스 값을 구한다 이때 mid 인덱스는 탐색하는 배열의 첫 원소와 마지막 원소의 인덱스의 중간값이다. mid = (start..

브루트 포스 알고리즘: 완전탐색의 미학 브루트 포스 알고리즘은 컴퓨터 과학에서 사용되는 중요한 탐색 기법 중 하나입니다. 브루트 포스는 '무식하게 푼다'라는 뜻으로, 모든 가능한 경우를 하나씩 검사하면서 정확한 답을 찾는 방법입니다. 비록 최적화된 알고리즘이 아니더라도, 경우에 따라서는 간단하고 직관적인 해결책을 찾는 데 유용합니다. 브루트 포스의 의미와 사용 이유 브루트 포스는 간단한 아이디어에서 출발합니다. 모든 가능한 조합을 시도해보면 결국 정확한 답을 얻을 수 있을 것이라는 믿음에 기반을 두고 있습니다. 이는 여러 이유로 유용합니다. 확실한 결과: 브루트 포스는 모든 가능한 경우를 탐색하기 때문에 정확한 답을 얻을 수 있습니다. 어떤 경우에도 해결책을 놓치지 않습니다. 단순한 구현: 브루트 포스는..

분할정복(divide and conquer) 분할정복이란 두괄식으로 설명하자면 큰 문제를 작은 문제로 나눠서 작은 문제의 문제들을 해결하고 그 해결한 값으로 큰문제를 해결하는 해결 방식이다. 분할정복의 구성 divide(분할) : 문제를 작은 크기의 문제들로 나눈다 conquer(정복): 더 이상 나눌 수 없는 문제라면 해를 구한다. conbine : 작은 문제의 해를 합쳐서 original 문제의 해를 구한다. conquer은 더 나눌수 있는 문제라면 위 방식을 재귀적으로 반복한다.큰문제 (divide) → 작은 문제 작은 문제 (conquer)하지만 더 나눌수 있다면 divide ex) 분할 정복 예 거듭 제곱 예 3^8을 구한다고 가정 3을 한번씩 8번 곱할 수 있음 하지만 분할정복을 사용하면 위 ..

greedy 알고리즘이란 매 선택의 순간마다 순간 (local)에 최적인 답을 선택하여 전체 최적해를 구할거라고 기대를 하는 알고리즘이다 순간마다의 최적이라고, 그 순간들을 수집한 최종적인 해답이 최적해를 보장하지는 않는다 (하지만 최적해를 보장하는 예는 계산 속도가 엄청 빠르다) -greedy 알고리즘을 적용하기 좋은 조건 → greedy 알고리즘은 항상 최적해를 보장하지는 않지만 최적해를 보장하는 2가지 조건이 있다 탐욕적 선택 속성: 앞의 최적해 선택이 이후의 최적해 선택에 영향을 주지않는다.즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. -greedy 알고리..

우선 그래프 이론과 큐와 스택을 모른다면 그래프 큐 스택 을보고 오시기 바랍니다. 그래프를 탐색하는 방법 DFS (깊이 우선 탐색) BFS (너비 우선 탐색) DFS(Depth-First-Search) 관련 있는 노드를 최대한 깊이 있게 탐색하는 방법 구현 방법 stack 재귀함수 구현 방법 우선 방문한 정점을 다시 방문하는 일이 없도록 visited 배열을 만들어 준다. 0은 아직 방문하지 않았다는 의미 시작 정점 하나부터 stack에 넣는다. 그리고 stack의 있는 원소를 pop 한다 pop 된 정점과 연결되어 있는 정점을 stack에 push 한다. pop 된 정점과 연결되어 있는 visited 원소를 1로 바꾼다. 이제 핵심 로직을 반복하면 된다. 4가 pop 되고 4와 연결되어 있는 정점을 찾..