Algorithm64 [백준 Gold 5] 1987 알파벳 - Java 문제 링크 : www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 접근 과정 시작점은 좌측 상단으로 고정, 이동방향은 상-하-좌-우. 이동방향이 상화좌우이기에, DP가 아닌 DFS로 접근 알파벳이 중복되지 않고 갈 수 있는 경로를 탐색 어떻게 지나온 길의 알파벳을 저장하고 비교할건지가 관건 (저장된 알파벳의 수 = 이동 칸의 수) HashSet -> boolean[] -> BitMask로 방식을 바꿔가며 시간을 줄여나감. 소스 코드 및 결과 Code 1 .. 2021. 4. 14. [백준 Gold 3] 1823 수확 - Java 문제 링크 : www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 접근 과정 벼가 일렬로 존재한다고 가정하고, 왼쪽 끝과 오른쪽 끝의 벼 중 하나를 수확! DFS 방법으로 왼쪽 끝의 벼와 오른쪽 끝의 벼를 수확하는 경우를 모두 탐색 => 시간초과 DP 방법으로 DP[][] : i번째 벼부터 j번째 벼가 남아있는 상태에서의 최대 수확량이라고 정의 소스 코드 및 결과 Code 1 : DFS import java.io.*; /* 수확 시간초과 */ public class BOJ1823 { public .. 2021. 4. 14. [백준 Gold 5] 1446 지름길 - Java 문제 링크 : www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 접근 과정 문제 유형은 다익스트라이지만, DP가 어울릴 것이라 생각하여 DP로 접근 DP[n] : 위치 n까지 이동한 최소 거리 HashMap ShortCut에 의 형식으로 지름길을 저장 Top-Down 과 Bottom-Up의 2가지 방식으로 DP(N)을 구하여 반환. 소스 코드 및 결과 Code 1 : Top-Down import java.io.*; import java.util.*;.. 2021. 4. 13. [프로그래머스 Lv.4] 선입 선출 스케줄링 - JAVA 문제 링크 : programmers.co.kr/learn/courses/30/lessons/12920 코딩테스트 연습 - 선입 선출 스케줄링 처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니 programmers.co.kr 접근 과정 1) 우선순위 큐와 반복문을 활용한 풀이 우선순위 큐를 이용하여 core들을 순회시켰다. 반복문안에서 core들이 순서대로 작업을 1개씩 담당하며 처리했고 n은 차감되었다. n이 0이 되었을 때, 마지막 작업을 처리한 core의 인덱스를 출력하였다. => 정확성은 통과하였으나, 효율성에서 시간초과라는 결과를 보였다. 2) .. 2021. 4. 13. 이전 1 ··· 13 14 15 16 다음
