그래프 이론8 [자바] 백준 24461 - 그래프의 줄기 (java) 목차문제 : boj24461 필요 알고리즘그래프 이론, 브루트 포스별다른 알고리즘 지식은 필요하지 않긴한데, 구현이 어려울 수 있다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같은 그래프를 생각해보자. 각 정점에 대해 현재 연결된 간선의 수를 적어보면 아래와 같다. 이번에 제거될 가장자리 정점은 연결된 간선의 수가 '1'인 정점들임을 알 수 있다. 한 번 삭제된 후엔 아래와 같이 된다. 그리고 그래.. 2024. 5. 15. [자바] 백준 2653 - 안정된 집단 (java) 목차 문제 : boj2653 필요 알고리즘 직관(?), 그래프 이론 어찌보면 그냥 구현 문제이긴 한데, 좀 헷갈릴 수도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 서로 싫어하는 사람들은 빼고, 그냥 서로 좋아하는 사람들끼리 집단을 만든다고 생각해보자. 이 때 문제에서 제시된 바에 따라 논리적으로 맞는지만 확인해주면 된다. 내 로직은 다음과 같다. 이하 로직대로 구현해주면 된다. 1. 1부터 N까지 확인하다가 아직 .. 2024. 4. 4. [자바] 백준 30536 - 시루의 산책 (java) 목차 문제 : boj30536 필요 알고리즘 그래프 이론, bfs (너비 우선 탐색) 문제에서 제시된 데이터를 그래프로 생각하고, 적절한 방식으로 탐색해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선.. 내 경우 맞왜틀을 많이 외친 문제였다 ㅠ. 그 이유는 아래와 같다. 1. 난 각 기둥의 상태가 'A. 다른 강아지 마킹 있음', 'B. 마킹은 없으나 다른 강아지 냄새가 영향을 끼침', 'C. .. 2023. 11. 28. [자바] 백준 17616 - 등수 찾기 (java) 목차 문제 : boj17616 필요 알고리즘 그래프 이론, 그래프 탐색 (bfs, dfs) A와 B의 관계를 단방향 그래프로 볼 수 있는 직관이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 너비 우선 탐색(BFS)을 모른다면 '이 글'을 참고해보자. 문제로 주어진 부분을 그래프로 변경해 생각해보는 아이디어가 필요한 문제로, 교육적으로도 상당히 좋은 문제라 생각된다. 우선 'A가 학생 B보다 더 잘했다.. 2023. 8. 11. [자바] 백준 17071 - 숨바꼭질 5 (java) 문제 : boj17071 필요 알고리즘 개념 그래프, BFS (너비 우선 탐색) 결론적으로 보면 그냥 BFS 문제이다. 다만 아이디어가 좀 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 생각 과정 및 풀이 이 문제의 경우 상당히 많이 잘못 생각했고, 결론적으로 proof by AC (정답 맞췄으니 증명됬다!) 느낌으로 풀었다 ㅋㅋ. 그러니 풀이를 생각한 과정을 적어보겠다. 정답 코드만 볼꺼면 맨 아래의 코드만 보면 될 .. 2022. 11. 29. [자바] 백준 19542 - 전단지 돌리기 (java) 문제 : boj19542 필요 알고리즘 개념 깊이 우선 탐색 (dfs), 트리 트리를 dfs로 적절한 방식으로 탐색하는 문제이다. 기본적으로 dfs에 대한 이해가 필요하다. 트리에 대한 이해도 있으면 생각하기 더 좋다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 요즘 바빠서 브론즈문제로 스트릭만 유지하고 있었다. 현재 405일이라 깨기는 너무 아깝다 ㅋㅋ 이제 좀 바쁜게 풀려서 다시 문제들좀 풀어보려니 오랜만이라 그런지 .. 2022. 11. 3. [자바] 백준 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. [자바] 백준 1115 - 순열 (boj java) 문제 : boj1115 오랜만에 엄청 잘만들었다고 느낀 문제였다. 아이디어 문제이다. 해설은 간단한데, 사실 이걸 떠올리는게 전부인 문제이다. 1. B[0] = 0 이므로 즉 A[0]부터 시작한다고 보면 된다. 2. B[i]=A[B[i-1]] 은 즉 A[0]부터 시작한댔으니, A[0] -> A[A[0]] -> A[A[A[0]]] 이런식으로 진행하겠다는 의미이다. 이 때 이게 순열이 되려면 결국 중간에 끊기지 않고 모든 A원소들을 들릴 수 있어야 한다. 그럼 당연히 처음 입력된 A가 모두 들릴 수 있다면? 그냥 0으로 끝이다. 중요한건 중간에 끊길 경우, 어떻게 최소로 교환해서 전체를 들릴 수 있도록 만들 것인지가 관건이다. 직관적으로 이걸 그래프로 생각해보면 좀 더 생각하기 편한데, 결국 끊겼다는 것은 .. 2022. 5. 17. 이전 1 다음
