mun dev

백트래킹이란? 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다. DFS와 백트래킹 DFS(Depth First Search) 깊이 우선 탐색은 가능한 모든 경로를 탐색한다. 불필요할 거 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다 . 따라서 N!의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 크다. 백트래킹 백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지 치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 ..

다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. 다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다. 일반적으로 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미합니다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어입니다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있습니다..

순차탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진탐색 - 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 이진 탐색 동작 예시 step1. 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거) step2. 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거) step3. 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거) 이진 탐색 소스코드: 자바(Java) public class Main { // 이진 탐색 소스코드 구현 public static int binarySearch(int[] arr, int target, int start, i..

정렬(Sort) 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됩니다. 1. 선택(Select) 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 선택 정렬 코드(Java) import java.util.*; public class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 0; i < n; i++) { int min_index = i; // 가장 작은 원소의 인덱스 ..

DFS(Depth First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀함수)를 이용 동작과정 탐색 시작 노드를 스택에 삽입하고 방문처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 DFS 구현 예제 위 과정을 구현한 코드입니다. import java.util.*; public class Main { public static boolean[] visited = new boolean[9]; public static ArrayList graph..

구현(Implementation) 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 예시 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 예제 문제1. 상하좌우 여행가 A는 N x M 크기의 정사각형 공간 위에 서있습니다. 이 공간은 1 x 1크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 ( N,N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상(1,1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 ..

그리디 알고리즘(탐욕법) 현재상황에서 지금 당장 좋은 것만 고르는 방법을 의미하며, 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다. 그리디 알고리즘은 매 상황에서 큰 값을 고르는 알고리즘이다. 예제 문제 1. 거스름돈 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까요? 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K) 시간 복잡도는 거슬러줘야 하는 금액과는 무관, 동전의 총 종류에만 영향을 받습니다. public class Main{ public static void main(String[]..