알고리즘/백준 문제풀이39 백준 [java 자바] 1092 : 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 배들이 한번에 적재 할 수 있는 최대 무게가 나와있는 상태에서, 주어진 상자를 옮길 수 있는 시간의 최솟값을 구하는 문제이다. 나는 현재 남은 화물들을 차례대로 배에 실으면서 시간을 재는 방법을 선택했다. 처음에는 우선순위큐를 사용하려고 했으나, 최대무게를 저장해놓은 배열과 비교하는 과정에서 훨씬 복잡해질 것 같아서 linkedlist를 사용했다. 그리고 시간을 최소화 하기 위해서.. 2023. 7. 18. 백준 [자바 java] 1461 : 도서관 https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 사실 한번에 통과하긴 했지만 4번은 갈아엎었던 것 같다. 처음에는 그냥 음수, 양수 나누어서 가장 끝에서부터 차례로 한번에 들을 수 있는 책 만큼 건너뛰면서 세면 되지 않을까라고 생각했지만 다시 0으로 돌아오지 않아도 된다는 조건 때문에 실패했다. 그리고 받는 수를 다 우선순위큐에 넣어서 차례로 빼려고 했지만 그렇게 하면 양수부분에서는 절댓값이 작은 부분부터 탐색해서 옳은 답이 나오지 않는다. 최종적으.. 2023. 7. 15. 백준 [자바 java] 14719 : 빗물 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀 문제 찾다가 우리학교 문제 발견해서 풀어봤어요. 처음 양 옆에가 벽인 것만 물을 채웠는데 그럼 절대 안되더라구요. 그래서 for문을 이용해서 가로로 한 줄씩 왼쪽부터 탐색하면서 벽이 나오면 다음 벽이 나올 때까지 세고.. 뭐 이런 알고리즘을 생각했는데 너무너무 복잡했어요. 생각해보니까 아래부터 가로로 한 줄씩 벽 사이의 간격을 재면 되더라구요! 그래서 stack을 이용해서 벽.. 2023. 7. 15. 백준 [자바 java] 17609 : 회문 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 처음에는 자료구조 시간에 회문 문제 스택으로 풀라고 했던 것 기억나서 그렇게 했는데 시간초과가 났다. 그래서 문제를 자세히 살펴보니 투포인터로 하는게 훨씬 효율적이었다. 여기서 두 포인터의 char값이 다를 때 값을 옮겨주는 과정에서 옮긴 후 모든 것들은 회문이어야 한다는 조건을 빼먹어서 틀렸습니다가 나왔다. 주의할 점 구현 까다로우면 더 쉬운 방법 있나 한번 더 생각하기 반례 더 있나 깊게 생각하기 import java.ut.. 2023. 7. 14. 백준 [자바 java] 1717번 : 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 이 문제는 유니온파인드를 사용하여 풀었다. 옛날에는 유니온파인드가 복잡하고 별로라고 생각했는데, 난이도가 올라갈수록 집합문제에 이 알고리즘을 안쓰면 시간초과, 메모리초과 없이 문제를 풀 수가 없다. 처음에는 find함수에서 return할 때 재귀로 받은 값을 union[k]에 넣는 것을 생략했는데, 이랬더니 시간초과가 났다. 앞으로는 귀찮다고 생략하지 말자. .. 2023. 7. 13. 백준 [자바 java] 11279 : 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 설명 수들을 입력받고, 0을 입력받을 때마다 이제까지 입력받았던 수 중 가장 큰 수를 출력하고 poll한다. 이외의 수를 받으면 힙에 수를 offer한다. 풀이 설명 우선순위큐를 하나 생성한다. 이 때 Collections.reverseOrder()을 이용하여 내림차순화 된 우선순위큐로 만들어준다. 수를 입력받고 이게 0이면 우선순위큐에서 poll하고 값을 string.. 2023. 7. 13. 이전 1 2 3 4 5 6 7 다음
