백준32 백준 [자바 java] 2839 : 설탕배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1년 전에 c언어로 풀었던 문제인데 이번 학습동아리를 위해 자바로 다시 풀었다. 이 문제는 그리디 알고리즘을 설명할 수 있는 가장 간단한 문제라고 생각한다. 최대한 적은 수의 봉지를 사용해서 설탕을 옮기는 방법을 구하는 문제인데, 이를 위해서는 5킬로그램 봉지를 최대한 많이 사용해야하면서도, 이를 사용하고 남은 설탕의 그람수가 3으로 나누어 떨어져야 한다. 따라서 나는 주어진 설탕의 수를 5로 나눈 후 이 .. 2023. 7. 23. 백준 [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. 이전 1 2 3 4 5 6 다음
