본문 바로가기

전체 글1068

[자바] 백준 11377 - 열혈강호 3 (java) 문제 : boj11377 필요 알고리즘 개념 이분매칭 네트워크 플로우에서 이분 그래프일 시 사용 가능한 이분매칭 알고리즘을 통해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N명의 직원이 M개의 일을 선택하는 것만 생각하자. 그럼 기본적인 형태의 이분매칭 알고리즘을 적용해서 풀 수 있다. 여기서 문제가 되는건 N명 중 K명은 일을 최대 2개할 수 있다는 점인데, 사실 약간의 아이디어만 추가하면 똑같다. .. 2022. 9. 17.
[자바] 백준 3197 - 백조의 호수 (java) 문제 : boj3197 필요 알고리즘 개념 너비 우선 탐색 (bfs) 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다. 분리 집합 (disjoint set) 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS에 대해 잘 모른다면 이 글.. 2022. 9. 17.
[자바] 백준 14572 - 스터디 그룹 (java) 문제 : boj14572 필요 알고리즘 개념 그리디 풀이를 보면 왜 그리디인지 알 수 있다! 투 포인터 (두 포인터) 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자. 1. 그룹 내의 학생들이 아는 모든 알고리즘의 수 -> 학생 수가 늘어나면 항상 동일하거나 늘어난다. 2. 그룹 내의 모든 학생들이 .. 2022. 9. 17.
[자바] 백준 16978 - 수열과 쿼리 22 (java) 문제 : boj16978 필요 알고리즘 개념 오프라인 쿼리 온라인 쿼리로 풀려면 어려운 문제지만, 오프라인 쿼리 아이디어가 떠올랐다면 훨씬 쉬워진다. 세그먼트 트리 또는 펜윅 트리 point update range query 문제로 세그먼트 혹은 펜윅 트리를 사용해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 point update와 range query가 존재하는 문제인데, 잘 생각해보면 update와 qu.. 2022. 9. 17.
[자바] 백준 2873 - 롤러코스터 (java) 문제 : boj2873 필요 알고리즘 개념 구성적, 그리디 정규화된 방식 없이 이 문제만을 위한 규칙이 필요한 구성적 문제이다. 또한 그리디를 적용해 해당 규칙을 정할 수 있긴하다(?). 구현 보통 플래급에서 '구현'이 태그로 있다는건 구현이 엄청 어렵다는 뜻이다 ㅋㅋ ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 규칙자체는 여러 케이스에 대해 마구 그려보면서 머리로 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 문제는.. 2022. 9. 17.
[자바] 백준 3683 - 고양이와 개 (java) 문제 : boj3683 필요 알고리즘 개념 이분 매칭 이분 매칭으로 풀 수 있긴 한데, 아이디어 떠올리기가 좀 많이 어려운 편인거같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 생각하기도 어려웠고, 이분 매칭으로 처리하려고 해도 모델링이 상당히 어려운 문제였다 ㅠ. 이분 매칭에서 좌측에 고양이를 좋아하는 사람, 우측에 개를 좋아하는 사람을 둔다. 그리고 좌측에서 우측으로 고양이를 좋아하는 사람이 싫어하는 개를 .. 2022. 9. 17.
[자바] 백준 13544 - 수열과 쿼리 3 (java) 문제 : boj13544 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를 배열로 처리한 머지 소트 트리를 사용해 풀었다. 내 경우엔 아직 세그먼트 트리를 정식으로 공부하지 않았으므로,.. 2022. 9. 17.
[자바] 백준 21508 - Список школ (java) 문제 : boj21508 타 언어 문제이므로 한글로 문제의 핵심 조건만 작성해본다. 1. 첫 줄에 이하 몇줄이 입력으로 들어올지에 대한 N이 주어진다. 2. 입력은 공백, 영어 대소문자, 숫자로 이루어져 있는데, 이 중 숫자만 뽑아낸게 학교 번호이다. 즉, "A41B"와 "41 AB"는 동일한 학교를 나타낸다. 3. 학교 번호 기준으로 각 학교가 몇 명 참가했는지 확인해서, 1명이상 5명이하가 참여한 학교의 학교 번호를 출력한다. 순서는 상관없다. 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시가 필요하다. 숫자로 처리되므로 그냥 배열같은걸로 처리해도 되지 않나 싶겠지만, 문제 어디에도 숫자가 몇 이하임이 제시되지 않았다. 따라서 문자열 길이가 100까지 가능하므로 100자리 숫자까지 판단해야 된다고 .. 2022. 9. 17.
[자바] 백준 6566 - 애너그램 그룹 (java) 문제 : boj6566 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시를 잘 이해하고 있어야 풀 수 있는 문제이다. 정렬 정렬 역시 잘 이해하고 있어야 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 상당히 복잡한 문제이다. 구현도 복잡하고 실수할 여지도 많으니 주의해서 풀어야 한다. 차근차근 로직을 정리하면서 구현을 해야 실수를 줄이면서 구현할 수 있다. 이정도 구현을 문제없이 짤 수 있는 정도면 사.. 2022. 9. 17.
[자바] 백준 23814 - 아 저는 볶음밥이요 (java) 문제 : boj23814 필요 알고리즘 개념 많은 조건 분기 여러 가능성을 고려해야 한다. 수학 이 문제를 풀기 위해 수식을 세울 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 말로만 적어서 한번 생각해보자. 결국 군만두가 최대치가 되어야 한다는게 가장 중요한 조건이고, 그러면서도 볶음밥의 최대 수를 구해야 한다. 1. 그렇다면 군만두를 최대치로 만들 수 없다면 볶음밥을 아무리 많이 주문 가능해도 버려.. 2022. 9. 17.

티스토리툴바