문제풀이
-
[프로그래머스]디스크 컨트롤러 - JAVA문제풀이/프로그래머스 2021. 2. 22. 14:31
[프로그래머스]디스크 컨트롤러 programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 이 문제의 개념은 CPU스케줄링의 비전섬 기법중 SJH스케줄링 기법이랑 완전히 동일하다. ReadyQueue에 있는 작업 중에 실행시간이 짧은 작업에게 먼저 CPU를 할당한다. ReadyQueue는 우선순위 큐를 사용하여 실행시간이 짧은 순서대로 정렬되게 해주었고, 기존의 jobs는 시작시간 순서대로 정렬해 주었다. 반복문을 사용하여 ..
-
[백준]14502: 연구소 - JAVA문제풀이/백준 2021. 2. 21. 17:41
[백준]14502: 연구소 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 조합 + 탐색문제이다. 조합을 사용하는 이유는 벽의 위치를 뽑을 때 순서가 상관없기 때문에 조합을 사용했다. 조합을 구현할 때 다음에 뽑을 벽의 위치를 부분이 까다로웠다. 이전의 뽑은 벽의 위치보다 이후의 위치에서 벽을 선택해야 했는데 입력받은 node는 이차원 배열로 되어있어 y값을 어떻게 처리해야 할지 고민이 되었다. 처음에는 다음과 같이 구현하였다. for(int i = x; i < n..
-
[백준]1937: 욕심쟁이 판다 -JAVA문제풀이/백준 2021. 2. 21. 15:02
[백준]1937: 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 처음에는 DFS만 사용해서 풀었더니 시간초과가 났다! DP와 DFS를사용해 메모이제이션 하면서 풀어야 한다. dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다. 즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때 dp[x][y] = dp[nx][ny] + 1과 dp..
-
[프로그래머스]징검다리 건너기 - JAVA문제풀이/프로그래머스 2021. 2. 21. 13:41
[프로그래머스]징검다리 건너기 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이 이분탐색 문제이다! 이분탐색을 하지 않고 풀면 시간초과가 날 것이다! 전형적인 이분탐색의 유형으로 최소값, 최대값을 건널 수 있는 프렌즈의 수 범위로 둔다. 처음에는 min을 0, max를 건널 수 있는 프렌즈의 최대값으로 둔 다음, mid이상의 프렌즈가 건널 수 있다면 min을 mid + 1로, mid이상의 프렌즈가 건널 수 없다면 max를 mid - 1로 변경하여 또 탐색한다. 이때 건널 수 있는지 없는지 판단하는 방법은 간단하다. stones의 각 ..
-
[백준]5052: 전화번호 목록 - JAVA문제풀이/백준 2021. 2. 20. 17:18
[백준]5052: 전화번호 목록 www.acmicpc.net/problem/5052 풀이 이 문제는 문자열 관련한 새로운 지식을 많이 쌓을 수 있었던 문제였다. 우선, 숫자를 String으로 입력받고 Arrays.sort()를 사용해 정렬을 하면 기존의 숫자 정렬과는 결과가 다르다. 기존의 숫자 정렬은 1, 9, 10, 44, 34, 4로 입력되었을때 정렬 결과가 1, 4, 9, 10, 34, 44가 된다. 그러나 이를 String으로 입력하고 정렬하면 결과가 1, 10, 34, 4, 44이 된다. 그 이유는 프로그램은 숫자가 아닌 문자로 인식해서 오름차순 정렬을 하기 때문이다. ( ex) 다 가나 다라 나 가 -> 가 가나 나 다 다라 순서로 정렬되듯이.) 이해가 잘 되는 예시는 다음과 같다. 입력) ..
-
[프로그래머스]등굣길 - JAVA문제풀이/프로그래머스 2021. 2. 20. 14:42
[프로그래머스]등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 문제 설명이 조금 이상하긴 한데 그림을 보면 m이 세로 행의 개수이고, n이 가로 열의 개수이다. 그러므로 board를 만들때 boar[n][m]으로 만들어 주었다. 이에 따라 puddles의 위치 좌표도 [y, x]좌표로 입력이 되어있다고 생각했다. 그런데 또 문제 설명에서 오른쪽 아래 학교의 좌표는 m, n이라고 한다. 배열로 생각하고..
-
[백준]1520: 내리막 길 - JAVA문제풀이/백준 2021. 2. 19. 21:34
[백준]1520: 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 DP문제로 dfs 풀이 방식과 매우 유사한 형식이였다. 그래서 많이 어렵지 않았다. node함수로 지도의 정보를 입력받고, dp함수를 사용해 메모이제이션과 현재 까지 올 수 있는 경로의 수를 저장해 주었다. dp함수가 초기값이면 그 방향으로 한번도 오지 않았다는 의미이므로 지도 값이 더 작은 곳이 주변에 위치하는지 확인하여 이동한다. 이때 이동 경로의 수를 더해준다. dp함수..
-
[백준]2170: 선 긋기 - JAVA문제풀이/백준 2021. 2. 18. 16:18
[백준]2170: 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 선의 정보를 입력 받은 후 계산을 순차적으로 진행하기 위해 x좌표를 기준으로 오름차순 정렬을 한다. x좌표가 같으면 y 좌표를 기준으로 오름차순 정렬 한다. 이전 선의 정보를 min, max에 저장해 주었고 현재 선의 정보와 비교하면서 조건에 따라 길이를 계산해 주었다. 선의 길이를 계산할 때 다음과 같은 3가지 조건이 있다.(이때 모든 선은 x, y..