본문 바로가기

전체 글108

Dynamic Programming(동적계획법) 알고리즘 Dynamic Programming (동적계획법) 이란? 동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 입니다. 핵심기술은 memoization 으로 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. 구현 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷합니다. 동적 계획법 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산값을 이용해 원래 문제의 답을 산출합니다. 분할정복과의 차이점은 메모이제이션 기술의 사용 여부에 있습니다. 구현 방식은 top-down, bottom-u.. 2021. 3. 19.
백준 2210번 : 숫자판 점프 www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 구현 방법 가능한 모든 곳을 탐색해야 하기 때문에 브루트포스 알고리즘을 사용해주었습니다. 깊이를 따라 가야하기 때문에 dfs를 통해 탐색을 진행하였습니다. 한 번 거쳤던 칸은 다시 거쳐도 되므로 방문체크는 따로 하지않고 카운팅을 해주어 다섯 곳을 이동했으면 중복을 허용하지 않는 TreeSet을 구현하여 해당 문자를 삽입해주었습니다. 다섯번을 이동했으면 더 이상의 탐색을.. 2021. 3. 18.
백준 2583번 : 영역 구하기 문제 www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 구현 방법 해당되는 영역들을 1로 채운 다음 빈 칸을 중심으로 dfs를 통해 구현하였습니다. 한 영역에서 탐색이 끝난 후 계산한 너비를 저장을 합니다. 모든 영역 탐색이 끝난 뒤에 저장해 둔 너비들을 정렬 하고 출력해줍니다. 구현 코드 package BOJ.Silver.bfsdfs; import java.io.BufferedReader; import java.io.IOException;.. 2021. 3. 18.
백준 1937번 : 욕심쟁이 판다 문제 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 구현 방법 그냥 bfs/dfs를 쓰면 시간 초과가 나기 때문에 dp를 써줘야합니다. 예제를 예로 들면 9->11->15 방향으로 탐색을 합니다. 나중에 5->11로 갈때면 11은 15까지밖에 못간다는걸 이미 알고있는데 탐색을 하므로 시간이 낭비됩니다. 그래서 자기가 이미 갔던 곳이라면 살 수 있는 날을 저장을 하고 그 곳을 또 방문하게 된다면 저장되어 있는 값을 가져와 +1을 해주면 자신의 살 수.. 2021. 3. 18.

티스토리툴바