본문 바로가기

해시를 사용한 집합과 맵24

[자바] 백준 30646 -최대 합 순서쌍의 개수(java) 목차 문제 : boj30646 필요 알고리즘 누적 합(prefix sum), 해시를 사용한 집합과 맵 누적합과 해시맵을 사용해 풀 수 있다. 물론 언제나 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 보자. 이 문제를 풀기위한 로직을 생각해보면 다음을 알 수 있어야 한다.. 2023. 12. 6.
[자바] 백준 20920 - 영단어 암기는 괴로워 (java) 목차 문제 : boj20920 필요 알고리즘 정렬, 해시를 사용한 집합과 맵 해당 단어가 몇 번 나왔는지 알기 위해 HashMap을 쓸 수 있어야 한다(다른 방법들도 있긴하다). 그 외에는 문제에서 제시된 방법대로 정렬이 가능한지 묻는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 Word라는 클래스를 만들고 name이 단어, cnt가 해당 단어가 몇 번 나왔는지를 뜻하도록 했다. 우선은 동일한 단어가 .. 2023. 4. 9.
[자바] 백준 25757 - 임스와 함께하는 미니게임 (java) 문제 : boj25757 필요 알고리즘 개념 해시를 사용한 집합과 맵, 문자열 문자열을 사용해 해싱하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 Y, F, O에 대해 임스는 무조건 포함되어야 하니 각각 추가로 1, 2, 3명의 인원수가 필요하다. Y에 따른 추가 인원수를 p라고 해보자. 이제 알아야 하는건 '최대 몇 번이나 임스와 함께 게임을 플레이할 수 있는지'와 '임스는 한 번 같이 플레이한 사람과는.. 2022. 10. 24.
[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java) 문제 : Programmers-호텔 방 배정 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 해시를 사용한 집합과 맵 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다. 생각 과정 (오답) * 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다. 아직 선택되지.. 2022. 10. 13.
[자바] 백준 25601 - 자바의 형변환 (java) 문제 : boj25601 필요 알고리즘 개념 그래프 탐색 (bfs, dfs) 그래프 탐색을 할 수 있어야 한다. bfs, dfs 등 해시를 사용한 집합과 맵 String에 대한 간선 표현을 위해 HashMap 등의 자료구조를 사용할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 뭔가 복잡해보일 수 있는데, 결국 그냥 그래프 정점과 간선이 주어지고 특정 지점에서 다른 지점으로 그래프 탐색이 가능하냐고 묻.. 2022. 10. 7.
[자바] 백준 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.
[자바] 백준 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.