본문 바로가기

PS831

[자바] 백준 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.
[자바] 백준 16165 - 걸그룹 마스터 준석이 (java) 문제 : boj16165 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시맵에 대해 제대로 이해하고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제의 두 쿼리를 나눠서 생각해보자. 우선 '1' 쿼리의 경우 멤버의 이름이 주어지면 팀명을 출력해야 한다. 이 부분은 입력을 받으면서 멤버의 이름을 key, 팀명을 value로 하는 해시맵을 구성해두면 각 쿼리마다 O(1)로 출력해줄 수 있다. while.. 2022. 9. 14.
[자바] 백준 5263 - samba (java) 문제 : boj5263 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시를 사용하지 않고 이 문제를 풀려면 값 압축이 필요하다. 그게 더 귀찮기도 하고, 시간복잡도적으로 비효율적이므로 해시를 사용하자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력된 숫자를 '숫자 - 입력된 횟수' 형태로 나눌 수 있어야 이 문제를 풀 수 있다. 예를들어 예제 입력 1의 경우 다음과 같이 나타낼 수 있다. 123 - 6번 1678 - 2.. 2022. 9. 13.
[자바] 백준 8975 - PJESMA (java) 문제 : boj8975 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시를 통해 어떠한 문자열이 존재하는지 빠르게 확인이 가능해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 해시에 대해 알고 있다면 문제 파악만 잘 됬다면 어렵지 않게 풀 수 있다. N개의 문자열에 대해, M개의 문자열을 하나씩 입력받다가 N개에서 존재했던 문자열 중 ⌈N/2⌉개가 나온 경우 몇번째인지 출력해주면 된다. 예를들어 예제 입력 1을 보자.. 2022. 9. 13.
[자바, C++] 백준 3052 - 나머지 (java cpp) 문제 : boj3052 필요 알고리즘 개념 사칙연산, 구현, 해시 나머지 연산을 어떻게 구하는지 알고 있어야 한다. 기본적으론 배열을 이용해 그냥 구현으로 풀 수 있으나, 해시를 사용해서도 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 코드에서 나머지연산은 '%'를 사용한다. (자바, c++ 둘 다) 풀이 1 : 해시 사용 10개의 입력을 받으면서 42로 나눈 뒤 나머지를 HashSet에 넣는다. 해시셋은 중복.. 2022. 9. 13.
[자바] 백준 1316 - 그룹 단어 체커 (java) 문제 : boj1316 필요 알고리즘 개념 구현, 문자열 문자열의 각 character를 어느정도 다룰 줄 알아야 하는 구현문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 간단히 생각해보려면 연속된 동일한 문자를 전부 하나로 줄인다고 생각해보자. 예를들어서 aaabbbbbbcccccddddaaaaaaa 의 경우 연속된 동일한 문자는 하나로 치면, abcda 라고 간단하게 생각해볼 수 있다. 위와 같이 볼 수만 있다면.. 2022. 9. 13.
[자바] 백준 25238 - 가희와 방어율 무시 (java) 문제 : boj25238 필요 알고리즘 개념 사칙연산 수학적으로 퍼센티지 계산을 할 수 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a와 b를 입력받은 후, a에서 b%를 제외해준다. 즉, a - a*(b/100) 를 해준다. 이 값이 100 이상이면 0, 아니면 1을 출력해주면 된다. 주의점은 실수로 계산을 해줘야 한다. 내 경우엔 1d 라는게 있는데, literal로 double 1.0을 의미한다... 2022. 9. 13.

티스토리툴바