알고리즘 문제풀이
-
프로그래머스 디스크 컨트롤러 자바(java) 풀이 Level 3 해시(Hash) 디스크 컨트롤러 문제 정리 하드 디스크는 한 번에 하나의 작업만 수행한다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 적게하여라. jobs의 길이는 최대 500이다. jobs의 각 행은 [작업이 요청되는 시점, 작업의 소요시간]이다. 각 작업에 대해 소요시간은 최대 1000이다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 문제 접근 만약 라면공장 문제를 풀지 않고 이 문제를 풀었다면 오래걸렸을 것 같습니다. 하지만 라면공장 문제를 풀고 감을 익혀서 문제를 풀 수 있었습니다. 이 문제는 문제를 파악하고 걸린시간의 평균을 가장 적게 하는 방법만 생각한다면 쉽습니다. 이 문제에 ..
[우선순위 큐] 프로그래머스 level3 디스크 컨트롤러 자바 풀이프로그래머스 디스크 컨트롤러 자바(java) 풀이 Level 3 해시(Hash) 디스크 컨트롤러 문제 정리 하드 디스크는 한 번에 하나의 작업만 수행한다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 적게하여라. jobs의 길이는 최대 500이다. jobs의 각 행은 [작업이 요청되는 시점, 작업의 소요시간]이다. 각 작업에 대해 소요시간은 최대 1000이다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 문제 접근 만약 라면공장 문제를 풀지 않고 이 문제를 풀었다면 오래걸렸을 것 같습니다. 하지만 라면공장 문제를 풀고 감을 익혀서 문제를 풀 수 있었습니다. 이 문제는 문제를 파악하고 걸린시간의 평균을 가장 적게 하는 방법만 생각한다면 쉽습니다. 이 문제에 ..
2020.05.27 -
sw expert academy 2112번 보호 필름 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2112번 보호 필름 문제 정리 보호 필름은 얇은 막 D개를 쌓아서 만든다 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!) 각 셀들은 특성 A 또는 B를 가진다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경) 약품을 ..
[dfs, 백트래킹] sw expert academy 2112번 보호 필름 자바 풀이sw expert academy 2112번 보호 필름 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2112번 보호 필름 문제 정리 보호 필름은 얇은 막 D개를 쌓아서 만든다 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!) 각 셀들은 특성 A 또는 B를 가진다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경) 약품을 ..
2020.05.22 -
프로그래머스 라면 공장 자바(java) 풀이 Level 2 힙 라면 공장 문제 정리 공장에서 하루에 밀가루 1톤씩 사용한다. 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다. 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다. 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다. 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라 stock: 현재 남아있는 밀가루 양 dates[]: 밀가루 공급 일정 supplies[]: 해당 시점에 공급 가능한 수량 K: 원래 공장으로부터 공급받을 수 있는 시점 stock에 있는 밀가루는 오늘(0일)부터 사용된다. k일 째에는..
[우선순위 큐, comparable] 프로그래머스 level2 라면공장 자바 풀이프로그래머스 라면 공장 자바(java) 풀이 Level 2 힙 라면 공장 문제 정리 공장에서 하루에 밀가루 1톤씩 사용한다. 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다. 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다. 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다. 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라 stock: 현재 남아있는 밀가루 양 dates[]: 밀가루 공급 일정 supplies[]: 해당 시점에 공급 가능한 수량 K: 원래 공장으로부터 공급받을 수 있는 시점 stock에 있는 밀가루는 오늘(0일)부터 사용된다. k일 째에는..
2020.05.15 -
프로그래머스 더 맵게 자바(java) 풀이 Level 2 힙 H-Index 문제 정리 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라. 힙, 우선순위 큐 이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(..
[우선순위 큐] 프로그래머스 level2 더 맵게 자바 풀이프로그래머스 더 맵게 자바(java) 풀이 Level 2 힙 H-Index 문제 정리 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라. 힙, 우선순위 큐 이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(..
2020.05.12 -
프로그래머스 단어 변환 자바(java) 풀이 Level 3 BFS/DFS 단어 변환 문제 정리 두 개의 단어 begin, target과 단어의 집합이 있다. 다음 규칙을 이용하여 begin에서 target으로 단어를 변환하는 가장 짧은 변환을 찾으려 한다. 규칙1: 한 번에 한 개의 알파벳만 바꿀 수 있다. 규칙2: words에 있는 단어로만 변환할 수 있다. 최소 몇 단계의 과정을 거쳐 target으로 바꿀 수 있는지 찾아라. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있습니다. 변환할 수 없는 경우에는 0을 return 합니다. 문제 풀이 이 문제는 bfs의 개념을 이용하면 생각보다 간단히 풀 수 있습니다. 하지만 그것까지 떠..
[BFS] 프로그래머스 level3 단어 변환 자바 풀이(아주 상세한 설명 포함)프로그래머스 단어 변환 자바(java) 풀이 Level 3 BFS/DFS 단어 변환 문제 정리 두 개의 단어 begin, target과 단어의 집합이 있다. 다음 규칙을 이용하여 begin에서 target으로 단어를 변환하는 가장 짧은 변환을 찾으려 한다. 규칙1: 한 번에 한 개의 알파벳만 바꿀 수 있다. 규칙2: words에 있는 단어로만 변환할 수 있다. 최소 몇 단계의 과정을 거쳐 target으로 바꿀 수 있는지 찾아라. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있습니다. 변환할 수 없는 경우에는 0을 return 합니다. 문제 풀이 이 문제는 bfs의 개념을 이용하면 생각보다 간단히 풀 수 있습니다. 하지만 그것까지 떠..
2020.05.11 -
프로그래머스 네트워크 자바(java) 풀이 Level 3 BFS/DFS 네트워크 문제 정리 컴퓨터A와 컴퓨터 B가 연결되있고, 컴퓨터 B와 컴퓨터 C가 연결되있으면 A와 C도 간접적으로 연결되 정보를 주고 받을 수 있다. 따라서 A,B,C는 같은 네트워크 상에 있다고 볼 수 있다. 각 컴퓨터는 0부터 n-1인 정수로 표현된다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]=1 이다. computers[i][i]는 항상 1이다. 문제 풀이 이 문제는 그래프로 바꿔서 생각하면 쉬운 문제입니다. level2에 놔도 될것 같네요 그래프 형태로 생각해서 bfs나 dfs를 이용해 탐색합니다. 저는 bfs를 이용했습니다. 방문하지 않은 경우 bfs를 이용해 탐색합니다. bfs로 이어져 있는..
[BFS] 프로그래머스 level3 네트워크 자바 풀이 (자세한 설명)프로그래머스 네트워크 자바(java) 풀이 Level 3 BFS/DFS 네트워크 문제 정리 컴퓨터A와 컴퓨터 B가 연결되있고, 컴퓨터 B와 컴퓨터 C가 연결되있으면 A와 C도 간접적으로 연결되 정보를 주고 받을 수 있다. 따라서 A,B,C는 같은 네트워크 상에 있다고 볼 수 있다. 각 컴퓨터는 0부터 n-1인 정수로 표현된다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]=1 이다. computers[i][i]는 항상 1이다. 문제 풀이 이 문제는 그래프로 바꿔서 생각하면 쉬운 문제입니다. level2에 놔도 될것 같네요 그래프 형태로 생각해서 bfs나 dfs를 이용해 탐색합니다. 저는 bfs를 이용했습니다. 방문하지 않은 경우 bfs를 이용해 탐색합니다. bfs로 이어져 있는..
2020.05.10