분류 전체보기 (164) 썸네일형 리스트형 [백준] JAVA - 2636. 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 생각 외부 영역과 맞닿아있는 치즈의 경계를 매초마다 지운다음 치즈가 모두 녹기 직전 치즈의 개수와 직전 시간을 구하는 문제입니다. 처음에 경계 치즈를 어떻게 구해줄까 생각하다가 내부에서 외부기준으로 판별하는게 어려워질껏같아 반대로 외부에서 내부를 BFS 탐색으로 체크해줬더니 경계를 체크할 수 있었습니다. 1. (0,0)부터 치즈가 없는 외부 영역 (map[y][x] = 0) 을 기준으로 BFS 탐색을 시작합니다. 이.. [백준] JAVA - 11727. 2×n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 생각 2*n 직사각형을 1*2, 2*1, 2*2 인 세가지 타일로 채우는 경우의 수를 구하는 문제입니다. 제가 정의한 dp[n] 은 너비가 n인 직사각형을 세가지의 타일로 채우는 경우의 수입니다. 타일의 경우가 세가지가 있는데 여기서 너비가 2인 타일이 두가지가 있기 때문에 dp[n] = dp[n-1] + dp[n-2] + dp[n-2]로 생각했습니다. 2*n 직사각형을 채우는 방법은 (1)n-1 너비인 직사각형에서 너비가 1.. [백준] JAVA - 11726. 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 생각 너비가 n이고 높이가 2인 직사각형을 1*2, 2*1 직사각형으로 채우는 경우의 수를 구하는 문제입니다. n이 1일땐 한가지 경우, n이 2일땐 너비가1인 직사각형을 두개 놓는 방법과 너비가 2인 직사각형을 두줄로 쌓는 경우로 두가지가 있습니다. 제가 정의한 dp[n]은 너비가 n일때 1*2, 2*1 타일로 채우는 경우의 수입니다. dp[n]일때 직사각형을 채울 수 있는 방법은 n-1 직사각형에서 너비가 1인 직.. [백준] JAVA - 1149.RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 생각 N번째 집을 정해진 조건에 따라서 칠했을때 최소비용을 찾는 문제입니다. 처음에 dp를 1차원 배열로 설정하고 N개의 집을 색칠하는 최소비용을 계산하려다가 색칠하는 경우를 나눌수가 없어서 2차원 배열로 수정했습니다. 이때 집을 칠하는 경우는 총 세가지로 첫번째집을 빨간색으로 칠했다면 그 다음 집에 칠해야할 색은 조건에 따라 분기됩니다. 제가 정의한 dp는 dp[i][j] .. [백준] JAVA - 1463. 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 생각 DP 문제로 주어진 세가지 연산을 사용하여 N을 1로 만드는 최소 연산의 횟수를 구하는 문제입니다. 제가 정의한 dp[N] 은 N을 1로 만드는 최소 연산의 횟수를 저장하고 있는 배열입니다. N이 2로만 나눠진다면 dp[i/2]와 dp[i-1] 연산 중 작은 값을 선택한뒤 연산 횟수를 1 증가시킵니다. N이 3으로만 나눠진다면 dp[i/3]와 dp[i-1] 연산 중 작은 값을 선택한뒤 연산 횟수를 1 증가시킵니다. N이 2와 3 모두 나눠진다면 dp[i/2], dp[i/3], dp[i-1] 중 작은 값을 .. [SWEA] JAVA - 1486. 장훈이의 높은 선반 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 생각 N이 최대 20까지이므로 최대 2^20 연산이 필요합니다. 따라서 부분집합으로 문제를 풀 수 있습니다. 공집합일때는 제외하고 1부터 N개를 뽑았을때의 부분집합을 만들어줍니다. 만들어진 부분집합의 총 합과 탑 높이의 차가 가장 적은것을 찾아주면 됩니다. 재귀로 부분집합을 구현했는데 비트마스킹으로 구현하는것도 연습해야겠습니다 Java Code import java.io.BufferedReader;.. [정올] JAVA - 1681.해밀턴 순환회로 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 생각 모든 노드들을 방문한뒤 다시 처음 시작점으로 돌아와야 할때 최소비용을 구하는 문제이다. 문제를 다 풀고나니 외판원 순회문제군요ㅎ.ㅎ 먼저 인접리스트를 사용하여 그래프의 정보를 나타냈습니다. 이때 비용이 0인 경우는 갈 수 없는 경우이므로 인접리스트에 담아주지 않습니다. 갈 수 있는 경우만 인접리스트에 추가해줍니다. dfs를 사용하여 현재 노드에서 내가 다음 노드로 갈수있는지 방문여부를 체크한 다음에 재귀호출하여 갈 수 있는 경우를 모두 탐색한다음 다시 돌아와 visited를 해제시켜줍니다. 모든 정점에 대한 방문여부를 반복문을 돌.. [백준] JAVA - 1753.최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 생각 우선순위 큐를 이용해서 다익스트라 알고리즘을 구현했습니다. 우선순위 큐를 사용하면 현재 노드에서 인접한 노드의 최소비용을 찾을때 불필요한 계산을 줄일 수 있기 때문입니다. 내부적으로는 logV (V : 노드개수) 만큼의 시간복잡도를 가지게 됩니다. 인접리스트를 사용하여 구현했습니다. 이때 반복문을 돌리며 현재 노드에서 다음으로 갈수있는 노드들을 탐색합니다. 만약 기.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 21 다음
