본문 바로가기

Algorithm44

[알고리즘] 프로그래머스 - 등굣길 (동적 계획법) 1. 문제 2. 문제 풀이 dp 배열을 먼저 초기화 하는데, 0행과 0열에 물웅덩이가 있으면 그 다음 지역으로는 갈 수 없으므로 0으로 초기화 된 값을 남겨둔다. 그리고 물웅덩이가 없을때가지 1로 초기화를 해준다. dp 배열을 채울때 물웅덩이가 있으면 0으로 바꿔주고, 나머지 경우는 코드를 참고하면 쉽게 이해할 수 있다. class Solution { private static int dp[][]; public static void calculateDp(int m, int n){ for(int i=0;i 2020. 10. 7.
[알고리즘] 프로그래머스 - 정수 삼각형 (동적 계획법) 1. 문제 2. 문제 풀이 문제를 보자마자 이항 계수(파스칼의 삼각형)가 떠올랐고 대표적인 동적 계획법 문제이다. 동적 계획법은 최적화와 관있고 반복되는 계산을 줄일 수 있다. 심지어 문제에 최댓값이라는 힌트까지 있다. 일단 dp배열을 정의하였는데 예를 들어서 dp[3][2] 면 3행 2열까지 이동했을때 가장 큰수를 저장한다고 생각하였다. 그러면 dp[3][2] = max(dp[2][1], dp[2][2]) + triangle[3][2] 이런식으로 표현이 가능하다. 그러면 그러면 dp[2][1]도 base case로 부터 이러한 연산을 시작해서 올라올 것이다. 삼각형의 가장자리에 있는 경우와 나머지 경우를 나눠서 수식을 세웠다. 자세한 내용은 calculateDp 메소드를 보면 된다. 메소드 연산이 끝났.. 2020. 10. 6.
[알고리즘] 프로그래머스 - 더 맵게(힙) 1. 문제 2. 문제 풀이 스코빌지수가 가장 낮은 2개의 음식을 뽑아서 새로운 음식을 만들어서 우선순위 큐에 계속 넣어주고, 가장 스코빌지수가 낮음 음식이 주어진 K와 같거나 커지면 몇번만에 K 이상으로 만들었는지 반환해주는 간단한 문제였다. 코드를 보면 크게 설명할게 없다는 것을 알 수 있다. import java.util.*; class Solution { PriorityQueue priorityQueue = new PriorityQueue(); int answer = 0; public int solution(int[] scoville, int K) { for(int i=0;i 2020. 8. 18.
[알고리즘] 프로그래머스 - 디스크 컨트롤러(힙) 1. 문제 2. 문제 풀이 최대값이나 최소값을 뽑아내는 우선순위큐(힙)를 이용해서 문제를 풀었다. 우선 요청시간과 처리시간을 저장할 수 있도록 Job 클래스를 만들어서 데이터를 저장하게 하였다. Job의 정렬 기준으로는 처리 시간이 더 작은게 앞으로 오게 하였다. waitQueue에는 현재 시간과 비교해서 하나의 작업이 끝났을 때 요청 시간이 현재 시간보다 작거나 같으면 waitQueue에 저장을 하였다. 주어진 jobs 배열을 요청 시간에 대해서 오름차순으로 정렬한다. 모든 job을 waitQueue에 넣고, 대기큐(waitQueue)에 job이 없을때까지 반복문을 실행한다. waitQueue에 작업을 넣지 않았고, 현재 시간이 작업 요청 시간보다 작거나 같으면 waitQueue에 job을 넣어준다. .. 2020. 8. 18.
[알고리즘] 프로그래머스 - 여행경로(dfs/bfs) 1. 문제 2. 문제풀이 처음에 풀때 인접행렬을 이용해서 인접행렬의 방문한 곳은 다시 방문하지 않는 형태로 풀었었다. 하지만 항공사를 여러번 방문 할 수 있기 때문에 인접행렬이아닌, 항공권을 사용했는지를 체크하는 형태로 바꾸었다. 주어진 조건중에 알파벳 순서가 앞서는 경로를 return 하라는 조건을 각 배열을 정렬해야하나 했다가 String으로 방문 가능한 경로를 ','로 이어주고 그 Stirng들을 저장한 list를 정렬하는 방식으로 수정하였다. 1. 출발 항공사가 "ICN"일 경우 그 항공권을 사용했다고 표시해주고 dfs알고리즘을 호출한다. 2. route에 현재 경로를 더해주고, 현재 사용하지 않은 티켓중에 이전 도착지와 현재 티켓의 출발지가 같다면 티켓을 사용했다고 표시하고 dfs 알고리즘을 다.. 2020. 8. 8.
[알고리즘] 프로그래머스 - 단어변환 (dfs/bfs) 1. 문제 2. 문제풀이 현재 주어진 단어를 한글자씩 수정해서 최종 목표 단어로 변환이 가능한지를 구하고, 만약 변환이 가능하다면 몇번만에 가능한지 최소 변환 횟수를 구하는 문제였다. 현재 단어에서 words 배열에 있는 단어로 변환이 가능하다면 visit 배열에 방문을했다고 표시를 한 후 dfs 탐색 방법을 이용해서 탐색을 진행한다. dfs의 base case로는 전부 방문했거나, 현재 단어와 찾는 단어가 같을 경우 탐색을 종료했다. 그리고 최소 횟수를 계속 갱신하여 최종적으로 minNum을 반환한다. 변환이 불가능할 경우 0을 반환한다. class Solution { int minNum = 999999999; public void dfs(boolean[] visit, String[] words, St.. 2020. 8. 8.

티스토리툴바