Algorithm (117) 썸네일형 리스트형 [백준] 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 : 노드개수) 만큼의 시간복잡도를 가지게 됩니다. 인접리스트를 사용하여 구현했습니다. 이때 반복문을 돌리며 현재 노드에서 다음으로 갈수있는 노드들을 탐색합니다. 만약 기.. [SWEA] JAVA - 1238.Contact https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 생각 인접리스트를 사용하여 BFS를 구현했습니다. 마지막 depth 까지 탐색할때 가장 숫자가 큰 Node를 찾아야하기 때문에 우선 첫번째로 distance 배열에 시작 정점으로부터의 거리값을 계산해줬습니다. distance 로 방문체크도 해주기위해 -1로 초기화를 해줬습니다. 이렇게 설정해주면 탐색한 노드의 distance를 시작정점으로부터의 거리값으로 계산해주기 때문에 if(distance[no.. [백준] JAVA - 13300.방배정 https://www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net Java Code package com.java.algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_13300_방배정 { public static .. [백준] JAVA - 2578.빙고 https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net Java Code package com.java.algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_2578_빙고 { static int[][] board; static int[][] or.. [SWEA] JAVA - 1227. 미로2 생각 (1,1) 에서 시작하여 (13,13)까지 도달할 수 있는지를 판단하는 문제입니다. DFS를 사용하여 도착지점까지 갈 수 있는지를 찾아줬습니다. 1. 출발좌표에서 DFS 탐색을 시작합니다. 2. dy,dx 방향 벡터를 이용하여 사방탐색을 합니다. 3. 다음좌표를 방문하지 않았고 벽이 아니라면 다음 좌표를 파라미터에 넣고 다음 단계를 정하러 한단계 더 들어갑니다. 4. 더 이상 이동할 수 없으면 이전에 다녀온 방문표시를 모두 해제합니다. 5. 기저조건인 도착지점에 도착한다면 ans=1 로 업데이트 시켜줍니다. Java code package com.java.algorithm; import java.io.BufferedReader; import java.io.IOException; import java.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음
