정의 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율서을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제는) 별도의 메모리 영여게 저장하여 다시 계산하지 않도록 합니다. 다 프로그래밍의 구현은 일반적으로 두가지 방식(탑다운 보텀업) 으로 구성 됩니다. 동적 계획법 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 대한 메모리를 할당하는 기법 조건 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답으 모아서 큰 문제를 해결할 수 있습니다. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야합니다. 예시) 피보나치 수열 public class fibonacci { // 피보나치 함수 재귀함수로 구현 public static int fibo(int..
이진 탐색은 배열 내부의 데이터가 정렬 되어 있어야만 사용할 수있는 알고리즘이다. 무작위일때 사용할수 있는 알고리즘이다. 이미 정렬되어있으면 빠르게 데이터를 찾을 수 있다는 것이 특징 이진 탐색은 위치를 나타내는 변수 3개를 사용하여 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점이다. 찾으려는 데이터를 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는데이터를 찾는게 이진 탐색이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Binary_Search{ public static int binarySearch(..
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색알고리즘 DFS, BFS 자주 등장 DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작노드를 스택에 삽입하고 방문 처리합니다. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다, 더이상 위에 과정을 수행 할수 없을때까지 반복합니다. import java.util.*; // 스택 public class Main { public..
문제 설명 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음..
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 지칭합니다. 구현 유형 예시 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제 문자열을 특정 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야하는 문제 시물레이션 및 완전 탐색 문제어서는 2차원 공간에서의 방향 벡터가 자주 활용 상하좌우 이때 여행가 A가 NxN 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1,1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N=5인 지도와 계획서이다. 계획서 : R -> R -> R -> U -> D -> D 이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1,2), (1,3)..
1. 버블 정렬 public void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 2. 선택 정렬 public void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < a..
