비트마스킹7 [자바] 백준 18112 - 이진수 게임 (java) 목차 문제 : boj18112 필요 알고리즘 BFS (너비우선탐색) 시작 이진수부터 목표 이진수까지 문제에서 제시된 동작들을 통해 순회하며 BFS를 진행하는 문제이다. 비트마스킹 애초에 문제 자체가 비트연산을 사용하는걸 전제로 만들어진 듯 하다. 안 쓸 이유가 없다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 먼저 읽어보자. 이 글에 제시된 동작들은 모두 비트.. 2023. 3. 7. [자바] 백준 1194 - 달이 차오른다, 가자. (java) 목차 문제 : boj1194 필요 알고리즘 BFS (너비우선 탐색) 최단거리를 찾는 문제로 BFS로 풀 수 있다. 비트마스킹 BFS 진행 시 모든 경우에 대해 방문체크가 가능해야한다. 이걸 위해 비트마스킹을 사용한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 우선 'BFS 알고리즘 (너비 우선 탐색)'을 보자. 특히 이 문제를 풀기 위해서는 '방문체크에 대해 좀 더 써봄' 부분에 적어놓은걸 이해해야 한.. 2023. 3. 6. [코틀린, 자바] 백준 1094 - 막대기 (boj kotlin java) 문제 : boj1094 결국 64에서 시작해서 2씩 나눠가면서 나오는 64, 32, 16, 8, 4, 2, 1을 하나씩만 사용해서 숫자 X를 표현하는 문제이다. 눈썰미가 있다면 막대기로 바꿔서 표현했지만 결국 2진법 표현방식과 동일하다는 것을 알 수 있을 것이다. 즉, 이 문제는 X라는 10진수를 받아서 2진법으로 표현했을 때 비트가 1인게 몇개냐고 묻는 문제와 동일하다. 예를들어 23을 보자. 23을 2진법으로 표현하면, 23=16+4+2+1 이므로 다음과 같다. 23(10) = 0010111(2) 그럼 저 비트 1인 부분에 막대기가 하나씩 들어가주면 된다. 따라서 비트의 수를 세보면 4개이므로 4가 답이다. 이하 코드에서 자바의 경우엔 직접 비트를 세줬다. 그리고 코틀린으로는 Integer.bitCo.. 2022. 7. 20. 백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++) 문제 : boj1187 감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다. 1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다. 1.1 k=1 k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다. A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다. B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다. C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다. .. 2022. 4. 1. 백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA) 문제 : boj1035 처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다. 저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다. 참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다. 1... 2022. 3. 21. 백준 9997 자바 - 폰트 (BOJ 9997 JAVA) 문제 : boj9997 1,2,3에 걸쳐서 점점 효율성이 좋은 풀이를 설명할 겁니다. 그러니 최종적으로는 '3'만 보셔도 되긴합니다. 왜 그렇게 설명하냐면 제가 그렇게 풀었기 때문입니다 ㅋㅋㅋ 시간 제한 딱 맞춰서 푸는건(1초제한인데 백준에서 자바로 제출할 시 '원래시간*2+1'초 이므로 자바로는 3초제한 이었어요.) 뭔가 기분나빠서 줄이다보니 줄여지네요. 1. 우선 빠듯하게 가능한 풀이 우선 모든 경우를 살펴보는게 가능할지 생각해보면, O(2^25*100*26)가 필요하다(2는 해당 문자를 사용하거나, 안하거나이고 25는 N의 최대수치, 100은 단어 길이의 최대수치, 26은 a~z 모든 문자가 포함되었는지 확인). 상당히 빠듯하긴 하지만, 어찌보면 할만해 보이므로 일단 해봤다. 이 때 단어 길이는 1.. 2022. 3. 20. 백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) 문제 : boj5568 우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다! -> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다. 그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 .. 2022. 3. 16. 이전 1 다음
