BOJ749 [자바] 백준 6086 - 최대 유량 (java) 문제 : boj6086 필요 알고리즘 개념 네트워크 플로우 (최대 유량) 최대 유량 기본 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 에드몬드-카프 알고리즘을 적용할 수 있는 기본 문제로, 별도로 구현에 대해서는 풀이하지 않는다. 주의점은 입력으로 들어온 간선의 용량(capacity)이 양방향이라는 점이다. 즉, 'A B 3'과 함께 'B A 3'도.. 2022. 9. 25. [자바] 백준 9440 - 숫자 더하기 (java) 문제 : boj9440 필요 알고리즘 개념 정렬 + 그리디 정렬을 통해 매번 낮은 수 부터 확인하는 그리디 개념으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 가장 처리하기 까다로운 부분은 두 수가 0으로 시작하면 안된다는 점이다. 그러니 우선 입력값에 0이 없다고 생각하고 한번 생각해보자. 1,2,7,8이 있다면 두 수를 어떻게 정해야 할까? 중요한건 각 자리수에 어떤 수 2개를 사용할지이다... 2022. 9. 23. [자바] 백준 12993 - 이동3 (java) 문제 : boj12993 필요 알고리즘 개념 정수론, 수학 수학적인 사고가 약간 필요하다. 그리디 태그엔 없긴한데 내 경우엔 그리디 개념으로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 x, y 중 큰 값이 [3^a, 3^(a+1)) 일 때, k=a 부터 0까지 감소하면서 현재 남은 x와 y중 큰 값에 3^k를 그리디하게 빼준다. 최종적으로 x와 y 모두 0이 되면 1을 출력해주고, 아니면 0을 출력해준다.. 이 .. 2022. 9. 22. [자바] 백준 17412 - 도시 왕복하기 1 (java) 문제 : boj17412 필요 알고리즘 개념 네트워크 플로우 (최대 유량) 최대 유량 기본 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 완전 기본 형태의 문제로, 간선이 존재하는 방향으로 용량(capacity)을 1로 잡고 알고리즘을 구현해주면 된다. 코드 : github import java.io.BufferedReader; import java... 2022. 9. 21. [자바] 백준 16956 - 늑대와 양 (java) 문제 : boj16956 필요 알고리즘 개념 애드 혹, 구성적 어떨 때 늑대와 양을 분리시킬 수 있는지와 없는지 생각해보면 생각보다 간단하게 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 어떨 때 무슨짓을 해도 늑대가 양이 있는 칸으로 갈 수 있을까? S와 W가 인접해있는 경우이다. 즉 1. SW 2. WS 3. S W 4. W S 위와 같은 경우엔 무슨짓을 해도 늑대가 양한테 갈 수 있다. 따라서 위와 .. 2022. 9. 19. [자바] 백준 14465 - 소가 길을 건너간 이유 5 (java) 문제 : boj14465 필요 알고리즘 개념 슬라이딩 윈도우, 누적합 알고리즘, 투 포인터 중 하나 세가지 방식 모두 구현이 가능하다. 당연히 다른 방법도 있을 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1부터 N까지 나타낼 수 있는 배열을 만들고, 고장난 신호등은 1, 정상인건 0이라고 하자. 이 경우 연속된 모든 K개의 구간의 합이 곧 해당 구간의 고장난 신호등의 갯수 = 수리해야 하는 신호등의 갯수가 된다.. 2022. 9. 18. [자바] 백준 16404 - 주식회사 승범이네 (java) 문제 : boj16404 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. 오일러 경로 테크닉 트리를 펴서 구간을 만드는 오일러 경로 테크닉이 필요하다. 어려운 개념도 아니고, 기존에 모르는 상태로도 얼마든지 생각해낼 수 있는 부분이라 반드시 알고있어야하는 부분은 아니다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀.. 2022. 9. 17. [자바] 백준 7469 - K번째 수 (java) 문제 : boj7469 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. 매개 변수 탐색 (parametric search) 이분 탐색의 응용 방법인 매개 변수 탐색이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를.. 2022. 9. 17. [자바] 백준 11377 - 열혈강호 3 (java) 문제 : boj11377 필요 알고리즘 개념 이분매칭 네트워크 플로우에서 이분 그래프일 시 사용 가능한 이분매칭 알고리즘을 통해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N명의 직원이 M개의 일을 선택하는 것만 생각하자. 그럼 기본적인 형태의 이분매칭 알고리즘을 적용해서 풀 수 있다. 여기서 문제가 되는건 N명 중 K명은 일을 최대 2개할 수 있다는 점인데, 사실 약간의 아이디어만 추가하면 똑같다. .. 2022. 9. 17. [자바] 백준 3197 - 백조의 호수 (java) 문제 : boj3197 필요 알고리즘 개념 너비 우선 탐색 (bfs) 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다. 분리 집합 (disjoint set) 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS에 대해 잘 모른다면 이 글.. 2022. 9. 17. 이전 1 ··· 26 27 28 29 30 31 32 ··· 75 다음
