반응형 실버114 [백준] 11497번 - 통나문 건너뛰기(Java)(○) https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 1. 오름차순 정렬을 한다. 2. 가장 큰 기둥을 중간에 배치하고 그 다음 큰 기둥은 오른쪽에, 그 다음 큰 기둥은 왼쪽에 배치한다. 3. 이런 식으로 마지막까지 배치를 완료한다. 4. ArrayList A는 오른쪽에 배치하는 기둥을 넣고, ArrayList B는 왼쪽으로 배치하는 기둥을 넣도록 한다. 5. 가장 큰 수는 A와 B 모두 집어넣는다. 6. 그 다음 수부터 번갈아가면서 A, B에 집.. 2023. 5. 31. [백준] 1946번 - 신입사원 (Java)(○) https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [문제접근] 입력값이 점수가 아니라 순위라는 것을 이해하지 못해서 한참을 헤맸다. 먼저 직원을 선발하지 않는 조건을 잘 살펴보자. * 선발하지 않는 조건 1. 서류순위와 면접순위가 더 높은 지원자가 있다면 그 지원자는 떨어진다. 2. 서류순위를 기준으로 오름차순 정렬을 하면, 자기보다 서류순위가 떨어지는 사람들은 비교할 필요가 없다. 3. 나보다 서류순위가 높음 지원자의 면접.. 2023. 5. 30. [백준] 11286번 - 절댓값 힙 (Java)(◎) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 입력값이 실시간으로 오른차순 정렬이 되어 있어야 한다. 2. 입력값이 양수와 정수가 번갈아 존재하고, 절대값 기준으로 정렬이 되어야 한다. 3. 절대값이 같을 경우 부호를 붙였을 때 작은 수가 앞쪽에 와야 한다. 4. PriorityQueue를 사용해서 실시간 정렬을 해보자. 5. class Node를 구성해서 num은 원래 값, abs는 절대값을 저장한다. class .. 2023. 1. 3. [백준] 11660번 - 구간 합 구하기5(△) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 구간합을 구하기 위해서 가로 기준으로 더해 나가는 합산 테이블 하나, 세로 기준으로 더해나간 합산 테이블 하나해서 총 2개를 준비한다. 2. 2차원 배열의 구간합 배열을 어떤 식으로 구성하느냐가 이 문제를 푸는 열쇠이다. * 점화식 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j] 3. DP테이블(구.. 2022. 12. 26. [백준] 2343번 - 기타 레슨 (Java) https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 강의 순서가 바뀌면 안된다는 것은 입력 받은 순서대로 디스크에 배치되어야 한다는 것이다. 2. 최소 디스크의 갯수는 M개로 정해져있다. 한 디스크의 최소 용량을 구해야 한다. 1) 완전탐색(DFS) 완전탐색으로 각 디스크에 곡들을 저장해서 그 중 최소값을 구하자. 각 디스크에 저장하는 곡의 수는 for문으로 정해야 하나? DFS로 구현을 하면 어떻게 할 수 있을까? 각 디스크에 저장하는 곡의 수가 .. 2022. 11. 7. [백준] 1931번 - 회의실 배정 (Java)(○) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [첫번째] N개의 회의가 주어지고, 각 회의마다 시작시간과 끝나는 시간이 주어진다. 각 회의가 겹치지 않게 하면서 최대한 많이 회의를 사용할 수 있는 개수를 구하라. 회의의 시작시간과 끝나는 시간이 같을 수 있다. 그리디 알고리즘으로 접근하자. class를 선언해서 시작시간과 끝나는 시간을 저장하자. 이 클래스 배열을 끝나는 시간 기준으로 오름차순 정렬을 하자. 루프를 돌리면서 지금 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교하자. 다음 회의의 시작 시간이 같거나 더 크면 회의 갯수를 누적합 시킨다. 선택.. 2022. 10. 11. [백준] 1926번 - 그림 (Java) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net map : 1과 0으로 구성. 그림 : 상하좌우가 1로 연결된 것 그림의 갯수와 가장 큰 그림의 넓이를 출력한다. 그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다. 입력정보 세로축 N : 2022. 10. 10. [백준] 14496번 - 그대, 그머가 되어 (Java) https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 문자열 a를 b로 바꾸는 최소 치환 횟수를 구하는 문제이다. 문자열 관련 문제처럼 보이나 실상은 문자열 a에서 b로 가는 최단경로를 구하는 문제이다. 우선순위 큐와 다익스트라 알고리즘을 사용해서 풀면된다. 인접리스트 방식 둘로 나눠서 풀어보자. 1. class Node를 구성하자. cost로 오름차순으로 PQ를 구성한다. 2. 방문배열(boolean v.. 2022. 10. 8. [백준] 7562번 - 나이트의 이동 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. BFS 탐색으로 최소이동거리를 구하는 문제이다. 2. TC가 여러개이므로 매번 맵을 초기화 해야 한다. 3. 누적거리는 map[][]에 탐색하면서 업데이트 한다. 4. 8방향으로 탐색이 가능하다. import java.util.*; /* [백준] 7562번 - 나이트의 이동 (Java) */ public class Main { static int N, M; static int map[][];.. 2022. 9. 13. 이전 1 2 다음 반응형
