정의 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율서을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제는) 별도의 메모리 영여게 저장하여 다시 계산하지 않도록 합니다. 다 프로그래밍의 구현은 일반적으로 두가지 방식(탑다운 보텀업) 으로 구성 됩니다. 동적 계획법 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 대한 메모리를 할당하는 기법 조건 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답으 모아서 큰 문제를 해결할 수 있습니다. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야합니다. 예시) 피보나치 수열 public class fibonacci { // 피보나치 함수 재귀함수로 구현 public static int fibo(int..
문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이 H를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기를 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm 이다, 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일때, 적어도 M만큼..
이진 탐색은 배열 내부의 데이터가 정렬 되어 있어야만 사용할 수있는 알고리즘이다. 무작위일때 사용할수 있는 알고리즘이다. 이미 정렬되어있으면 빠르게 데이터를 찾을 수 있다는 것이 특징 이진 탐색은 위치를 나타내는 변수 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(..
문제 설명 정수 n을 기준으로 n과 가까운 수부터 정렬하려고 합니다. 이때 n으로부터의 거리가 같다면 더 큰 수를 앞에 오도록 배치합니다. 정수가 담긴 배열 numlist와 정수 n이 주어질 때 numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 10,000 1 ≤ numlist의 원소 ≤ 10,000 1 ≤ numlist의 길이 ≤ 100 numlist는 중복된 원소를 갖지 않습니다. 문제풀이 1 import java.util.*; class Solution { public int[] solution(int[] numlist, int n) { // 거리와 원소를 저장하는 Map 생성 Map distanceMap ..
문제 설명 동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1) 이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M (4
문제 설명 N, M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 입력 예시 15 14 00000111100000 11111101111110 11011101101110 11011101100000 11011111111111 11011111111100 11000000011111 01111111111111 00000000011111 01111111111000 00011111111000 00000001111000 11111111110011 11100011111111..
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색알고리즘 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도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음..
