티스토리

Gecko in a cage

검색하기

블로그 홈

Gecko in a cage

gecko-in-a-cage.tistory.com/m

gecko_in_a_cage 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

동적 계획법 / 다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming, DP). 다른 말로는 동적 계획법이라고도 한다. 큰 문제를 한 번에 해결하기 어려울 때 이를 작은 여러 개의 문제로 나누어서 푸는 기법이다. 일반적으로 부분 문제 반복과 최적 부분 구조를 가진 문제를 해결할 때 사용한다. 각 하위 문제의 해답을 계산하고 이를 별도의 저장공간에 저장하여 이후 같은 하위 문제가 나오는 경우 재차 계산하지 않고 간단히 해결할 수 있다. 최단 경로 탐색, 행렬 제곱 등의 최적화에 사용한다. DP이 문제를 해결하기 위한 모든 방법을 검토하고, 그중 최적의 풀이법을 찾아내기 때문이다. 상향식 접근법을 사용한다. 상향식 접근법이란 최하위 해답을 구한 뒤 이를 저장하고, 저장된 결과를 이용해서 상위 문제의 해.. 공감수 0 댓글수 0 2020. 9. 7.
BOJ1932 / 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 예제 입력.. 공감수 0 댓글수 0 2020. 9. 6.
BOJ1043 / 거짓말 문제 지민이는 파티에 가서 이야기하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다. 그리고 그 .. 공감수 0 댓글수 0 2020. 8. 28.
BOJ1149 / RGB거리 문제 요약 N개의 집을 각각 R, G, B 중 하나의 색으로 칠할 때 이웃한 집과 같은 색을 칠하지 않으면서 모든 집을 칠하는 최소 비용을 구하라. 입력 첫째 줄에 집의 수 N(2 공감수 0 댓글수 0 2020. 8. 27.
BOJ14500 / 테트로미노 문제 요약 각 칸에 숫자가 쓰여진 NxM 크기의 종이 위에 임의의 테트로미노 하나를 놓는다고 할 때 테트로미노가 놓인 칸에 쓰여 있는 수의 합의 최댓값을 구하라. 입력 첫 줄에 종이의 세로 크기 N, 가로 크기 M이 주어진다. (4 공감수 0 댓글수 0 2020. 8. 25.
BOJ11403 / 경로 찾기 문제 요약 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점(i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하라. 입력 첫 줄에 정점의 개수 N(1 공감수 0 댓글수 0 2020. 8. 15.
BOJ10026 / 적록색약 문제 요약 NxN 그리드의 각 칸이 RGB로 칠해진 그림이 같은 색으로 이루어진 몇 개의 구역으로 나뉘어 있다. 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역에 속한다. RRRBB GGBBB BBBRR BBRRR RRRRR 위 그림을 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개 (R 2, B 1, G 1), 적록색약인 사람이 봤을 때는 총 3개 구역을 볼 수 있다.(R-G 2, B 1) 그림이 입력으로 주어질 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하라. 입력 첫째 줄에 N이 주어진다. (1 = 0 && x < n) { // 방문한 적 없고 같은 색일 경우 if (!visited[y][x] && img[i][j] == img[y][x]) { q.offer(y .. 공감수 0 댓글수 0 2020. 8. 14.
BOJ9205 / 맥주 마시면서 걸어가기 문제 요약 집에서 페스티벌까지 맥주를 마시며 가려고 한다. 맥주는 한 번에 1000미터를 이동할 수 있을만큼만 들고다닌다. 편의점에서 맥주를 충전할 수 있다. 집에서 페스티벌까지 맥주가 떨어지지 않고 갈 수 있을지 없을지 구하라. 입력 첫째줄에 테스트 케이스의 개수 t가 주어진다. (t 공감수 0 댓글수 0 2020. 8. 13.
BOJ9019 / DSLR BOJ9019.java // https://www.acmicpc.net/problem/9019 // 20.8.12. ventania1680 // BFS package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ9019 { static boolean[] visited = new boolean[10001]; static String[] path = new String[10001]; static int .. 공감수 0 댓글수 0 2020. 8. 12.
BOJ6064 / 카잉 달력 BOJ6064.java // https://www.acmicpc.net/problem/6064 // 20.8.11. ventania1680 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ6064 { public static int findGCD(int m, int n) { while (n > 0) { int r = m % n; m = n; n = r; } return m; } public static void solution() throws Exception { BufferedReader br = new BufferedRea.. 공감수 0 댓글수 0 2020. 8. 11.
BOJ1654 / 랜선 자르기 BOJ1654.java // https://www.acmicpc.net/problem/1654 // 20.8.10. ventania1680 // 이분탐색 변형으로 풀이 가능 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1654 { public static void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.. 공감수 0 댓글수 0 2020. 8. 10.
BOJ1436 / 영화감독 숌 BOJ1436.java // https://www.acmicpc.net/problem/1436 // 20.8.8. ventania1680 // 브루트포스로 해결 가능 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ1436 { public static void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); final int doom = 666; if (n == 1) { Syst.. 공감수 0 댓글수 0 2020. 8. 8.
프로그래머스 / 코딩테스트 연습 / 탐욕법(Greedy) / 큰 수 만들기 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 number k return "1924" 2 "94" .. 공감수 0 댓글수 0 2020. 8. 7.
프로그래머스 / 코딩테스트 연습 / 탐욕법(Greedy) / 체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를.. 공감수 0 댓글수 0 2020. 8. 7.
프로그래머스 / 코딩테스트 연습 / 완전탐색 / 카펫 문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 .. 공감수 0 댓글수 0 2020. 8. 6.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.