java

백준이든 api를 만들든 나는 항상 코드가 잘 돌아가기만 하면 된다고 생각했다. 그래서 몇 중 for문이든 그냥 쓰고, 함수로 빼는 일도 잘 없었다. 하지만 팀원들은 내 코드를 보고 이해하기 어려워서 손도 못대겠다고 했다.. 😥😥😥 잘 짠 코드는 남이 알아보기 쉽게 작성한 코드라고 한다. 기능이 잘 돌아가는 것 외에 코드를 어떻게 깔끔하게, 남이 알아보기 쉽게 만들 수 있는지 고민을 해볼 단계가 된 것 같다. 이번에 우테코를 지원하였는데, 프리코스의 문제 요구사항 중 코드컨벤션 맞추기가 있었다. 이번에 Google Java Style Guide를 정리하며 자바 코드 컨벤션을 공부하고, 컨벤션에 맞추어 코드를 짜는 연습을 해보려고 한다. https://google.github.io/styleguide/ja..

이전 글(Union-Find 정리 글) https://fladi.tistory.com/348 [JAVA] Disjoint Set과 Union-Find 알고리즘(백준 1717 집합의 표현) 서론 백준 1717번 문제를 몇 시간동안 못풀어서 결국 구글링을 해봤는데, 이 문제는 Union-find알고리즘을 써야한다는 걸 알게되었다. Union-Find 알고리즘을 처음 접했을 땐 너무 참신해서 짜릿했다! fladi.tistory.com 이전에 Union-Find 알고리즘에 대해 공부했다 활용문제를 조금 더 풀고싶어 비슷한 문제를 풀어보려고 한다! 4195 친구 네트워크 - 골드2 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진..

서론 백준 1717번 문제를 몇 시간동안 못풀어서 결국 구글링을 해봤는데, 이 문제는 Union-find알고리즘을 써야한다는 걸 알게되었다. Union-Find 알고리즘을 처음 접했을 땐 너무 참신해서 짜릿했다! 이 알고리즘을 정리해두면 나중에도 유용하게 쓰일 것 같아 글을 포스팅한다 Disjoint Set(서로소 집합)이란? Union-find 알고리즘은 Disjoint set을 표현할 때 사용된다 Disjoint는 "뿔뿔이 흩어지다"라는 뜻이다 Disjoint set은 공통원소가 없는 집합을 뜻한다 (백준 1717번 문제는 Disjoint Set이 주어진다) Union-Find 알고리즘이란? Disjoint Set(서로소 집합)을 효율적으로 표현하는 알고리즘이다 집합을 트리구조로 표현한다 각 값이 자..

24416 알고리즘 수업 - 피보나치 수 1 - 브론즈1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 그냥 하라는대로 따라가면 된다. 의사코드만 잘 구현하면 될듯 dp가 재귀호출보다 성능이 좋다는 걸 알려주려는 듯 하다 한 번 구한 값을 재활용하는 dp와 달리 필요할 때마다 계속 값을 구해야하는 재귀호출이 훨씬 성능이 나쁜 것을 알 수 있음 풀이 class Main { static int cnt1 = 0; static int ..

Dynamic programming(동적계획법)이란? 1950년대 Richard Bellman에 의해 개발된 알고리즘 패러다임 복잡한 문제를 더 간단한 하위 문제로 분해하여 단순화하는 것을 의미 간단한 문제의 해를 구하고, 이를 이용하여 복잡한 문제를 푼다 동적계획법 문제는 두 가지 특성을 가진다 1. 최적의 하위 구조 최적화 문제에 대한 솔루션이 해당 하위 문제에 대한 최적 솔루션의 조합으로 얻어낼 수 있다 작은 문제로 큰 문제를 해결할 때 사용되는 관계가 존재하고, 이를 함축적 순서라고 한다 2. 중첩되는 하위 문제 동적계획 알고리즘은 분할 정복 알고리즘과 구분된다 분할 정복 알고리즘은 해결이 어려운 문제를 분할하여 문제를 해결한다는 점에서 동적계획법과 비슷하지만 차이점이 존재한다. 동적계획법은 하위..

2467 용액 - 골드5 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전에 비슷한(같은) 문제를 푼 적이 있는데, 그 때는 포인터 2개를 이용하여 문제를 풀었다 이번에는 이진탐색으로 풀어보려고 한다 산성과 알칼리 용액 모두 합쳐 오름차순 정렬한다 알칼리 용액들을 하나씩 빼면서 배열에서 내 절댓값과 가장 가까운 값을 찾는다 [작음, 작음, (같거나)큼, 큼, 큼, ...] 이런 꼴로 나올 것이기 때문에 lowerbound를 구해준다 l..

어느정도 이진탐색 기본기를 다진 것 같으니 활용을 열심히 해보자! 2512 예산 - 실버2 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 처음부터 배정이 가능한 경우 -> 예산의 최댓값 출력 배정 불가능 경우 -> 상한액 출력 그냥 상한액을 이진탐색으로 찾는다고 생각하면 되겠다 배정이 가능하면 오른쪽을 탐색, 배정이 불가능하면 왼쪽 탐색 [가능, 가능, 가능, 불가능, 불가능, ...] 이런식으로 나올 것이니 upperbound값을 구하..

Lower bound, Upper bound란? 그림을 보면 쉽게 이해할 수 있다. lower bound: 찾고자 하는 값이 처음 나타나는 위치 upper bound: 찾고자 하는 값 바로 뒤 위치 원래 이진탐색 코드 //오름차순 정렬된 arr에서 target값을 찾아 인덱스를 반환하는 함수 private int findIdx(int[] arr, int target) { int start = 0; int end = arr.length; while (start target end ..

이진탐색 관련 문제를 풀던 중, Arrays에 binarySearch 메서드가 있는 걸 발견하였다! 원래는 직접 이진탐색을 구현하여 사용하였지만 컬렉션에서 지원된다면 사용하는 게 더 효율적일 것 같다. 그래서 이번엔 binarySearch 메서드를 알아보려고 한다. 정의 binarySearch 메서드를 타고 들어가보면 이렇게 긴 설명이 있다. Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the r..

1181 단어 정렬(실버5) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 저번에 풀었던 문제다! (2달전 쯤) 중복된 단어는 하나만 남기고 제거해야한다는 것에서 set냄새가 난다 정렬을 해야하는 set이라면 treeset을 사용하는 게 좋을 것 같다 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br...