본문 바로가기

back tracking16

[자바] 백준 14562 - 태권왕 (java) 문제 : boj14562 필요 알고리즘 개념 너비 우선 탐색 (bfs) 너비 우선 탐색을 떠오르기 힘들 수 있고 다른 풀이도 존재하는 문제이다. 이하 풀이는 너비 우선 탐색으로 진행한다. 백트래킹 부가적으로 백트래킹 개념도 넣으면 좋다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로 bfs는 목적지(이 문제에서는 t에 해당)는 고정되어 있고 목적지까지 탐색해나가곤 한다. 하지만 출발지점과 목적지를 동시에 사용해서 .. 2022. 10. 1.
[자바] 백준 1038 - 감소하는 수 (java) 문제 : boj1038 필요 알고리즘 개념 브루트포스 모든 경우의 수를 살펴보는 브루트포스 개념을 알고 있어야 한다. 브루트포스 글 백트래킹 브루트포스에서 모든 경우를 볼 때, 중간에 답이 될 가능성이 없는 부분을 제외시켜 시간복잡도를 낮추는 백트래킹 개념에 대해 알고 있어야 한다. 백트래킹 글 ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 이 문제에서 나올 수 있는 가장 큰 감소하는 수가 '9876543210'임은 생.. 2022. 8. 18.
[자바] 백준 21941 - 문자열 제거 (boj java) 문제 : boj21941 기존에 그리디로 생각해서 풀었었는데, 재채점이 되어 틀려있었다. 기존 틀린 풀이는 여기에 있다. 다시 풀어서 작성한다. 문자열 s를 각 인덱스(이하 idx)를 정점으로 하는 가중치를 가지는 방향 그래프로 바꿔서 생각해보자. 이 때, '문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.' 라는 부분은 idx -> idx+1 로 가는 가중치 1의 간선으로 바꿀 것이다. 그리고 문자열 Ai와 그에 따른 가중치는 예를들어 s가 "abcd"이고, A1이 bc이고 가중치가 3이라고 한다면 idx=1 -> idx=3으로 향하는 가중치 3의 간선이라고 할 수 있다. 예제 입력 1을 봐보자. abcxyzxabc 2 abc 10 xyz 5 위에서 말한 그래프로 그려보면 다음과 같다. .. 2022. 5. 31.
[자바] 백준 25195 - YES or yes (boj java) 문제 : boj25195 그래프 탐색에 대해 단순하게 DFS, BFS만 익힌게 아니고 이해하고 있다면 사실 엄청 쉬운 문제이다. 결국 DFS(깊이 우선 탐색)으로 진행하면서 팬을 만나지 않고 더이상 진행할 간선이 없는 곳에 도착하는지만 보면 된다. 주의할 점은 방문체크를 두면 안된다. 왜냐면 이미 팬을 만난채로 진행한 경로라서 방문체크가 됬더라도 팬을 만나지 않은채로 진행이 가능해야 하기 때문이다. 이럼 사실 방문체크를 하되, 팬을 만나고 도착했는지 팬을 안만나고 도착했는지에 따라 dp를 좀 끼얹어서 그래프 탐색을 해도 되긴한다. 근데 어차피 DAG(Directed Acyclic Graph. 사이클 없는 방향그래프)이므로 팬을 만났다면 바로 back tracking으로 이전으로 돌아가기만 해도 된다. 이.. 2022. 5. 16.
[ABC251] B - At Most 3 (Judge ver.) (AtCoder Beginner Contest 251 in Java) 문제 : abc251_b 1~3개의 합이 W이하인지 확인하는 문제이다. 최소 1개, 최대 3개를 모두 골라보면 된다. 따라서 모든 경우를 확인하는데 O(N^3)이 필요하며, N이 최대 300개이므로 시간은 널널하다. 중간에 합이 W보다 커지는 경우 해당 경우를 확인하지 않는 백트래킹 개념도 더하면 더 효율적으로 짤 수 있다. 주의점은 모든 경우 중, W이하를 만족하는 모든 경우를 구하는게 아니라 그러한 합계를 구해야 한다. 따라서 HashSet 등을 통해 중복된 값은 카운팅 하지 않도록 별도로 처리가 필요하다. 코드 : github ... int n, w, ans=0; int[] arr; boolean[] v; HashSet hs = new HashSet(); private void proc(int id.. 2022. 5. 15.
알고스팟 - BOGGLE - 자바 (aoj java) 문제 : BOGGLE [ 종만북 책에 풀이가 있는데 제 풀이를 올리는 이유 ] 블로그에 풀이 글 쓰는게 오답노트 및 개인 복기용 이기도 하므로 책에 풀이가 있더라도 제 풀이 및 정답까지 접근한 방식을 올리는 겁니다. 즉, '책의 풀이를 보기 전에 문제를 푼다 -> 제 풀이를 올린다 -> 책의 풀이를 보고 더 좋은 방법이 있다면 풀이 뒤에 추가한다.' 처럼 진행합니다. 6장(무식하게 풀기)에 나온 첫 문제이다. '알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.' 라는 주의문구가 있긴 했는데, 대충 시간복잡도 때려보니 별 문제 없을 것 같아서 일단 도전해봤다. 물론 쌩 brute force.. 2022. 4. 17.