Algorithms (31) 썸네일형 리스트형 [LeetCode] 15. 3Sum 풀이 - 정렬 + Two Pointer (Java) ✔️ 오늘의 리트코드 공부 기록 – 3Sum (Two Pointer와 HashSet 접근 비교) 문제 요약 (3Sum)정수 배열 nums가 주어졌을 때, 합이 0이 되는 서로 다른 3개의 원소 [a, b, c]를 모두 찾는 문제.결과 내 triplet은 중복 없어야 함. 문제링크: https://leetcode.com/problems/3sum1. 처음 접근 방식: 완전탐색 + 잘못된 이해로 시작했다✔️ “그냥 모든 조합을 확인하면 되지 않을까?” 가장 처음엔 자연스럽게 이렇게 생각했다.“3개의 원소를 모두 조합해서 확인하면 되지 않을까?”→ 즉, 완전탐색(Brute Force, O(n³)) 하지만 이 방식은시간 복잡도가 O(n³) 로 너무 비효율적이다.❗️그리고 중요한 오해 하나 처음엔 이렇게 생각했다.. [LeetCode] 19. Remove-nth-node-from-end-of-list 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Remove Nth Node From End of List 문제 요약연결 리스트에서 뒤에서 n번째 노드를 제거한 뒤 리스트를 반환하는 문제 문제링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/1. 처음 접근 방식이 문제는 처음엔 직관적으로 이렇게 생각했다.우선 리스트의 길이를 알아야 뒤에서 N번째가 어디 위치인지 알 수 있으므로한 번 리스트를 끝까지 순회해서 길이를 구하고다시 (길이 - n) 번째까지 가서 그 노드를 삭제이 방법도 가능하지만,👉 2번 순회가 필요해서 O(2N) 이라👉 인터뷰에서 더 효율적인 풀이를 기대한다. 그래서 자연스럽게 이런 생각이 든다. “리스트를 한 번만 돌고 해결할 .. [LeetCode] 11. Container With Most Water 최적화 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Container With Most Water 문제 요약 (Container with Most Water)높이 배열에서 두 막대를 선택해 만들 수 있는 “가장 큰 물 담는 용기 넓이”를 구하는 문제 문제링크: https://leetcode.com/problems/container-with-most-water 이 문제는 비교적 쉽게 풀었다. 가장 큰 넓이가 되려면 가로 × 세로 값이 최대가 되면 된다. 가로 길이는 두 막대 사이 거리이고, 세로 길이는 두 막대 중 더 낮은 높이다. 우선, 세로 길이는 배열이 정렬되어 있지 않으니 어디가 최적인지 단번에 알 수 없다. 하지만 가로 길이는 가장 긴 경우가 양 끝 점이므로, 양 끝에서 시작해서 점점 좁혀가면서 최적의 높이를 .. [LeetCode] 3. Longest Substring Without Repeating Characters — 슬라이딩 윈도우 개념 & 최적 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Longest Substring Without Repeating Characters (슬라이딩 윈도우 사고가 핵심이었다) 문제 요약 (Longest Substring Without Repeating Characters)문자열에서 중복 문자가 없는 가장 긴 “연속 부분 문자열(substring)”의 길이를 구하는 문제 문제링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/🤔 처음 떠올린 접근 — 하지만 실패한 방법 문제를 처음 보자마자 자연스럽게 이렇게 생각했다. “Set으로 중복만 막으면 되지 않을까?”“right 포인터만 움직이면 되겠네?” 그래서 이.. [LeetCode] 5. Longest Palindromic Substring 풀이 및 설명 (Java) ✔️ 오늘의 리트코드 공부 기록 – Longest Palindromic Substring (생각보다 사고 전환이 핵심이었다) 문제 요약 (Longest Palindromic Substring)문자열에서 가장 긴 팰린드롬(앞뒤가 동일한 연속 부분 문자열)을 찾는 문제 문제링크: https://leetcode.com/problems/longest-palindromic-substring 처음엔 가장 자연스럽게 이런 생각이 들었다.“왼쪽부터 substring 을 늘려가면서 확인하면 되지 않을까?”“아니면 길이를 1, 2, 3... 이렇게 늘리면서 가장 긴 팰린드롬을 찾을까?”그런데 조금만 생각해보니 이 방식은 결국 모든 substring 을 확인해야 한다.팰린드롬 확인(O(n)) + substring 개수(O.. Lower_bound & Upper_bound 알고리즘 최근 leet code의 Longest Increasing Sequence (최장 부분 수열) 알고리즘 문제를 풀다가, 예전에 공부했던 lower_bound, upper_bound 개념과 구현이 기억이 나질 않아... 이번 기회에 정리해 보았습니다 ㅎㅎ 항상 두 개념이 헷갈렸었는데 이번 포스팅을 통해 개념을 계속 기억하길 바라는 마음으로 두 개념 비교 위주로 정리하였습니다.Lower_bound와 Upper_bound 비교 개념알고리즘 구현Lower_bound특정 k값의 시작 위치(k값보다 크거나 같은 위치)를 찾는 알고리즘[1, 2, 3, 3, 5, 6, 8] ^(lower bound of 3)1. 배열의 중간값 (mid) 를 가져옵니다.2. 중간 값과 검색 값(k)를 비교합니다. - 중간.. Suffix Array (접미사 배열) 접미사 배열 접미사 배열이란, 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 의미합니다. 즉 아래 예시처럼 문자열 "banana"의 모든 접미사들을 정렬한 배열이라고 할 수 있습니다. 0 banana 5 a 1 anana Sort the Suffixes 3 ana 2 nana ----------------> 1 anana 3 ana alphabetically 0 banana 4 na 4 na 5 a 2 nana 접미사 배열 구하기 접미사 배열을 구현하는 알고리즘에는, Naive 알고리즘과 Manber-Myers 알고리즘이 있습니다. Naive 알고리즘 접미사 배열을 만드는 가장 쉬운 방법으로, 단순히 비교 정렬 알고리즘을 이용해서 구현하는 방식입니다. 문자열의 길이가 n이라고 할 때, 접미사는 n.. 해시 함수 (Hash Table) Hash Function 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 이 고정된 길이는 해시 함수마다 다릅니다. 하지만 동일한 해시 함수는 동일한 길이의 데이터를 출력합니다. 아래 그림과 같이, data를 hash function에 입력하면, 이 함수는 고정된 길이의 값을 출력합니다. 해시 함수에 의해 얻어지는 값을 해시 값(Hash value) 이라고 합니다. 해시 함수의 특징 해시 값은 항상 고정된 길이의 값을 가집니다.(위 설명 참고) 같은 입력값이면 해시 값은 항상 동일합니다. 다른 입력값일 때, 1bit만 다르더라도 해시 값은 크게 달라질 수 있습니다. 다른 입력값일 때, 같은 .. 이전 1 2 3 4 다음
