땅다람쥐의 개발 일기

지난주 Leetcode Daily Problem의 테마는 Disjoint Set을 사용하는 문제가 많이 나왔었다. 그래서 이번에 개념을 확실히 정리해두려고 . Disjoint Set두 개의 겹치치 않는 집합(Set) 이 있다. 이런 집합을 Disjoint set이라고 부른다. 즉 공통 원소(Common Element)가 존재하지 않는 부분 집합(Subset)의 집합을 말한다. 그리고 Disjoint Set을 표현하기 가장 좋은 자료구조 중 하나가 Union-Find 자료구조다. Union-Find그럼 Union-Find 자료구조는 어떻게 Disjoint Set을 표현할까요? 제일 먼저 Union-Find는 보통 Tree 방식으로 표현이 됩니다. 그리고 세 가지 연산을 이용해서 Disjoint Set을 만..

알고리즘 해답 중에 해시맵을 배열로 속도가 빨라지는 경우가 있어서, 그 부분을 기록으로 남길까 합니다. 왜 배열로 바꿨을 때 빨라질까?배열이나 해시맵이나 원소(Element)에 접근할 때의 시간 복잡도는 O(1)로 같습니다. 하지만 해시맵은 내부적으로 해시 함수를 거쳐야 하는 등 여러 오버헤드가 발생하기 때문에, 실제 연산 속도는 배열이 훨씬 빠릅니다.두 구조의 내부 접근 순서를 비교해 보면 다음과 같습니다.배열: Arr[Index] => 인덱스를 통한 메모리 주소 접근 => 원소 반환해시맵: Map.get(key) => 해시 함수(Hash Function) 연산 => 해시 값을 버킷 인덱스로 변환 => 해당 버킷 접근 => Collision 있을 시 연결 리스트나 트리 탐색 및 Key 동등성 비교 =>..

최근 Leetcode Daily Problem에서 Dynamic Progrmming을 사용해야 되는 문제가 나왔습니다. Total Waviness of Numbers in Range II라는 문제로, 정해진 범위 내에 조건에 맞는 숫자가 몇 개가 있는지 찾아보는 문제였습니다. Brute Force로 쉽게 풀 수 있지만 범위가 너무 커지면 TLE (Time Limit Exceeded) 오류를 받게 되죠. 그래서 오늘은 이러한 범위 내에 특정 숫자들을 찾을 수 있는 알고리즘인 Digit Dynamic Programming을 소개합니다.Digit Dynamic ProgrammingDigit Dynamic Programming은 숫자의 가장 큰 자릿수(왼쪽)부터 작은 자릿수(오른쪽)로 순회하면서, 특정 조건을 ..

문제 레모네이드의 가격은 $5입니다. 손님들은 $5, $10, $20을 낼 수가 있는데, $5보다 큰 금액을 내면은 정확한 거스름돈을 줘야합니다. 여기서 명심해야 할 것은 처음에 가지고 있는 거스름돈은 없습니다. Integer array로 bills을 받게 되는데 bills[i]는 ith 번째 손님이 지불하는 bill을 말합니다. 만약에 고객들한테 정확하게 거스름돈을 줄 수 있으면 true를 반환하고 아니면 false를 반환해야합니다. 조건을 보자면 아래와 같이 정리할 수 있는데요. 초기에 가지고 있는 거스름돈 없음 고객이 낼 수 있는 돈의 종류는 3가지 정확하게 거스름돈을 줄 수 있는지 아닌지 풀이 푸는 방법은 여러가지 일 수 가 있겠는데요. 처음에 생각나는건 HashMap 이였습니다. key 값에 5..

문제 n개의 주유소가 순환 루트에 있다. 주어진 Gas와 Cost를 사용해서 한 바퀴를 돌 수 있는 인덱스를 찾기 만약에 없다면 -1 리턴하기. 해결방법 계속 여행을 할 수 있는 조건은 gas[i] - cost[i+1]가 0보다 클 때 그래서 모든 gas[i] - cost[i+1]를 더한 값이 0 보다 작으면 -1 그렇지 않을 경우에는 한 바퀴를 돌 수 있다. 그리고 gas[i] - cost[i+1]의 값과 잔여 연료의 값을 더 했을 때 0 보다 큰 값이 나오면 거기서부터 한 바퀴를 돌 수 있다. int fuel = 0; int size = gas.length; for (int i = 0; i < size; i++){ fuel += gas[i] - cost[i]; } if (fuel < 0) { retu..

문제 회전된 배열에서 target 넘버 찾기 넘버가 없으면 -1의 값을 리턴 런타임이 O (log n)이 되야함 해결방법 Modified Binary Search class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left

문제 화단에서 꽃 몇 송이를 심을 수 있는가? 화단에 심은 꽃이 n보다 같거나 작은가? 해결방법 세가지 인덱스의 값을 비교하면서 n을 줄여나가기 n이 만약 0 보다 크다면 false 작으면 true. public class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { for(int i = 0; i = flowerbed.length ? 0 : flowerbed[i+1]; int curr = flowerbed[i]; if(pre == 0 && post == 0 && curr == 0) ..

Two Sum과 Binary Search의 개념을 이용해서 풀 수 있는 간단한 문제 문제 - 정렬된 배열에서 target이 되는 값을 찾아 index + 1 되는 배열을 return하기 해결방법 - 배열이 이미 정렬되어 있어서 Binary Search를 사용 class Solution { public int[] twoSum(int[] numbers, int target) { int start = 0; int end = numbers.length - 1; int[] output = new int[2]; while (end > start) { int sum = numbers[start] + numbers[end]; if (sum == target){ output[0] = start + 1; output[1]..

문제 - 두 가지 곡 시간의 합이 60으로 나뉘어지는 Pair의 수를 찾아라 해결방법 1. Brute Force를 이용해서 곡 pair의 합이 60으로 나뉘어지는 곡들 찾기 2. 각 곡들의 시간을 60으로 나누었을 때 나머지 값이 같은 곡이 있다면 +1 해주기. class Solution { public int numPairsDivisibleBy60(int[] time) { int output = 0; int size = time.length; for (int i = 0; i < size; i++){ for(int j = i+1; j < size; j++){ int totalTime = time[i] + time[j]; if (totalTime % 60 == 0){ output++; } } } retur..

학기 끝나고 오랜만에 풀어보는 알고리즘 문제다. C++을 사용하다가 Java로 넘어오면서 적응하느라 고생을 좀 했다. 문제 - 숫자와 도메인으로 이루어진 String pair - 앞에 숫자는 도메인을 얼마나 방문했는지 나타내는 것 - 도메인을 "."으로 나누었을 때 각각 총 방문 숫자를 각각 나태는 List를 return 할 것 해결 방법 - Hash Table과 Brute Force를 이용하기 public List subdomainVisits(String[] cpdomains) { int size = cpdomains.length; HashMap map = new HashMap(); List output = new ArrayList(); for (int i = 0; i < size; i++){ //Sp..