Algorithm (7) 썸네일형 리스트형 HashMap의 containsKey()는 왜 시간 복잡도가 O(1)일까? 혹시 HashMap의 containsKey() 메서드가 왜 평균적으로 O(1)의 시간 복잡도를 갖는지 아시나요? 그동안 사용할 때마다 궁금했습니다. Collection이 어떤 값을 포함하는지 확인하려면 내부의 자료를 순회해야할텐데 어떻게 O(1)의 시간 복잡도로 포함 여부를 확인할 수 있을까? 그래서 몇 번인가 찾아봤었지만 설명이 어려워서 이해하지 못했었는데, 오늘은 드디어 이해가 돼서 이해한 내용을 글로 정리해두려고 합니다! 이 글에서는 1. HashMap이란? 2. HashMap이 내부적으로 이용하는 HashTable 3. HashTable이 자료의 중복을 해결하는 방법 의 순서로 살펴보려고 합니다. 1. HashMap이란? HashMap은 키(Key)와 값(Value)으로 구성된 Entry 객체를 .. 이진탐색 종이를 접듯이 탐색 범위를 반씩 좁혀나감으로써 $O(logN)$의 시간복잡도 내에 탐색을 마칠 수 있는 사기적인 탐색 방법! 오늘은 이진탐색에 꽂혀서 하루 종일 이진탐색 세 문제를 풀었다. 푼 문제 수는 적지만 많은 깨달음을 얻었기 때문에 오히려 좋아. 오늘 알게 된 사실은 아래와 같다. 1. 이진탐색의 기본적인 틀은 아래와 같다. int start = s, end = e; while (start target) end = mid - 1; else { ans = mid; break; } } 2. 꼭 mid가 target보다 클 때, 작을 때, 같을 때로 나누지 않고, 클 때, 작거나 같을 때와 같이 유연하게 나눌 수 있다. 예를 들어 target보다 작은 수 중에 가장 큰 수를 찾고 싶다면 클 때와 작거나.. 클래스, 튜닝의 끝은 순정 프로그래머스 「2023 KAKAO BLIND RECRUITMENT 개인정보 수집 유효기간」 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제에서 날짜가 "yyyy.MM.dd" 형식의 문자열로 주어졌고, 나는 이를 int 타입의 날짜로 변환하려고 했다. 그래서 문자열을 날짜로 변환하기 위해 dayToString() 메소드를 만들고, 반대로도 하기 위해 stringToDay() 메소드도 만들었다. 그런데 그냥 LocalDate 타입을 사용해서 문제를 푼 사람이 있더라! 만약에 LocalDate 타입을 사용할 수 있으면 plusMonths(), isBe.. 컴퓨터는 재귀를 사랑해 프로그래머스 「Summer/Winter Coding(~2018) 스티커 모으기(2)」 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재귀적으로 생각할 때 중요한 것은 꺾이지 않는 마음 $i$번째의 결과와 $(i - 1)$번째 결과와의 관련성이다. 해당 문제의 경우 $i\geq 2$일 때 $i$번째 점수는 1. $(i - 2)$번째 점수 + sticker[$i$](choose case) 또는 2. $(i - 1)$번째 점수(pass case) 중에서 큰 것이었다. 내가 해당 알고리즘을 고려하지 못한 주요한 이유는 기본 예시에서 4번째 점수가 14, 1.. 선분이 겹치는 구간의 길이를 찾는 문제. 그런데 인덱스를 사용하지 않는 Q. lines = [[1, 3], [2, 4], [3, 5]]와 같이, 선분의 시작과 끝 좌표로 이루어진 배열의 배열이 주어진다. 두개 이상의 선분이 겹치는 길이를 구해보자. 처음의 계획 1. lines를 순회하면서 [자연수, 자연수 + 1]의 구간을 Map에 저장한다. 2. Map을 순회하면서 value가 2이면 answer을 1만큼 증가시킨다. 시간 복잡도 = O(\(N^2\)) (N: lines를 통해 주어지는 구간의 전체 길이) N이 크지 않아서 이 방법도 좋았는데, 구간의 처음과 끝을 아는 상태에서 일일이 길이가 1인 구간으로 나눠서 맵에 추가한다는게 번거로웠다. 굳이 인덱스를 다루고 싶지 않았다. 그래서 둘째 계획으로 변경했다. 1. 구간 전체를 순회하면서 [자연수, 자연수 + 1]의 구간을.. 재귀적으로 최댓값 찾기 i = n, n + 1, ..., e 중에서 f(i)가 최대인 i를 max[n]에 저장하는 알고리즘. max[0] = 0; for (int i = 0; i = f[i + 1] ? max[i] : i + 1; } 자그마치 외부 변수 max를 쓰지 않았다! 소인수분해 간단한 소인수분해 알고리즘. for (int i = 1; i 이전 1 다음
