본문 바로가기

PS/BOJ764

[자바] 백준 27159 - 노 땡스! (java) 문제 : boj27159 필요 알고리즘 개념 구현 제시된 조건에 따라 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N개의 입력 앞에 0을 추가하고 생각해보자. int[] arr = [0, 6, 7, 10, 12, 13, 14, 15, 20, 21, 22] 와 같이 배열이 있다고 해보자. 그럼 arr[x]에서 'x=1부터 배열끝까지' 차례대로 보면서, arr[x-1] != arr[x]-1 이라면 연속된 그룹.. 2023. 1. 15.
[자바] 백준 13699 - 점화식 (java) 문제 : boj13699 필요 알고리즘 개념 다이나믹 프로그래밍 (동적 계획법, DP) DP 문제이긴한데, 그냥 memoization 문제라고 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 t(n)을 계산하기 위해서는 t(0)부터 t(n-1) 까지의 계산 결과가 모두 필요한데, 이걸 매번 점화식대로 구해주면 당연히 시간초과가 될 것이다. 그러니 매번 x = 1부터 35까지 t(x)를 순서대로 계산해주고, t(x).. 2023. 1. 14.
[자바] 백준 17609 - 회문 (java) 문제 : boj17609 필요 알고리즘 개념 두 포인터 (투 포인터) 회문이 아닐 시 예외처리가 들어가긴 하지만, 기본은 회문을 검사하는 투 포인터 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 기본적인 회문은 아래와 같이 찾을 수 있다. 양끝에서 두개의 포인터가 중간으로 오면서 두 포인터가 가르키는 값이 동일한지 확인하는 것이다. 근데 이 문제는 1번은 건너띄어도 된다. 어떻게 처리하면 될까? summmmu.. 2023. 1. 13.
[자바] 백준 27157, 26081 - GGANALi, 곰곰이와 GGANALi (java) 문제 : boj27157, boj26081 ... (생략) 필요 알고리즘 개념 트리, 구현 기본적으로 트리 구조를 만들고 탐색할 줄은 알아야 한다. 하지만 이것대문에 플래인건 아니고, 그냥 구현이 복잡해서 플래티어이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 RPG Extreme 문제가 생각나는 구현 플래 문제이다. 트리구조로 구현해야 하므로 RPG Extreme보단 구현 난이도가 좀 더 높은 것 같다. 다만 개념적으.. 2023. 1. 13.
[자바] 백준 21740 - 도도의 수학놀이 (java) 문제 : boj21740 필요 알고리즘 개념 그리디, 정렬, 문자열 그리디로 풀 수 있는 문제이다. 다만 플래문제답게 세세하게 예외를 생각해봐야하고, 구현이 좀 까다로울 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 이 문제가 플래인 이유는 '단 한 번, 한 수를 두 번 사용할 수 있다.' 이것 때문이다. 아마 저 조건이 없었으면 실버급이었을 것 같다. 그러므로 우선 '단 한 번, 한 수를 두 번 사용할 수 .. 2023. 1. 11.
[자바] 백준 20303 - 할로윈의 양아치 (java) 문제 : boj20303 필요 알고리즘 개념 분리집합 또는 dfs 또는 bfs DP로 실제 답을 구하는 로직 이전에 아이들의 그룹을 만들기 위해 분리집합 알고리즘(union-find) 혹은 그래프 탐색이 필요하다. 이하 풀이는 분리집합으로 풀었다. DP (Knapsack) DP 활용법 중 유명한 냅색류의 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 연결된 아이들의 그룹별로 선택할 수 밖에 없다. 따라서 만약.. 2023. 1. 11.
[자바] 백준 8783 - Architektura niezależna (java) 문제 : boj8783 필요 알고리즘 개념 - 그래프 탐색 (bfs, dfs) 단순히 bfs 혹은 dfs로 그래프 탐색만 해주면 된다. 다만 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 bfs를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 문제 자체는 간단하다. '#'으로 둘러싸인 부분 내부의 빈칸까지 포함해서 넓이를 구하면 된다. 예를들어 예.. 2023. 1. 10.
[자바] 백준 2571 - 색종이 - 3 (java) 문제 : boj2571 필요 알고리즘 개념 누적 합 (prefix sum) 2차원 누적합 문제인데, 빈 공간을 포함하지 않기 위한 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 누적합 알고리즘으로 O(N^4)으로 풀었다. 다만 실제로 N^4은 아니고, 약간의 백트래킹도 포함되었고, 한쪽 방향으로 탐색 범위를 고정했으므로 4중 반복문이긴 하지만 N^4보단 낮다. 우선 2차원 누적합 알고리즘으로 직.. 2023. 1. 10.
[자바] 백준 11663 - 선분 위의 점 (java) 문제 : boj11663 필요 알고리즘 개념 정렬, 해시, 이분 탐색, 누적합 이분 탐색을 활용하는 문제이다. 내 경우엔 prefix sum 개념도 좀 들어갔다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 [a, b] 이내에 포함된 점을 알려면 '[0, b]에 포함된 점의 개수 - [0, a-1]에 포함된 점의 개수' 를 구하면 될 것이다. (누적합 알고리즘 개념) 그럼 임의의 x에 대해 [0, x]에 포함된 점의 개수를.. 2023. 1. 9.
[자바] 백준 14927 - 전구 끄기 (java) 문제 : boj14927 필요 알고리즘 개념 브루트 포스, 그리디 약간의 브루트 포스 + 그리디가 필요하다. 둘 다 알고리즘이라기보다는 개념적인 부분이라, 구현이 크게 어렵지 않은데 아이디어가 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 보통 2차원 문제는 1차원으로 먼저 생각하면 더 쉽게 아이디어를 떠올릴 수 있다. 문제를 간단히 하기 위해 1차원에서만 우선 생각해보자. A. 1차원에서 생각해보자. 선택.. 2023. 1. 6.

티스토리툴바