애드혹11 [자바] 백준 26598 - 색종이와 공예 (java) 목차 문제 : boj26598 필요 알고리즘 애드 혹(ad hoc), 그래프 탐색(dfs, bfs) 이 문제만의 규칙을 찾아 해결하는 애드혹 문제이다. 구현을 위해 그래프 탐색을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 이하의 로직으로 진행했다. 1. 맵의 좌측상단부터 우측 하단으로 진행하면서, 이미 찾은 직사각형임을 찾은 곳은 체크를 해둔다 (다시 직사각형의 여부를 확인하지 않아도 되도록). 2. .. 2023. 11. 28. [자바] 백준 27468 - 2배 또는 0.5배 (java) 목차 문제 : boj27468 필요 알고리즘 애드 혹 이 문제에 맞는 규칙을 찾아 푸는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 힌트는 서브태스크 2번에서 얻었다. N은 4의 배수에 배점이 있는걸보고 4의 배수면 쉽겠구나 생각했다. 손으로 그려보면서 찾아보니 1,3,2,4 / 5,7,6,8 / ... 이런식으로 4의 배수는 무한정 가능함을 확인했다. 그리고 4로 나눈 나머지가 1인 경우도 문제없고(1,3.. 2023. 5. 15. [자바] 백준 14254 - 비밀번호 변경 (java) 목차 문제 : boj14254 필요 알고리즘 애드 혹 (ad hoc) 특정한 알고리즘 없이 이 문제를 위한 로직을 찾는 애드혹 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 * 애드혹 문제의 경우 별다른 알고리즘이 필요한 문제가 아니라서, 풀이의 아이디어를 보게되면 그냥 다 푼거나 다름없다. 따라서 정말 열심히 생각해봤는데도 진짜 모르겠고, 그냥 넘어가긴 싫고 너무 억울해서 풀이를 꼭 보고싶다면 풀이를 보자. 예제.. 2023. 5. 11. [자바] 백준 3765 - Celebrity jeopardy (java) 문제 : boj3765 필요 알고리즘 개념 애드 혹 정형화된 방식이 존재하지 않고 이 문제만의 아이디어를 생각해내야 한다. EOF (end of file) 판단 별도로 입력 줄 수가 주어지지 않으므로 EOF를 판단해서 입력 받아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 장황하게 설명되어 있지만, 입력받은 그대로 다시 출력해주면 된다 ㅋㅋ 자바의 BufferedReader의 경우 eof를 만날 시 null을 리턴.. 2022. 11. 25. [자바] 백준 23970 - 알고리즘 수업 - 버블 정렬 3 (java) 문제 : boj23970 필요 알고리즘 개념 애드 혹 정형화된 방식이 존재하지 않고 이 문제만의 아이디어를 생각해내야 한다. 정렬 기본적인 정렬 방식을 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 당연히 직접 버블정렬을 진행하면서 비교할 시, 버블 정렬이 O(N^2)이고 비교가 O(N)이므로 O(N^3)이 걸리게되어 시간초과가 나게 된다. 내 경우엔 정형화된 방식이 아니고 아이디어를 내서 시간을 줄여 O(N^.. 2022. 8. 26. [자바] 백준 25200 - 곰곰이와 자판기 (boj java) 문제 : boj25200 에디토리얼과도 아예 다른 풀이이고, 난이도 기여의 다른 사람들 의견과도 다른 방식인걸로 보아 상당히 독특하게 푼 것 같다. 당연히 N개의 음료수에 대해 M번의 차원 이동을 실제로 해보려면 현재 이동할 차원 U, V(3, 3->2 라면 1->3으로 차원3에는 1과 3의 두개가 있을 것이다. 따라서 3->2는 3만 이동하면 안되고 1과 3을 둘 다 이동해야 한다. 그러므로 O(NM)의 시간복잡도가 필요하므로 통과할 수 없다. 그렇다면, 첫 시작을 N개의 LinkedList로 해보면 어떨까? LinkedList[N+1] 짜리에 각각 LinkedList[1]엔 1만 있고, [2]엔 2만 있고, ... [N]엔 N만 두고 시작해보자. 그럼 M개의 쿼리에 대해 U->V로 빠르게 Linked.. 2022. 5. 16. [자바] 백준 25194 - 결전의 금요일 (boj java) 문제 : boj25194 우선 문제를 이해했다면, N개의 정수에서 1~N개를 더한 여러 경우의 수 중 7로 나눈 나머지가 4가 되는 경우가 있는지 찾는 문제라고 이해할 수 있다. 하지만 이걸 구하는 방법을 찾긴 좀 어려웠다. 단순히 찾아보면 O(1000!) 이기 때문에 말도 안되는 경우의 수가 나오기 때문이다. 내 기본 아이디어는 나머지 연산의 분배법칙을 활용하는 것이었다. 나머지 연산의 경우 다음의 분배법칙을 따른다. 즉, 100000이하의 큰 'A일'들이 입력으로 들어오지만, 결국 그냥 미리 7로 나눠놔도 결과를 구하는데에 지장이 없다는 얘기이다. 또한 7로 나눈 나머지가 0이 되는 경우는 아예 필요가 없는 경우이다(원점임). 따라서 버려준다. 그렇게 되면 이 문제는 1~6 까지의 숫자가 각각 여러개.. 2022. 5. 16. 백준 2041 자바 - 숫자채우기 (boj 2041 java) 문제 : boj2041 배열이랑 반복문만 알면 풀 수 있는 순수 아이디어 문제인데도 다이아 티어를 받은 무서운 문제이다. 별다른 알고리즘적 지식이 필요하지 않으므로 풀기 전에 이 글을 보면 얻어갈 수 있는건 아이디어 뿐이다. 따라서 밑으로 내려 풀이를 보자마자 스포가 되므로, 최대한 스스로 풀어보고 풀이를 보는걸 추천한다(하지만 스스로 풀어봤다면 더이상 풀이가 필요없지) 백준1187번을 같이 풀었던 선배같은 후배와 같이 풀었다. 1187때는 결국 난 못풀었고 후배의 도움으로 풀 수 있었지만 이번엔 내가 먼저 풀이를 찾았다. 기분 좋다. ----- 풀이 스포주의 ----- 내 경우엔 여러 방식으로 해보다가, 결국 해답을 찾은 키 아이디어는 배열에 어떤 수가 들어갈지 고민하기 보다, 차이를 어떻게 배치할지 .. 2022. 4. 7. 백준 20127 자바 - Y-수열 (BOJ 20127 JAVA) 문제 : boj20127 증가수열 또는 감소수열인 것은 해결 로직을 세우는데에 상관이 없다. 증가수열, 감소수열 둘다 별도 로직으로 계산한다고 생각하면 그 중 작은걸 출력하면 된다. 기본적으론 이런데, 이 문제의 경우 정답률이 낮은만큼 많은 경우를 세세하게 예외처리해줘야 통과할 수 있다. 이하 여러가지 케이스에 대해 설명해본다. 1. 기본 로직은 증가수열을 체크한다면 수가 작아지는 부분을, 감소수열을 체크한다면 수가 커지는 부분의 개수가 2개 이상이라면 증가 혹은 감소수열이 될 수 없다. 예를들어 '예제 입력 1'에 대해 증가수열로써 체크한다면 감소하는 경우가 1번 이하이므로 가능하다! 하지만 감소수열로써 체크한다면 감소하는 경우가 2번 이상이므로 감소수열로는 만들 수 없다. 2. 이번엔 '1'와 같은 .. 2021. 12. 26. 백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA) 문제 : https://www.acmicpc.net/problem/10542 오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져 AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다. 1. 문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당.. 2021. 11. 18. 이전 1 2 다음
